LeetCode

LeetCode Contest 149 No.2 这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, …, f。 我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。 如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。 一开始我以为这是一道数学题，排列组合的数学题 因为上学的时候就是那样做的，只是有些特殊情况 然后我发现这道题的特殊情况数都数不完，我傻了 有那么一个瞬间我在想会不会是 DP ，似乎有点像 但是我不确定，随便想一下也没有想到 DP 怎么做 于是我就放弃这条思路去看 airpods 去了。。。。 竞赛结束之后我看了看别人的答案，只看了两秒钟 这不就是DP么，我关掉解答开始自己好好做这道题 开始： class Solution: def numRollsToTarget(self, d: int, f: int, target: int) -> int: MOD = 10**9 + 7 nums = [[0]*target for _ in range(d)] for i in range(min(f,target)): nums[0][i] = 1 for k in range(1,d): for i in range(1,target): nums[k][i] = sum(nums[k-1][max(0,i-f):i]) return nums[-1][-1]%MOD 下面以5个骰子，每个骰子6个面，要求总和为16举例： 创建一个5*16的数组，横向代表骰子的点数总和，纵向代表骰子的数量，表格内的数字代表用x个骰子拼凑出y的点数总和，共有多少种情况 首先填写第一行的数据：用一个骰子扔出总和是 1、2、3、4、5、6 的情况均只有一种，用一个骰子扔出总和是7、8、9等的情况不存在 填写第二行的数据： 用两个骰子扔出总和是1的可能情况不存在 用两个骰子扔出总和是2的可能情况只有1种，是(1,1) 用两个骰子扔出总和是3的可能情况有两种，是(1,2)和(2,1) 依次类推 我们可以这样去考虑：第二个骰子可能扔出的情况是1、2、3、4、5、6六种情况，举例如果我们要填写第二行第八个空格，即要求扔出的总和为8，那么8的可能情况数量为以前的骰子扔出的情况为7、6、5、4、3、2这六种情况的总和。即，当第二个骰子扔出1时，以前的骰子总和为7，第二个骰子扔出2时，以前的骰子总和为6，依次类推 在表格中表示即为，某一格的值为在上一行不包括当前格子向左数六个格子的总和，即下图橙色框表示的区域 以此类推填写完整个表格 在本例中，表格右下角的数字即为5个骰子扔出总和为16的可能情况数量，为735 将本例拓宽到d个骰子f个面扔出总和为target的情况数量即为题目要求 下面重新看一下程序并将整个过程梳理一遍 class Solution: def numRollsToTarget(self, d: int, f: int, target: int) -> int: MOD = 10**9 + 7 nums = [[0]*target for _ in range(d)] # 初始化数组 for i in range(min(f,target)): nums[0][i] = 1 # 填第一行的数 for k in range(1,d): for i in range(1,target): nums[k][i] = sum(nums[k-1][max(0,i-f):i]) # 依次填写后面行的数 return nums[-1][-1]%MOD #返回最终数的MOD值 建立一个二维矩阵，行数为d，列数为target，矩阵内容初始化为0 将第一行前f个数填为1 对于剩余的格子，每个格子等于上一行向前数f个数的和 返回矩阵的最后一个数 DONE ...

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)$ ...