JZX 轻语

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

不难得知，在每个对角线的元素中，列号和行号的差值是恒定的，可以根据行号确定某个对角线元素的列号。按行/列其中一个维度斜着就地快速排序即可，需要注意边界条件。 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 39 & 216 & 377 - 组合总和相关问题

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

这三天的每日一题都是组合总和的问题：第一天的题目39可以用回溯法解决，在参数中记录当前回溯的数组开始位置（由于重复选取，下一次回溯的数组开始位置可以和本次相同）、当前所选用的数字组合arr及其和cur_sum = sum(arr)。如果当前的cur_sum等于target，则加入到结果列表中并返回。为了加快搜寻，如果下一次回溯的cur_sum已经大于target，则直接剪...

Posted by Jeza Chen on April 22, 2024

LeetCode 725 - 分割链表

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

链表题，首先需要遍历一次得到链表的长度length，然后按k切分链表，如果块i满足i < length % k，则该块的长度为length // k + 1（如果切分不均匀，前面的块比后面的块长）；否则，该块的长度为length // k。遍历的时候，使用两个变量curr和prev分别指向当前节点及前驱节点，当curr刚好指向某个块的头节点，则断开prev和curr的联系，将curr添...

Posted by Jeza Chen on April 21, 2024

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

LeetCode 743 - 网络延迟时间

LeetCode 735 - 小行星碰撞

LeetCode 1017 - 负二进制转换

LeetCode 779 - 第K个语法符号

LeetCode 1146 - 快照数组

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

LeetCode 1052 - 爱生气的书店老板

LeetCode 39 & 216 & 377 - 组合总和相关问题

LeetCode 725 - 分割链表

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04