- 博客(77)
- 收藏
- 关注
RSS订阅原创 算法趣题-Q37
一开始，我使用了贪心的方式（也在C/C++实现中，是错的），认为短视能够获得好的结果，运行结果确实是13步最少，但是路径却不是数组路径，debug发现在0开始的贪心路径中，得到的最好结果是14，而书中0开始的最好结果为13，也就是说贪心算法至少在求局部最优时达不到效果；于是想到DP（也在C/C++实现中），但是对于DP来说，中间的计算结果不易保存，那么递归实现必然有大量的重复计算，而且DP的最终效果依旧是遍历所有排列，故最终还是选择了对所有排列的遍历（Python实现）。...
2022-08-15 19:05:50
375
1
原创 算法趣题-Q36
第一个想法依然是对所有元素进行遍历，如C/C++代码，然后确实还有可以改进的空间，在计算一次循环序列的过程中，很容易发现，在这个循环节中间的所有元素都满足要求，那么我们就可以讲这些元素存储下来，无需对其再次求循环序列，如Python代码。但是在实现过程中，我选择使用了列表进行存储，导致搜索和计算中的复杂度大大变高，使得计算时间变得相当长，但是整体思想和代码没有问题，感兴趣的话可以对Python版本的代码进行进一步的优化。...
2022-08-12 15:33:10
122
原创 算法趣题-Q35
很明显，此题想考的就是反推思想，在正向遍历时的计算复杂度是不确定的，但一定很大，根据书中给出的答案可知确实如此，由此需要我们从结果向前进行推导，虽然根据结果反向遍历的计算复杂度同样不确定，但可以肯定的是其复杂度必然不会超过正向的，而且减少了大量的无效计算。因此，在代码实现时，我们通过生成只包含0和7的序列反向验证以得到结果。...
2022-08-10 20:51:21
107
原创 算法趣题-Q34
自己的想法是将两个条件拆开计算，因为第二个条件的独立计算比较简单，将所有在对角线汇合的点的可能相加就可，然后对于第一个条件就进行递归搜索，记录在同一直线上的次数，在抵达目标端点时，若次数等于2时（书中实现使用的是大于等于2，于是在下面的实现中也进行了统一）总计数值加一，但是这样计算可能会有重复计数，当两人相交后，继续沿同一直线前进时（一人向上，一人向下）。原书中的是实现则更加巧妙，对于两种情况，将其合并实现。...
2022-08-10 11:04:24
85
原创 算法趣题-Q33
直接遍历统计，但是能够发现有部分是重复的，需要把问题分成4个相同的小问题，在边长为9的时候，分成4个4*5的矩形和最中间的那个点。把飞或者角固定在这个小矩形范围内，另一个棋子则可以无限制在棋盘的任意位置，这样将小矩形结果乘以4再加上中间的的可能就可以得到结果，还能减少重复计算。......
2022-07-29 16:12:52
169
原创 算法趣题-Q32
没仔细看题，于是一开始还是当作计数题，尝试分解为小问题，而后发现是输出所有的可能那么就得遍历，在遍历的基础上对条件（“仪式铺法”）进行限制达到剪枝的效果，而后就是条件的代码实现问题，另一方面如何进行输出和记录中间结果也十分重要，在实现中，我使用的方法与原书一致，主要差别在于书中使用“自然数组边界”的方法，而我对数组访问进行判断。...
2022-07-28 17:27:17
141
原创 算法趣题-Q31
一开始想法跑偏，一直想着按照是否右交点进行问题分解尝试进行分治，（好像是有一道对角线的类似题），后来按交点分治不可行，无交点时计算不可再分，于是放弃。而后进行了DFS遍历，可行，代码如C/C++实现。进一步发现另一种子问题划分方式，如原书题解，将路径的第一步和最后一步进行讨论划分为小问题可以达到优化的目标，代码如Python实现。......
2022-07-26 21:34:00
163
原创 算法趣题-Q30
一上来还是先尝试进行模拟，运行时发现模拟的复杂度相当高，于是乎改用为分治法，在一个插座上，按若干个插口进行分治，思路为在这个插口上连接的插线板需要提供n个新的插口，那么当前这个插座上提供的总插口为其若干插口上分别提供的新插口数目，其次对于计数来说，这若干个插口是独立的，故起计数相乘。比较需要注意的就是子问题的构建需要考虑同一个插板上的连接不分次序。代码C/C++实现是直接递归计算，有大量重复计算，Python代码则优化了这一问题，使用字典记录每部分的计算结果。...
2022-07-22 11:03:27
170
原创 算法趣题-Q29
总的来说就是穷举法计算每一种可能的排列的总电阻，然后如何列举每一种排列并计算就是解题的重点，有两种方法，一种是递归法，另一种是递推法（如C/C++实现和Python实现）。
2022-07-21 09:24:06
77
原创 算法趣题-Q28
一眼背包问题，那么就是使用动态规划可以比较好的解决，当然在这种数据量比较小的题目也可以暴力，并且也可以不用数组迭代直接递归，如C/C++实现。然而这体由于数据的分布过于离散，使用数组迭代也会有内存浪费，那么可以使用字典或者vector只记录有的数据，不去直接开辟所有空间，如Python实现。...
2022-07-20 19:44:11
218
原创 算法趣题-Q27
本题的难点在于如何记录已经走过的边以及如何记录当前行驶方向以达到判断“直行”和“左转”的目的，按照书中所提示的，将车辆的坐标变换按上、左、下、右排列那么“直行”就是继续当前下标的坐标变换，“左转”就是下一个下标的坐标变换（取模），这样就可以较为简单地实现方向上的约束；另一方面就是如何记录走过了边，那么书中是使用的bitmap形式记录，本人的实现亦是如此。解决了这两部分问题后就是进行深度遍历搜索，这里需要注意边界和结束条件。...
2022-07-19 16:26:59
134
原创 算法趣题-Q26
书中的解题思路为用二维数组模拟，但是实际上我们只关注空白车位和目标车的位置，那么没有必要使用数组存储其他车的状态，只需要将空白车位和目标车的位置记录下来就可以，然后就是广度遍历，如Python实现。另一种解题思路同样建立在以存储两点位置的基础上，对于空白车位的移动目标位置是有规律的，其必然会与目标车的当前位置相邻，且是靠近最终出口位置的，所以我们可以直接根据空白车位的移动规律设计代码，如C/C++实现。...
2022-07-18 18:53:37
257
原创 算法趣题-Q25
此类具体的题目最常见的做法就是模拟求解，在模拟求解的过程中，需要遍历所有可能的情况，然后需要注意的就是如何计算交叉点，这在本书中有提到，也正如Python代码实现，此处不多介绍。 而另一种方法如C/C++实现将具体的问题进行进一步的抽象和转化，将问题简化为若干根直线具有的最多交点数目，在减去鞋带孔自带的交点就是目标所求。2.Python实现......
2022-06-12 22:22:52
61
原创 算法趣题-Q24
直观的求解方法就是暴力模拟，进一步进行简化可以发现数字的编号对于求解关系不大，那么就可以用另一种编号模拟，再进一步简化可以发现当不考虑中间5的时候，其他的编号的地位是等价的，那么可以只算其中一种方式的解（比如除5外，第一次击中的必有1），再乘以8，同样可以得出结果。如下代码实现均使用第二种模拟方法。2.Python实现...
2022-06-10 17:39:01
57
原创 算法趣题-Q23
首先，每日一吐，这个题目的意思依旧让我陷入了理解误区，问题要求每次只能下注1枚硬币（理解成了可以一次下注多枚），其次，当24回合中途没有了硬币也会直接结束，并且不算在一种可能里。 在以上限定条件下可以使用递归进行简易解题，当然可以使用内存优化方法，其中需要注意如果使用数组存储需要在数组大小上小心，使用递归的方式（C/C++实现）代码实现比较简单，但是对于回合数比较大的样例可能会有爆栈危险，故也可以将递归实现转换为递推实现（Python实现）。2.Python实现...
2022-06-08 22:35:26
64
原创 算法趣题-Q22
首先需要明确的是每个结点都是不同的所以在分组计算时就无需考虑旋转重复，如图中第一行第二个和第二行第一个被视为不同的结对方式。然后就是对问题的拆分，能够发现对于一个大问题来说，可以将其拆分为若干两个小问题，而这个大问题的解可以由这子问题的解组合出来。即将n个结点分为3组，其中1组为分割组只有两个结点，剩下的结点分为两组，也就是两个子问题组。在实现过程中可以通过使用数组存储避免重复计算，代码如下。2.Python实现...
2022-06-07 16:25:04
47
原创 算法趣题-Q21
本题可以直接进行模拟解题，如代码实现中的Python实现，而书中提到另一种模拟方式，只需要使用一个大整数进行迭代，代码思路如C++实现，下一层的数为当前层的数与当前层数左移一位异或的结果，由于最后结果为75，超出了C++存储容量，这里代码仅供参考。2.Python实现......
2022-06-06 17:42:15
57
原创 算法趣题-Q20
在满足问题的条件的情况下可以将问题简化描述为计算16个数字的所有可能的和的结果，并统计得到具有最大的频次的和。 由于只有16个数字，使用暴力法是可以做到的，从1个数和，2个数和，...，16个数和的计算并没有什么难度，但是其时间复杂度过高（），在输入进一步增大时，计算速度会变得很慢，那么需要对其进行改进。我们能够发现暴力法进行了大量的重复计算，我们的目的就是将这些重复计算省去，其中一种方法是动态规划，先计算前n-1个数的所有可能和，在基于其上计算n个数的所欲可能和。2.Python实现.
2022-06-05 16:08:16
96
原创 算法趣题-Q19
一、问题描述二、问题分析 先进行吐槽，依旧是题目理解错了，导致一直不能解题（不知道是题目表述有问题还是我理解有问题，太难了！）。通过看解析，那么题目应该是：求从1~N种选取7个合数，最多且存在恰好经过6层就可以与其他所选取的所有合数产生联系的最小的N。个人理解为与所有的数（包括未被选择的质数和合数，而且也没有说必须有刚好经过6层的）产生联系，导致无法求解。 按照书中的题解进行问题理解后只需要a*a, a*b, b*c, c*d, d*e, e*f, f*f就可以达......
2022-03-02 21:26:24
243
原创 算法趣题-Q18
一、问题描述二、问题分析 做此题的时候陷入了思维误区，总想着如何用算法去直接得出答案，忘记了使用搜索的办法，当然直接暴力的话运行还是比较慢的，需要根据情况去减少遍历的次数。这里，个人使用的是按相邻两个数的和是平方数的前提下进行搜索，最后使用递归方法进行代码实现。三、代码实现1.C/C++实现#include <iostream>#include <vector>using namespace std;vector<int&...
2022-03-01 21:08:12
123
原创 算法趣题-Q17
一、问题描述二、问题分析 基础动态规划问题，可以由小问题的解推出大问题的解，设有N个人，一共有F(N)种排列方式，那么有F(N)=F(N-1)+F(N-2)。思路：有N个人时，当第一个人是男生时，其排列方式与有N-1个人时一样，即F(N-1)种；当第一个人是女生时，第二个人必须是男生，接下来其排列方式与N-2个人时一样，即F(N-2)种。 在代码实现方面，可以使用递归实现，也可以使用计算保存过程的递推实现，这里由于只需要计算指定人数一次，就没有保存中间结果。（同时...
2022-02-28 22:39:58
344
原创 算法趣题-Q16
一、问题描述二、问题分析三、代码实现1.C/C++实现2.Python实现# coding=utf-8import mathdef get_sqrt(n): tmp = math.ceil(math.sqrt(n)) if tmp ** 2 != n: return -1, False return tmp, Trueif __name__ == '__main__': count = 0 ...
2022-02-27 21:14:35
350
原创 算法趣题-Q15
一、问题描述二、问题分析 A，B两个人的运动规则相同，那么先只考虑A或者B，此时就是一个基础的动态规划上台阶问题。那么当考虑A，B相向而行，且最后同时到达同一级台阶上的可能情况就是：同样步数时，A和B加起来一共走10级的可能性。而A，B运动规则相同则可以只计算其中一个人的情况数量，在根据题目进行阶梯数量对应相乘累加即可。在实现方面，可以对动态规划进行优化减少重复运算。三、代码实现1.C/C++实现#include <iostream>#define...
2022-02-27 15:44:57
222
原创 算法趣题-Q14
一、问题描述二、问题分析 解题石炉比较清晰，递归计算深度就行。问题在于如何更快地找到或者确认下一个国名，以及如何把末尾的字母大小写统一。在Python的代码实现中，将所有的字母都大写，并且根据每个国名的首字母将其归类，在递归中可以更快地搜索；而在C/C++的代码中没有做对应的归类而是使用一个个遍历的办法进行搜索，并增加了一个标志标识该国名是否被使用过，而且在统一末尾字母时，只是将最后一个字符大写并附加到源字符串中，没有对字符串做整体的大写。三、代码实现1...
2022-02-26 22:07:38
389
原创 算法趣题-Q13
一、问题描述二、问题分析 一种方法是直接暴力列举所有的排列数，再进行计算判定，那么需要进行10！次判断，效率太低，如代码实现中Python实现，但由于Python语言的友好，导致其代码数量少；另一种方法是DFS深度优先遍历，并结合一些的剪枝操作，能够大量排除无效的排列，加快了运行速度，在我的C/C++实现中就是如此，当然也可以使用递归的方式避免重复编码（这里我将代码展开方便理清逻辑）。三、代码实现1.C/C++实现#include <i...
2022-02-24 22:43:25
670
原创 算法趣题-Q12
一、问题描述二、问题分析 题目的问题描述看的有点懵，按照其做法反推，觉得应该是求其算平方根后，前10个数就包含所有0-9的最小的数，然后分包含整数的情况和只看小数部分的情况。 按照个人理解后进行实现就是将开方后的小数取一定的精度进行统计，看前10个数字是否符合要求。要点在于浮点数的格式化和字符统计。三、代码实现1.C/C++实现#include <iostream>using namespace std;int main()...
2022-02-22 21:32:15
99
原创 算法趣题-Q11
一、问题描述二、问题分析 斐波那契数列的计算比较简单，题目重点在于整形的溢出，在进行C/C++实现时，使用 long 还是溢出，最后使用了 long long 才得出答案。而在Python的实现中则无需考虑这么多。三、代码实现1.C/C++实现#include <iostream>using namespace std;int getSum(long long n){ int sum = 0; while (n > 0) ...
2022-02-21 15:15:22
449
原创 算法趣题-Q10
一、问题描述二、问题分析 这个就是循环求和，比较容易暴力求解（Python实现），当然也可以进行一些优化，减少计算次数，如使用数组进行迭代求和（C/C++实现）。三、代码实现1.C/C++实现#include <iostream>#define MAX_N 36#define MIN_N 2#define ARRAY_SIZE 40using namespace std;// 37 个数int erule[] = { 0, 32, 15, ...
2021-09-20 14:40:59
94
原创 算法趣题-Q09
一、问题描述二、问题分析 最近用递归有点上头，于是本能地尝试使用递归进行代码实现，最后报错了，原因是栈溢出了，于是乎，将递归转换为普通的循环。而本题的根本逻辑是路径组合问题（如图），只不过有一些组合是不被允许的。另外，我在做题时感觉题目描述有些问题，应该是求两组人中男女都不相等的顺序。（我看题以为是两组有一组不均等就行，那可太简单了，汗！）三、代码实现1.C/C++实现2.Python实现...
2021-09-17 23:38:27
47
原创 算法趣题-Q08
一、问题描述二、问题分析 如题干所描述的这种寻路问题可以直接用深度遍历来解决，那么，在这题的难点上就是如何判断这个机器人是否走过了本节点，即如何记录机器人走过的路径。我能想到的就有两种：一种是直接构建一个足够大的二维数组，用数组记录路径，在移动次数较多时会有较大的空间开销；另一种是用坐标数组存储路径，有较好的空间复杂度。这两种方法就类似于存储稀疏矩阵的方法。三、代码实现1.C/C++实现#include <iostream>#define MAX_X 2...
2021-09-13 23:18:25
49
原创 算法趣题-Q07
一、问题描述二、问题分析 这题没啥好说的，跟着题目操作编程就行，对于没有相应函数的C/C++来说相对有些麻烦，那么，我的思路就是构造所有的日期进行判断。而另一边，使用有时间转换相关函数的语言能够更简单的进行代码实现。三、代码实现1.C/C++实现#include <iostream>#include <string>using namespace std;int days_of_month[] = { 31, 28, 31, 30...
2021-09-11 22:45:35
40
原创 算法趣题-Q06
一、问题描述二、问题分析 一开始看到这种类型的题目，我进行了找规律的尝试，于是，没尝试出来，最后选择了暴力破解。用暴力破解的方法，根据题干可以很简单地写出代码。（写到这里，我想说明，我的两种代码实现会尽可能地尝试不同的方法，故有时可能会觉得 Python 的代码冗余，而在这题，我仅仅想试试 Python 中的 yield） 那么，本书的作者说，即使不限制上限为 10000，也不会再有这种数字，我没整出来为啥，有知道的可以留言。三、代码实现1.C/C++实现...
2021-09-10 23:05:08
71
原创 算法趣题-Q05
一、问题描述二、问题分析 经过Q04的题目后，这道题也同样可以视为是将一个大问题拆分成同类型小问题。于是，依旧选择递归算法。三、代码实现1.C/C++实现#include <iostream>using namespace std;int coins[5] = { 500, 100, 50, 10, 0 };int change(int money, int max_count, int type){ // 将 money 找零...
2021-09-09 18:56:43
71
原创 算法趣题-Q04
一、问题描述二、问题分析 分析题干，很明显是一个将大问题拆分为若干相同的小问题的典型题，那么最简单且有效的方法就是使用递归算法。（说实话，由于太久没有做题，我的第一反应竟然是使用队列进行广度优先遍历。）而递归算法也是一种深度优先遍历。下面将给出C/C++的递归算法及广度优先遍历，只给出Python的广度优先遍历。三、代码实现1.C/C++实现#include <iostream>#include <queue>usin...
2021-09-08 12:49:24
46
原创 算法趣题-Q03
一、问题描述二、问题分析 这里补充一点，由于只有100张牌按序排列，故n不大于100，不用考虑的过于复杂。 此题的解决想法比较简单，按题干顺序编程即可。但在结果出来后，会发现结果具有一致的某种性质，同时这个翻牌游戏与数的因子数目具有一定的关系。那么，在做题前找到这个关系就可以很容易的解决该问题，但这不妨碍我们暴力解决，暴力代码如下。三、代码实现1.C/C++ 实现#include <iostream>using namespace s...
2021-09-06 14:27:40
59
原创 算法趣题-Q02
一、问题描述二、问题分析 在这个问题中，我们需要构造表达式并计算其值，最后与其逆序的数进行比较。难点在于表达式的构造与计算。 在得到表达式后，其值的计算变得相对简单，那么，能否将表达式筛选，去除一些不可能的解？例如，当只使用加法时，其表达式最大值为999+9=1008，减除同理，当使用乘法和加法时，其最大值为9*99+9<1000。那么经过一些分析，我们可以发现：当使用加、减、除时，表达式的值不能与其逆序的数字相等。故我们在表达式中只使用乘法进行运算。...
2021-09-05 13:45:34
80
原创 算法趣题-Q01
一、问题描述二、问题分析分析问题可以得出，解决该问题的需要两个主要步骤。第一个为进制的转换；第二个为“回文数”的判断。 其次，对于目标解的搜索域来说，可以从“回文数”入手进行缩写，例如，直接构造十进制的回文数字在进行判断；也可以分析二进制，由于末尾与第一位相同，则二进制最后一位必须为1，得出其十进制为奇数等。三、代码实现1.C/C++实现#include <iostream>using namespace std;enum Co...
2021-09-04 15:21:14
56
原创 STL-set
1.包含<set>头文件#include<set>2.set的创建与初始化set<T> s：创建一个空的集合 set<T> s {n1, n2, ..., ni}：创建一个初始元素为n1，n2，...，ni的集合 set<T> s {begin, end}：用迭代器创建集合set<T[, cmp]>可以传入比较参数，对应于以上所有创建方式#include<iostream>#include<
2020-05-19 10:08:09
117
原创 STL-map
1.包含<map>头文件#include<map>2.map的创建与初始化map<T keyType, T valueType> m：创建一个键为 keyType 类型，值为 valueType 类型的空 map map<T keyType, T valueType> m {pair_1, pair_2, ..., pair_i}：......
2020-05-05 16:33:05
505
原创 STL-queue
1.包含头文件<queue>#include<queue>2.queue的创建与初始化queue<T[, Container=deque<T>]> q：创建一个存储类型 T 的空队列，默认以 deque<T> 组织，可指定其他容器 queue<T, container<T>> q1 (q)：创建一个...
2020-04-30 10:17:46
120
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人