JZX 轻语

LeetCode 707 - 设计链表

链表数据结构设计题，比较传统的做法是只使用一个变量head来指向头节点。也可以再多一个变量tail来指向尾节点以加快addAtTail的速度，但每次新增/删除的时候都需要额外处理下tail。仅使用head的版本： from typing import NamedTuple, Optional class LinkNode: def __init__(self, val:...

Posted by Jeza Chen on April 17, 2024

LeetCode 700 & 701 - 二叉搜索树的搜索/插入

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

二叉搜索树(BST)的模板题，均可以使用一个函数递归实现。插入方法是搜索方法的一个扩展情况：如果当前节点为空，则新建一个节点并返回；递归遍历的时候，都需要重新设置下左/右孩子，并返回自身。这是大二数据结构课本的一个做法，不得不说确实挺妙的，很好地体现递归的特点。此外，由于BST的遍历是单方向的，可以很容易地将递归改为循环的方式。类似于链表的遍历，使用一个dummy头节点来保证算法的一致性...

Posted by Jeza Chen on April 17, 2024

LeetCode 671 - 二叉树中第二小的节点

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

有两种做法：一种就是遍历树，不断更新第二小的结果，如果当前节点的值大于当前结果，则剪枝以加快处理；另外一种则是使用同一个函数进行递归处理：如果当前节点为空或为叶节点，则返回-1；否则，递归检查左右子树的结果：如果左孩子的值等于右孩子（同样等于该节点的值），则取左右子树结果中的最小者返回；如果两孩子值不相等，则先遍历最小者的子树，若结果为-1，则直接返回较大的孩子值，否则返回该结果。 ...

Posted by Jeza Chen on April 16, 2024

LeetCode 695 - 岛屿的最大面积

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

DFS往四个方面扩展面积即可，使用一个visited数组来维护已经访问的信息，如果遍历到已经visit的节点则不再统计。 class Solution: moves = [ (-1, 0), (0, -1), (1, 0), (0, 1) ] def maxAreaOfIsland(self, g...

Posted by Jeza Chen on April 15, 2024

LeetCode 687 - 最长等值路径

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

二叉树DFS的典型用法，其中路径可以绕过根节点连接左右子树中的节点。因此，在遍历到某个节点时, 首先分别在左右子树中寻找值等于该节点的、端点为左右孩子的最长路径(即，路径不会绕过左/右孩子去到另一边)，然后拼接起来作为绕过当前节点的最长路径, 并更新最优解；最后，如果当前节点的值等于父节点的值，则返回以该节点作为端点的最长路径形成递归即可(从左右子树中选择一个较长的路径并加上该节点)；否则，...

Posted by Jeza Chen on April 13, 2024

LeetCode 684 - 冗余连接

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

并查集的模板题目，思路类似于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 707 - 设计链表

LeetCode 700 & 701 - 二叉搜索树的搜索/插入

LeetCode 671 - 二叉树中第二小的节点

LeetCode 695 - 岛屿的最大面积

LeetCode 687 - 最长等值路径

LeetCode 684 - 冗余连接

LeetCode 678 - 有效的括号字符串

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

LeetCode 677 - 键值映射

LeetCode 676 - 实现一个魔法字典

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04