JZX 轻语

LeetCode 713 - 乘积小于K的子数组

使用一个滑动窗口维护当前乘积小于k的最长连续子数组。每当窗口右侧向右扩展一个元素时，结果(有效子数组数量)加上新窗口的长度(即，新增了以窗口当前右侧元素结尾的长度为1,2,…,滑动窗口大小的数组)。当窗口无法向右扩展时，则左侧边界向右移动以减少乘积，直到下一次尝试向右扩展成功。 class Solution: def numSubarrayProductLessThanK(se...

Posted by Jeza Chen on April 18, 2024

LeetCode 712 - 两个字符串的最小ASCII删除和

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

带权重的编辑问题，其中删除一个字符的成本为字符的ASCII值。令dp[i][j]为子串s1[:i]和s2[:j]的最小编辑距离：如果s1[i - 1]等于s2[j - 1]，则dp[i][j] = dp[i - 1][j - 1](两字符串该字符无需修改)，否则dp[i][j] = min(dp[i][j - 1] + ord(s2[j - 1]), dp[i - 1][j] + ord(s...

Posted by Jeza Chen on April 18, 2024

LeetCode 2007 - 从双倍数组中还原数组

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

数组题，朴素的想法是遍历数组，对于数字i寻找是否有i // 2或者i * 2，但这样子如果都存在上述两种可能，则无法确定用哪个（如果用i // 2，则可能会存在i // 2 // 2找不到匹配的情况，而这个数是用来匹配i * 2的）。因此，需要使用贪心的办法，从小到大寻找双倍匹配，如果其中有个数无法找到双倍匹配，则直接返回空数组。有两种做法：一种基于哈希表，另一种则基于双指针查找。 ...

Posted by Jeza Chen on April 18, 2024

LeetCode 707 - 设计链表

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

链表数据结构设计题，比较传统的做法是只使用一个变量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 713 - 乘积小于K的子数组

LeetCode 712 - 两个字符串的最小ASCII删除和

LeetCode 2007 - 从双倍数组中还原数组

LeetCode 707 - 设计链表

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

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

LeetCode 695 - 岛屿的最大面积

LeetCode 687 - 最长等值路径

LeetCode 684 - 冗余连接

LeetCode 678 - 有效的括号字符串

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04