JZX 轻语

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

这三天的每日一题都是组合总和的问题：第一天的题目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 713 - 乘积小于K的子数组

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

使用一个滑动窗口维护当前乘积小于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 39 & 216 & 377 - 组合总和相关问题

LeetCode 725 - 分割链表

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

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

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

LeetCode 707 - 设计链表

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

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

LeetCode 695 - 岛屿的最大面积

LeetCode 687 - 最长等值路径

FEATURED TAGS

ABOUT ME

RECOMMENDATIONS

MY REPOS

SSEPy

Searchable Symmetric Encryption

PyQtInspect

MendeleyDesktop For Ubuntu 22.04