JZX 轻语

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

可以使用贪心解决：首先直接将参数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 724 - 寻找数组的中心索引

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

比较简单的前缀和题目，但有个优化点值得记录下。该题目可以套用前缀和模板做法，即计算双侧前缀和，先记录一遍前缀和，然后再反向遍历一遍数组，如果当前前缀和和后缀和相等，则返回当前索引即可。但是这样的时间复杂度是O(n)。有一个更好的做法，可以在前缀和计算的过程中直接判断是否满足条件，这样可以减少空间开销。具体做法是，先计算出数组的总和total，然后遍历数组，如果当前前缀和prefix(不包括当...

Posted by Jeza Chen on July 8, 2024

LeetCode 1958 - 检查操作是否合法

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

直接枚举八个方向，如果有一个方向满足要求，直接返回True即可。如何判断是否满足要求呢？先记目标颜色color为A，相反颜色为B，我们需要在至少一种方向的路径上满足AB..BA格式。从落点(rMove, cMove)出发，枚举八个方向，沿着方向一路检查，如果走出边界或者遇到空格，说明无法构成AB..BA的格式，不满足要求；如果遇到相反颜色，则判断B的个数是否大于等于1，如果是，则满足要求。 ...

Posted by Jeza Chen on July 7, 2024

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

LeetCode 1249 - 移除无效括号

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

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

LeetCode 3102 - 最小化曼哈顿距离

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

LeetCode 1219 - 黄金矿工

LeetCode 1218 - 最长定差子序列

LeetCode 724 - 寻找数组的中心索引

LeetCode 1958 - 检查操作是否合法

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04