JZX 轻语

LeetCode 1262 - 可被三整除的最大和

比较容易想到使用动态规划的方法，定义dp[j][i](其中0 <= i < 3)表示数组前j个元素中，模3余数为i的最大和。遍历数组，对于每一个nums[j]，更新dp[j][(i + nums[j]) % 3] = max(dp[j - 1][(i + nums[j]) % 3], dp[j - 1][i] + nums[j])。最终的答案就是dp[len(nums) - 1]...

Posted by Jeza Chen on July 15, 2024

LeetCode 1254 - 统计封闭岛屿的数目

Flash 此文章属于Flash闪念部分的短文

所谓的封闭是指四周全都被1包围的0，因此我们可以通过BFS遍历整个矩阵，将所有相邻的0视作为一个岛屿，如果四周没有遇到边界，说明就是封闭岛屿。为了避免重复遍历，我们可以将遍历过的0原地置为1，表示已经遍历过，且不会影响后续的遍历。 from collections import deque class Solution: moves = ((0, 1), (0, -1), ...

Posted by Jeza Chen on July 15, 2024

LeetCode 1253 - 重构2行二进制矩阵

Flash 此文章属于Flash闪念部分的短文

可以使用贪心解决：首先直接将参数upper和lower视作为第一行和第二行待填充1的个数。从左到右遍历colsum，如果遇到2，则需要同时填充两行，并更新upper和lower；如果遇到1，即仅需填充一行，此时取upper和lower中剩余值较大的一个进行填充，并更新计数；如果遇到0，则不需要填充，直接跳过。最后，如果upper和lower都为0，则返回填充后的矩阵，否则返回空列表(题意表明...

Posted by Jeza Chen on July 14, 2024

LeetCode 1249 - 移除无效括号

Flash 此文章属于Flash闪念部分的短文

使用栈来维护未匹配的左括号的位置信息。如果遇到了右括号，且栈为空，则说明该右括号是多余的，需要被移除；如果栈非空，则弹出栈顶元素，表示该左括号已经匹配。最后，栈中剩余的元素即为多余的左括号，需要被移除。对于Python而言，由于字符串是不可变的，需要将字符串转换为列表进行处理，移除操作等价于将列表对应位置的元素置为""。最后，将列表使用str.join转换为字符串返回即可。 cla...

Posted by Jeza Chen on July 14, 2024

LeetCode 1247 - 交换字符使得字符串相同

Flash 此文章属于Flash闪念部分的短文

需要一些观察和分析，首先，在同一个下标i下，如果s1[i]为x，而s2[i]为y，将其记为xy对；如果s1[i]为y，而s2[i]为x，将其记为yx对。那么，如果存在两个相同的xy对(或者两个相同的yx对)，那么可以通过一次交换将这两个对应的下标变为相同的字符；而如果仅有一个xy对以及一个yx对，那么需要两次交换才能将其变为相同的字符。对于整个字符串而言，如果xy对和yx对的个数总和为奇数，...

Posted by Jeza Chen on July 14, 2024

LeetCode 3011 - 判断一个数组是否可以变为有序

Flash 此文章属于Flash闪念部分的短文

题目中的交换操作以实现排序，本质就是冒泡排序的做法。因此，我们可以模拟冒泡排序的过程，如果在交换过程中发现需要交换的相邻两个元素的二进制数位1不同，那么就无法通过交换操作实现排序，返回False；否则，返回True。上述的模拟冒泡排序做法的时间复杂度为O(n^2)，其实还有一种不用排序，且仅需一次遍历的做法。通过观察发现，某个元素能交换的位置范围是有限的，即该范围内所有的元素都具有相同的...

Posted by Jeza Chen on July 13, 2024

LeetCode 3102 - 最小化曼哈顿距离

Flash 此文章属于Flash闪念部分的短文

两个点p0(x1, y1)和p1(x2, y2)的曼哈顿距离为|x1 - x2| + |y1 - y2|。不妨将绝对值分情况讨论，即有四种情况： x1 >= x2，y1 >= y2，有x1 - x2 + y1 - y2 = (x1 + y1) - (x2 + y2)； x1 >= x2，y1 < y2，有x1 - x2 + y2 ...

Posted by Jeza Chen on July 9, 2024

LeetCode 1222 - 可以攻击国王的皇后

Flash 此文章属于Flash闪念部分的短文

类似于1958-检查操作是否合法，枚举八个方向，如果有一个方向具有皇后，则将该皇后坐标添加到结果数组中(后续该方向不用寻找了，只关注该方向的第一个皇后)，然后转向下一个方向继续寻找。 class Solution: moves = ( (-1, 0), # 左 (1, 0), # 右 (0, -1), # 上 ...

Posted by Jeza Chen on July 9, 2024

LeetCode 1219 - 黄金矿工

Flash 此文章属于Flash闪念部分的短文

此类问题均可考虑使用DFS+回溯法解决。在这道题中，以每一个有黄金的点为起点，进行深度优先搜索，找到最大的路径和。在搜索过程中，由于不允许回到已经开采的点，需要记录已经访问过的点，以避免重复访问。有一个节省空间的trick，即在访问过一个点后，将其值置为0，这样就不需要额外的空间记录已经访问过的点，待回溯结束后，将其值恢复即可。上述节省空间的trick可以更形象地理解为，将已经访问过...

Posted by Jeza Chen on July 9, 2024

LeetCode 1218 - 最长定差子序列

Flash 此文章属于Flash闪念部分的短文

定义dp[i]为以数字i(注意不是以下标i结尾)结尾的最长定差子序列的长度(用哈希表维护dp)。对于每个数字num，如果num - difference在哈希表中，那么dp[num] = dp[num - difference] + 1，否则dp[num] = 1。最后返回哈希表中的最大值即可。为啥无需dp[num] = max(dp[num], dp[num - differenc...

Posted by Jeza Chen on July 9, 2024

LeetCode 1262 - 可被三整除的最大和

LeetCode 1254 - 统计封闭岛屿的数目

LeetCode 1253 - 重构2行二进制矩阵

LeetCode 1249 - 移除无效括号

LeetCode 1247 - 交换字符使得字符串相同

LeetCode 3011 - 判断一个数组是否可以变为有序

LeetCode 3102 - 最小化曼哈顿距离

LeetCode 1222 - 可以攻击国王的皇后

LeetCode 1219 - 黄金矿工

LeetCode 1218 - 最长定差子序列

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04