刷题记录- 202512

已做题目

sorting

quick sort/ quick selection

Find TopK largest- QuickSelect快速选择 method

思路： divide and conquer. 每次找到start, end-1 范围内array[end]适合插入的位置，该位置左边是大于array[end]的所以元素，右边是所有小于array[end]的元素

searching

154. 寻找旋转排序数组中的最小值 II - 力扣（LeetCode）力扣 LeetCode

思路: 旋转数组考虑2点： arr[left]和arr[right]大小关系和arr[mid]与arr[left]之间关系，怎么在非递增矩阵情况下right边界一直默认左移且默认在最小的结果位置上而不会死循环。

二分查找-II_牛客题霸_牛客网www.nowcoder.com

思路：移动边界时，+1， -1是为了避免死循环，不+/-1是为了保留数值

class Solution:
    def search(self , nums: List[int], target: int) -> int:
        if not nums:
            return -1
        # write code here
        l, r = 0, len(nums)
        while l<r:
            mid = (l+r)//2
            if nums[mid] <target:
                # +1是确保在 r= l+1时 不会mid=l 导致死循环
                l = mid+1
            elif nums[mid] > target:
                # -1 是确保在 r= l+1时 不会mid=r 导致死循环
                r = mid-1
            else:
                #确保找到target后，l和r至少有一个是包含target
                r = mid
        if l< len(nums) and nums[l]==target:
            return l
        if r >=0 and nums[r] == target:
            return r
        return -1

LinkedList

24. 两两交换链表中的节点 - 力扣（LeetCode）力扣 LeetCode

思路： fast slow pointer，对 slow.next节点开始, fast 节点结尾的group进行反转

25. K 个一组翻转链表 - 力扣（LeetCode）力扣 LeetCode

heap/Array/Stack

23. 合并 K 个升序链表 - 力扣（LeetCode）力扣 LeetCode

思路: min-heap, 时间复杂度nlogk

滑动窗口的最大值_牛客题霸_牛客网www.nowcoder.com

滑动窗口+ 单调队列（单调递减队列存放window里第1，2，3.。k大值）

LCR 039. 柱状图中最大的矩形 - 力扣（LeetCode）力扣 LeetCode

思路：单调栈存储， left[i] = 从左往右数比heights[i] 小的最大数 right[i]同理

Set

3. 无重复字符的最长子串 - 力扣（LeetCode）力扣 LeetCode

思路: sliding window + set

DFS

permutation 排列

47. 全排列 II - 力扣（LeetCode）力扣 LeetCode

46. 全排列 - 力扣（LeetCode）力扣 LeetCode

思路： dfs + 排序去重逻辑
- 要先把选项排序，然后在dfs的递归里的for循环中对比 opt[i-1], opt[i]把已经选择过的元素skip掉

combination

40. 组合总和 II - 力扣（LeetCode）力扣 LeetCode

思路: 类似凑硬币问题，有2个问题先要解决
- 选项数字可能重复，需要先通过字典进行去重和次数存储
  - dfs recursion里面的for循环是当前选项数字的使用次数。(排序问题里面的for循环是当前位置选择用哪个数字)
- terminal state 递归层数最大是去重后的选项数或者和为target的组合数字的层数。有2个条件。

216. 组合总和 III - 力扣（LeetCode）力扣 LeetCode

思路：组合问题，不是排列问题， recursion 里只有2个child/ 选和不选。重点是终止条件的先后
备注：细节问题，注意传参被传错

Palidrome回文数

131. 分割回文串 - 力扣（LeetCode）力扣 LeetCode

思路: 分割回文数得到所有回文数组合，和 全排列逻辑类似，区别只在
- for循环里面从选择数字变成选择边界数字(分割的最后一个数字)
- for循环里面，进入下一层递归时，从起始位置pos +1变成终止位置i+1 来跳过中间的分割选项
- 加入dp存储回文数状态，dp[i][j] 取决于dp[i+1][j-1] 和s[i]==s[j]
回文数判断方法:
- 分奇数偶数长度情况判断corner case，然后从外到内或内到外延申判断

BFS

岛屿数量_牛客题霸_牛客网www.nowcoder.com

思路： bfs，遍历整个matrix，每次找到element=1 就bfs queue。注意：queue append要是当前位置的上下左右4个方向，而不是右下，因为queue append的方向并不是往右下角遍历

Tree

树遍历

LCR 050. 路径总和 III - 力扣（LeetCode）力扣 LeetCode

思路： 前缀和 + 树遍历，可以参考和为target的子数组题目，只是变成树结构遍历而已

在二叉树中找到两个节点的最近公共祖先_牛客题霸_牛客网www.nowcoder.com

注意：o1, o2不能是ancester
代码

class Solution:
    def helper(self, root, o1, o2):
        if not root:
            return -1

        l = self.helper(root.left, o1, o2)
        r = self.helper(root.right, o1, o2)
        if (l and r ) or (root.val in [o1, o2] and (l or r)):
            self.ancester = root.val
            
        if root.val in [o1,o2] or l or r:
            return 1
        return -1

    def helper2(self, root, o1, o2):
        if not root:
            return None
        if root.val in [o1, o2]:
            return root
        t1 = self.helper2(root.left, o1,o2)
        t2 = self.helper2(root.right, o1,o2)
        if not t1:
            return t2
        if not t2:
            return t1
        return root


    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        # self.ancester = -1
        # self.helper(root, o1,o2)
        # return self.ancester
        val= self.helper2(root,o1,o2)
        if val:
            return val.val
        return -1

二叉树的镜像_牛客题霸_牛客网www.nowcoder.com

recursion swap 左右节点即可

DP

dp思路技巧回顾
- 问题凡是带 "最xx" 最长最短等等找某个状态的极端值，用dp存储状态 + 贪心算法找极值
- dp存储的状态1个维度是存答案的状态，其他维度是其他中间状态。
  - 比如 ”最长长度“，dp[i][j] 里i存长度， j可以存其他维度状态

1027. 最长等差数列 - 力扣（LeetCode）力扣 LeetCode

思路：二维dp， dp[i][d], i是以第i个数字结尾的等差=d的子序列长度

72. 编辑距离 - 力扣（LeetCode）力扣 LeetCode

思路: 二维dp，dp[i][j] , i, j都是代表字符的位置

300. 最长递增子序列 - 力扣（LeetCode）力扣 LeetCode

思路: dp[i] = 以s[i]结尾的字串的最长递增子序列长度

1278. 分割回文串 III - 力扣（LeetCode）力扣 LeetCode

思路：
- 拆分2个问题
  - 子串变成回文数的编辑次数 cost[i][j]
  - 对字串s[:i] 分割为 j 次的最小次数 dp[i][j]
  - dp[i][j]转移方程: dp[i][j] 变成用 i1 遍历0 ~i 位置里的上一个位置状态dp[i1][j-1] + 最后一次编辑的次数cost[i1][i-1]
- code

// Some code
class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        """
        拆分问题
        1. find palindrome first and use dp[i][j] = cost of modifying s[i:j+1] to palindrome
        2. The find  min cost
        """
        n = len(s)
        cost = [ [0] * len(s)  for _ in range(len(s))]
        # find  palindrome cost
        for gap in range(2, n+1):
            # gap between left, right boundary
            for left in range( n-gap +1):
                right = left + gap -1
                # 从左到右移动，gap从小到大变大
                # cost = 变成回文数的编辑次数
                cost[left][right] = cost[left+1][right-1] + 0 if s[left] == s[right] else 1
        
        dp = [ [10**9] * (k+1) for _ in range(n+1) ]
        dp[0][0] = 0
        # dp[i][j] = 对s[:i+1]切分成j个回文数的次数和 
        # dp[i][j] 依赖上一个相邻字串的总编辑次数 +  新增字串的cost
        for i in range(1, n+1):
            # 字串长度为i
            for j in range(1, min(k, i) +1):
                # 切分成 j个分区，j< k,i
                if j == 1:
                    # 只切分1个分区，就是 s[0: i]字串
                    dp[i][j] = cost[0][i-1]
                else:
                    for i1 in range(j-1, i):
                        # cost[i1][i-1] = 最后一个分区的编辑次数
                        # dp[i1][j-1] 前j-1个分区且末尾字串为i1的字串的编辑次数
                        dp[i][j] = min(dp[i][j] , dp[i1][j-1] + cost[i1][i-1])
        return dp[n][k]