Algorithm

问题 暴力求解 解答分析 对于循环次数 对于判断范围 若不是因为爱着你，怎么会夜深还没睡意。每个念头都关于你，我想你 想你 好想你。 若不是因为爱着你，怎会不经意就叹息。有种不完整的心情，爱你 爱你 爱着你。 问题 最近做了一些 Project Euler 的题目。目前只做了前十题，感觉和一般的编程题目比还是挺有意思的，单一案例，不限时间，不限做法，只要做出来的就可以，你愿意的话暴力求解，手动去算都可以，还是挺有意思的。 前面有几道关于质数 (Prime Number) 的题目，需要判断一个数是否是质数，也就是这次的问题了。 Problem 7. 10001st prime By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number? Problem 10. Summation of primes The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. ...

Contest 130 通过：4/4 排名：59/1293 1:58:42 6WA No.1018 可被 5 整除的二进制前缀 思考过多，还在想那样做对不对，做的太少所以对题目类型不熟悉。 No.1017 负二进制转换 2WA emmmmmm，这道题怎么就过了呢。。。 思考过程：用几个数字尝试拼凑了一下，感觉上是要拼凑到最近的2的幂次上去，但是并没有找到绝对的规律。 然后发现某一位数字可以通过其他位来拼凑，如 $(2)^1=(-2)^2+(-2)^1$ ，然后将原始数字以4进制做拆分，再由低位至高位依次处理大于1的情况。例如：$9=1\times(-2)^0+2\times(-2)^2$，负二进制表示为201，然后从低位到高位，分别处理2、3、4的情况，200 和 11000 相等，300 和 11100相等， 400 和 10000 相等。最后即可得到结果。（好麻烦啊） 看了一下别人的回答，类似于二进制转换，得到 %2 后再进行 /2 的操作。区别只是在奇数位时+1而不是-1。不知道如何证明这样是正确的，但是感觉上是正确的，嗯。不懂得东西先记住就好了。 另外还有一点思考，如何证明负二进制是可以表示所有数字的呢，类似的，负三进制是否可以，负四进制是否可以，待求证。 No.1019 链表中的下一个更大节点 1WA 以前做过一道类似的题，维护一个栈，当下一个数字比栈顶的数字大时，取出栈顶的数字并记录，否则将下一个数字入栈，全部循环后若栈内还有数字，均输出0。 这道题对比了一下我的做法和别人的，思路是一样的，但是代码量差距很大，自己在这种问题的边界条件和条件分类处理上有点死板和脑袋不清楚，所以代码量大，代码思路也不是十分清晰，还需要多多练习。 No.1020 飞地的数量 3WA 前面大量时间浪费在了一个错误的思路上，第一反应是和做过的类似，进行一个DFS的遍历，遍历每一个“陆地”，然后向四个方向去搜索，看是否能够找到依然是陆地并接触到边界，如果能，那么不是飞地，如果不能，是飞地，然后标记，进行计数。后来发现越做思路越乱，且复杂，在进行深度搜索的时候还需要维护一个表去标记该地是否是已经搜索过的，极度复杂。然后转回去做第二题，做第二题的途中想到，应该反向去搜索，从接触边界的陆地进行深度搜索，每个搜索过的陆地都进行标记，为不是飞地的陆地，全部搜索遍历结束后，再进行遍历计数。 两个可优化的点：一个是根据看别人的代码发现，我是使用迭代进行深度搜索的，有人是使用一个 queue，需要进行搜索的陆地都推入 queue 中，在搜索过程中新搜索到的相邻的不是飞地的地也推入 queue 中，直至整个 queue 清空为止，感觉这种方法思路更加清晰一些，下次做到类似的题需要尝试一下。 另外一个是搜索上下左右四个方向的时候，建立一个数组 [[0,1],[0,-1],[1,0],[-1,0]]，然后对每个点循环加这四个变量即可，这种方法在前面做题过程中有见到提过，但是自己仍然没有用过，后面遇到一样的题也是需要尝试一下使用这种方法实现。

Contest 131 通过：4/4 排名：44/917 1:10:59 2WA 这次竞赛整体感觉难度一般，基本看到题目后直接就有思路，看了看其他人的做法，基本上思路一样。但是依旧~~~错的多、逻辑复杂、做题的时候感觉考虑清楚了但是做的时候细节还是有没考虑到的地方。速度嘛，不要求了，目前的目的还是能做出来吧。 No.5016 删除最外层的括号 1WA 一开始使用迭代器进行 string 的遍历，然后在测试的时候，有时候测试结果是正确的，有时候是 out of range，最后也没有发现是什么原因，就先去做剩下三个题了，回来之后改成循环数字下标就好了，可能是最后一个位置超出了 string 的长度，以后还是多用下标比较合适，除非循环内要做的工作比较简单。 No.5017 从根到叶的二进制数之和 一开始初始值给错了，没有大问题。 No.5018 驼峰式匹配 居然，做到一半的时候，忘记题目了！！！ 做到一半的时候只记得要匹配对了就可以了，完全忘记了是只能插入小写字母，但是还好还好这道题给的测试用例比较全面，才通过了。 另外可以多接触一下库啊，isupper这种函数的用法，多知道一些总是好事。 No.5019 视频拼接 1WA 完完全全忘记了那次错误提交是为什么，明明是昨天刚做过的题…… 嗯，那就没啥说的了

Contest 132 通过：3/4 排名：99/1047 0:59:44 1WA 最后一道题规定时间内没有做出来，超时7分钟做出来的，无错误提交（似乎）。 这次竞赛感觉看完题都比较虚，但是其实做题之后的效果比预想的好，虽然最后一道题规定时间内没有做出来，但是感觉可以接受，也是很久没有出过 hard 的题目了，这次的 hard 题目实现的相当的。。。。复杂且乱，但是能做出来就是好事。 No.5024 除数博弈 1WA 看到这个题，感觉可能是动态规划后，第一个想法：动态规划都是简单的题了啊！ 是的，这道题还花了整整20分钟才做出来，感觉其中十分钟浪费在了不可置信上和另外一些事情上。。。这次做竞赛太不专心了，批评一下自己，竞赛还是要好好做的。 实现思路上没啥可说的，就是动态规划的思路，从小到大依次遍历所有约数对应的N-x的值，所有约数全部为 true 的时候，这时无论先手做如何操作，对方都是必胜的情况，所以这时的 N 为 false ，其余所有情况均为 true ，只需要在每一步操作时将 N 的值变为对应的 false 的 N-x 的值即可。 No.5030 节点与其祖先之间的最大差值 一开始脑袋有点乱，想用 pair<int,int> 去实现同时寻找最大值最小值，但是思路一直没有理顺，抱着这次竞赛就放弃了的态度（。。。。）就想着先只写一个 max 吧，很快完成之后，同样的方法复制一份 min ，游戏结束。 思路：后序遍历，先左后右找最大最小值，然后向上计算最大差值，重复循环即可。 注：这里的最大最小值是需要跟着遍历走的，而且必须是后序遍历，这样才不会左右子树之间的最大最小值互串。 No.5025 最长等差数列 最没想到的一道题，看完题目毫无思路，而且感觉以前见过类似的题，但是没有做，也没有去找答案怎么实现，感觉自己栽在了自己的手上。按照上一道题的破罐子破摔的思路，想着就用朴素方法做吧，最后一道 hard 的题目看着也不面善，这个至少朴素方法的思路还是有的，甚至实现后都没怎么跑例子测试，没想到直接通过了。思路也没啥思路，暴力搜索。 TODO: 认真去看看别人的实现，回来写一下思路。 No.5031 从先序遍历还原二叉树 好可惜的题，有了思路之后只剩下不到二十分钟了，然后最后快到时的时候其实主要思路也完成了，缺少一个判断，没有理清楚逻辑放在哪里，生生拖到七分钟。 字符串！字符串！字符串！重要的事情，唉，说三遍也不管用，不知道第几次栽在字符串上面了，但是我的字符串水平还是停留在磕磕绊绊能实现上。用了一个超复杂的方式把原始字符串的数据整齐的摆放在了一个 vector<pair<int,int» 当中，嗯，是我做事情的风格，东西要摆整齐。后面遍历问题倒是不大。 用一个 stack 保存当前处理的 TreeNode 节点，并留一个变量保存当前深度，对每一个新的数字，判断深度的关系:。情况1：如果新数是当前节点的下一层，判断当前节点的左子树是否为空，为空的话放在左子树，否则放在右子树。情况2：如果新数是当前节点的层数或者更高层，从 stack 中取出上一个保存的节点，并且深度-1，直到满足情况1为止。情况3：如果新数是当前节点的下一层以下，将当前处理的节点推入 stack 中，并且深度+1，这时需要判断当前节点的右子树是否为空 ，如果为空的话当前节点等于当前节点的左子树，否则为当前节点的右子树，直到满足情况1为止。 看到这里，我居然又忘记为什么这么判断了，唔，应该是因为原始数据为先序遍历的结果，所以新数如果比当前节点的子节点更深的话，有两种情况。一种是先序遍历的左子树，这时候左子树有值，右子树为空，那下一个处理的节点必定为左子树。另一种情况是之前经过了情况2后当前处理的节点上升到了该层，这时候当前层的左子树已经处理完毕了， 所以如果右子树不为空的话，当前要处理的必定在右子树内。 好了，什么乱七八糟的，因为是先序遍历，先输出再遍历左再遍历右，所以如果右子树有数的话，必定左子树是完整的了，所以如果右子树不为空，就继续处理右子树，否则处理左子树。OVER。 这次竞赛给我的感觉就是，感觉这道题应该有更好的办法吧，感觉这样实现好蠢，但是一时半会又想不到好的解决办法，最后直接使用朴素方法去实现，但是也没想到，其实朴素实现的结果都还不错，至少通过了，也没有出现超时的现象，虽然这个不应该是目标，目标应该是和我的能力之间有一段距离的，这样才能够得到提升。但是也告诉了我一个现在我做题时的一个不太好的想法，一直去寻找方法，而忽略朴素的实现方法，所以经常有时候一道题看了看没有好思路就一直放着，放很久都没有做。这样做一下竞赛，对自己有压力了，不得不做了，就会着急不管用什么方法先做出来再说，也会让自己踏实一些。 PS: 再碎碎念一下，过年的时候报名的比赛，居然忘记比了！居然忘记比了！！！简直了，当时就感觉这么久以后的事情到时候可能会忘记吧，果然不假。

Contest 167 通过：4/4 排名：107 / 1534 1:43:12 5WA No.5283 二进制链表转整数 给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。 请你返回该链表所表示数字的 十进制值 。 示例 1： 输入：head = [1,0,1] 输出：5 解释：二进制数 (101) 转化为十进制数 (5) 示例 2： 输入：head = [0] 输出：0 示例 3： 输入：head = [1] 输出：1 示例 4： 输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0] 输出：18880 示例 5： 输入：head = [0,0] 输出：0 提示： 链表不为空。 链表的结点总数不超过 30。 每个结点的值不是 0 就是 1。 嗯，水题。 时间复杂度：$O(n)$ class Solution: def getDecimalValue(self, head: ListNode) -> int: ans = 0 while head!=None: ans = ans*2+head.val head = head.next return ans No.5124 顺次数 我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。 请你返回由 [low, high] 范围内所有顺次数组成的 有序 列表（从小到大排序）。 ...

Contest 168 通过：4/4 排名：61 / 1552 1:08:39 1WA No.5291 统计位数为偶数的数字 给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。 示例 1： 输入： nums = [12,345,2,6,7896] 输出： 2 解释： 12 是 2 位数字（位数为偶数） 345 是 3 位数字（位数为奇数） 2 是 1 位数字（位数为奇数） 6 是 1 位数字 位数为奇数） 7896 是 4 位数字（位数为偶数） 因此只有 12 和 7896 是位数为偶数的数字 示例 2： 输入： nums = [555,901,482,1771] 输出： 1 解释： 只有 1771 是位数为偶数的数字。 提示： 1 <= nums.length <= 500 1 <= nums[i] <= 10^5 嗯，水题。（但是大佬一行代码。。） 时间复杂度：$O(n)$ ...