JZX 轻语

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

题目中的交换操作以实现排序，本质就是冒泡排序的做法。因此，我们可以模拟冒泡排序的过程，如果在交换过程中发现需要交换的相邻两个元素的二进制数位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 1209 - 删除字符串中的所有相邻重复项II

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

从左往右遍历字符串，使用一个栈来维护已遍历字符的连续计数，如果当前字符与栈顶字符相同，则将计数加一，否则将当前字符入栈，并将栈顶计数计为1。如果栈顶字符计数超过了k，则需要出栈。最后拼接栈中尚存的字符即可。 class Solution: def removeDuplicates(self, s: str, k: int) -> str: stack = ...

Posted by Jeza Chen on July 7, 2024

LeetCode 1202 - 交换字符串中的元素

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

一开始没啥思路，以为是贪心算法之类的。后面想了下可以用图来建模，将字符串的index视作为节点，如果某两个位置的字符可以交换，则将这两个位置的节点连接起来(如果a和b可以交换，b和c可以交换，则a和c可以交换，具有传递性，这和连通分量的特性一致)。由于连通分量里面对应的字符可通过交换排成任意的次序，因此，对于每个连通分量，将其内部的字符排序后，再按照index从小到大的顺序填回去即可。连通分...

Posted by Jeza Chen on July 7, 2024

LeetCode 3101 - 交替子数组计数

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

比较简单的动态规划题目，使用dp[i]表示以A[i]结尾的交替子数组的个数，那么状态转移方程为dp[i] = dp[i - 1] + 1 if A[i] != A[i - 1] else 1。最后的结果累加dp数组即可。 class Solution: def countAlternatingSubarrays(self, nums: List[int]) -> int:...

Posted by Jeza Chen on July 6, 2024

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

LeetCode 3102 - 最小化曼哈顿距离

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

LeetCode 1219 - 黄金矿工

LeetCode 1218 - 最长定差子序列

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

LeetCode 1958 - 检查操作是否合法

LeetCode 1209 - 删除字符串中的所有相邻重复项II

LeetCode 1202 - 交换字符串中的元素

LeetCode 3101 - 交替子数组计数

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04