JZX 轻语

LeetCode 684 - 冗余连接

并查集的模板题目，思路类似于Krustal算法，先依次添加这些边到并查集, 然后某个边加入后形成了一个环, 则直接return即可。 class DSU: def __init__(self, n): self.pa = [i for i in range(n)] def find(self, x: int) -> int: if...

Posted by Jeza Chen on April 10, 2024

LeetCode 678 - 有效的括号字符串

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

经典括号匹配题目的衍生题目，在此基础上新增了一个通配符(可以用作左括号、右括号或者空字符)。首先按通常的做法来做，并记录已读取的星号数(先不使用, 用一个栈来存储出现的位置)，如果当前处理右括号但左括号已经用完，则使用一个星号(弹出栈顶，如果栈为空则直接返回false)。当处理完所有的字符串后，还有多余的左括号需要处理，则比对左括号的位置和星号的位置(如有，如果没有星号则返回false)，如...

Posted by Jeza Chen on April 10, 2024

LeetCode每日一题(20240410) - 修改后的最大二进制字符串

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

比较偏脑筋急转弯的题目，类似于冒泡排序。分析可以得到，题目的两个操作只能将0往前面挪，不能往后面移动，且两个以上的连续0可以最终合并成一个0(在最后一个连续0的位置上)。因此，可以有以下做法：将所有的0都逐步冒泡集合到第一个0的后面, 然后再全部合并至只剩下一个0。而第一个0就没必要往前移动了，这样结果会更小(最后剩下的0的位置会往前了)。 class Solution: de...

Posted by Jeza Chen on April 10, 2024

LeetCode 677 - 键值映射

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

Trie的经典题目，需要在Trie节点维护一个用于存储该前缀和的变量prefixSum，然后搜索的时候遍历到指定前缀的最后一个节点时，返回该变量即可。需要注意的是，该题目允许insert已存在的单词，且会覆盖原来的val，因此，上述情况还需要更新所有前缀的prefixSum。为解决上述问题，还需要在Trie节点上新增一个变量finishedVal以存储以该节点结尾的单词val(如果该变量...

Posted by Jeza Chen on April 9, 2024

LeetCode 676 - 实现一个魔法字典

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

该题目有两种做法：第一种使用一个字典维护下单词长度 -> 单词列表信息，搜索的时候取相同长度的单词列表，依次比对是否存在差一个字母的单词；第二种则是Trie树的经典做法，使用Trie维护所有的单词信息，然后搜索的时候使用DFS递归，如果当前字母没有相应的节点可以递归，则使用一个布尔变量modified标记该搜索发生了一次字母变更，并改为向兄弟节点继续遍历。如果第二次遇到没有可递归的...

Posted by Jeza Chen on April 9, 2024

LeetCode每日一题(20240409) - 正整数和负整数的最大计数

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

二分搜索的简单题目，先实现一个二分搜索函数maximumCount以计算大于等于指定值target的最小值索引，然后负整数的数目为maximumCount(0)(比0小的数量)，正整数的数目为n - maximumCount(1)(大于等于1的数量)。 import math class Solution: def maximumCount(self, nums: List[...

Posted by Jeza Chen on April 9, 2024

LeetCode每日一题(20240406) - 树节点的第K个祖先

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

倍增思想的经典题目，可以使用ST表存储每个节点跳2^i步的祖先节点信息，然后查询的时候像快速幂那样快速地跳到第k个祖先节点即可。 import math class TreeAncestor: def __init__(self, n: int, parent: List[int]): self._l = math.ceil(math.log2(n)) ...

Posted by Jeza Chen on April 6, 2024

LeetCode每日一题(20240405) - 节点与其祖先之间的最大差值

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

可以使用层次遍历 + 维护根节点至当前节点路径的最大/最小值，然后每次遍历的时候都更新下最优解（选用当前最优解 or 当前路径的最大值 - 最小值）。 # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # ...

Posted by Jeza Chen on April 5, 2024

LeetCode每日一题(20240404) - 有向无环图中一个节点的所有祖先

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

思路比较直观，就是利用拓扑排序的想法，每次寻找入度为0的节点，然后更新子节点的祖先数据和入度即可，直至所有的节点都遍历完毕(因为没有环，最终所有的节点都会入度为0)。寻找入度为0的节点的过程可以利用队列优化下，使用队列维护当前入度为0的节点，当处理子节点的时候若子节点的入度也变为0了，则将该子节点推入队列即可。 from collections import deque clas...

Posted by Jeza Chen on April 4, 2024

解决文件资源管理器中鼠标频繁转圈的问题

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

今天入职装环境的时候发现文件管理器中鼠标疯狂转圈（加载），打开文件夹和右键的反应都比较卡顿，最后发现是安装了Windows Terminal的问题，卸载了就好了~自己建个目录手动安装就可以。

Posted by Jeza Chen on January 30, 2023

LeetCode 684 - 冗余连接

LeetCode 678 - 有效的括号字符串

LeetCode每日一题(20240410) - 修改后的最大二进制字符串

LeetCode 677 - 键值映射

LeetCode 676 - 实现一个魔法字典

LeetCode每日一题(20240409) - 正整数和负整数的最大计数

LeetCode每日一题(20240406) - 树节点的第K个祖先

LeetCode每日一题(20240405) - 节点与其祖先之间的最大差值

LeetCode每日一题(20240404) - 有向无环图中一个节点的所有祖先

解决文件资源管理器中鼠标频繁转圈的问题

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04