JZX 轻语

LeetCode 419 - 甲板上的战舰

本来想通过DFS这些方法来扫描的，后面发现只要枚举每个战舰的起点即可：只要某个’X’的左边和上边都不是’X’，那么这个’X’就是一个战舰的起点。 class Solution: def countBattleships(self, board: List[List[str]]) -> int: ans = 0 for i in range...

Posted by Jeza Chen on June 11, 2024

LeetCode 1061 - 按列翻转得到最大值等行数

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

不妨取个例子：如果通过多次列翻转后，数组[0, 0, 1]变为全0或者全1，那么通过相同的列翻转操作，数组[1, 1, 0](注意，110和011异或后为0)也可以变为全1或者全0，而其他排列的数组则不会变为全0或者全1(具有互斥性)。我们将这些两两异或后为0的行放在一个集合内，该问题本质就是求解最大的集合，其中集合内的行通过相同的列翻转操作可以变为全0或者全1。我们可以使用哈希表进行集合计...

Posted by Jeza Chen on June 11, 2024

LeetCode 1061 - 按字典序排列最小的等效字符串

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

题目有点绕，但由于等价关系具有对称性和传递性(即a等价于b，b等价于c，则a等价于c)，因此可以使用集合来表示等价关系(即上述的a、b和c可以放在一个集合内)，而此类问题的解法通常是使用并查集。对于每个集合，我们需要找到集合内最小的字符，可适当修改下并查集的模板实现：每个集合的代表(即根节点)使用最小字符，在合并两个集合时，取两个集合内最小的字符作为合并后集合的最小字符。 import...

Posted by Jeza Chen on June 11, 2024

LeetCode 1053 - 交换一次的先前排列

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

为了保证交换后的数字在小于原数字的要求下尽可能大，交换的位置应尽可能靠右。因此，我们从右往左扫描，找到第一个不满足升序的位置(即对于位置i有arr[i] > arr[i - 1])，然后在其右边找到最大的比它小的数（如果有重复值, 则交换最靠左的）arr[j]，交换这两个数即可。贪心可行性的证明: 证明上述的待交换左侧位置i是最优的：如果存在一个更优的位置k，...

Posted by Jeza Chen on June 11, 2024

LeetCode 3067 - 在带权树网络中统计可连接服务器对数目

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

其实没啥好的做法，需要枚举每个节点，计算其作为根节点时，每棵子树(每个方向)中路径长度为signalSpeed的倍数的边的数量。然后经过该节点的服务器对数目就是以该节点作为根时，不同子树中满足上述条件的边两两乘积的和。可以用BFS或DFS来实现。两两乘积的和，可以利用后缀和来优化二次循环：先计算出各个方向结果的总和，然后每次遍历的时候减去当前的值，就可以得到剩下未遍历元素的总和，然后...

Posted by Jeza Chen on June 4, 2024

LeetCode 1020 - 飞地的数量

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

该题目的本质就是求解和边界不相通的陆地单元格数量。可以使用BFS就地对和边界相连的陆地单元格进行标记(将其改为2即可)，然后再次遍历整个矩阵，统计未被标记的陆地单元格数量。这里有两个注意点：避免重复标记，可以在遍历边界时，避免重复标记。在移动的时候就标记为2，而非在出队的时候标记，避免重复入队浪费时间。 class Solution...

Posted by Jeza Chen on June 4, 2024

LeetCode 1019 - 链表中的下一个更大节点

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

一般而言，求解下一个更大元素的题目可以考虑单调栈。在此类题目中，可以使用栈来存储当前右侧还没有更大元素的链表节点(必然单调递减，否则和前提矛盾)。遍历链表节点，如果当前节点的值大于栈顶节点的值，则弹出栈顶节点并设置其结果为当前节点的值，直至栈为空或栈顶节点的值大于当前节点的值。最后将当前节点入栈。在这里需要注意一点的是，由于遍历完毕前并不清楚链表的长度，在遍历每个节点时，需要先追加一...

Posted by Jeza Chen on June 4, 2024

LeetCode 1011 - 在D天内送达包裹的能力

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

此类求解满足条件的最小值的题目，且满足小于该值时均不满足条件，大于该值时均满足条件，可考虑使用二分法来解决。首先确定二分的上下界[货物最大值, 货物总量](小于货物最大值必然不满足条件, 大于货物总量必然满足条件)，然后使用二分法来逼近满足条件的最小值。 class Solution: def shipWithinDays(self, weights: List[int], d...

Posted by Jeza Chen on June 4, 2024

LeetCode 1015 - 可被K整除的最小整数

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

记r(i)为i个1组成的数字，不难得知r(i) % k = ((r(i-1) % k) * 10 + 1) % k。因此，我们可以不断累加i并计算r(i)的值，直到r(i) % k == 0为止。此外，我们还需要一个哈希表来存储r(i) % k的值，以便在遇到重复的r(i) % k时(意味着后面产生了循环的结果)，直接返回-1。此外，如果k为偶数或者5的倍数，那么不可能找到符合条件的i（所有...

Posted by Jeza Chen on June 2, 2024

LeetCode 1010 - 总持续时间可被60整除的歌曲

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

该题目本质是统计数对(a, b)的个数，其中(a + b) % 60 == 0。由于(a + b) % 60 == 0等价于(a % 60 + b % 60) % 60 == 0，我们可以使用一个哈希表来存储前面已处理的数字模60后结果的计数，然后遍历元素b，累加哈希表中(60 - b % 60) % 60的计数即可。也可以先计数后，再遍历哈希表中的1-29的数字，累加count[i] * ...

Posted by Jeza Chen on June 2, 2024

LeetCode 419 - 甲板上的战舰

LeetCode 1061 - 按列翻转得到最大值等行数

LeetCode 1061 - 按字典序排列最小的等效字符串

LeetCode 1053 - 交换一次的先前排列

LeetCode 3067 - 在带权树网络中统计可连接服务器对数目

LeetCode 1020 - 飞地的数量

LeetCode 1019 - 链表中的下一个更大节点

LeetCode 1011 - 在D天内送达包裹的能力

LeetCode 1015 - 可被K整除的最小整数

LeetCode 1010 - 总持续时间可被60整除的歌曲

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04