JZX 轻语

LeetCode 594 - 最长和谐子序列

使用哈希表记录每个数组的个数，然后再遍历哈希表的键key，如果key + 1也在哈希表里，则使用其和更新结果(取两者最大值)；此外，也可以先排序，然后再遍历计数，维护最近两个数字的计数，如果这两个数字相邻，则使用其和更新结果。基于哈希表： class Solution: def findLHS(self, nums: List[int]) -> int: ...

Posted by Jeza Chen on May 2, 2024

LeetCode 752 - 打开转盘锁

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

BFS的应用，使用BFS模拟可能的所有转法(从第1位开始，往上拨or往下拨，直至第4位)。如果某个转法已经处理过or锁死，则不加入队列中。 from collections import deque class Solution: def _roll(self, cur_lock: str): for i in range(4): y...

Posted by Jeza Chen on April 29, 2024

LeetCode 1329 - 将矩阵按对角线排序

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

不难得知，在每个对角线的元素中，列号和行号的差值是恒定的，可以根据行号确定某个对角线元素的列号。按行/列其中一个维度斜着就地快速排序即可，需要注意边界条件。 class Solution: def diagonalSort(self, mat: List[List[int]]) -> List[List[int]]: def partition(lo: ...

Posted by Jeza Chen on April 29, 2024

LeetCode 743 - 网络延迟时间

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

本质就是求单源最短路径，然后返回节点K到其他节点的路径中的最大者即可。普通的Dijkstra算法： from collections import deque class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: adj_...

Posted by Jeza Chen on April 28, 2024

LeetCode 735 - 小行星碰撞

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

使用栈来维护存活的小行星(不难推出，这个数组中，往左走的小行星必定在所有往右走小行星的前面，否则会继续发生碰撞)。从左往右处理小行星，如果小行星往左走、仍存活、且栈顶的小行星(存活的小行星中最靠右的)往右走，则处理碰撞，直至不满足上述条件。 class Solution: def asteroidCollision(self, asteroids: List[int]) -&g...

Posted by Jeza Chen on April 28, 2024

LeetCode 1017 - 负二进制转换

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

首先对数字按正常的二进制展开，然后如果某个二进制位在新的表示法中属于负数，则需要”往前借一位”，比如，第3个比特在新的表示法中是-8，如果需要表示8，则需要利用第4个比特，即8 = -8 + 16，然后再进一步处理16之后的数字(前面的处理结果已经固定了，无后效)。如果某一位比特不仅原来的表示法需要使用到，且前面的数字又存在进位，则需要合并、往后面继续进位，如24 = 8 + 16 = -8...

Posted by Jeza Chen on April 28, 2024

LeetCode 779 - 第K个语法符号

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

数组规律题，可以通过列举前面几层得出规律：0 -> 0,1 -> 0,1,1,0 -> 0,1,1,0,1,0,0,1 -> 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0。每一层的长度都是上一层长度的两倍(一个数分裂出两个数)，且前半段即上一层数组，后半段是前半段的取反。令k从0开始计数，因此，第k位的取值，是第k - int(sqrt(k)) * ...

Posted by Jeza Chen on April 26, 2024

LeetCode 1146 - 快照数组

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

简单想法是每次快照时，都存一份完整的列表，但这样会导致内存超限。优化思路类似于开散列法的哈希表。其中每个索引self._arr[i]使用一个桶来存储快照信息，其元素为一个记录快照id和值的元组(snap_id, val)。只有调用set保存的时候，才针对index新建一个快照信息。当使用get查询某个索引index内特定快照snap_id的值时，使用二分法搜索桶内self._arr[inde...

Posted by Jeza Chen on April 26, 2024

LeetCode 2385 - 感染二叉树需要的总时间

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

有点难度的二叉树递归，节点的感染路径有三个方向：往下感染左子树，右子树以及往上感染祖先。可以通过一次遍历得到结果：使用一个变量ans维护当前的感染最长路径，按后序遍历树节点，如果遇到了start节点，则先将ans设置为其子树的高度。否则，对于某个节点，如果其左子树包含start节点，则可能的最长感染路径为start节点->...[从左子树往上感染]->本节点->...[往下...

Posted by Jeza Chen on April 24, 2024

LeetCode 1052 - 爱生气的书店老板

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

题目中带有”连续”、”只能使用一次”等字眼，说明可以尝试使用滑动窗口解决。首先计算老板不抑制情绪的情况下，原始的满意度orig_satisfied = sum(cnt * (1 - is_grumpy) for cnt, is_grumpy in zip(customers, grumpy))，然后使用一个大小为minutes的窗口，计算窗口下抑制情绪所能带来的满意度提升，然后不断向右滑动窗...

Posted by Jeza Chen on April 23, 2024

LeetCode 594 - 最长和谐子序列

LeetCode 752 - 打开转盘锁

LeetCode 1329 - 将矩阵按对角线排序

LeetCode 743 - 网络延迟时间

LeetCode 735 - 小行星碰撞

LeetCode 1017 - 负二进制转换

LeetCode 779 - 第K个语法符号

LeetCode 1146 - 快照数组

LeetCode 2385 - 感染二叉树需要的总时间

LeetCode 1052 - 爱生气的书店老板

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04