首页 技能工具

Leetcode 刷题记录

# Leetcode 刷题

# 数组 / 字符串

# 1071. 字符串的最大公因子

对于字符串 s 和 t ，只有在 s = t + t + t + ... + t + t （ t 自身连接 1 次或多次）时，我们才认定 “ t 能除尽 s ”。

给定两个字符串 str1 和 str2 。返回 最长字符串 x ，要求满足 x 能除尽 str1 且 x 能除尽 str2 。

若两个字符串是由同一个字符串 X 重复拼接而成，那么无论先拼哪个，结果应该相同。
如果 str1 + str2 != str2 +str1，说明不存在公共的重复因子，直接返回空串 ""。
如果两个字符串都是由同一个字符串 X 组成，那么 X 的长度必然是 str1.size () 和 str2.size () 的最大公约数。

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if not str1 + str2 == str2 + str1:
            return ""
        return str1[0:self.gcd(len(str1), len(str2))]
    
    def gcd(self, a,b):
        if b == 0: return a
        else: return gcd(b, a%b)

作者：Random
链接：https://leetcode.cn/problems/greatest-common-divisor-of-strings/solutions/3749891/shu-xue-zui-da-gong-yue-shu-by-coder-ran-a88u/

# 605. 种花问题

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花， 1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false 。

从左到右遍历数组，能种花就立刻种花。

如何判断能否种花？由于「花不能种植在相邻的地块上」，如果要在下标 i 处种花，需要满足 flowerbed [i−1],flowerbed [i],flowerbed [i+1] 均为 0。

每种一朵花，就把 n 减一。如果最后 n≤0，则返回 true，否则返回 false。

为了简化判断逻辑，可以在数组的开头和末尾各插入一个 0。

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
      nums = len(flowerbed)
      new_flowerbed = [0] + flowerbed + [0]
      for i in range(1,len(new_flowerbed)-1):
        if new_flowerbed[i-1] == 0 and new_flowerbed[i+1] == 0 and new_flowerbed[i] == 0:
          new_flowerbed[i] = 1
          n -= 1
      return n <= 0

作者：灵茶山艾府
链接：https://leetcode.cn/problems/can-place-flowers/solutions/2463018/ben-ti-zui-jian-dan-xie-fa-pythonjavacgo-6a6k/

# 334. 递增的三元子序列

给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。

如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。

核心想法：遍历一遍数组，希望遍历到的这个数 three，前面已经有一个比他小的数 two，再前面有一个比 two 小的数 one。
我们需要维护两个变量：one 和 two。代表递增子序列的第一个数和第二个数。
假设我们已经有了这两个数，那么 three 的大小有以下三种情况：

  1. three 大于 two 此情况下：即找到了三元组，直接返回 true。

  2. three 介于 two 和 one 之间 此情况下：应更新 two，赋值为这个更小的值。这相当于帮我们扩大了 three 的可选择范围，当再次遇到一个比更新过的 two 大的数即可找到。

  3. three 小于 one 此情况下：应更新 one，赋值为这个更小的值。而不需要动 two。这相当于帮我们扩大了之后出现的 two 的可选择范围。进而扩大了之后出现的 three 的可选择范围。

需要注意的是，我们只更新 one，原先的 two 不需要更改，因为子序列是从前往后的，只有当之后再出现比 two 小的数的时候再按照第二步那样更改。

假设有如下示例：[2,5,1,6]，在遇到 1 之后更新了 one，后遇到 6，因为先判断是否大于 two，由于 6 大于 5，就直接返回 true 了。

注意：two 附带隐含信息 —— 这之前有个数比 two 小
所以此时找到的递增子序列不是 one、two、three 的 1 5 6，而是 old one、two、three 的 2 5 6。

这里更新的 one 的意思是，为之后可能存在的更小的递增子序列打基础。
假设有如下示例：[2,5,1,2,6]，在遇到 1 之后更新了 one，后遇到 2，2 介于 1 和 5（two）之间，更新 two 为 2，后遇到 6，由于 6 大于 2，返回 true。
此时找到的递增子序列才是 one、two、three 的 1 2 6

最后考虑 one、two 的初值，容易想到设定为 Integer.MAX_VALUE 即可。

作者：Xzz
链接：https://leetcode.cn/problems/increasing-triplet-subsequence/solutions/535725/pou-xi-ben-zhi-yi-wen-bang-ni-kan-qing-t-3ye2/

class Solution:
    def increasingTriplet(self, nums: List[int]) -> bool:
      one, two = inf, inf
      for three in nums:
        if three > two : return True
        elif three <= one: one = three
        else: two = three
      return False
解析（GPT）

1. 递增三元组的性质

假设数组中存在递增三元组 a < b < c ，它们的顺序在数组中是 前后顺序，我们只关心：

  • 第一个数最小
  • 第二个数比第一个数大
  • 第三个数比第二个数大

关键点：我们不需要知道三元组具体位置，只需要保证存在。

2. one 和 two 的作用

  • one ：当前找到的最小的候选第一个数
  • two ：在 one 之后，找到的最小的候选第二个数

核心思想：

  • 我们并不是在找数组中所有可能的三元组，而是在维护最优候选序列。
  • “最优候选” 意味着 尽可能小的 one 和 two，这样可以最大化出现第三个数 three 的机会。

换句话说：

  1. 遍历到一个数 three：
    • 如果 three > two → 说明找到了一个合法三元组（不管前面 one/two 是不是更新过的，都会形成合法的递增序列）。
  2. 如果 three <= one → 更新 one
    • 因为这个更小的 one 可以为之后出现的 two 提供更多可能。
  3. 否则 → 更新 two
    • 因为这个更小的 two 可以为之后出现的 three 提供更多可能。

3. 为什么不会漏掉任何情况

假设数组中有递增三元组 x < y < z ，为什么算法一定能找到它？

  • 当我们遍历到 x：
    • one 会被更新为 ≤ x
  • 当我们遍历到 y：
    • two 会被更新为 ≤ y
  • 当我们遍历到 z：
    • 如果 z > two → 返回 True

关键点：

  • 即使 one/two 被后面更小的数更新过，old one/two 仍然保留了前序信息，保证当前 three 大于某个二元组时，必然能形成递增三元组。
  • 换句话说，one/two 是动态维护的 最小可能序列候选，任何真正存在的递增三元组都会被捕获。

常规解法

# 56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

重要定理：能够合并的区间都必然是连续的。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        result = []
        for interval in intervals:
            if not result or interval[0] > result[-1][-1]:
                result.append(interval)
            else:
                result[-1][-1] = max(result[-1][-1], interval[-1])
        return result

作者：力扣官方题解
链接：https://leetcode.cn/problems/merge-intervals/solutions/203562/he-bing-qu-jian-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 189. 轮转数组

给定一个整数数组 nums ，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

这里假设 0≤k<n，对于 k≥n 的情况，可以转换成 0≤k<n 的情况（证明见后文）。

设 nums=A+B，其中 A 是 nums 的前 n−k 个数，B 是后 k 个数。在上例中，A=[1,2,3,4]，B=[5,6,7]。

题目要求把 A+B 变成 B+A，这可以用三次反转实现：

把 nums=A+B 反转，我们得到了 rev (B)+rev (A)，其中 rev (A) 表示数组 A 反转后的结果。在上例中，rev (B)+rev (A)=[7,6,5]+[4,3,2,1]。
单独反转 rev (B)，因为一个数组反转两次是不变的，所以 rev (rev (B))=B，我们得到了 B。
单独反转 rev (A)，得到 rev (rev (A))=A。
现在数组变成 B+A。在上例中，B+A=[5,6,7]+[1,2,3,4]，这正是我们想要的结果。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(l,r):
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1
        n = len(nums)
        k = k % n
        reverse(0,n-1)
        reverse(0,k-1)
        reverse(k,n-1)
        return

作者：灵茶山艾府
链接：https://leetcode.cn/problems/rotate-array/solutions/2784427/tu-jie-yuan-di-zuo-fa-yi-tu-miao-dong-py-ryfv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例

示例 1：

输入：nums = [1,2,0]
输出：3
解释：范围 [1,2] 中的数字都在数组中。

示例 2：

输入：nums = [3,4,-1,1]
输出：2
解释：1 在数组中，但 2 没有。

示例 3：

输入：nums = [7,8,9,11,12]
输出：1
解释：最小的正数 1 没有出现。

由于我们只在意 [1,N] 中的数，因此我们可以先对数组进行遍历，把不在 [1,N] 范围内的数修改成任意一个大于 N 的数（例如 N+1）。这样一来，数组中的所有数就都是正数了，因此我们就可以将「标记」表示为「负号」。算法的流程如下：

我们将数组中所有小于等于 0 的数修改为 N+1；

我们遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣，其中 ∣∣ 为绝对值符号。如果 ∣x∣∈[1,N]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号。注意如果它已经有负号，不需要重复添加；

在遍历完成之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            if nums[i] <= 0:
                nums[i] = n+1
        for i in range(n):
            num = abs(nums[i])
            if num <= n:
                nums[num-1] = -abs(nums[num-1])
        for i in range(n):
            if nums[i] > 0:
                return i+1
        return n+1

作者：力扣官方题解
链接：https://leetcode.cn/problems/first-missing-positive/solutions/304743/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例

示例 1：

** 输入：**nums = [1,1,1,2,2,3], k = 2

输出：[1,2]

示例 2：

** 输入：**nums = [1], k = 1

输出：[1]

示例 3：

** 输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2

输出：[1,2]

答案与元素的出现次数有关，我们首先用一个哈希表 cnt 统计每个元素的出现次数。哈希表的 key 是元素值，value 是 key 在数组中的出现次数。

此时问题变成：返回一个列表，包含前 k 大的出现次数对应的元素值。

设出现次数最大值为 maxCnt，由于 maxCnt≤n，我们可以用桶排序，把出现次数相同的元素，放到同一个桶中。

创建一个大小为 maxCnt+1 的列表 buckets，其中 buckets [c] 存储出现次数为 c 的元素。（每个 buckets [c] 都是一个列表）

遍历 cnt，把出现次数为 c 的元素 x 添加到 buckets [c] 中。

倒序遍历 buckets，把 buckets [c] 中的元素加到答案中。一旦答案的长度等于 k，就立刻返回答案。

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        max_cnt = max(cnt.values())
        pocket = [[] for _ in range(max_cnt+1)]
        for i in cnt.keys():
            pocket[cnt[i]].append(i)
        result = []
        print(pocket)
        for i in range(max_cnt,-1,-1):
            print(result,len(result),k)
            if len(result) == k:return result
            result+=pocket[i]
作者：灵茶山艾府
链接：https://leetcode.cn/problems/top-k-frequent-elements/solutions/3655287/tong-pai-xu-on-xian-xing-zuo-fa-pythonja-oqq2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
:::
# 矩阵
# 54. 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        visited = [[0]*n for _ in range(m)]
        count = m*n
        directions = [[0,1],[1,0],[0,-1],[-1,0]]
        x, y = 0, 0
        mode = 0
        result = []
        for i in range(count):
            visited[x][y] = 1
            result.append(matrix[x][y])
            mode = mode % 4
            if 0 <= x + directions[mode][0] < m and 0 <= y + directions[mode][1] < n and visited[x + directions[mode][0]][y + directions[mode][1]]==0:
                x += directions[mode][0]
                y += directions[mode][1]
                # print(visited)
            else:
                mode = (mode + 1)%4
                x += directions[mode][0]
                y += directions[mode][1]
        return result
# 48. 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
示例
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

先沿对角线翻转，后沿中轴线翻转。
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        m = len(matrix)
        for i in range(m):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for i in range(m):
            for j in range(m//2):
                matrix[i][j], matrix[i][m-1-j] = matrix[i][m-1-j], matrix[i][j]
        return
# 240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
分离出每行，在每行内执行二分查找。
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        def bi_sect(rows, left, right):
            while left <= right:
                mid = (left + right) // 2
                if target == rows[mid]: return True
                elif target > rows[mid]: left = mid+1
                else:right = mid-1
            return False
        n = len(matrix)
        for i in range(n):
            if bi_sect(matrix[i],0,len(matrix[i])-1):return True
        return False
# 滑动窗口
# 1208. 尽可能使字符串相等
给你两个长度相同的字符串， s 和 t 。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost 。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0 。
示例
示例 1：
输入：s = "abcd", t = "bcdf", maxCost = 3
输出：3
解释：s 中的 "abc" 可以变为 "bcd"。开销为 3，所以最大长度为 3。

示例 2：
输入：s = "abcd", t = "cdef", maxCost = 3
输出：1
解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。

示例 3：
输入：s = "abcd", t = "acde", maxCost = 0
输出：1
解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。

两个长度相等字符串的 s 和 t ，把 i 位置的 s [i] 转成 t [i] 的开销是两者 ASCII 码之差的绝对值。题目给出了允许的最大预算 maxCost ，求不超过预算的情况下能够转换的最长子串。
比如，对于 s = "abcd", t = "bcdf", cost = 3 而言，我们使用 costs [i] 表示从 s [i] 转成 t [i] 的开销，那么 costs = [1, 1, 1, 2] 。由于 maxCost = 3， 所以最多允许其前面三个字符进行转换。
于是题目变成了：已知一个数组 costs ，求：和不超过 maxCost 时最长的子数组的长度。
class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        left, right = 0, 0
        result = 0
        cost = 0
        while right < n:
            cost += abs(ord(s[right]) - ord(t[right]))
            while cost > maxCost:
                cost -= abs(ord(s[left]) - ord(t[left]))
                left += 1
                
            result = max(result, right - left + 1)
            right += 1
        return result
《挑战程序设计竞赛》这本书中把滑动窗口叫做「虫取法」，我觉得非常生动形象。因为滑动窗口的两个指针移动的过程和虫子爬动的过程非常像：前脚不动，把后脚移动过来；后脚不动，把前脚向前移动。
滑动窗口问题模板
我分享一个滑动窗口的模板，能解决大多数的滑动窗口问题（1004. 最大连续 1 的个数 III，424. 替换后的最长重复字符）：
def findSubArray(nums):
    N = len(nums) # 数组 / 字符串长度
    left, right = 0, 0 # 双指针，表示当前遍历的区间 [left, right]，闭区间
    sums = 0 # 用于统计 子数组 / 子区间 是否有效，根据题目可能会改成求和 / 计数
    res = 0 # 保存最大的满足题目要求的 子数组 / 子串 长度
    while right < N: # 当右边的指针没有搜索到 数组 / 字符串 的结尾
        sums += nums[right] # 增加当前右边指针的数字 / 字符的求和 / 计数
        while 区间[left, right]不符合题意：# 此时需要一直移动左指针，直至找到一个符合题意的区间
            sums -= nums[left] # 移动左指针前需要从 counter 中减少 left 位置字符的求和 / 计数
            left += 1 # 真正的移动左指针，注意不能跟上面一行代码写反
        # 到 while 结束时，我们找到了一个符合题意要求的 子数组 / 子串
        res = max(res, right - left + 1) # 需要更新结果
        right += 1 # 移动右指针，去探索新的区间
    return res
滑动窗口中用到了左右两个指针，它们移动的思路是：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。
模板的整体思想是：
定义两个指针 left 和 right 分别指向区间的开头和结尾，注意是闭区间；定义 sums 用来统计该区间内的各个字符出现次数；
第一重 while 循环是为了判断 right 指针的位置是否超出了数组边界；当 right 每次到了新位置，需要增加 right 指针的求和 / 计数；
第二重 while 循环是让 left 指针向右移动到 [left, right] 区间符合题意的位置；当 left 每次移动到了新位置，需要减少 left 指针的求和 / 计数；
在第二重 while 循环之后，成功找到了一个符合题意的 [left, right] 区间，题目要求最大的区间长度，因此更新 res 为 max (res, 当前区间的长度) 。
right 指针每次向右移动一步，开始探索新的区间。
模板中的 sums 需要根据题目意思具体去修改，本题是求和题目因此把 sums 定义成整数用于求和；如果是计数题目，就需要改成字典用于计数。当左右指针发生变化的时候，都需要更新 sums 。
另外一个需要根据题目去修改的是内层 while 循环的判断条件，即： 区间 [left, right] 不符合题意 。对于本题而言，就是该区内的和 sums 超过了 maxCost 。
作者：负雪明烛
链接：https://leetcode.cn/problems/get-equal-substrings-within-budget/solutions/592354/fen-xiang-zhen-cang-de-hua-dong-chuang-k-e3rd/
# 424. 替换后的最长重复字符
给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符，并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。
在执行上述操作后，返回 包含相同字母的最长子字符串的长度。
示例
示例 1：
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。
可能存在其他的方法来得到同样的结果。

本题解根据常规的滑动窗口思路进行解题，不需要任何的技巧。
滑动窗口法是指通过 Left 以及 Right 指针来框定一个窗口，当在窗口内的字符串满足题目要求则记录下当前窗口长度并进一步扩张寻找更长的窗口，若不满足则进行窗口平移。
题目中给定的 K 值是让我们在选定有效窗口时的要求放宽了：
当 K=0 时，要求滑动窗口内部的所有字母都必须相同；
而当 K>0 时，要求滑动窗口内最多替换 K 次使得所有字母都必须相同。这里有一个关键点，即我们将当前滑动窗口内出现次数最多的字母作为基准字母（Benchmark），那么其他不一样的字母 (Others) 都选择替换操作即可以最小的代价转换为全部相同的字母。
因此，我们首先通过一个数组 (count) 记录所有字母在当前窗口出现的次数，通过 Max 函数选择窗口内的基准字母，然后其他字母出现的次数为 Sum (count)-Max (count)，通过与 K 进行比较，即可知道当前窗口是否有效，下一步是继续扩张还是位移。
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = [0 for _ in range(26)]  #记录当前窗口的字母出现次数
        
        left = 0    #滑动窗口左边界
        right = 0   #滑动窗口右边界
        retval = 0  #最长窗口长度
        
        while right < len(s):
            count[ord(s[right])-ord('A')] += 1  
            benchmark = max(count)              #选择出现次数最多的字母为基准 
            others = sum(count) - benchmark     #则其他字母需要通过替换操作来变为基准
            if others <= k:                     #通过与 K 进行比较来判断窗口是进行扩张？
                right += 1
                retval = max(retval, right-left)#记录当前有效窗口长度
            else:                               #通过与 K 进行比较来判断窗口还是进行位移？
                count[ord(s[left])-ord('A')] -= 1
                left += 1
                right += 1                      #这里注意：位移操作需要整个向右移，不仅仅只是 left 向右
        
        return retval                           #返回最长窗口长度
作者：Derrick.S
链接：https://leetcode.cn/problems/longest-repeating-character-replacement/solutions/799013/hua-dong-chuang-kou-fa-jian-dan-yi-dong-3qwel/
# 239. 滑动窗口最大值
给你一个整数数组 nums ，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：
输入：nums = [1], k = 1
输出：[1]

回忆 最小栈 ，其使用 单调栈 实现了随意入栈、出栈情况下的 O (1) 时间获取 “栈内最小值” 。本题同理，不同点在于 “出栈操作” 删除的是 “列表尾部元素” ，而 “窗口滑动” 删除的是 “列表首部元素” 。
窗口对应的数据结构为 双端队列 ，本题使用 单调队列 即可解决以上问题。遍历数组时，每轮保证单调队列 deque ：
  1. deque 内 仅包含窗口内的元素 ⇒ 每轮窗口滑动移除了元素 nums [i−1] ，需将 deque 内的对应元素一起删除。
  2. deque 内的元素 非严格递减 ⇒ 每轮窗口滑动添加了元素 nums [j+1] ，需将 deque 内所有 <nums [j+1] 的元素删除。
算法流程：
  1. 初始化： 双端队列 deque ，结果列表 res ，数组长度 n ；
  2. 滑动窗口： 左边界范围 i∈[1−k,n−k] ，右边界范围 j∈[0,n−1]
    • 若 i>0 且 队首元素 deque [0] = 被删除元素 nums [i−1] ：则队首元素出队；
    • 删除 deque 内所有 <nums [j] 的元素，以保持 deque 递减；
    • 将 nums [j] 添加至 deque 尾部；
    • 若已形成窗口（即 i≥0 ）：将窗口最大值（即队首元素 deque [0] ）添加至列表 res ；
  3. 返回值： 返回结果列表 res ；
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # if n < k:return []
        # elif n == k :return [max(nums)]
        deque = []
        result = []
        for right in range(n):
            left = right - k + 1
            if left > 0 and deque[0] == nums[left-1]:
                deque.pop(0)
            while deque and deque[-1] < nums[right]:
                deque.pop(-1)
            deque.append(nums[right])
            if left >= 0:
                result.append(deque[0])
        return result
作者：Krahets
链接：https://leetcode.cn/problems/sliding-window-maximum/solutions/2361228/239-hua-dong-chuang-kou-zui-da-zhi-dan-d-u6h0/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

  1. 初始化 ansLeft=−1, ansRight=m，用来记录最短子串的左右端点，其中 m 是 s 的长度。
  2. 用一个哈希表（或者数组）cntT 统计 t 中每个字母的出现次数。
  3. 初始化 left=0，以及一个空哈希表（或者数组）cntS，用来统计 s 子串中每个字母的出现次数。
  4. 初始化 less 为 t 中的不同字母个数。
  5. 遍历 s，设当前枚举的子串右端点为 right，把字母 c=s [right] 的出现次数加一。加一后，如果 cntS [c]=cntT [c]，说明 c 的出现次数满足要求，把 less 减一。
  6. 如果 less=0，说明 cntS 中的每个字母及其出现次数都大于等于 cntT 中的字母出现次数，那么：
    • 如果 right−left<ansRight−ansLeft，说明我们找到了更短的子串，更新 ansLeft=left, ansRight=right。
    • 把字母 x=s [left] 的出现次数减一。减一前，如果 cntS [x]=cntT [x]，说明 x 的出现次数不满足要求，把 less 加一。
    • 左端点右移，即 left 加一。
    • 重复上述三步，直到 less>0，即 cntS 有字母的出现次数小于 cntT 中该字母的出现次数为止。
  7. 最后，如果 ansLeft<0，说明没有找到符合要求的子串，返回空字符串，否则返回下标 ansLeft 到下标 ansRight 之间的子串。
代码实现时，可以把 cntS 和 cntT 合并成一个 cnt，定义
cnt[x]=cntT[x]−cntS[x]cnt[x]=cntT[x]−cntS[x]
如果 cnt [x]=0，就意味着窗口内字母 x 的出现次数和 t 的一样多。
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        cnt = collections.defaultdict(int)
        for c in t:
            cnt[c] += 1
        count = len(cnt)
        res_left, res_right = -1, len(s)
        left = 0
        for right, c in enumerate(s):
            cnt[c] -= 1
            if cnt[c] == 0:
                count -= 1
            while count == 0:
                if right-left < res_right-res_left:
                    res_left, res_right = left, right
                if cnt[s[left]] == 0:
                    count += 1
                cnt[s[left]] += 1
                left += 1
        return '' if res_left<0 else s[res_left: res_right+1]
作者：灵茶山艾府
链接：https://leetcode.cn/problems/minimum-window-substring/solutions/2713911/liang-chong-fang-fa-cong-o52mn-dao-omnfu-3ezz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 前缀和
# 724. 寻找数组的中心下标
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例
示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

设 nums 的元素之和为 s。
设中心下标为 i，其左侧元素和为 leftS=nums[0]+nums[1]+⋯+nums[i−1]leftS=nums[0]+nums[1]+⋯+nums[i−1]，那么右侧元素和为 s−nums[i]−leftSs−nums[i]−leftS。
由于左侧元素和等于右侧元素和，所以有
leftS=s−nums[i]−leftSleftS=s−nums[i]−leftS
即
2⋅leftS=s−nums[i]2⋅leftS=s−nums[i]
从左到右遍历数组，一边遍历，一边累加元素更新 leftS。每次累加前，检查是否满足上式，满足则返回 i。
如果不存在这样的 i，返回 −1。
class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        s = sum(nums)
        sum_left = 0
        for i, num in enumerate(nums):
            if 2*sum_left == s - num:
                return i
            sum_left += num
        return -1
作者：灵茶山艾府
链接：https://leetcode.cn/problems/find-pivot-index/solutions/2834687/jian-ji-xie-fa-o1-e-wai-kong-jian-python-tz0p/
# 2352. 相等行列对
给你一个下标从 0 开始、大小为 n x n 的整数矩阵 grid ，返回满足 Ri 行和 Cj 列相等的行列对 (Ri, Cj) 的数目 *。*
如果行和列以相同的顺序包含相同的元素（即相等的数组），则认为二者是相等的。
用哈希表统计每行出现的次数，然后遍历列，累加哈希表中列出现的次数。
作者：灵茶山艾府
链接：https://leetcode.cn/problems/equal-row-and-column-pairs/solutions/1694047/ha-xi-biao-python-liang-xing-by-endlessc-ljae/
class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        cnt = Counter(tuple(row) for row in grid)
        return sum(cnt[col] for col in zip(*grid))
class Solution:
    def equalPairs(self, grid: List[List[int]]) -> int:
        n = len(grid)
        count = {}
        result = 0
        for i in range(n):
            count[tuple(grid[i])] = count.get(tuple(grid[i]), 0) + 1
        print(count)
        for j in zip(*grid):
            print(j)
            result += count.get(j,0)
            # print(grid[:][j], grid[j][:])
        return result
# 560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例
示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

转化
回顾 303 题的前缀和的定义：s [0]=0, s [i]=nums [0]+nums [1]+⋯+nums [i−1]。注意 s 是一个长为 n+1 的数组，第一项一定是 0。
设 i<j，如果 nums [i] 到 nums [j−1] 的元素和等于 k，用前缀和表示，就是
s[j]−s[i]=ks[j]−s[i]=k
问题转化为：
  • s 中有多少对下标 (i,j) 满足 i<j 且 s [j]−s [i]=k？
写成 s [j]+(−s [i])=k 就能看得更明白，这是梦开始的地方 ——1. 两数之和。不过那题只需找到一对下标，而本题需要计算所有满足条件的下标对的个数。
枚举右，维护左
以 nums=[1,1,−1,1,−1]，k=1 为例，其前缀和数组为 s=[0,1,2,1,2,1]。
如果用二重循环暴力枚举有多少个 s [j]−s [i]=k，时间复杂度是 O (n2n^2)，太慢了。如何加速？
从两数之和中，我们可以学到什么？我们可以把 s [j]−s [i]=k 移项，得
s[i]=s[j]−ks[i]=s[j]−k
遍历 s，一边枚举右边的 j，一边用哈希表统计左边有多少个 i 满足 i<j 且 s [i]=s [j]−k。
比如 s [j]=2，那么 s [i]=s [j]−k=2−1=1，我们要找的是 j 左边有多少个 s [i]=1。在上面的例子中，遍历到 s [4]=2 时，我们知道左边有 2 个 s [i]=1，所以新找到了 2 个和为 1 的子数组。
def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        sums = 0
        ht = collections.defaultdict(int)
        ht[0] = 1
        result = 0
        for i in range(n):
            sums += nums[i]
            cnt = sums - k
            result += ht[cnt]
            ht[sums] += 1 
        return result
作者：灵茶山艾府
链接：https://leetcode.cn/problems/subarray-sum-equals-k/solutions/2781031/qian-zhui-he-ha-xi-biao-cong-liang-ci-bi-4mwr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 栈与队列
# 735. 小行星碰撞
给定一个整数数组 asteroids ，表示在同一行的小行星。数组中小行星的索引表示它们在空间中的相对位置。
对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。
找出碰撞后剩下的所有小行星。碰撞规则：两个小行星相互碰撞，较小的小行星会爆炸。如果两颗小行星大小相同，则两颗小行星都会爆炸。两颗移动方向相同的小行星，永远不会发生碰撞。
示例
示例 1：
输入：asteroids = [5,10,-5]
输出：[5,10]
解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

示例 2：
输入：asteroids = [8,-8]
输出：[]
解释：8 和 -8 碰撞后，两者都发生爆炸。

示例 3：
输入：asteroids = [10,2,-5]
输出：[10]
解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。

这道栈的题目难点应该主要是在分析场景上了。
我们需要明确什么时候无脑入栈，什么时候需要判断，理解这两点就可以轻松解题了。
首先，循环每一个元素时，在什么情况下无脑入栈呢？
栈为空
栈顶元素为负数 (下一个为负数则一起向左，下一个为正数则分向两边)
当前元素为正数（栈顶为正一起向右，栈顶为负分向两边）
下来，我们需要看碰撞的场景又细分为什么情况：
栈顶元素大于 abs (当前元素)，当前元素被撞毁
栈顶元素等于 abs (当前元素)，栈顶弹出和当前元素抵消
栈顶元素小于 abs (当前元素)，栈顶弹出，并与新栈顶完成上述判断
最终返回栈即可。
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        stack, index = [], 0
        while index < len(asteroids):
            ast = asteroids[index]
            if ast > 0 or len(stack)==0 or stack[-1]<0: stack.append(ast)
            elif stack[-1] <= - ast:
                if stack.pop(-1) < - ast:
                    continue
            index += 1
        return stack
作者：清风 Python
链接：https://leetcode.cn/problems/asteroid-collision/solutions/994100/735xing-xing-peng-zhuang-ji-yu-zhan-qu-f-xpd1/
# 394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string] ，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
测试用例保证输出的长度不会超过 105 。
示例
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"

示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"

示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

  • 本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。
  • 算法流程：
    • 构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
      • 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
      • 当 c 为字母时，在 res 尾部添加 c；
      • 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 0：
        记录此 [前的临时结果 res 至栈，用于发现对应] 后的拼接操作；
        记录此 [前的倍数 multi 至栈，用于发现对应] 后，获取 multi × [...] 字符串。
        进入到新 [ 后，res 和 multi 重新记录。
      • 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
        • last_res 是上个 [到当前 [ 的字符串，例如 "3 [a2 [c]]" 中的 a；
        • cur_multi 是当前 [到] 内字符串的重复倍数，例如 "3 [a2 [c]]" 中的 2。
    • 返回字符串 res。
class Solution:
    def decodeString(self, s: str) -> str:
        result = ''
        stack = []
        res, num = '', 0
        for c in s:
            if c == '[':
                stack.append((res, num))
                res, num = '', 0
            elif c == ']':
                out_res, out_num = stack.pop()
                res = out_res + out_num*res
            elif '0'<= c <= '9':
                num = num*10 + int(c)
            else:
                res += c
        return res
作者：Krahets
链接：https://leetcode.cn/problems/decode-string/solutions/19447/decode-string-fu-zhu-zhan-fa-di-gui-fa-by-jyd/
# 649. Dota2 参议院
Dota2 的世界里有两个阵营： Radiant （天辉）和 Dire （夜魇）
Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的 一 项：
  • 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失 所有的权利 。
  • 宣布胜利：如果参议员发现有权利投票的参议员都是 同一个阵营的 ，他可以宣布胜利并决定在游戏中的有关变化。
给你一个字符串 senate 代表每个参议员的阵营。字母 'R' 和 'D' 分别代表了 Radiant （天辉）和 Dire （夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n 。
以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。
假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 "Radiant" 或 "Dire" 。
示例
示例 1：
输入：senate = "RD"
输出："Radiant"
解释：
第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。

示例 2：
输入：senate = "RDD"
输出："Dire"
解释：
第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

这道题模拟了一个游戏过程，最终当有权利投票的参议员都是 同一个阵营的 ，这个阵营即获胜。
那么两个阵营的每个参议员为了获胜，当他拥有权力的时候，一定是会将自己之后首个对立阵营的参议员的权力禁止掉。【这就是每一位参议会为自己的政党做出最好的策略】。请注意：当之后没有对立阵营的参议员的时候，相当于将之前的参议员加到其之后。
class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        radiants, dires = [], []
        n = len(senate)
        for i, se in enumerate(senate):
            if se == 'R': radiants.append(i)
            else: dires.append(i)
        while radiants and dires:
            if radiants[0] < dires[0]:
                dires.pop(0)
                radiants.append(radiants.pop(0) + n)
            else:
                radiants.pop(0)
                dires.append(dires.pop(0) + n)
        return "Radiant" if radiants else 'Dire'
作者：画图小匠
链接：https://leetcode.cn/problems/dota2-senate/solutions/2862115/javapython3cdui-lie-mo-ni-jin-zhi-zhi-ho-l4pb/
# 1190. 反转每对括号间的子串
给出一个字符串 s （仅含有小写英文字母和括号）。
请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。
注意，您的结果中 不应 包含任何括号。
示例
示例 1：
输入：s = "(abcd)"
输出："dcba"

示例 2：
输入：s = "(u(love)i)"
输出："iloveu"
解释：先反转子字符串 "love" ，然后反转整个字符串。

示例 3：
输入：s = "(ed(et(oc))el)"
输出："leetcode"
解释：先反转子字符串 "oc" ，接着反转 "etco" ，然后反转整个字符串。

class Solution:
    def reverseParentheses(self, s: str) -> str:
        s_list = []
        for c in s:
            if c == ')':
                temp = []
                while s_list and s_list[-1] != '(':
                    temp.append(s_list.pop(-1))
                s_list.pop(-1)
                s_list.extend(temp)
            else:
                s_list.append(c)
        return ''.join(s_list)
# 排序相关
# 215. 数组中的第 K 个最大元素
给定整数数组 nums 和整数 k ，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

快速选择
快速排序的核心包括 “哨兵划分” 和 “递归” 。
哨兵划分： 以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
递归： 对 左子数组 和 右子数组 递归执行 哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。
下图展示了数组 [2,4,1,0,3,5] 的快速排序流程。
Picture1.png
「快速选择」：设 N 为数组长度。根据快速排序原理，如果某次哨兵划分后，基准数的索引正好是 N−k ，则意味着它就是第 k 大的数字 。此时就可以直接返回它，无需继续递归下去了。
然而，对于包含大量重复元素的数组，每轮的哨兵划分都可能将数组划分为长度为 1 和 n−1 的两个部分，这种情况下快速排序的时间复杂度会退化至 O (N^2)。
一种解决方案是使用「三路划分」，即每轮将数组划分为三个部分：小于、等于和大于基准数的所有元素。这样当发现第 k 大数字处在 “等于基准数” 的子数组中时，便可以直接返回该元素。
为了进一步提升算法的稳健性，我们采用随机选择的方式来选定基准数。
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 快排
        def quick_sort(seq,k):
            pivot = seq[len(seq)//2]
            big, equ, small = [], [], []
            for i in seq:
                if i > pivot: big.append(i)
                elif i == pivot: equ.append(i)
                else: small.append(i)
            if k <= len(big):
                return quick_sort(big, k)
            if k > len(big) + len(equ):
                return quick_sort(small, k-len(big)-len(equ))
            else:
                return pivot
        return quick_sort(nums, k)
作者：Krahets
链接：https://leetcode.cn/problems/kth-largest-element-in-an-array/solutions/2361969/215-shu-zu-zhong-de-di-k-ge-zui-da-yuan-d786p/
# 347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例
示例 1：
** 输入：**nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
** 输入：**nums = [1], k = 1
输出：[1]
示例 3：
** 输入：**nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
第一步
既然答案与元素的出现次数有关，那么先用一个哈希表 cnt 统计每个元素的出现次数。哈希表的 key 是元素值，value 是 key 在数组中的出现次数。
此时问题变成：
返回一个列表，包含前 k 大的出现次数对应的元素值。
第二步
把出现次数相同的元素，放到同一个桶中。同一个桶内的元素出现次数相同，无需对桶内元素排序。
设出现次数的最大值为 maxCnt。创建一个大小为 maxCnt+1 的列表 buckets，其中 buckets [c] 存储出现次数为 c 的元素。（每个 buckets [c] 都是一个列表）
注意 maxCnt≤n，这保证了时间复杂度是 O (n) 的。
遍历 cnt，把出现次数为 c 的元素 x 添加到 buckets [c] 中。
第三步
倒序遍历 buckets，把 buckets [c] 中的元素加到答案中。
一旦答案的长度等于 k，就立刻返回答案。
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = Counter(nums)
        max_cnt = max(cnt.values())
        pockets = [[] for _ in range(max_cnt+1)]
        for i in cnt.keys():
            pockets[cnt[i]].append(i)
        result = []
        for i in range(max_cnt, -1, -1):
            result+=pockets[i]
            if len(result) == k: break
        return result
作者：灵茶山艾府
链接：https://leetcode.cn/problems/top-k-frequent-elements/solutions/3655287/tong-pai-xu-on-xian-xing-zuo-fa-pythonja-oqq2/
# 链表
  1. 找中间节点：快慢指针
  • 中间值左侧：需要加一个 dummy 节点。
    dummy = ListNode(0, head)
    slow, fast = dummy, dummy
    while fast and fast.next:
        fast = fast.next.next
        if not fast: break
        slow = slow.next
  • 中间值右侧：直接从 head 开始
    slow, fast = head, head
    while fast and fast.next:
        fast = fast.next.next
        if not fast: break
        slow = slow.next
# 2095. 删除链表的中间节点
给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
  • 对于 n = 1 、 2 、 3 、 4 和 5 的情况，中间节点的下标分别是 0 、 1 、 1 、 2 和 2 。
本题可遍历计数先得到 n，再遍历一次删除指定节点即可，这很简单。本篇讲的是快慢指针这种方法。
我们令 fast 和 slow 这两个指针同时前进，fast 每次移动两格，slow 每次移动一格，在检测到 fast.next == null 或者 fast.next.next == null 时退出循环。
引入一个哑巴节点 dummy 便于处理，考虑循环停止时的场景。
为方便考虑，本篇题解认为原链表下标从 1 开始，需要删除第 ⌊n2⌋+1⌊\frac{n}{2}⌋+1 个节点。
  • 如果 n 为偶数，如下所示。设 n=2k，fast 停在第 2k 个节点，slow 停在第 k 即 ⌊n2⌋⌊\frac{n}{2}⌋ 个节点。
  • 如果 n 为奇数，如下所示，设 n=2k+1。fast 停在第 2k 个节点，slow 停在第 k 即 ⌊n2⌋⌊\frac{n}{2}⌋ 个节点。
所以退出循环时 slow 一定停在 ⌊n2⌋⌊\frac{n}{2}⌋ 个节点，令 slow.next = slow.next.next 即删除了 ⌊n2⌋+1⌊\frac{n}{2}⌋+1 个节点。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        zero = ListNode(0, head)
        slow, fast = zero, zero
        while fast and fast.next:
            fast = fast.next.next
            if not fast: break
            slow = slow.next
        slow.next = slow.next.next
        return zero.next
作者：Shawxing 精讲算法
链接：https://leetcode.cn/problems/delete-the-middle-node-of-a-linked-list/solutions/2844229/jian-ming-yan-jin-de-kuai-man-zhi-zhen-f-84sx/
# 328. 奇偶链表
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
如果链表为空，则直接返回链表。
对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，合并后的链表即为结果链表。
原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点，head 的后一个节点是偶数链表的头节点。令 evenHead = head.next，则 evenHead 是偶数链表的头节点。
维护两个指针 odd 和 even 分别指向奇数节点和偶数节点，初始时 odd = head，even = evenHead。通过迭代的方式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。
  • 更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点，因此令 odd.next = even.next，然后令 odd = odd.next，此时 odd 变成 even 的后一个节点。
  • 更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点，因此令 even.next = odd.next，然后令 even = even.next，此时 even 变成 odd 的后一个节点。
在上述操作之后，即完成了对一个奇数节点和一个偶数节点的分离。重复上述操作，直到全部节点分离完毕。全部节点分离完毕的条件是 even 为空节点或者 even.next 为空节点，此时 odd 指向最后一个奇数节点（即奇数链表的最后一个节点）。
最后令 odd.next = evenHead，将偶数链表连接在奇数链表之后，即完成了奇数链表和偶数链表的合并，结果链表的头节点仍然是 head。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head: return head
        even_head = head.next
        odd, even = head, even_head
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return head
作者：力扣官方题解
链接：https://leetcode.cn/problems/odd-even-linked-list/solutions/482737/qi-ou-lian-biao-by-leetcode-solution/
# 2130. 链表最大孪生和
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
  • 比方说， n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
示例
示例 1：
输入：head = [5,4,2,1]
输出：6
解释：
节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。
链表中没有其他孪生节点。
所以，链表的最大孪生和是 6 。

示例 2：
输入：head = [4,2,2,3]
输出：7
解释：
链表中的孪生节点为：
- 节点 0 是节点 3 的孪生节点，孪生和为 4 + 3 = 7 。
- 节点 1 是节点 2 的孪生节点，孪生和为 2 + 2 = 4 。
所以，最大孪生和为 max(7, 4) = 7 。

核心思想：寻找链表中间值
以下两种方法的快慢指针有所不同，参见链表。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        mid = self.middleNode(head)
        head2 = self.reverseNode(mid)
        result = -inf
        while head2:
            result = max(result, head.val + head2.val)
            head = head.next
            head2 = head2.next
        return result
    def reverseNode(self, head):
        cur, pre = head, None
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
        return pre
        
    def middleNode(self, head):
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        return slow
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        dummy = ListNode(next=head)
        slow, fast = dummy, dummy
        stack = []
        result = -inf
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            stack.append(slow.val)
        print(slow.val)
        while slow.next:
            slow = slow.next
            result = max(result, stack.pop(-1)+slow.val)
        return result
# 160. 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交 **：**
300
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        A, B = headA, headB
        while A != B :
            A = A.next if A else headB
            B = B.next if B else headA
        return B
# 206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
输入：head = [1,2]
输出：[2,1]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur_p, pre_p = head, None
        while cur_p:
            next_p = cur_p.next
            cur_p.next = pre_p
            pre_p = cur_p
            cur_p = next_p
        return pre_p
# 138. 随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。每个节点用一个 [val, random_index] 表示：
  • val ：一个表示 Node.val 的整数。
  • random_index ：随机指针指向的节点索引（范围从 0 到 n-1 ）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

# 148. 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例
示例 1：
300
输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：
300
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：
输入：head = []
输出：[]

归并排序（递归法）
  • 题目要求时间空间复杂度分别为 O (nlogn) 和 O (1)，根据时间复杂度我们自然想到二分法，从而联想到归并排序；
  • 对数组做归并排序的空间复杂度为 O (n)，分别由新开辟数组 O (n) 和递归函数调用 O (logn) 组成，而根据链表特性：
    • 数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间；
    • 递归额外空间：递归调用函数将带来 O (logn) 的空间复杂度，因此若希望达到 O (1) 空间复杂度，则不能使用递归。
  • 通过递归实现链表归并排序，有以下两个环节：
    • 分割 cut 环节： 找到当前链表 中点，并从 中点 将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；
      • 我们使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
      • 找到中点 slow 后，执行 slow.next = None 将链表切断。
      • 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp (因为链表是从 slow 切断的)。
      • cut 递归终止条件： 当 head.next == None 时，说明只有一个节点了，直接返回此节点。
    • 合并 merge 环节： 将两个排序链表合并，转化为一个排序链表
      • 双指针法合并，建立辅助 ListNode h 作为头部。
      • 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
      • 返回辅助 ListNode h 作为头部的下个节点 h.next。
      • 时间复杂度 O (l + r)，l, r 分别代表两个链表长度。
    • 当题目输入的 head == None 时，直接返回 None。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        dummy = ListNode(next=head)
        slow, fast = dummy, dummy
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        mid = slow.next
        slow.next = None
        left, right = self.sortList(head), self.sortList(mid)
        h = ListNode()
        point = h
        while left and right:
            if left.val < right.val:
                point.next = left
                left = left.next
            else:
                point.next = right
                right = right.next
            point = point.next
        if left: point.next = left
        if right: point.next = right
        return h.next
作者：Krahets
链接：https://leetcode.cn/problems/sort-list/solutions/13728/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：
输入：lists = []
输出：[]

示例 3：
输入：lists = [[]]
输出：[]

分治
暴力做法是，按照 21. 合并两个有序链表 的 题解思路，先合并前两个链表，再把得到的新链表和第三个链表合并，再和第四个链表合并，依此类推。
但是这种做法，平均每个节点会参与到 O (m) 次合并中（用 (1+2+⋯+m)/m 粗略估计），所以总的时间复杂度为 O (L⋅m)。
一个巧妙的思路是，把 lists 一分为二（尽量均分），先合并前一半的链表，再合并后一半的链表，然后把这两个链表合并成最终的链表。如何合并前一半的链表呢？我们可以继续一分为二。如此分下去直到只有一个链表，此时无需合并。
我们可以写一个递归来完成上述逻辑，如果你对递归头晕，请看【基础算法精讲 09】。
按照一分为二再合并的逻辑，递归像是在后序遍历一棵平衡二叉树。由于平衡树的高度是 O (logm)，所以每个链表节点只会出现在 O (logm) 次合并中！这样就做到了更快的 O (Llogm) 时间。
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def merge(list1, list2):
            dummy = ListNode()
            point = dummy
            while list1 and list2:
                if list1.val < list2.val:
                    point.next = list1
                    list1 = list1.next
                else:
                    point.next = list2
                    list2 = list2.next
                point = point.next
            point.next = list1 if list1 else list2
            return dummy.next
        m = len(lists)
        if m == 0:return None
        if m == 1: return lists[0]
        left = self.mergeKLists(lists[:m//2])
        right = self.mergeKLists(lists[m//2:])
 
        return merge(left, right)
作者：灵茶山艾府
链接：https://leetcode.cn/problems/merge-k-sorted-lists/solutions/2384305/liang-chong-fang-fa-zui-xiao-dui-fen-zhi-zbzx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 二叉树
  1. 看到递归就晕？带你理解递归的本质！【基础算法精讲 09】_哔哩哔哩_bilibili
# 226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：
输入：root = [2,1,3]
输出：[2,3,1]

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return root
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left = right
        root.right = left
        return root
# 101. 对称二叉树
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true

判断核心是从上到下，重点是判断出不符合对称的情况，如果符合就持续深层判断直到根节点。
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        def dfs(left, right):
            if not left and not right:
                return True
            elif not (left and right):
                return False
            else:
                if left.val != right.val:
                    return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
        return dfs(root.left, root.right)
# 98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
  • 节点的左子树只包含 严格小于 当前节点的数。
  • 节点的右子树只包含 严格大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。
方法一：前序遍历
dfs 额外传入两个参数，分别表示从根到当前节点路径上的最小值和最大值。当前节点的值必须在最小值和最大值之间（不能等于）。
class Solution:
    def isValidBST(self, root: Optional[TreeNode], left = -inf, right = inf) -> bool:
        if not root:return True
        x = root.val
        if x >= right or x <= left: return False
        return self.isValidBST(root.left, left, x) and self.isValidBST(root.right, x, right)
方法二：中序遍历
本题是二叉搜索树，中序遍历是自然的做法。
中序遍历时，可以把二叉搜索树看成一个有序数组。
怎么判断一个数组是有序数组？比较相邻元素的大小即可。
class Solution:
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        if not self.isValidBST(root.left):  # 左
            return False
        if root.val <= self.pre:  # 中
            return False
        self.pre = root.val
        return self.isValidBST(root.right)  # 右
方法三：后序遍历
dfs 返回子树的最小值和最大值，供上面的节点判断是否为二叉搜索树。
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def dfs(node: Optional[TreeNode]) -> Tuple:
            if node is None:
                return inf, -inf
            l_min, l_max = dfs(node.left)
            r_min, r_max = dfs(node.right)
            x = node.val
            # 也可以在递归完左子树之后立刻判断，如果发现不是二叉搜索树，就不用递归右子树了
            if x <= l_max or x >= r_min:
                return -inf, inf
            return min(l_min, x), max(r_max, x)
        return dfs(root)[1] != inf
作者：灵茶山艾府
链接：https://leetcode.cn/problems/validate-binary-search-tree/solutions/2020306/qian-xu-zhong-xu-hou-xu-san-chong-fang-f-yxvh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 114. 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。
示例
示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

class Solution:
    head = None
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:return root
        self.flatten(root.right)
        self.flatten(root.left)
        root.left = None
        root.right = self.head
        self.head = root
# 437. 路径总和 III（与 560. 和为 K 的子数组方法相似）
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

如果二叉树是一条链，本题就和 560. 和为 K 的子数组 完全一样了：统计有多少个非空连续子数组的元素和恰好等于 targetSum。所以你必须先弄明白 560 题（特殊情况），再来做本题（一般情况）。560 题的做法见 我的题解。
这两题的联系如下：
560 题本题
连续子数组方向向下的路径
前缀从根节点开始的路径
做法：枚举子数组右端点，统计有多少个左端点做法：枚举路径的终点，统计有多少个起点 <br/> 我们要解决的问题是：DFS 遍历这棵树，遍历到节点 node 时，假设 node 是路径的终点，那么有多少个起点，满足起点到终点 node 的路径总和恰好等于 targetSum？
和 560 题一样的套路：一边遍历二叉树，一边用哈希表 cnt 统计前缀和（从根节点开始的路径和）的出现次数。设从根到终点 node 的路径和为 s，那么起点的个数就是 cnt [s−targetSum]，加入答案。对比 560 题，我们在枚举子数组的右端点（终点），统计有多少个左端点（起点），做法完全一致。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans = 0
        hp = collections.defaultdict(int)
        hp[0] = 1
        def dfs(node, s):
            if not node: return 
            nonlocal ans
            s += node.val
            ans += hp[s - targetSum]
            hp[s] += 1
            dfs(node.left, s)
            dfs(node.right, s)
            hp[s] -= 1
        dfs(root, 0)
        return ans
作者：灵茶山艾府
链接：https://leetcode.cn/problems/path-sum-iii/solutions/2784856/zuo-fa-he-560-ti-shi-yi-yang-de-pythonja-fmzo/
# 124. 二叉树中的最大路径和（与 543. 二叉树的直径相似）
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
示例
示例 1：
输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：
输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        max_result = -inf
        def max_(a,b,c):
            d = max(a,b)
            return max(d,c)
        def dfs(root):
            if not root: return 0
            left, right = dfs(root.left), dfs(root.right)
            node_max = root.val
            if left > 0: node_max += left
            if right > 0: node_max += right
            nonlocal max_result
            max_result = max(max_result, node_max)
            return root.val + max_(left, right, 0)
        dfs(root)
        return max_result
[543. 二叉树的直径](https://leetcode.cn/problems/diameter-of-binary-tree/)
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1：
输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        max_result = 0
        def dfs(root):
            if not root:
                return 0
            left, right = dfs(root.left), dfs(root.right)
            result = left + right + 1
            nonlocal max_result
            max_result = max(max_result, result)
            return max(left, right) + 1
        dfs(root)
        return max_result - 1
# 1372. 二叉树中的最长交错路径
给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
  • 选择二叉树中 任意 节点和一个方向（左或者右）。
  • 如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。
  • 改变前进方向：左变右或者右变左。
  • 重复第二步和第三步，直到你在树中无法继续移动。
交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
请你返回给定树中最长 交错路径 的长度。
示例
示例 1：
输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
输出：3
解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。

示例 2：
输入：root = [1,1,1,null,1,null,null,1,1,null,1]
输出：4
解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。

在 DFS 的过程中，每次我们都把当前点的 len 参数和答案 maxAns 打擂台，这样可以比出一个最大的。然后我们根据 dir 分类讨论。如果当前点应该向左且可以向左，那么就让他向左走一步，新的 len 是当前的 len 加一。如果的的点应该向左但是却没有左子树呢？很无奈那就只能向右了，这个时候 len 的值应该「重置」。
思考：「重置」为什么是把 len 变成 1 而不是 0？ 因为当前的点下传到它的子节点的时候已经走了一条长度为 1 的边。那么为什么 main 函数中传入的 len 值是 0 而不是 1 呢？ 因为 main 函数中的 root 是没有父亲节点的，所以当前已经走过的路为 0。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        result = 0
        def search(node, mode, l):
            if not node:return 
            nonlocal result
            result = max(result, l)
            if mode == 'left': 
                search(node.right, 'right',l+1)
                search(node.left, 'left', 1)
            elif mode == 'right': 
                search(node.left, 'left', l+1)
                search(node.right, 'right', 1)
        search(root,'left', 0)
        search(root, 'right', 0)
        return result
作者：力扣官方题解
链接：https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/solutions/147425/er-cha-shu-zhong-de-zui-chang-jiao-cuo-lu-jing-b-2/
# 105. 从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
示例
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

# 236. 二叉树的最近公共祖先
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

二叉树的最近公共祖先【基础算法精讲 12】_哔哩哔哩_bilibili
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root == None or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if right and left: return root
        return left or right
补充理解
基于灵神的题解，我加了一些自己的解释说明。
见 我的补充题解。
不好理解，是因为灵神代码复用了 lowestCommonAncestor 方法做递归。
但是从字面代码看，语义更接近于 find_p_or_q 才对。
改个名字，稍加注释后，似乎一切都说得通了。
在题目限制条件下（有解且唯一，且节点 unique），find_p_or_q 等价于 find_LCA，是关键所在。
改名 & 加注释后代码：
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def find_p_or_q(_r, _p, _q) -> tuple[bool, bool]:
            # (1) 因为有解且唯一，所以递归过程类似于寻找 p 或 q。
            if not _r:
                return False
            elif _r.val == _p.val or _r.val == _q.val:
                # (2) 自顶向下查找，找到一个匹配的立即返回即可（因为题目一定有解）
                return _r
            else:
                _lret = find_p_or_q(_r.left, _p, _q)
                _rret = find_p_or_q(_r.right, _p, _q)
                if _lret and _rret:
                    # (3) 都有的情况，应该是一左一右，所以父节点是 lca
                    return _r
                else:
                    return _lret or _rret
        return find_p_or_q(root, p, q)
# 199. 二叉树的右视图
给定一个二叉树的 根节点 root ，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例
示例 1：
输入： root = [1,2,3,null,5,null,4]
输出：[1,3,4]
解释：
示例 2：
输入： root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]
解释：
示例 3：
输入： root = [1,null,3]
输出：[1,3]
视频讲解：【基础算法精讲 10】
思路：先递归右子树，再递归左子树，当某个深度首次到达时，对应的节点就在右视图中。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        result = []
        def dfs(root, depth):
            if not root: return 
            if depth == len(result):
                result.append(root.val)
            dfs(root.right, depth + 1)
            dfs(root.left, depth + 1)
        dfs(root, 0)
        return result
作者：灵茶山艾府
链接：https://leetcode.cn/problems/binary-tree-right-side-view/solutions/2015061/ru-he-ling-huo-yun-yong-di-gui-lai-kan-s-r1nc/
思路：将每层的元素加入队列，从右到左依序遍历每层。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        if not root: return []
        result = []
        que = [root]
        while len(que) > 0:
            result.append(que[0].val)
            for _ in range(len(que)):
                node = que.pop(0)
                if node.right: que.append(node.right)
                if node.left: que.append(node.left)
        return result
# 450. 删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。
示例
示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

[视频解析](【LeetCode75】第四十二题 删除二叉搜索树中的节点_哔哩哔哩_bilibili)
二叉搜索树的题目往往可以用递归来解决。此题要求删除二叉树的节点，函数 deleteNode 的输入是二叉树的根节点 root 和一个整数 key，输出是删除值为 key 的节点后的二叉树，并保持二叉树的有序性。可以按照以下情况分类讨论：
  • root 为空，代表未搜索到值为 key 的节点，返回空。
  • root.val>key，表示值为 key 的节点可能存在于 root 的左子树中，需要递归地在 root.left 调用 deleteNode，并返回 root。
  • root.val<key，表示值为 key 的节点可能存在于 root 的右子树中，需要递归地在 root.right 调用 deleteNode，并返回 root。
  • root.val=key，root 即为要删除的节点。此时要做的是删除 root，并将它的子树合并成一棵子树，保持有序性，并返回根节点。根据 root 的子树情况分成以下情况讨论：
    • root 为叶子节点，没有子树。此时可以直接将它删除，即返回空。
    • root 只有左子树，没有右子树。此时可以将它的左子树作为新的子树，返回它的左子节点。
    • root 只有右子树，没有左子树。此时可以将它的右子树作为新的子树，返回它的右子节点。
    • root 有左右子树。此时可以把右子树接到左子树中（通过循环找到左子树的最右叶子，插在这个叶子上作为右子树，因为 root 的右子树必然比左子树的任意值大）。
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
        if not root: return 
        if root.val == key:
            if not root.left and not root.right: return 
            elif not root.left: return root.right
            elif not root.right: return root.left
            else:
                node = root.left
                while node.right: node = node.right
                node.right = root.right
                root = root.left
        elif root.val > key: root.left = self.deleteNode(root.left, key)
        elif root.val < key: root.right = self.deleteNode(root.right, key)
        return root
作者：力扣官方题解
链接：https://leetcode.cn/problems/delete-node-in-a-bst/solutions/1529700/shan-chu-er-cha-sou-suo-shu-zhong-de-jie-n6vo/
# 图
# 200. 岛屿数量
给你一个由 '1' （陆地）和 '0' （水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例
示例 1：
输入：grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
输出：1

示例 2：
输入：grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出：3

总体思路
看示例 2：
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
假设你是哥伦布。先从左上角开始，把第一个岛全部插上旗子🚩，这里用 2 表示。插满旗子后，把答案（岛屿个数）加一。
⚠注意：在岛上，你只能左右上下走，不能斜方向走。
2 2 0 0 0
2 2 0 0 0
0 0 1 0 0
0 0 0 1 1
继续遍历，寻找其他的岛屿，也就是 1。找到 1 意味着发现了一个新的岛，继续插上旗子🚩，把答案加一。
2 2 0 0 0
2 2 0 0 0
0 0 2 0 0
0 0 0 1 1
继续遍历，寻找其他的岛屿。找到 1 意味着发现了一个新的岛，插满旗子🚩，把答案加一。
2 2 0 0 0
2 2 0 0 0
0 0 2 0 0
0 0 0 2 2
如果没有 1 了，算法就结束了，返回答案（岛屿个数）。
如何实现？
一旦我们发现 (i,j) 是 1，就从 (i,j) 开始，DFS 这个岛。每一步可以往左右上下四个方向走，也就是 (i,j−1),(i,j+1),(i−1,j),(i+1,j) 这四个格子。
如果到达一块未发现的陆地格子，就插上旗子🚩，把 grid [i][j] 改成 2。
如果 (i,j) 出界，或者 (i,j) 是水，或者 (i,j) 已发现（已插上旗子🚩），就不再继续往下递归。
⚠注意：DFS 的过程中，最重要的是不能重复访问之前访问过的格子。
比如从左上角 (0,0) 向右移动到 (0,1)，然后从 (0,1) 又向左移动到 (0,0)，再从 (0,0) 向右移动到 (0,1)，如此往复，就无限递归下去了。
怎么避免重复访问？本题的做法是把访问过的格子都插上旗子🚩。例如从 (0,1) 往左走，发现 (0,0) 是插过旗子的格子，就不继续走了。
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        visit = [[0] * m for _ in range(n)]
        def dfs(x, y):
            if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] != '1':
                return 
            grid[x][y] = '2'
            dfs(x-1, y)
            dfs(x+1, y)
            dfs(x, y-1) 
            dfs(x, y+1)
        result = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    result += 1
                    dfs(i, j)
        return result
作者：灵茶山艾府
链接：https://leetcode.cn/problems/number-of-islands/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 994. 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
  • 值 0 代表空单元格；
  • 值 1 代表新鲜橘子；
  • 值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
示例
示例 1：
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。

示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

看示例 1：
  1. 统计所有初始就腐烂的橘子的位置，加到列表 q 中，现在 q=[(0,0)]。
  2. 初始化答案 ans=0。模拟橘子腐烂的过程，不断循环，直到没有新鲜橘子，或者 q 为空。
  3. 答案加一，在第 ans=1 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(0,1),(1,0)]。
  4. 答案加一，在第 ans=2 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(0,2),(1,1)]。
  5. 答案加一，在第 ans=3 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(2,1)]。
  6. 答案加一，在第 ans=4 分钟，遍历 q 中橘子的四方向相邻的新鲜橘子，把这些橘子腐烂，q 更新为这些橘子的位置，现在 q=[(2,2)]。
  7. 由于没有新鲜橘子，退出循环。
为了判断是否有永远不会腐烂的橘子（如示例 2），我们可以统计初始新鲜橘子的个数 fresh。在 BFS 中，每有一个新鲜橘子被腐烂，就把 fresh 减一，这样最后如果发现 fresh>0，就意味着有橘子永远不会腐烂，返回 −1。
代码实现时，在 BFS 中要将 grid [i][j]=1 的橘子修改成 2（或者其它不等于 1 的数），这可以保证每个橘子加入 q 中至多一次。如果不修改，我们就无法知道哪些橘子被腐烂过了，比如示例 1 中 (0,1) 去腐烂 (1,1)，而 (1,1) 在此之后又重新腐烂 (0,1)，如此反复，程序就会陷入死循环。读者可以注释掉下面代码中的 grid [i][j] = 2 这行代码试试。
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m , n = len(grid), len(grid[0])
        good = 0
        q = []
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1: good += 1
                elif grid[i][j] == 2 : q.append((i, j))
        result = 0
        while q and good:
            result += 1
            temp = q
            q = []
            for i, j in temp:
                near = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
                for x, y in near:
                    if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
                        good -= 1
                        grid[x][y] = 2
                        q.append((x, y))
        return -1 if good else result
作者：灵茶山艾府
链接：https://leetcode.cn/problems/rotting-oranges/solutions/2773461/duo-yuan-bfsfu-ti-dan-pythonjavacgojsrus-yfmh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

对于每个节点 x，都定义三种颜色值（状态值）：
0：节点 x 尚未被访问到。
1：节点 x 正在访问中，dfs (x) 尚未结束。
2：节点 x 已经完全访问完毕。注意这还说明从 x 出发无法找到环。所以当我们遇到状态值为 2 的节点 x 时，无需递归 x。
⚠误区：不能只用两种状态表示节点「没有访问过」和「访问过」。例如上图，我们先 dfs (0)，再 dfs (1)，此时 1 的邻居 0 已经访问过，但这并不能表示此时就找到了环。
算法流程：
  1. 建图：把每个 prerequisites [i]=[a,b] 看成一条有向边 b→a，构建一个有向图 g。
  2. 创建长为 numCourses 的颜色数组 colors，所有元素值初始化成 0。
  3. 遍历 colors，如果 colors [i]=0，则调用递归函数 dfs (i)。
  4. 执行 dfs (x)：
    • 首先标记 colors [x]=1，表示节点 x 正在访问中。
    • 然后遍历 x 的邻居 y。如果 colors [y]=1，则找到环，返回 true。如果 colors [y]=0（没有访问过）且 dfs (y) 返回了 true，那么 dfs (x) 也返回 true。
    • 如果没有找到环，那么先标记 colors [x]=2，表示 x 已经完全访问完毕，然后返回 false。
  5. 如果 dfs (i) 返回 true，那么找到了环，返回 false。
  6. 如果遍历完所有节点也没有找到环，返回 true。
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g = [[] for _ in range(numCourses)]
        for a,b in prerequisites:
            g[b].append(a)
        colors = [0] * numCourses
        def dfs(x):
            colors[x] = 1
            for y in g[x]:
                if colors[y] == 1 or colors[y] == 0 and dfs(y):
                    return True
            colors[x] = 2
            return False
        for i, c in enumerate(colors):
            if c == 0 and dfs(i):
                return False
        return True
作者：灵茶山艾府
链接：https://leetcode.cn/problems/course-schedule/solutions/2992884/san-se-biao-ji-fa-pythonjavacgojsrust-by-pll7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 二分查找
  • 二分查找的开区间模板：(后面的 162,33,81,153,154,34 由于预先设置右侧为答案，故不考虑右侧在区间内)
left, right = -1, n-1
while left + 1 < right:
    mid = (left + right) // 2
    if nums[mid] > target:
        right = mid
    else:
        left = mid
return right
# 162. 寻找峰值
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums ，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞ 。
你必须实现时间复杂度为 O(log n) 的算法来解决此问题。
示例
示例 1：
输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。

示例 2：
输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5 
解释：你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

定理：如果 i<n−1 且 nums [i]<nums [i+1]，那么在下标 [i+1,n−1] 中一定存在峰值。
证明：反证法，假设下标 [i+1,n−1] 中没有峰值。
由于 i+1 不是峰值且 nums [i]<nums [i+1]，所以一定有 nums [i+1]<nums [i+2] 成立，否则 i+1 就是峰值了。注意题目保证相邻元素不同，不存在相邻元素相等的情况。
由于 i+2 不是峰值且 nums [i+1]<nums [i+2]，所以一定有 nums [i+2]<nums [i+3] 成立，否则 i+2 就是峰值了。
依此类推，得
nums [i]<nums [i+1]<nums [i+2]<⋯<nums [n−1]>nums [n]=−∞
这意味着 nums [n−1] 是峰值，矛盾，所以原命题成立。
同理可得，如果 i<n−1 且 nums [i]>nums [i+1]，那么在 [0,i] 中一定存在峰值。
所以，通过比较 nums [i] 和 nums [i+1] 的大小关系，不断地缩小存在峰值的范围，二分找到峰值。
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        left, right = -1, len(nums)-1
        while left + 1 < right:
            mid = (left + right) // 2
            if nums[mid] < nums[mid+1]:
                left = mid
            else:
                right = mid
        return right
作者：灵茶山艾府
链接：https://leetcode.cn/problems/find-peak-element/solutions/1987497/by-endlesscheng-9ass/
# 33. 搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前， nums 在预先未知的某个下标 k （ 0 <= k < nums.length ）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] （下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

设 x=nums[mid] 是我们现在二分取到的数。
我们需要判断 x 和 target 的位置关系，谁在左边，谁在右边？
分类讨论：
  • 如果 x 和 target 在不同的递增段：
    • 如果 target 在第一段，x 在第二段，说明 target 在 x 在左边。
    • 如果 x 在第一段，target 在第二段，说明 target 在 x 在右边。
  • 如果 x 和 target 在相同的递增段：
    • 和 lowerBound 函数一样，比较 x 和 target 的大小即可。
下面代码用的开区间二分，用其他二分写法也是可以的。
二分的范围可以是 (−1,n−1)，也就是闭区间 [0,n−2]。
这是因为，如果 target=nums [n−1]，那么下面代码每次循环更新的都是 left，而 right 始终不变。循环结束后，答案自然就是 n−1 了。
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        left, right = -1, n-1
        while left+1 < right:
            mid = (left + right) // 2
            if target <= nums[-1] and nums[mid] > nums[-1]:
                left = mid
            elif target > nums[-1] and nums[mid] <= nums[-1]:
                right = mid
            elif nums[mid] >= target:
                right = mid
            else:
                left = mid
        return right if nums[right] == target else -1
作者：灵茶山艾府
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array/solutions/1987503/by-endlesscheng-auuh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 81. 搜索旋转排序数组 II
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前， nums 在预先未知的某个下标 k （ 0 <= k < nums.length ）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] （下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
你必须尽可能减少整个操作步骤。
示例
示例 1：
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true

示例 2：
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false

本题与 33 题的区别是有相同元素，这会导致在二分查找时，可能会遇到恰好二分元素 nums [mid] 与数组末尾元素 nums [n−1] 相同的情况，此时无法确定答案在左半区间中还是右半区间中。
既然无法确定最小值所在区间，那么干脆去掉 nums 的最后一个数，继续二分。换句话说，此时问题变成了一个规模为 n−1 的子问题。
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        left, right = -1, n-1
        while left+1 < right:
            mid = (left + right) // 2
            if nums[mid] == nums[right]: right -= 1   ## ** 相较于 33 题，多了这一个判断
            elif target <= nums[right] and nums[mid] > nums[right]:
                left = mid
            elif target > nums[right] and nums[mid] <= nums[right]:
                right = mid
            elif nums[mid] >= target:
                right = mid
            else:
                left = mid
        return nums[right] == target
作者：灵茶山艾府
链接：https://leetcode.cn/problems/search-in-rotated-sorted-array-ii/solutions/3058425/ji-yu-33-ti-de-jian-ji-xie-fa-zhi-xu-zen-uayi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 153. 寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
  • 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。

示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = -1, n-1
        while left+1 < right:
            mid = (left + right) // 2
            if nums[mid] > nums[-1]:left = mid
            else: right = mid
        return nums[right]
# 154. 寻找旋转排序数组中的最小值 II
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
  • 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4]
  • 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
示例
示例 1：
输入：nums = [1,3,5]
输出：1

示例 2：
输入：nums = [2,2,2,0,1]
输出：0

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        left, right = -1, n-1
        while left+1 < right:
            mid = (left + right) // 2
            if nums[mid] == nums[right]: right -= 1
            elif nums[mid] > nums[right]: left = mid
            else: right = mid
        return nums[right]
# 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums ，和一个目标值 target 。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target ，返回 [-1, -1] 。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def bi_search2(target):
            left, right = -1, len(nums)
            while left+1 < right:
                mid = (left + right) // 2
                if nums[mid] >= target:
                    right = mid
                else:
                    left = mid
            return right
        left = bi_search2(target)
        if left == len(nums) or nums[left] != target:return [-1,-1]
        right = bi_search2(target+1)-1
        return [left, right]
# 4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2 。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        nums1 = [-inf] + nums1 + [inf]
        nums2 = [-inf] + nums2 + [inf]
        i, j = 0, (m+n+1)//2
        while nums2[j] >= nums1[i+1]:
            i += 1
            j -= 1
        if (m+n)%2 == 1:
            return max(nums1[i], nums2[j])
        else:
            return (max(nums1[i], nums2[j]) + min(nums1[i+1], nums2[j+1])) / 2
作者：灵茶山艾府
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/solutions/2950686/tu-jie-xun-xu-jian-jin-cong-shuang-zhi-z-p2gd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 475. 供暖器
冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。
示例
示例 1:
输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置 2 上有一个供暖器。如果我们将加热半径设为 1，那么所有房屋就都能得到供暖。

示例 2:
输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置 1, 4 上有两个供暖器。我们需要将加热半径设为 1，这样所有房屋就都能得到供暖。

示例 3：
输入：houses = [1,5], heaters = [2]
输出：3

对于每个房屋，要么用前面的暖气，要么用后面的，二者取近的，得到距离。
class Solution:
    def findRadius(self, houses: List[int], heaters: List[int]) -> int:
        result = 0
        houses.sort()
        heaters.sort()
        j = 0
        for i, house in enumerate(houses):
            if house <= heaters[0]: dis = abs(house - heaters[0])
            elif house >= heaters[-1] : dis = abs(house - heaters[-1])
            else:
                l, r = -1, len(heaters)-1
                while l+1 < r:
                    mid = (l+r) // 2
                    if house < heaters[mid]:
                        r = mid
                    else:
                        l = mid
                dis = min(abs(house-heaters[r]), abs(house-heaters[l]))
            result = max(result, dis)
        return result
# 回溯
# 46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

对于一个长度为 n 的数组（假设元素互不重复），其排列方案数共有：
n×(n−1)×(n−2)…×2×1
排列方案的生成：
根据数组排列的特点，考虑深度优先搜索所有排列方案。即通过元素交换，先固定第 1 位元素（ n 种情况）、再固定第 2 位元素（ n−1 种情况）、... 、最后固定第 n 位元素（ 1 种情况）。
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result, n = [], len(nums)
        def back(index):
            if index == n-1:
                result.append(nums[:])
            
            for i in range(index, n):
                nums[i], nums[index] = nums[index], nums[i]
                back(index+1)
                nums[i],nums[index] = nums[index], nums[i]
        back(0)
        return result
作者：Krahets
链接：https://leetcode.cn/problems/permutations/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
我的解法
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        def back(index,visit):
            if index == n:
                ans.append(visit.copy())
                return 
            for i in range(n):
                if nums[i] not in visit:
                    back(index+1, visit+[nums[i]])
        back(0, [])
        return ans
# 78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result, n = [], len(nums)
        def back(index, temp):
            result.append(temp)
            for i in range(index, n):
                back(i+1, temp+[nums[i]])
        back(0, [])
        return result
# 17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        if n == 0: return []
        coder = {"2":'abc',"3":'def',"4":'ghi',"5":'jkl',"6":'mno',"7":'pqrs',"8":'tuv',"9":'wxyz'}
        result = []
        def back(index, s):
            if index == n:
                result.append(s)
                return 
            for c in coder[digits[index]]:
                back(index+1, s+c)
        back(0, '')
        return result
# 39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result, n = [], len(candidates)
        def back(s, temp, index):
            if s == target: 
                result.append(temp)
                return
            elif s > target: return
            for i in range(index, n):
                back(s + candidates[i], temp+[candidates[i]], i)
        back(0,[],0)
        return result
# 22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1
输出：["()"]

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        def back(temp, left, right):
            print(temp)
            if left + right == n*2:
                result.append(temp)
                return
            if right < left and right < n:
                back(temp+')', left, right+1)
            if left<n:
                back(temp+'(', left+1, right)
        back('', 0, 0)
        return result
# 79. 单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中 “相邻” 单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例
示例 1：
输入：board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"
输出：true

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        visited = [[0]*n for _ in range(m)]
        diections = [[1,0], [0,1], [-1,0], [0,-1]]
        flag = False
        num_word = len(word)
        def back(index, x, y):
            print(x,y)
            if board[x][y] != word[index]: return
            if index == num_word - 1:
                nonlocal flag
                flag = True
                return 
            visited[x][y] = 1
            for diection in diections:
                if 0 <= x+diection[0] <m and 0<=y+diection[1]<n and visited[x+diection[0]][y+diection[1]] == 0:
                    back(index + 1, x+diection[0], y+diection[1])
        for i in range(m):
            for j in range(n):
                if board[i][j] == word[0]:
                    back(0, i, j)
        return flag
# 131. 分割回文串
给你一个字符串 s ，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：
输入：s = "a"
输出：[["a"]]

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        result, n = [], len(s)
        def back(index, temp):
            if index == n:
                result.append(temp)
                return 
            for i in range(index, n):
                s_temp = s[index:i+1]
                if s_temp == s_temp[::-1]:
                    back(i+1, temp+[s_temp])
        back(0, [])
        return result
# 51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例
示例 1：
img
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

与 46. 全排列类似
问题转换为 [1,2,...,n] 的排列中符合皇后不攻击的条件。
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        ans = []
        def isable(row, vis):
            if row == 0: return True
            new_r, new_c = row, vis[-1] 
            for i in range(row):
                if vis[i] + i == new_c + new_r or vis[i] - i == new_c - new_r:
                    return False
            return True
        def dfs(row, vis):
            if row == n:
                ans.append(['.'*i+'Q'+'.'*(n-1-i) for i in vis])
                return 
            for i in range(n):
                if i not in vis and isable(row, vis+[i]):
                    dfs(row+1, vis+[i])
        dfs(0, [])
        return ans
# 贪心算法
# 55. 跳跃游戏
给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
示例
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        now, right = 0, 0
        n = len(nums)
        for i in range(n):
            if right < i: return False
            right = max(right, i+nums[i])
        return right >= n-1
# 45. 跳跃游戏 II
给定一个长度为 n 的 0 索引整数数组 nums 。初始位置在下标 0。
每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在索引 i 处，你可以跳转到任意 (i + j) 处：
  • 0 <= j <= nums[i] 且
  • i + j < n
返回到达 n - 1 的最小跳跃次数。测试用例保证可以到达 n - 1 。
示例
示例 1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:
输入: nums = [2,3,0,1,4]
输出: 2

⚠注意：不是在无路可走的那个位置造桥，而是当发现无路可走的时候，时光倒流到能跳到最远点的那个位置造桥。换句话说，在无路可走之前，我们只是在默默地收集信息，没有实际造桥。当发现无路可走的时候，才从收集到的信息中，选择最远点造桥。所建造的这座桥的左端点（起跳位置）在我们当前走的这座桥的中间，而不是桥的末尾。
class Solution:
    def jump(self, nums: List[int]) -> int:
        result = 0
        cur_distance = 0
        next_distance = 0
        
        for i in range(len(nums)-1):
            next_distance = max(next_distance, i + nums[i])
            if i == cur_distance:
                cur_distance = next_distance
                result += 1
        return result
作者：灵茶山艾府
链接：https://leetcode.cn/problems/jump-game-ii/solutions/2926993/tu-jie-yi-zhang-tu-miao-dong-tiao-yue-yo-h2d4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"] ，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例
示例 1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。 

示例 2：
输入：s = "eccbbbbdec"
输出：[10]

其实思路很简单，
1， 首先看第一个字母，找到它在串里最后的一个位置，记作 last 或一段的最后位置。
2， 在从 0~last 这个范围里，挨个查其他字母，看他们的最后位置是不是比刚才的 last 或一段的最后位置大。
如果没有刚才的 last 或一段的最后位置大，无视它继续往后找。
如果比刚才的大，说明这一段的分隔位置必须往后移动，所以我们把 last 或一段的最后位置更新为当前的字母的最后位置。
3，肯定到有一个时间，这个 last 就更新不了了，那么这个时候这个位置就是我们的分隔位置。
注意题目要分隔后的长度，我们就用 last - startindex + 1。
4，找到一个分割位，更新一下起始位置，同理搜索就行了。
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        dic = {}
        for i, c in enumerate(s):
            dic[c] = i
        n = len(s)
        num, result = 0, []
        last = dic[s[0]]
        for i in range(n):
            num += 1
            if dic[s[i]] > last:
                last = dic[s[i]]
            if i == last:
                result.append(num)
                num = 0
        return result
作者：Flying_Du
链接：https://leetcode.cn/problems/partition-labels/solutions/455898/python-jiu-zhe-quan-guo-zui-cai-you-hua-dai-ma-by-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 动态规划
# 198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:return 0
        if n == 1:return nums[0]
        if n == 2:return max(nums[0], nums[1])
        dp = [0]*n
        dp[0], dp[1] = nums[0], max(nums[0], nums[1])
        for i in range(2,n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        return max(dp[-1], dp[-2])
# 279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如， 1 、 4 、 9 和 16 都是完全平方数，而 3 和 11 不是。
示例
示例 1：
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9

把 1,4,9,16,⋯ 这些完全平方数视作物品体积，物品价值都是 1。由于每个数（物品）选的次数没有限制，所以本题是一道标准的完全背包问题。
按照视频中的做法，定义 dfs (i,j) 表示从前 i 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j，最少要选的数字个数。
考虑第 i 个完全平方数 i^2 选或不选：
不选：问题变成从前 i−1 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j，最少要选的数字个数，即
dfs(i,j)=dfs(i−1,j)dfs(i,j)=dfs(i−1,j)
选：前提是 j≥i^2。问题变成从前 i 个完全平方数中选一些数（可以重复选），满足元素和恰好等于 j−i^2 ，最少要选的数字个数，即 。注意这里是 i 而不是 i−1，因为我们可以继续选第 i 个完全平方数。
这两种情况取最小值，就得到了 dfs (i,j)，即
递归边界：dfs (0,0)=0，因为没有数可以选了，且要得到的数等于 0，那么答案为 0。如果 j>0，那么 dfs (0,j)=∞，这里用 ∞ 表示不合法的状态，从而保证上式中的 min 取到合法的状态。注意本题是一定有解的，因为 1 是完全平方数。
012345...n
00infinfinfinfinf...inf
1
2
3
...
m
class Solution:
    def numSquares(self, n: int) -> int:
        m = isqrt(n)
        f = [[0]*(n+1) for _ in range(m+1)]
        f[0] = [0] + [inf] * n
        for i in range(1,m+1):
            for j in range(n+1):
                if j < i*i:
                    f[i][j] = f[i-1][j]
                else:
                    f[i][j] = min(f[i][j-i*i]+1, f[i-1][j])
        return f[m][n]
作者：灵茶山艾府
链接：https://leetcode.cn/problems/perfect-squares/solutions/2830762/dong-tai-gui-hua-cong-ji-yi-hua-sou-suo-3kz1g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        m, n = len(coins), amount
        f = [[0]*(amount+1) for _ in range(m+1)]
        f[0] = [0] + [inf]*amount
        for i in range(1,m+1):
            for j in range(n+1):
                if j < coins[i-1]:
                    f[i][j] = f[i-1][j]
                else:
                    f[i][j] = min(f[i-1][j], f[i][j-coins[i-1]]+1)
        return f[-1][-1] if f[-1][-1] < inf else -1
# 139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true 。
** 注意：** 不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

枚举 j=i−1,i−2,i−3,…,max (i−maxLen,0)，只要其中一个 j 满足 s [j:i] 在 wordDict 中且 f [j]=true，那么 f [i] 就是 true。
初始值 f [0]=true，翻译自递归边界 dfs (0)=true。
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n+1)
        dp[0] = True
        for i in range(1, n+1):
            for j in range(i):
                if s[j:i] in wordDict and dp[j]:
                    dp[i] = True
        return dp[-1]
作者：灵茶山艾府
链接：https://leetcode.cn/problems/word-break/solutions/2968135/jiao-ni-yi-bu-bu-si-kao-dpcong-ji-yi-hua-chrs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 300. 最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如， [3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

dfs (i) 表示以 nums [i] 结尾的最长递增子序列（LIS）的长度。
枚举子序列的倒数第二个数的下标是 j，如果 nums [j]<nums [i]，那么有 dfs (i)=dfs (j)+1，取最大值。
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            max_len = 0
            for j in range(i):
                if nums[i] > nums[j]:
                    max_len = max(max_len, dp[j])
            dp[i] = max_len + 1
        return max(dp)
# 152. 乘积最大子数组
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32 - 位 整数。
请注意，一个只包含一个元素的数组的乘积是这个元素的值。
示例
示例 1:
输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:
输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        min_val, max_val = 1, 1
        result = nums[0]
        print(result)
        for i, num in enumerate(nums):
            new_min_val = min(min_val*num, max_val*num, num)
            new_max_val = max(min_val*num, max_val*num, num)
            result = max(result, new_max_val)
            max_val = new_max_val
            min_val = new_min_val
        return result
# 416. 分割等和子集
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

012345...target
111000000
5110001
11
5
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        n = len(nums)
        if s % 2: return False
        target = s // 2
        if max(nums) > target: return False
        dp = [[0]*(target+1) for _ in range(n)]
        dp[0][0], dp[0][nums[0]] = 1, 1
        for i in range(1, n):
            for j in range(target+1):
                if nums[i] > j: dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = 1 if dp[i-1][j] or dp[i-1][j-nums[i]] else 0
        return bool(dp[-1][-1])
# 32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号 子串 的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())" 。
示例
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

示例 3：
输入：s = ""
输出：0

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        dp = [0] * n
        for i in range(1,n):
            c = s[i]
            if c == '(': continue
            if s[i-1] =='(':
                dp[i] = 2
                if i-1 - 1 >= 0: dp[i] += dp[i-2]
            else:
                if i-1-dp[i-1] >= 0 and s[i-1-dp[i-1]] == '(':
                    dp[i] = dp[i-1] + 2
                    if i-1-dp[i-1] - 1 >= 0:
                        dp[i] += dp[i-1-dp[i-1]-1]
        print(dp)
        return max(dp)
# 5. 最长回文子串
给你一个字符串 s ，找到 s 中最长的 回文 子串。
示例
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        result_left, result_right = 0, 0
        for i in range(2*n-1):
            left, right = i // 2, (i+1)//2
            while left >= 0 and right < n and s[left] == s[right]:
                right += 1
                left -= 1
            if right- left > result_right - result_left:
                result_left, result_right = left, right
        return s[result_left+1: result_right]
# 1143. 最长公共子序列
给定两个字符串 text1 和 text2 ，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
  • 例如， "ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例
示例 1：
输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

示例 2：
输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

示例 3：
输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text2), len(text1)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[j-1] == text2[i-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        return dp[-1][-1]
# 72. 编辑距离
给你两个单词 word1 和 word2 ， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
  • 插入一个字符
  • 删除一个字符
  • 替换一个字符
示例
示例 1：
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：
输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

0house
0012345
r112234
o221234
s332223
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[i]*(n+1) for i in range(m+1)]
        for i in range(1,n+1):
            dp[0][i] = i
        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] 
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
        return dp[-1][-1]
# 技巧
# 136. 只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例
示例 1 ：
输入：nums = [2,2,1]
输出：1

示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：
输入：nums = [1]
输出：1

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count = Counter(nums)
        for k in count.keys():
            if count[k] == 1:
                return k
        return 0
利用异或运算 a⊕a=0 的性质，我们可以用异或来「消除」所有出现了两次的元素，最后剩下的一定是只出现一次的元素。
例如 nums=[4,1,2,1,2]，把所有元素异或：
4⊕1⊕2⊕1⊕24⊕1⊕2⊕1⊕2
=4⊕(1⊕1)⊕(2⊕2)=4⊕(1⊕1)⊕(2⊕2)
=4⊕0⊕0=4⊕0⊕0
=4=4
其中用到了异或运算的交换律 a⊕b=b⊕a，以及结合律 (a⊕b)⊕c=a⊕(b⊕c)（类比加法）。
代码中，初始化 ans=0 是因为 0⊕a=a，相当于我们从第一个数开始，和其它数异或。
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(xor, nums)
reduce函数/xor函数
reduce 函数的基本用法
在 Python 3 中，reduce 函数已经被移到 functools 模块中，因此在使用之前需要先导入这个模块。reduce 的基本语法如下：
from functools import reduce
def add(x, y):
	return x + y
result = reduce(add, [1, 2, 3, 4, 5])
print(result) # 输出: 15
xor 函数为异或函数（^）
作者：灵茶山艾府
链接：https://leetcode.cn/problems/single-number/solutions/2481594/li-yong-yi-huo-de-xing-zhi-fu-ti-dan-pyt-oizc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 169. 多数元素
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例
示例 1：
输入：nums = [3,2,3]
输出：3

示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2

用「擂台赛」打比方：
  1. 擂主登场：nums [0] 成为初始擂主，生命值为 1。
  2. 挑战者出现：遍历后续元素，作为挑战者。
  3. 比武：如果挑战者与擂主属于同一门派（值相同），那么擂主生命值加 1，否则擂主生命值减 1。
  4. 擂主更迭：如果比武后，擂主生命值降为 0（同归于尽），那么下一个挑战者成为新的擂主，生命值为 1。
  5. 最后在擂台上的那人，便是武林盟主（严格众数）。
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        count = 1
        n, c = len(nums), nums[0]
        for i in range(1,n):
            if nums[i] == c: count += 1
            else:
                count -= 1
                if count < 0: count, c = 1, nums[i]
        return c
作者：灵茶山艾府
链接：https://leetcode.cn/problems/majority-element/solutions/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 常见面试题
# 179. 最大数
给定一组非负整数 nums ，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
** 注意：** 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例
示例 1：
输入：nums = [10,2]
输出："210"

示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"

此题求拼接起来的最大数字。设数组 nums 中任意两数字的字符串为 x 和 y ，则规定 贪心策略：
若拼接字符串 x+y>y+x ，则 x “大于” y 。
反之，若 x+y<y+x ，则 x “小于” y 。
x “小于” y 代表：排序完成后，数组中 x 应在 y 左边；“大于” 则反之。
根据以上规则，套用任何排序方法对 nums 执行排序即可。
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        def quick_sort(l, r):
            if l >= r: return
            i, j = l, r
            while i < j:
                while strs[j]+strs[l] >= strs[l]+strs[j] and i<j: j -= 1
                while strs[i]+strs[l] <= strs[l]+strs[i] and i<j: i += 1
                strs[i], strs[j] = strs[j], strs[i]
            strs[i], strs[l] = strs[l], strs[i]
            quick_sort(l,i-1)
            quick_sort(i+1,r)
        strs = [str(i) for i in nums]
        quick_sort(0, len(strs)-1)
        if strs[-1] == '0':return '0'
        return ''.join(strs[::-1])
作者：Krahets
链接：https://leetcode.cn/problems/largest-number/solutions/2361893/179-zui-da-shu-tan-xin-qing-xi-tu-jie-by-wboz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 621. 任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，用字母 A 到 Z 表示，以及一个冷却时间 n 。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成，但有一个限制：两个 相同种类 的任务之间必须有长度为 n 的冷却时间。
返回完成所有任务所需要的 最短时间间隔 。
示例
示例 1：
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：
在完成任务 A 之后，你必须等待两个间隔。对任务 B 来说也是一样。在第 3 个间隔，A 和 B 都不能完成，所以你需要待命。在第 4 个间隔，由于已经经过了 2 个间隔，你可以再次执行 A 任务。

示例 2：
输入：tasks = ["A","C","A","B","D","B"], n = 1
输出：6
解释：一种可能的序列是：A -> B -> C -> D -> A -> B。
由于冷却间隔为 1，你可以在完成另一个任务后重复执行这个任务。

本题核心问题就是冷却时间 n 意味着 CPU 可能必须要待命，实际完成任务时间 = len (tasks)+ 待命 > len (tasks);
如果不需要待命，实际完成任务时间 = len (tasks)
假设需要 待命，由数量最大的任务种类来决定 完成任务时间:
假设 A 有 3 个 (maxCt = 3), n = 2, 需要 待命 说明 'x' 的位置都填不满，实际完成任务时间 = (maxCt-1)*(n+1)+1 > len (tasks)
A x x
A x x
A
如果 'x' 的位置能填满的话，实际完成任务时间 = len (tasks) > (maxCt-1)*(n+1)+1, e.g.
A B C D
A B C
A
另外要注意的是数量最大的任务可能有好几个，比如 A 有 3 个 (maxCt = 3), B 也有 3 个，eleMaxCt = 2,
A B x
A B x
A B
那么最后一行的个数就不是 1, 而是 eleMaxCt,
综上，实际完成任务时间 = max ((maxCt-1)*(n+1)+eleMaxCt , len (tasks))
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = list(Counter(tasks).values())
        max_ct = max(count)
        num_max = count.count(max_ct)
        return max(len(tasks), (max_ct-1)*(n+1)+num_max)
作者：MingZhang
链接：https://leetcode.cn/problems/task-scheduler/solutions/954985/pythonsi-xing-dai-ma-chao-jian-ji-si-lu-eopmo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 316. 去除重复字母
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例
示例 1：
输入：s = "bcabc"
输出："abc"

示例 2：
输入：s = "cbacdcbc"
输出："acdb"

具体算法如下：
  • 统计每个字母的出现次数，记到一个哈希表或者数组 left 中。
  • 遍历 s，先把 left [s [i]] 减一。
  • 如果 s [i] 在 ans 中，直接 continue。为了快速判断 s [i] 是否在 ans 中，可以用一个哈希表或者布尔数组 inAns 辅助判断。
  • 如果 s [i] 不在 ans 中，那么判断 s [i] 是否小于 ans 的最后一个字母（记作 x），如果 s [i]<x 且 left [x]>0，那么可以把 x 从 ans 中去掉，同时标记 inAns [x]=false。
  • 反复执行第 4 步，直到 ans 为空，或者 s [i]>x，或者 left [x]=0。
  • 把 s [i] 添加到 ans 末尾，同时标记 inAns [s [i]]=true。然后继续遍历 s 的下一个字母。
  • 遍历完 s 后，返回 ans。
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        result = []
        count = Counter(s)
        for c in s:
            count[c] -= 1
            if c in result:
                continue
            while result and c < result[-1] and count[result[-1]] >= 1:
                result.pop(-1)
            result.append(c)
        return ''.join(result)
作者：灵茶山艾府
链接：https://leetcode.cn/problems/remove-duplicate-letters/solutions/2381483/gen-zhao-wo-guo-yi-bian-shi-li-2ni-jiu-m-zd6u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
# 221. 最大正方形
在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例
示例 1：
300
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

300
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        visited = [[0]*(n+1) for _ in range(m+1)]
        result = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == '0': visited[i+1][j+1] = 0
                else:
                    visited[i+1][j+1] = min(visited[i+1][j], visited[i][j+1], visited[i][j]) + 1
                    result = max(visited[i+1][j+1], result)
        return result ** 2
 更新于   阅读次数  次