Leetcode Hot 100

1. 两数之和

用一个dict来存过去见过的 target-nums[i] ，然后如果当前和这个一致的话就找到匹配的两个数

from collections import defaultdict

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        mem = defaultdict()
        for i in range(len(nums)):
            if target - nums[i] in mem:
                return [mem[target-nums[i]], i]
            mem[nums[i]] = i
        return []

49. 字母异位词分组

排序然后用dict存起来就行了

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        seen = defaultdict(list)
        for st in strs:
            seen["".join(sorted(st))].append(st)
        ans = []
        for k, v in seen.items():
            ans.append(v)
        return ans

128. 最长连续序列

先用一个 set 来去重，然后对于每一个元素，如果有比它刚好-1的元素在set里面就继续（因为这样必然会有长度大于该起点的序列）；如果没有的话，就+1的向后遍历即可。

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        set_nums = set(nums)
        ans = 0
        for num in set_nums:
            if num-1 in set_nums:
                continue
            y = num+1
            while y in set_nums:
                y += 1
            ans = max(ans, y-num)
        return ans

283. 移动零

left 指针指向的是已经处理好的序列的末尾， right 指针指向的是待处理序列的头部。

左指针左边均为非零数；右指针左边直到左指针处均为零。

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        left, right = 0, 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

11. 盛最多水的容器

盛水容器问题具有明显的短板效应：容器所能盛水的高度始终由两侧较低的一边决定。

因此可以使用双指针策略：初始时，左指针指向位置 0，右指针指向位置 n-1。在每一步中，当前可盛水量为

(right - left) × min(height[left], height[right])。

关键在于指针的移动策略：每次只移动高度较小的一侧指针。原因是，如果移动高度较大的一侧，宽度虽然减小，但高度仍然受限于原本较小的一侧，盛水量只会变小或不变，不可能得到更优解。

只有移动高度较小的一侧，才有可能遇到更高的边，从而在宽度减小的情况下提高有效高度，进而产生更大的盛水面积。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        left, right = 0, n-1
        max_area = 0
        while left!=right:
            max_area = max(min(height[left], height[right])*(right-left), max_area)
            if height[left] <= height[right]: left += 1
            else:
                right -= 1
        return max_area

15. 三数之和

nums[i] + nums[j] = -nums[k]

因此把数组排序，然后固定k，利用两个指针分别指向下一个元素和最后一个元素，双指针查找即可。

这题目麻烦的点在于需要去重。首先需要对固定的k元素进行去重；对查找到的符合要求的元素也需要进行去重。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        nums = sorted(nums)
        for k in range(n):
		        # 去重
            if k > 0 and nums[k] == nums[k-1]:
                k += 1
                continue
            if nums[k] > 0:
                continue

            left, right = k+1, n-1

            while left < right:
                sum_up = nums[left]+nums[right]

                if sum_up == -nums[k]:
                    ans.append([nums[left], nums[right], nums[k]])
                    # 去重	             
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    
                    left += 1
                    right -= 1

                elif sum_up < -nums[k]:
                    left += 1
                else:
                    right -= 1
        return an

42. 接雨水

首先可以得到，当前位置能够接的雨水量等于左右高度的最小值减去当前高度。那么朴素的算法就是遍历每一个位置，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的雨水量。该做法需要对每个下标位置使用 $O(n)$ 的时间向两边扫描并得到最大高度，因此总时间复杂度是 $O(n^2)$.

实际上，对于某个位置，我们只关心在当前位置，左边的最大值以及右边的最大值。这样的思想很类似买卖股票的最佳时机，只需要存当前的最小以及当前的最大即可。因此，很容易想到用两个数组分别来存当前位置从左边开始遍历的最高点以及当前位置从右边开始遍历的最高点。用额外 $O(n)$ 的空间来减少了一次遍历的时间，时间复杂度降为 $O(n)$

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        ans = 0
        left_max, right_max = [0 for i in range(n)], [0 for i in range(n)]
        left_max[0] = height[0]
        right_max[n-1] = height[n-1]
        for i in range(n-1):
            left_max[i+1] = max(left_max[i], height[i+1])
        
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])
        
        for i in range(n):
            ans += min(left_max[i], right_max[i]) - height[i]
        return ans

124. 二叉树中的最大路径和

以当前节点的作为路径的开始，向下延伸，使得该路径上的节点值之和最大，只有两种选法：

选择左右子树里面最大的
如果左右子树都是负数，那么当前的最大值就只是 node.val

这两种情况可以融合为 max(func(left or right), 0)

上面这个思考过程可以找到以每一个节点开始的最大的路径，那么对于某一个节点，题目需要求的路径和就是当前的 node.val 与当前节点左右子树的最大路径之和。

那么实际上再维护一个全局的最大值，初始化成-inf，随着后续遍历的时候更新即可。

辅助函数用来算从当前节点为开始的最大路径，递归的同时计算题目需要的路径和

# 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 maxPathSum(self, root: Optional[TreeNode]) -> int:
        self.ans = float("-inf")
        def helper(node):
            if not node: return 0

            left = max(helper(node.left), 0)
            right = max(helper(node.right), 0)

            self.ans = max(self.ans, left + right + node.val)

            return node.val + max(left, right)
        
        helper(root)
        return self.ans

200. 岛屿数量

类似这种图相关的问题，一般都是用深度优先搜索和广度优先搜索进行解决：

def dfs(grid, r, c):
	  if not check(r, c) or grid[r][c] != 1:
	      return 0
	
	  grid[r][c] = 2 # 标志以及走过的部分
	
	  return dfs(grid, r-1, c) + dfs(grid, r, c+1) + dfs(grid, r, c-1) + dfs(grid, r+1, c)

这道题的核心思路就是把遍历到的岛屿给换个数字标记一下，统计个数即可。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        def check(i, j, m, n):
            return (0<=i<=m-1) and (0<=j<=n-1)
    
        def dfs(grid, i, j):
            m, n = len(grid), len(grid[0])
            if not check(i, j, m, n) or grid[i][j] != '1':
                return 0
            
            grid[i][j] = '2'

            dfs(grid, i-1, j)
            dfs(grid, i, j+1)
            dfs(grid, i, j-1)
            dfs(grid, i+1, j)
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    res += 1
        
        return res

994. 腐烂的橘子

最好想到的办法就是模拟这个过程，在每一次找到腐烂的橘子，然后遍历他的上下左右四个位置，修改对应位置的橘子的情况。这里需要重新建立一个new_grid，方便每一次更新完状态之后修改整个图。

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        def check(i,j):
            return (0<=i<=m-1) and (0<=j<=n-1)
        
        changed = True
        total_time = 0

        while changed:
            changed = False
            new_grid = [row[:] for row in grid]

            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 2:
                        if check(i - 1, j) and grid[i - 1][j] == 1:
                            new_grid[i - 1][j] = 2
                            changed = True
                        if check(i + 1, j) and grid[i + 1][j] == 1:
                            new_grid[i + 1][j] = 2
                            changed = True
                        if check(i, j - 1) and grid[i][j - 1] == 1:
                            new_grid[i][j - 1] = 2
                            changed = True
                        if check(i, j + 1) and grid[i][j + 1] == 1:
                            new_grid[i][j + 1] = 2
                            changed = True
            if changed:
                total_time += 1
            grid = new_grid
        
        for row in grid:
            if 1 in row:
                return -1
        
        return total_time

还有一种方法就是BFS，在初始状态之下把所有的腐烂的橘子加入到队列里面，每次把队列内的元素取出来对他们周围进行遍历，直到队列中没有腐烂的橘子了。

from collections import deque
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        def check(i,j):
            return (0<=i<=m-1) and (0<=j<=n-1)

        queue = deque()
        fresh_oranges = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i,j))  
                if grid[i][j] == 1:
                    fresh_oranges += 1     
        while queue:
            new_queue = []
            old_queue_len = len(queue)
            while old_queue_len:
                old_queue_len -= 1
                cur_orange = queue.popleft()
                i, j = cur_orange
                for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
                    ni, nj = i + di, j + dj
                    if check(ni, nj) and grid[ni][nj] == 1:
                        grid[ni][nj] = 2
                        fresh_oranges -= 1
                        new_queue.append((ni, nj))
            if new_queue:
                res += 1
                queue = deque(new_queue)
            else:
                break

        return res if fresh_oranges == 0 else -1

207. 课程表

拓扑排序板子

把题目里面给的修课顺序看成是有向图，那么这道题的意思就是考察这个有向图中是否存在环，如果有环就表明是不可能修完这些课程的。

DFS的思想就是遍历一个节点的某一条路径上的所有的节点，遍历的时候维护一个临时的遍历状态，如果说在遍历这条边的时候遍历到了之前的节点（也就是之前的节点的状态为临时的），那么很显然这是一条环，返回False。如果遍历完了都没有环，就修改为永久的遍历状态。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        for a, b in prerequisites:
            graph[b].append(a)

        state = [0] * numCourses
        def dfs(node):
            if state[node] == 2:
                return True
            if state[node] == 1:
                return False
            neighbours = graph[node]
            state[node] = 1
            for n in neighbours:
                if not dfs(n):
                    return False
            state[node] = 2
            return True
        
        res = True
        for n in graph.keys():
            if state[n] == 0:
                res = dfs(n) and res

        return res

bfs的核心在于，统计每一个节点的入度。如果某个节点的入度是0，表明它不需要前置的课程，可以直接进行修读，因此可以把这个节点给加入到修读的队列中，同时对他后续的节点的入度进行更新。遍历完之后查看修读的队列是否和节点数相等，相等的话就没有环，不相等为有环。

from collections import deque
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        indegree = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            indegree[a] += 1
        
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        res = 0
        while queue:
            cur = queue.popleft()
            res += 1
            for nei in graph[cur]:
                indegree[nei] -= 1
                if indegree[nei] == 0:
                    queue.append(nei)
        
        return res == numCourses

208. 实现 Trie (前缀树)

前缀树的核心思想是让前缀一样的单词共享前缀一样的部分，这样能够加快进行查找的速度。实例如下：

(root)
 ├── c
 │    └── a
 │         ├── t (is_end=True)
 │         └── r (is_end=True)
 └── d
      └── o
           └── g (is_end=True)

这里用了嵌套的字典来实现前缀树，主要思想是对于输入的单词拆分成每一个字母，利用 setdefault 这个操作，把不在字典内的字母嵌套进入，在的话就继续。同时对于每一个已经插入的单词，在最后一个字母的字典里插入 # 作为结束的标识。

class Trie:

    def __init__(self):
        self.trie = {}

    def insert(self, word: str) -> None:
        node = self.trie
        for ch in word:
            node = node.setdefault(ch, {})
        node['#'] = True

    def search(self, word: str) -> bool:
        node = self.trie
        for ch in word:
            if ch not in node:
                return False
            node = node[ch]
        return '#' in node

    def startsWith(self, prefix: str) -> bool:
        node = self.trie
        for ch in prefix:
            if ch not in node:
                return False
            node = node[ch]
        return True

46. 全排列

回溯的题目一般会用一个新数组来维护是否被访问过，然后用DFS进行递归求解。

这道题目就用一个 visited 数组来维护当前数字是否被使用过，如果没有被使用过表明是新的排列组合，那么就可以添加到当前结果的后面；在整个遍历过程结束之后，需要把 visited 的状态切换回去。

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        visited = [False for _ in range(n)] 

        def dfs(path, depth):
            if depth == n:
                res.append(path[:])
                return 
            
            for i in range(n):
                if not visited[i]:
                    visited[i] = True
                    path.append(nums[i])
                    dfs(path, depth+1)
                    visited[i] = False
                    path.pop()
        
        dfs([], 0)
        return res

78. 子集

也是一道回溯问题，对于子问题就是对每一个字母是选还是不选，因此进行两个分支的递归来求解即可，同时对于选择的分支，进行选择完之后需要及时回溯掉。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []

        def dfs(path, i):
            if i == n:
                return res.append(path[:])
            
            path.append(nums[i])
            dfs(path, i+1)
            path.pop()
            dfs(path, i+1)
        
        dfs([], 0)
        return res

17. 电话号码的字母组合

对于对应位置的字母，每一次仅仅选择一个，然后就递归到下一层继续选择，同时选择完之后进行回溯。

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        MAPPING = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        n = len(digits)
        if n == 0: return []
        res = []
        def dfs(path, depth):
            if depth == n:
                return res.append(''.join(path[:]))
            
            for ch in MAPPING[int(digits[depth])]:
                path.append(ch)
                dfs(path, depth+1)
                path.pop()

        dfs([], 0)
        return res

39. 组合总和

这里需要注意的点是用一个start参数来追踪下一次递归的开始，因为如果强制规定顺序遍历的话，可能会出现重复的答案，比如 [2, 2, 3] 与 [3, 2, 2] 是同一个答案，直接遍历的话就会出现大量重复。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        res = []

        def dfs(path, total, start):
            if total == target:
                res.append(path[:])
                return 
            if total > target:
                return
            
            for i in range(start, n):
                path.append(candidates[i])
                dfs(path, total+candidates[i], i)
                path.pop()

        dfs([], 0, 0)
        return res

给新手的回溯法总结：

1）当组合中允许元素重复：则迭代的起始值就是i，每次递增

2）当组合中不允许重复：迭代的起始值是i + 1，每次递增

3）当这是排列不是组合：迭代的起始值是传进去的start（初始位），每次都从头开始遍历所有元素

22. 括号生成

没有想到思路的一道题。题解灵性的把左右括号在某一位置的选择看成是一个选/不选的问题，但是这个问题有约束：

左括号的数量一定要在每个时刻大于右括号的数量；
左括号和右括号最后加在一起一定要等于2*n。事实上当左括号数量为n的时候，后面就只能填右括号了。

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []

        def dfs(left_count, right_count, path):
            if left_count + right_count == 2*n:
                res.append("".join(path[:]))
                return
            
            if left_count < n:
                path.append("(")
                dfs(left_count+1, right_count, path)
                path.pop()
            
            if right_count < left_count:
                path.append(")")
                dfs(left_count, right_count+1, path)
                path.pop()
        
        dfs(0,0,[])
        return res

79. 单词搜索

和岛屿数量差不多，主要就是要找一个联通的道路同时道路上每一个元素都和word相对应。同时需要注意走过的路就不能再走了，第一次WA就是因为没有用visited这个数组来统计走过的路径。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        def check(i, j):
            return (0<=i<=m-1) and (0<=j<=n-1)

        def dfs(i, j, depth):
            if not check(i, j) or visited[i][j] or board[i][j] != word[depth]:
                return False
            if depth == len(word) - 1 and board[i][j] == word[depth]:
                return True

            visited[i][j] = True
            res  = (dfs(i+1, j, depth+1) or \
            dfs(i-1, j, depth+1) or \
            dfs(i, j-1, depth+1) or \
            dfs(i, j+1, depth+1))
            visited[i][j] = False
            return res

        for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False

131. 分割回文串

枚举每一个子串的末尾位置，如果是回文串就加入，然后把开始位置挪动到原来的末尾，枚举完成之后复原；如果不是就继续往后遍历。

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        res = []
        def check(path):
            s_in = ''.join(path)
            left, right = 0, len(s_in)-1
            while left <= right:
                if s_in[left] != s_in[right]:
                    return False
                left += 1
                right -= 1
            return True

        def dfs(start, path):
            if start == n:
                res.append(path[:])
                return
            
            for i in range(start, n):
                substring = s[start:i+1]
                if check(substring):
                    path.append(substring)
                    dfs(i+1, path)
                    path.pop()

        dfs(0, [])
        return res

51. N 皇后

根据题目的意思，对于每一行有且仅有一个皇后会出现，因此在dfs遍历的时候，可以把行号作为变量进行输入，然后遍历该行所有的列，如果满足条件就是一个合理的位置，dfs遍历下一行。同时恢复状态的时候需要进行回溯复原。

为了记录哪些列，以及正负对角线能够放皇后，采用了三个 set() 进行记录。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        board = [["." for _ in range(n)] for _ in range(n)]
        flag_board = [[False for _ in range(n)] for _ in range(n)]

        res = []
        col, dig1, dig2 = set(), set(), set()

        def dfs(i):
            if i == n:
                return res.append(["".join(r) for r in board])

            for j in range(n):
                if j not in col and (i-j) not in dig1 and (i+j) not in dig2:
                    board[i][j] = "Q"
                    col.add(j)
                    dig1.add(i-j)
                    dig2.add(i+j)
                    dfs(i+1)
                    col.remove(j)
                    dig1.remove(i-j)
                    dig2.remove(i+j)
                    board[i][j] = "."
        
        dfs(0)
        return res

35. 搜索插入位置

二分查找，没找到就返回最后 left==right 的时候指向的位置。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        def binary_search(nums, target):
            left, right = 0, len(nums)-1
            while left <= right:
                mid = (left+right) // 2
                if nums[mid] > target:
                    right = mid-1
                elif nums[mid] < target:
                    left = mid+1
                else: return mid
            
            return left
        
        return binary_search(nums, target)

74. 搜索二维矩阵

正确的做法是两次二分查找，不知道为什么我这个也击败100%了

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])

        def binary_search(nums, target):
            left, right = 0, len(nums)-1 
            while left <= right:
                mid = (left+right) // 2
                if nums[mid] == target: return True
                if nums[mid] > target: right = mid -1
                else: left = mid + 1
            return False

        for i in range(m):
            if matrix[i][n-1] < target:
                continue
            return binary_search(matrix[i], target)
        
        return False

34. 在排序数组中查找元素的第一个和最后一个位置

用两次二分查找分别的找到左端点和右端点，然后判断是不是真的找到了符合要求的端点（就是可能不存在这个数字）

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binary_search_left(nums, target):
            left, right = 0, len(nums)-1
            while left <= right:
                mid = (left+right) // 2
                if nums[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1
            return left
        
        def binary_search_right(nums, target):
            left, right = 0, len(nums)-1
            while left <= right:
                mid = (left+right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right
        
        left = binary_search_left(nums, target)
        right = binary_search_right(nums, target)
        if left <= right and right < len(nums) and nums[left] == target and nums[right] == target:
            return [left, right]
        else:
            return [-1, -1]

33. 搜索旋转排序数组

无论如何，在mid分开的部分总有一边是有序的。

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left+right) // 2
            if nums[mid] == target: return mid

            if nums[0] <= nums[mid]:
                if nums[left] <= target <= nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
            else:
                if nums[mid] <= target <= nums[len(nums)-1]:
                    left = mid+1
                else:
                    right = mid-1
        
        return -1

153. 寻找旋转排序数组中的最小值

和最后一个元素比，如果比它大，那么肯定是左边界大了；如果比它小，右边界大了。夹逼到最后的结果。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        if nums[0] <= nums[-1]: return nums[0]

        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left+right) // 2
            if nums[mid] > nums[-1]:
                left = mid + 1
            else:
                right = mid - 1
        
        return nums[left]

4. 寻找两个正序数组的中位数

对于两个数组长度之和为奇数的情况，中位数是最中间的那个数字；对于偶数的情况，中位数为中间两个数字之和除以2。

本质上就是找到一个分界，让这个分界左边的最大元素比右边的最小元素都要小，如下图所示：

2 4 | 6 8
			i
1 3 5 | 7 9
        j

然后再根据长度的奇偶性质来判断中位数是哪一个。在这里为了方便我们判断，我们让分界左边的部分始终比右边的部分长度要大1，这样的话无论对于奇数还是偶数的情况，左边部分的长度都可以写成 (m+n+1)//2 ，因为会自动的向下取整。同时让上面的数组始终为长度较小的那一个。

有了这样的前置知识之后，我们让这两个数组分界线的右边边界分别叫做 i, j ，那么我们只需要二分查找到其中一个边界，另一个就可以用长度减去该边界即可。

在这里我们需要让它满足：

$$
nums[i-1] <= nums[j] \space && \space nums[j-1] <= nums[i]
$$

再根据奇偶性质得到最终的中位数的结果。

注意这里有一些边界情况需要讨论，比如 i 或者 j 为数组的左右边界的情况，这样再访问 i-1 或 j-1 就会有越界的风险。用一个最大值/最小值来处理这样的越界情况即可。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        m, n = len(nums1), len(nums2)
        if m > n:
            nums1, nums2 = nums2, nums1
            m, n = n, m
        left_size = (m+n+1)//2
        left, right = 0, m 
        while left < right:
            i = (left+right+1) // 2
            j = left_size - i
            if nums1[i-1] > nums2[j]:
                right = i - 1
            else:
                left = i
        i = left
        j = left_size - i
        nums1_left = nums1[i-1] if i > 0 else float("-inf")
        nums1_right = nums1[i] if i < m else float("inf")
        nums2_left = nums2[j-1] if j > 0 else float("-inf")
        nums2_right = nums2[j] if j < n else float("inf")

        if (m+n) % 2 == 1:
            return max(nums1_left, nums2_left)
        else:
            return (max(nums1_left, nums2_left)+min(nums1_right, nums2_right)) / 2

时间复杂度 O(log(m+n))

20. 有效的括号

用一个栈来存储左括号，如果是右括号，那么就看是否和栈顶元素相匹配，匹配就把栈顶元素 pop 出来，然后继续；不匹配就直接返回 False

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {
            ")": "(",
            "}": "{",
            "]": "["
        }
        stack = []

        for ch in s:
            if ch in pairs:
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:
                stack.append(ch)
        
        return False if len(stack) > 0 else True

155. 最小栈

用两个栈分别来维护最小值和当前值，这两个栈是保持同步一致的

class MinStack:

    def __init__(self):
        self.cur_stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        if not self.min_stack:
            self.min_stack.append(val)
        else:
            self.min_stack.append(min(val, self.min_stack[-1]))

        self.cur_stack.append(val)

    def pop(self) -> None:
        self.cur_stack.pop()
        self.min_stack.pop()
        
    def top(self) -> int:
        return self.cur_stack[-1]

394. 字符串解码

用两个栈分别来存储数字和之前的字符串，然后分类讨论，按照对应的情况处理左右括号进行入栈出栈即可。

class Solution:
    def decodeString(self, s: str) -> str:
        num_stack, str_stack = [], []
        res = ""
        cur_num = 0
        cur_str = ""
        for ch in s:
            if ch.isdigit():
                cur_num = cur_num*10 + int(ch) # 处理多位数字的情况，比如105这种
            elif ch == "[":
                num_stack.append(cur_num)
                str_stack.append(cur_str)
                cur_num = 0
                cur_str = ""
            
            elif ch == "]":
                num = num_stack.pop()
                prev = str_stack.pop()
                cur_str = prev + num*cur_str
            
            else:
                cur_str += ch
        
        return cur_str

739. 每日温度

栈存的是温度的索引，直到找到一个比栈顶元素大的温度，再出栈处理。

为什么可行：遍历的时候每一次都会查看栈顶元素和当前温度的大小，如果入栈的话一定是按照温度大小来进行排列的。

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        answer = [0]*n
        stack = []

        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                answer[stack[-1]] = i - stack[-1]
                stack.pop()
            stack.append(i)
        return answer

84. 柱状图中最大的矩形

这道题目和上一题每日温度有相似之处。重点在于，这里使用一个单调栈来存高度的下标，直到遇见了比当前栈顶元素小的高度的时候，此时此刻就可以确定由当前栈顶元素围成的矩形面积了：栈顶元素出栈，所对应的高度为当前高度；宽度为当前位置到下一个栈顶元素之间的距离。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        new_height = [0] + heights + [0] # 增加两个哨兵节点方便后续处理
        n = len(heights)
        stack = [0]
        max_area = 0
        for i in range(1, n+2):
            while stack and new_height[stack[-1]] > new_height[i]:
                cur_height_index = stack.pop()
                cur_height = new_height[cur_height_index]
                width = i - stack[-1] - 1
                max_area = max(max_area, width*cur_height)
            stack.append(i)
        return max_area

215. 数组中的第K个最大元素

写一个快排就行了。

这是空间复杂度为 O(n) 的写法，简单易懂而且还能过；

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_sort(nums, k):
            pivot = random.choice(nums)
            bigger, smaller, equal = [], [], []
            for num in nums:
                if num > pivot:
                    bigger.append(num)
                elif num == pivot:
                    equal.append(num)
                else:
                    smaller.append(num)

            if k <= len(bigger):
                return quick_sort(bigger, k)
            elif len(bigger) < k <= len(bigger) + len(equal):
                return pivot
            else: 
                return quick_sort(smaller, k - len(nums) + len(smaller))
        
        return quick_sort(nums, k)

这是空间复杂度为 O(1) 的写法，比较抽象，但是空间性能优秀。

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        n=len(nums)
        def partition(nums, left, right):
            pivot_index = random.randrange(left, right+1)
            nums[left], nums[pivot_index] = nums[pivot_index], nums[left]
            pivot = nums[left]

            i, j = left + 1, right

            while True:
                while i<=j and nums[j] > pivot:
                    j -= 1
                while i<=j and nums[i] < pivot:
                    i += 1
                if i >= j: break
                nums[i], nums[j] = nums[j], nums[i]
                j -= 1
                i += 1
            nums[left], nums[j] = nums[j], nums[left]
            return j
        
        left, right = 0, n-1
        while left<=right:
            index = partition(nums, left, right)
            if index == n-k: return nums[index]
            elif index < n-k: 
                left = index+1
            else:
                right = index-1

347. 前 K 个高频元素

快速排序写法，平均复杂度 O(n) ，最坏复杂度 O(n^2)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = {}
        for num in nums:
            cnt[num] = cnt.get(num, 0) + 1
        res, li = [], []
        for count in cnt.values():
            li.append(count)
        
        def partition(nums, left, right):
            pivot_index = random.randrange(left, right+1)
            nums[left], nums[pivot_index] = nums[pivot_index], nums[left]
            pivot = nums[left]
            i, j = left+1, right

            while True:
                while i<=j and nums[j] < pivot:
                    j -= 1
                while i<=j and nums[i] > pivot:
                    i += 1
                if i >= j: break
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
            nums[left], nums[j] = nums[j], nums[left]
            return j

        def quick_sort(nums, left, right):
            while left <= right:
                index = partition(nums, left, right)
                if index == k-1: break # 前面都是出现次数比k还大的
                elif index < k-1:
                    left = index + 1
                else:
                    right = index - 1
        quick_sort(li, 0, len(li)-1)
        for key, v in cnt.items():
            if v >= li[k-1]:
                res.append(key)
        
        return res

桶排序， 0(n) 复杂度

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        cnt = {}
        for num in nums:
            cnt[num] = cnt.get(num, 0) + 1
        bucket = [[] for _ in range(len(nums)+1)]
        res = []
        for key, value in cnt.items():
            bucket[value].append(key)
        
        for i in range(len(bucket)-1, -1, -1):
            if bucket[i] != [] and len(res) < k:
                for num in bucket[i]:
                    res.append(num)
                    if len(res) == k: break
        return res

295. 数据流的中位数

用两个堆来进行维护，通过两个互补的堆，将中位数放在堆顶位置，插入保持平衡，中位数 O(1) 拿到。大根堆负责较小一侧，小根堆负责较大一侧，插入时分类、插入后平衡，堆顶即中位数。

import heapq
class MedianFinder:
    def __init__(self):
        self.big_heap = []
        self.small_heap = []

    def addNum(self, num: int) -> None:
        if not self.big_heap or num < -(self.big_heap[0]):
            heapq.heappush(self.big_heap, -num)
        else:
            heapq.heappush(self.small_heap, num)
        
        if len(self.big_heap) > len(self.small_heap) + 1:
            heapq.heappush(self.small_heap, -heapq.heappop(self.big_heap))
        elif len(self.small_heap) > len(self.big_heap):
            heapq.heappush(self.big_heap, -heapq.heappop(self.small_heap))

    def findMedian(self) -> float:
        if (len(self.small_heap)+len(self.big_heap)) % 2 != 0:
            return -self.big_heap[0]
        else:
            return (-self.big_heap[0] + self.small_heap[0]) / 2

121. 买卖股票的最佳时机

用一个数字维护前面的最小值，用一个数字维护当前利润的最大值，就可以解决了。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cur_min, ans = float("inf"), 0
        for p in prices:
            if p < cur_min: cur_min = p
            ans = max(ans, p-cur_min)
        return ans if cur_min != float("inf") else 0

55. 跳跃游戏

每次能够到达的最远距离为 max（当前所在的位置+每次能够移动的最大值，之前的最远到达距离）

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        reachable = 0
        for i, step in enumerate(nums):
            if reachable < i:
                return False
            reachable = max(reachable, i+step)
            if reachable > len(nums):
                return True
        return True

45. 跳跃游戏 II

和I一样，先维护一个能到达的最大值，如果说当前的坐标是跟之前维护的最大值相同。那么就证明需要走出最大的一步到达这里了，所以需要的步数+1

class Solution:
    def jump(self, nums: List[int]) -> int:
        cur_max, furtherest, steps = 0, 0, 0
        for i in range(len(nums)-1):
            cur_max = max(cur_max, i+nums[i])
            if i == furtherest:
                steps += 1
                furtherest = cur_max
        return steps

763. 划分字母区间

存储所有字母的最后出现的位置，如果当前的索引和前面所有字母的最大最后出现位置一样，证明是一个最大的区间，返回区间长度，重置prev数值

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last, res = {}, []
        for i, c in enumerate(s):
            last[c] = i
        
        res, prev, furtherest = [], 0, 0
        for i, c in enumerate(s):
            furtherest = max(furtherest, last[c])
            if i == furtherest:
                res.append(i - prev + 1)
                prev = i+1
        
        return res

70. 爬楼梯

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1: return 1
        dp = [0] * n
        dp[0] = 1
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n-1]

118. 杨辉三角

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 1: return [[1]]
        res = [[1]]
        for i in range(2, numRows+1):
            cur = [1]
            last = res[-1]
            for j in range(1, i-1):
                cur.append(last[j]+last[j-1])
            cur.append(1)
            res.append(cur)
        return res

198. 打家劫舍

$$
dp[i] = max(dp[i-2]+nums[i], dp[i-1])
$$

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i] = max(dp[i-2]+cur, dp[i-1])
        dp = [0] * len(nums)
        n = len(nums)
        if n == 1: return nums[0]
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i-2]+nums[i], dp[i-1])
        
        return dp[n-1]

279. 完全平方数

最小的肯定是减去上一个的最小值减去一个完全平方数。

$$
dp[i] = min(dp[i], dp[i-j*j]+1)
$$

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float("inf")] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            j = 1
            while i-j*j >= 0:
                dp[i] = min(dp[i], dp[i-j*j]+1)
                j += 1
        return dp[n]

322. 零钱兑换

和前面的完全平方数相似

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0: return 0
        dp = [float("inf")] * (amount+1)
        dp[0] = 0
        for coin in coins:
            for i in range(coin, amount+1):
                dp[i] = min(dp[i], dp[i-coin]+1)
        return dp[amount] if dp[amount]!=float("inf") else -1

139. 单词拆分

记忆化搜索，遍历过的串就存起来就行了。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        memo = {}
        def dfs(s):
            if len(s) == 0: return True
            if s in memo:
                return memo[s]
            for word in wordDict:
                if s[:len(word)] == word:
                    if dfs(s[len(word):]):
                        memo[s] = True
                        return True
            memo[s] = False
            return False
        return dfs(s)

动态规划

dp[i] 表示 s 的前 i 个字符能否被字典切分；对于每个可切分的位置 i，尝试用字典中的单词向后扩展，如果 s[i:j] 是单词，就让 dp[j] = True。

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        wordDict = set(wordDict)
        dp = [True] + [False] * n
        max_len = 0
        for word in wordDict:
            max_len = max(max_len, len(word))
        for i in range(n):
            for j in range(i+1, min(n+1, i+max_len+1)):
                if s[i:j] in wordDict and dp[i]:
                    dp[j] = True
        return dp[n]

300. 最长递增子序列

题目只要求写出数值即可，这里同时还打印出来了序列应该是什么样的。

具体做法是用一个dp数组来表示当前数字可以到达的最大递增子序列。对于每一个位置，都从0开始遍历到当前位置，如果满足 $nums[j] < nums[i] and dp[j]+1 > dp[i]$ 就是更新当前的dp[i]。这里的时间复杂度是 O(n)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1]*n # 表示当前的数字能够达到的最长递增子序列
        parent = [-1]*n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i] and dp[j]+1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j

        max_length = max(dp)
        max_index = dp.index(max_length)

        res_sequence = []
        while max_index!=-1:
            res_sequence.append(nums[max_index])
            max_index = parent[max_index]
        res_sequence.reverse()
        print(res_sequence)
        return max_length

还可以用贪心+二分查找的形式来做这道题目。

对于最长递增子序列，我们肯定是希望他增长的速度是比较慢的。那么就用一个tails数组来维护 tails[k] 表示：所有长度为 k+1 的递增子序列中，末尾元素最小是多少。对于nums里面的元素，每一次都是用二分查找在tails里面第一个 大于等于它 的位置。如果是在tails的最后，也就是 pos==len(tails) 的这种情况，那么就这个元素就是目前的最大值；如果能够找到某个位置，那么就把那个位置原来的数字变更为当前的元素。时间复杂度为 O(nlogn)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        tails = []

        def binary_search(nums, x):
            if not nums: return 0
            left, right = 0, len(nums)-1
            while left <= right:
                mid = (left+right) // 2
                if nums[mid] < x:
                    left = mid+1
                else:
                    right = mid-1
            return left

        for num in nums:
            position = binary_search(tails, num)
            if position == len(tails):
                tails.append(num)
            else:
                tails[position] = num
        return len(tails)

152. 乘积最大子数组

对于都是正数的情况下，很明显能够推出是 $dp[i] = max(dp[i-1]*nums[i], nums[i])$ 。但是由于这道题目有负数，那么就可以额外用一个数组来存最小的数字，每次都更新最大值和最小值，这样对于负数的情况也能正确的更新最大的乘积。

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        if len(nums) == 1: return nums[0]
        n = len(nums)
        dp_max = [1]*n
        dp_min = [1]*n
        for i in range(n):
            dp_max[i] = max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
            dp_min[i] = min(dp_min[i-1]*nums[i], dp_max[i-1]*nums[i], nums[i])
        return max(dp_max)

416. 分割等和子集

记忆化搜索，先排序，然后记忆化搜索，最后成功的TLE了。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        used = [False] * n
        target = sum(nums) / 2
        nums.sort(reverse=True) # 从大到小开始遍历

        def dfs(i, cur_sum):
            if cur_sum == target: return True
            if cur_sum > target: return False
            for j in range(i, n):
                if used[j]:
                    continue
                else:
                    used[j] = True
                    if dfs(j+1, cur_sum+nums[j]):
                        return True
                    used[j] = False
            return False
        
        return dfs(0, 0)

正确的做法是，这道题是一个01背包问题，按照GPT老师给的套路模版就很快能做出来正确的答案了。

我们用一个数组dp[j]来记录「、是否能用 nums 中的部分数字凑出和 j，然后依次处理数组中的每个数，并从 大到小 更新dp，最终检查 dp[target] == True

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        nums.sort(reverse=True)
        total = sum(nums)
        if total % 2 != 0:
            return False
        target = total // 2 
        dp = [False]*(target+1)
        dp[0] = True
        for num in nums:
            for j in range(target, num-1, -1):
                dp[j] = dp[j] or dp[j-num]
        return dp[target]

32. 最长有效括号

立马能够想到的思路就是先用栈遍历一遍，找到能够匹配的位置，用另一个数组来进行标记匹配性即可，最后算一下数组最长为True的子序列就行了：

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        can = [False]*n
        stack = []
        for i, ch in enumerate(s):
            if ch == "(":
                stack.append((i, ch))
            else:
                if stack and stack[-1][1] == "(":
                    prev_i, prev_ch = stack.pop()
                    can[i] = True
                    can[prev_i] = True
                else:
                    continue
        dp = [0]*n
        for i in range(n):
            if can[i] == True:
                dp[i] = dp[i-1]+1
            else:
                continue
        return max(dp)

但是实际上可以在进出栈的同时就计算出来需要的长度。用一个栈来存索引，并且栈底永远放一个“最后一个不可能匹配的位置”标记。

算法如下：

遍历字符串
遇到 '(' → 把索引压栈
遇到 ')' → 尝试匹配：
- 若栈顶是 '(' 的索引 → 出栈并更新最大长度
- 若无法匹配 → 把当前 ')' 的索引入栈作为新的“断点”

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        stack = [-1]
        max_length = 0
        for i in range(n):
            if s[i] == "(":
                stack.append(i)
            else:
                stack.pop()
                if stack:
                    max_length = max(max_length, i - stack[-1])
                else:
                    stack.append(i)
        return max_length

62. 不同路径

注意第一行和第一列只有一种走法，初始化正确即可。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0 for i in range(n)] for j in range(m)]
        dp[0][0] = 1
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        for i in range(m-1):
            for j in range(n-1):
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1]
        return dp[m-1][n-1]

64. 最小路径和

和上面那题一样

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1, m):
            dp[i][0] = grid[i][0] + dp[i-1][0]
        for j in range(1, n):
            dp[0][j] = grid[0][j] + dp[0][j-1]
        for i in range(m-1):
            for j in range(n-1):
                dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j]) + grid[i+1][j+1]
        return dp[m-1][n-1]

5. 最长回文子串

中心拓展，首先对于奇数回文串的情况，有n个中心可以扩展；对于偶数回文串的情况，相当于是对输入s的每个空隙之间进行拓展，所有有n-1个中心可以拓展，故拓展中心一共有 2n-1 个中心。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        res = []
        n = len(s)
        max_length = 0
        for i in range(2*n-1):
            left = i // 2
            right = left + i % 2
            while left >=0 and right <= n-1 and s[left] == s[right]:
                if right-left+1 > max_length:
                    max_length = right-left+1
                    res = s[left: right+1]
                left -= 1
                right += 1
        return res

1143. 最长公共子序列

dp[i][j] 数组表示从 text[:i] 到 text[:j] 能够得到的最长公共子序列的长度。那么对于该位置，如果相等，那么就是从上一个状态挪过来+1；如果不相等，那么就是选择最大的之前状态。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1, n2 = len(text1), len(text2)
        dp = [[0 for i in range(n2+1)] for j in range(n1+1)]
        for i in range(1, n1+1):
            for j in range(1, n2+1):
                if text1[i-1] == text2[j-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[n1][n2]

72. 编辑距离

dp[i][j] 数组表示把 word1 的前 i 个字符转换成 word2 的前 j 个字符的最小操作数。本题一共有三种操作，插入，删除与替换。分别可以用三种不同的方式进行表示：

插入： $dp[i][j] = dp[i][j-1]+1$
删除： $dp[i][j] = dp[i-1][j]+1$
替换： $dp[i][j] = dp[i-1][j-1] + 1$

那么当 word1[i] == word2[j] 的时候，就不需要进行任何的操作，直接让 $dp[i][j] = dp[i-1][j-1]$ 即可。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1, n2 = len(word1), len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        for i in range(n1 + 1):
            dp[i][0] = i
        for j in range(n2 + 1):
            dp[0][j] = j
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 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] + 1,     # 插入
                        dp[i - 1][j - 1] + 1  # 替换
                    )

        return dp[n1][n2]

136. 只出现一次的数字

出现两次的数字异或之后就是0了，所以直接遍历整个数组进行异或，最后得到的就是只出现一次的数字。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        if len(nums) == 1: return nums[0]
        ans = nums[0]
        for i in range(1, len(nums)):
            ans = ans^nums[i]
        return ans

169. 多数元素

留下来的最终的肯定是投票数最多的。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num  # 更换候选人
            if num == candidate:
                count += 1
            else:
                count -= 1
        return candidate

75. 颜色分类

由于只有三种颜色，遍历数组排序好其中的两个就行了。

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        ptr = 0
        n = len(nums)
        for i in range(n):
            if nums[i] == 0:
                nums[i], nums[ptr] = nums[ptr], nums[i]
                ptr += 1
        # 此时ptr前面应该全都是0了
        for i in range(ptr, n):
            if nums[i] == 1:
                nums[i], nums[ptr] = nums[ptr], nums[i]
                ptr += 1

31. 下一个排列

从右往左找第一个递增对 x[i] < x[i+1]
找到以后在 i 之后寻找第一个大于 x[i] 的数字
然后交换这两个数字，并把 i 后面的序列全部翻转

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n == 1: return nums[0]
        index = -1
        for i in range(n-2, -1, -1):
            if nums[i] < nums[i+1]:
                index = i
                break
        if index == -1: return nums.reverse()
        for j in range(n-1, index, -1):
            if nums[j] > nums[index]:
                nums[j], nums[index] = nums[index], nums[j]
                break
        nums[index+1:] = reversed(nums[index+1:])
        return nums

287. 寻找重复数

最简单的方法就是排序然后遍历，时间复杂度 O(nlogn)

这里用快慢指针实现 O(n) 的做法。实际上就是把这一题看作环形链表来做。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        head = 0
        while head!=slow:
            head = nums[head]
            slow = nums[slow]
        return slow