回溯法

回溯法 ：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解的话（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。

回溯 or dp

1.首先看取值范围，递归回溯一维数组，100就是深度的极限了（何况本题是100²） 
2.如果是求走迷宫的【路径】，必然是回溯；如果是走迷宫的【路径的条数】，必然是dp--------(这个竟然屡试不爽！！！！)

39. 组合总和

• 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        n = len(candidates)
        candidates = sorted(candidates) # 排序

        def cal(index, current_sum, current_val, current_res):
            if index >= n or current_sum > target: # 当循环到底或超过目标值
                return
            if current_sum == target:
                result.append(current_res)
            for i in range(n):
                if candidates[i] < current_val: # 当前选取的值不能比上一个选取的值大 去重
                    continue
                cal(i, current_sum+candidates[i], candidates[i], current_res + [candidates[i]])

        cal(0, 0, candidates[0], [])
        return result
    
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        sel_list = []
        def cal(num, target, sel_list, cur_list=[]):
            if len(cur_list) >= 2:
                if cur_list[-1] > cur_list[-2]:
                    return
            if target == 0:
                sel_list.append(cur_list)
                return
            if target < 0:
                return
            for num in candidates:
                cal(num, target - num, sel_list, cur_list + [num])

        candidates.sort()
        a = cal(0, target, sel_list, [])

        return sel_list

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        sel_list = []
        def cal(target, sel_list, cur_list=[], index=0):
            if target == 0:
                sel_list.append(cur_list)
                return
            if target < 0:
                return
            if index == len(candidates):
                return
            for cur in range(index, len(candidates)):
                // 核心点 剪枝
                if cur > index and candidates[cur-1] == candidates[cur]:
                    continue
                cal(target - candidates[cur], sel_list, cur_list + [candidates[cur]], cur + 1)

        candidates.sort()
        a = cal(target, sel_list, [], 0)

        return sel_list

电话号码的字母组合

• 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

  给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

def letterCombinations(self, digits: str) -> List[str]:
        dict_letter = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"]
        }
        if not digits: return []
        array = [""]
        for letter in digits:
            array = [y+x for x in dict_letter[letter] for y in array]
            # itertools.product(A, B) <=> ((x, y) for x in A for y in B) 笛卡尔积，嵌套for循环
        return array

排列组合迭代器

itertools
product("ABCD", "ABCD") # AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD 笛卡尔积
permutations("ABCD", 2) # AB AC AD BA BC BD CA CB CD DA DB DC 元祖所有可能排列 无重复
combinations("ABCD", 2) # AB AC AD BC BD CD 有序元祖 无重复
combinations_with_replacement("ABCD", 2) # AA AB AC AD BB BC BD CC CD DD 有序元祖 可重复

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s
        if len(p) > 1 and p[1] == '*':
            if s and (p[0] == '.' or s[0] == p[0]):
                return self.isMatch(s, p[2:]) or self.isMatch(s[1:], p)
            return self.isMatch(s, p[2:])
        if s and (p[0] == '.' or s[0] == p[0]):
            return self.isMatch(s[1:], p[1:])
        return False

37. 解数独

编写一个程序，通过填充空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        need_write = []
        row = {}
        colume = {}
        line = {}

        def dfs(index):
            if index == len(need_write):
                return True
            i, j = need_write[index]
            _index = "%d%d" % (i // 3, j // 3)

            for num in range(1, 10):
                num = str(num)
                if i not in row:
                    row[i] = []
                if j not in colume:
                    colume[j] = []
                if _index not in line:
                    line[_index] = []
                if num not in row[i] and num not in colume[j] and num not in line[_index]:
                    
                    row[i].append(num)
                    colume[j].append(num)
                    line[_index].append(num)

                    if dfs(index+1):
                        board[i][j] = num
                        return True
                    else:
                        row[i].remove(num)
                        colume[j].remove(num)
                        line[_index].remove(num)


        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j] != ".":
                    if i not in row:
                        row[i] = [board[i][j]]
                    else:
                        if board[i][j] in row[i]:
                            return False
                        row[i].append(board[i][j])
     
                    if j not in colume:
                        colume[j] = [board[i][j]]
                    else:
                        if board[i][j] in colume[j]:
                            return False
                        colume[j].append(board[i][j])
        
                    index = "%d%d" % (i // 3, j // 3)
                    if index not in line:
                        line[index] = [board[i][j]]
                    else:
                        if board[i][j] in line[index]:
                            return False
                        line[index].append(board[i][j])
                else:
                    need_write.append((i, j))
        dfs(0)

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]
 class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 先排序
        nums.sort()
        def cal(all_list, current_list, boolean_array):
            if current_list in all_list:
                return
            if len(current_list) == len(nums):
                all_list.append(current_list.copy())
                return
            for i in range(len(nums)):
                # 去重
                if boolean_array[i] or (i > 0 and nums[i] == nums[i-1] and not boolean_array[i-1]):
                    continue
                current_list.append(nums[i])
                boolean_array[i] = True
                cal(all_list, current_list, boolean_array)
                boolean_array[i] = False
                current_list.pop(-1)
        all_list = []
        # 布尔数组
        boolean_array = [False] * len(nums)
        cal(all_list, [], boolean_array)
        return all_list

60. 排列序列

给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        index_array = [1 for _ in range(n + 1)]
        for i in range(1, n):
            index_array[i] = index_array[i-1]*i
        used = set()
        path = []
        def cal(k, index):
            if index == n:
                 return
            cut = index_array[n-index-1]
            for i in range(1, n+1):
                if i in used:
                    continue
                if k > cut:
                    k -= cut
                    continue
                used.add(i)
                path.append(i)
                cal(k, index+1)
        cal(k, 0)
        return str(reduce(lambda x, y: str(x)+str(y), path)

51. N 皇后

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def generateBoard():
            board = list()
            for i in range(n):
                row[queens[i]] = "Q"
                board.append("".join(row))
                row[queens[i]] = "."
            return board

        def backtrack(row: int):
            if row == n:
                board = generateBoard()
                solutions.append(board)
            else:
                for i in range(n):
                    # 三种情况 不在一列 不在斜线上
                    if i in columns or row - i in diagonal1 or row + i in diagonal2:
                        continue
                    # 用一位数组表示二维 太巧妙 索引表示行 索引的值表示列
                    queens[row] = i
                    columns.add(i)
                    diagonal1.add(row - i)
                    diagonal2.add(row + i)
                    backtrack(row + 1)
                    columns.remove(i)
                    diagonal1.remove(row - i)
                    diagonal2.remove(row + i)
                    
        solutions = list()
        queens = [-1] * n
        columns = set()
        diagonal1 = set()
        diagonal2 = set()
        row = ["."] * n
        backtrack(0)
        return solutions

递归

50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的 n 次幂函数。
示例 1:
输入: 2.00000, 10
输出: 1024.00000
    
输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/2^2 = 1/4 = 0.25
 class Solution:
    def myPow(self, x: float, n: int) -> float:
  
        def cal(x, n):
            if n == 0:
                return 1
            value = cal(x, n//2)
            return value * value if n % 2 == 0 else value * value * x
        return cal(x, n) if n >= 0 else 1/cal(x, -n)

二叉树

中序遍历

tree_list = []
def cal(root, tree_list):
    if root:
        cal(root.left, tree_list)
        tree_list.append(root.val)
        cal(root.right, tree_list)

二叉树的序列化与反序列化

class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        result = []
        def cal(node):
            if node:
                result.append(node.val)
                cal(node.left)
                cal(node.right)
            else:
                result.append("N")
        cal(root)
        # print(result)
        return result

    def deserialize(self, data):
        """Decodes your encoded data to tree.        
        :type data: str
        :rtype: TreeNode
        """
        def cal(data):
            if data[0] == "N": # 结束标志
                data.pop(0)
                return None
            root = TreeNode(data[0])
            data.pop(0)
            root.left = cal(data)
            root.right = cal(data)
            return root
        node = cal(data)
        return node

95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def generateTrees(start, end):
            if start > end:
                return [None,]
            
            allTrees = []
            for i in range(start, end + 1):  # 枚举可行根节点
                # 获得所有可行的左子树集合
                leftTrees = generateTrees(start, i - 1)
                
                # 获得所有可行的右子树集合
                rightTrees = generateTrees(i + 1, end)
                
                # 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
                for l in leftTrees:
                    for r in rightTrees:
                        currTree = TreeNode(i)
                        currTree.left = l
                        currTree.right = r
                        allTrees.append(currTree)
            
            return allTrees
        
        return generateTrees(1, n) if n else []

二分法

bisect模块

• bisect.bisect_left(array, target, lo=0, hi=None) 找到目标值应该插入的位置(找到target，就是最左边traget的位置，没找到target，就是处于左小右大的位置)

def bisect_left(a, x, lo=0, hi=None):
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid + 1
        elif a[mid] == x: # 找到最左边的位置
            hi = mid
        elif a[mid] > x:
            hi = mid
    return lo
bisect.bisect_left([1,1,2,2,3,4,5], 1) # 0
bisect.bisect_left([1,1,2,2,3,4,5], 0) # 0
bisect.bisect_left([1,1,2,2,3,4,5], 6) # 7

• bisect.bisect_right(array, target, lo=0, hi=None) 找到目标值应该插入到位置(找到target，就是最右边目标值的下一个位置，没找到目标值，就是处于左小右大的位置)

def bisect_right(a, x, lo=0, hi=None):
    hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x:
            lo = mid + 1
        elif a[mid] == x: # 找到最右边的位置
            lo = mid + 1
        elif a[mid] > x:
            hi = mid
    return lo
bisect.bisect_right([1,1,2,2,3,4,5], 1) # 2
bisect.bisect_right([1,1,2,2,3,4,5], 0) # 0
bisect.bisect_right([1,1,2,2,3,4,5], 6) # 7

1011. 在 D 天内送达包裹的能力

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
输入：weights = [1,2,3,4,5,6,7,8,9,10], D = 5
输出：15

# 找下界问题 可以用二分法
class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        l = max(weights)
        r = sum(weights)

        def is_right(weight_list, val, day):
            sum_package = 0
            d = 1
            for i in range(len(weight_list)):
                if sum_package + weight_list[i] <= val:
                    sum_package += weight_list[i]
                else:
                    d += 1
                    sum_package = weight_list[i]
                if d > day:
                    return False
            return True

        while l < r:
            mid = (l+r)//2
            if is_right(weights, mid, D):
                r = mid
            else:
                l = mid + 1
        return l

有序数组中的单一元素

• 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

def singleNonDuplicate(self, nums: List[int]) -> int:
    lo = 0
    hi = len(nums) - 1   
    while lo < hi:
        mid = lo + (hi - lo) // 2
        halves_are_even = (hi - mid) % 2 == 0
        if nums[mid + 1] == nums[mid]:
            if halves_are_even:
                lo = mid + 2
            else:
                hi = mid - 1
        elif nums[mid - 1] == nums[mid]:
            if halves_are_even:
                hi = mid - 2
            else:
                lo = mid + 1
        else:
            return nums[mid]
    return nums[lo]

33. 搜索旋转排序数组

给你一个升序排列的整数数组 nums ，和一个整数 target 。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
输入：nums = [4,5,6,7,0,1,2], target = 0  6,7,0,1,2,3,4,5
输出：4
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l = 0
        r = len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[l] <= nums[mid]:
                if nums[l] <= target <= nums[mid]:
                    if target == nums[l]:
                        return l
                    elif target == nums[mid]:
                        return mid
                    else:
                        r = mid - 1
                else:
                    if target == nums[r]:
                        return r
                    elif target == nums[mid]:
                        return mid
                    else:
                        l = mid + 1
            elif nums[mid] <= nums[r]:
                if nums[mid] <= target <= nums[r]:
                    if target == nums[r]:
                        return r
                    elif target == nums[mid]:
                        return mid
                    else:
                        l = mid + 1
                else:
                    if target == nums[l]:
                        return l
                    elif target == nums[mid]:
                        return mid
                    else:
                        r = mid - 1
        return -1

广度优先

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

输入:
11110
11010
11000
00000
输出: 1

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 广度优先
        from collections import deque

        def cal(x, y, distance_matrix):

            q = deque()
            used = set()
            q.appendleft((x, y))
            while q:
                for _ in range(len(q)):
                    (x, y) = q.pop()
                    for x_, y_ in zip((x - 1, x + 1, x, x), (y, y, y - 1, y + 1)):
                        if 0 <= x_ < len(distance_matrix) and 0 <= y_ < len(distance_matrix[0]) and (x_, y_) not in used:
                            if grid[x_][y_] == "1":
                                distance_matrix[x_][y_] = True
                                used.add((x_, y_))
                                q.appendleft((x_, y_))

        matrix = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
        count = 0
        for row_index, row_value in enumerate(grid):
            for column_index, column_value in enumerate(row_value):
                if not matrix[row_index][column_index] and grid[row_index][column_index] == "1":
                    count += 1
                    cal(row_index, column_index, matrix)
        return count
    # 深度优先
    used = set()
    def cal(x, y, distance_matrix):
        for x_, y_ in zip((x - 1, x + 1, x, x), (y, y, y - 1, y + 1)):
            if 0 <= x_ < len(distance_matrix) and 0 <= y_ < len(distance_matrix[0]) and (x_, y_) not in used:
                if grid[x_][y_] == "1":
                    distance_matrix[x_][y_] = True
                    used.add((x_, y_))
                    cal(x_, y_, distance_matrix)

    matrix = [[False for _ in range(len(grid[0]))] for _ in range(len(grid))]
    count = 0
    for row_index, row_value in enumerate(grid):
        for column_index, column_value in enumerate(row_value):
            if not matrix[row_index][column_index] and grid[row_index][column_index] == "1":
                count += 1
                cal(row_index, column_index, matrix)
    return count
# 并查集 带路径压缩的按秩合并法
class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0
        self.parent = [-1] * (m * n)
        self.rank = [0] * (m * n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    self.parent[i * n + j] = i * n + j
                    self.count += 1
    
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]
    
    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            if self.rank[rootx] < self.rank[rooty]:
                rootx, rooty = rooty, rootx
            # 秩低的指向秩高的
            self.parent[rooty] = rootx
            if self.rank[rootx] < self.rank[rooty]:
                self.rank[rootx] += 1
            self.count -= 1
    
    def getCount(self):
        return self.count
     
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if nr == 0:
            return 0
        nc = len(grid[0])
        uf = UnionFind(grid)
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == "1":
                    grid[r][c] = "0"
                    for x, y in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
                        if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                            uf.union(r*nc+c, x*nc+y)
        return uf.getCount()

深度优先

寻找重复子树

• 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。

  class Solution:
      def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
          result, dict_node = [], {}
          def cal(node):
              if node:
                  val = "%s_%s_%s" % (node.val, cal(node.left), cal(node.right))
                  if val not in dict_node:
                      dict_node[val] = True
                  elif dict_node[val]:
                      result.append(node)
                      dict_node[val] = False
                  return val
              else:
                  return "N"
          cal(root)
          return result

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:

        res = []
        cur_str = ''

        def dfs(cur_str, left, right):
            """
            :param cur_str: 从根结点到叶子结点的路径字符串
            :param left: 左括号还可以使用的个数
            :param right: 右括号还可以使用的个数
            :return:
            """
            if left == 0 and right == 0:
                res.append(cur_str)
                return
            if right < left:
                return
            if left > 0:
                dfs(cur_str + '(', left - 1, right)
            if right > 0:
                dfs(cur_str + ')', left, right - 1)

        dfs(cur_str, n, n)
        return res

贪心算法

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
# 递归 超时 过85
class Solution:
    def jump(self, nums: List[int]) -> int:
        self.min_times = len(nums)
        def cal(index, times):
            if times >= self.min_times:
                return
            if index >= len(nums) - 1:
                self.min_times = min(times, self.min_times)
                return
            for i in range(1, nums[index]+1):
                cal(index+i, times+1)
        cal(0, 0)
        return self.min_times
# 广度 过92
from collections import deque
        q = deque()
        used = set()
        q.appendleft(0)
        times = 0
        while q:
            len_q = len(q)
            for _ in range(len_q):
                index = q.pop()
                if index >= len(nums) - 1:
                    return times
                for i in range(1, nums[index]+1):
                    if (index+i) not in used:
                        used.add(index+i)
                        q.appendleft(index+i)
            times += 1
# 贪心1 过66 通过局部解得到最优解，贪心的选择举例最后一个位置最远的那个位置
times = 0
        current_index = len(nums)-1
        while True:
            if current_index == 0:
                return times
            for i in range(current_index+1):
                if nums[i] + i >= current_index:
                    max_index = i
                    break
            current_index = max_index
            times += 1
# 贪心2 全过 擦 正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数
 max_pos = 0
        end = 0
        times = 0
        for i in range(len(nums)-1):
            if max_pos >= i:
                max_pos = max(max_pos, i+nums[i])
                if i == end:
                    end = max_pos
                    times += 1
        return times

动态规划

62. 不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
# 唉
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        matrix = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(n):
            matrix[0][i] = 1
        for i in range(m):
            matrix[i][0] = 1
        for i in range(1, n):
            for j in range(1, m):
                matrix[j][i] = matrix[j-1][i] + matrix[j][i-1]

        return matrix[m-1][n-1]
# 不同路径2：现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        n = len(obstacleGrid[0])
        m = len(obstacleGrid)
        if m == 1 and n == 1:
            if obstacleGrid[0][0] == 1:
                return 0
            else:
                return 1
        matrix = [[0 for _ in range(n)] for _ in range(m)]
        for i in range(n):
            if obstacleGrid[0][i] != 1:
                matrix[0][i] = 1
            else:
                break
        for i in range(m):
            if obstacleGrid[i][0] != 1:
                matrix[i][0] = 1
            else:
                break
        for i in range(1, n):
            for j in range(1, m):
                if obstacleGrid[j][i] != 1:
                    matrix[j][i] = matrix[j - 1][i] + matrix[j][i - 1]

        return matrix[m - 1][n - 1]

面试题 17.16. 按摩师

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
输入： [1,2,3,1]
输出： 4
# 状态转移方程：当天不预约=max(昨天预约, 昨天不预约), 当天预约=当天+昨天不预约
# 真他娘的难
class Solution:
    def massage(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[1]
        dp = [[0, 0] for _ in range(len(nums))]
        dp[0][0] = 0
        dp[0][1] = nums[0]
        for i in range(1, len(nums)):
            dp[i][0] = max(dp[i-1][1], dp[i-1][0])
            dp[i][1] = nums[i] + dp[i-1][0]
        return max(dp[-1][0], dp[-1][1])

1186. 删除一次得到子数组最大和

给你一个整数数组，返回它的某个 非空 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。
换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。
注意，删除一个元素后，子数组 不能为空。
输入：arr = [1,-2,0,3]
输出：4
class Solution:
    def maximumSum(self, arr: List[int]) -> int:
        f = [0 for _ in range(len(arr))]
        g = [0 for _ in range(len(arr))]
        f[0] = arr[0]
        g[0] = -200001
        for i in range(1, len(arr)):
            f[i] = max(f[i-1]+arr[i], arr[i])
            g[i] = max(g[i-1]+arr[i], f[i-1])
        max_sum = -100000
        for i in range(0, len(arr)):
            max_sum = max(max_sum, max(g[i], f[i]))
        return max_sum

91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

• 递归法

  def numDecodings(self, s: str) -> int:
       start_dict = {}
        def cal(s, start):
            if start == len(s):
                return 1
            if s[start] == "0":
                return 0
            if start in start_dict:
                return start_dict[start]
            dp1 = cal(s, start+1)
            dp2 = 0
            if start <= len(s) - 2:
                if int(s[start: start+2]) <= 26:
                    dp2 = cal(s, start + 2)
            start_dict[start] = dp1+dp2
            return start_dict[start]
        return cal(s, 0)

• 动态规划法

def numDecodings(self, s: str) -> int:
    dp = [0 for _ in range(len(s)+1)]
        dp[len(s)] = 1
        if s[len(s)-1] != "0":
            dp[len(s)-1] =  1
        for i in range(len(s)-1)[::-1]:
            if s[i] == "0":
                continue
            dp1 = dp[i+1]
            dp2 = 0
            if int(s[i: i+2]) <= 26:
                dp2 = dp[i+2]
            dp[i] = dp1+dp2
        return dp[0]

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        size = len(s)
        dp = [[False for _ in range(size)] for _ in range(size)]
        for i in range(size):
            dp[i][i] = True
        current_i = 0
        current_j = 0
        for j in range(1, size):
            for i in range(0, j):
                if s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                if dp[i][j]:
                    if j - i > current_j - current_i:
                        current_i = i
                        current_j = j
        return s[current_i:current_j+1]

32. 最长有效括号

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
    
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if len(s) <= 1:
            return 0
        if len(s) == 2:
            return 2 if s[0] == "(" and s[1] == ")" else 0
        dp_array = [ 0 ] * len(s)
        dp_array[1] = 2 if s[0] == "(" and s[1] == ")" else 0
        for i in range(2, len(s)):
            if s[i] == ")" and i - dp_array[i-1] - 1 >= 0 and s[i - dp_array[i-1] - 1] == "(":
                dp_array[i] = 2 + dp_array[i-1] + dp_array[i - dp_array[i-1] - 2]
        return max(dp_array)

44. 通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
    
    # 状态转移方程
    dp[i][j] = dp[i-1][j-1] si与pj相同或pj是问号
              dp[i][j-1] 或 dp[i-1][j] pj是*号 要与不要
              False
    # 初始条件
    dp[0][0] = True, dp[i][0] = False, dp[0][j]只有当p的前j个字符全为*时，dp[0][j]才为True
    class Solution:
        def isMatch(self, s: str, p: str) -> bool:
            m = len(s)
            n = len(p)
            dp = [[False] * (n+1) for _ in range(m+1)]
            # 初始条件
            dp[0][0] = True
            for i in range(1, n+1):
                if p[i-1] == "*":
                    dp[0][i] = True
                else:
                    break
            for i in range(1, m+1):
                for j in range(1, n+1):
                    if s[i-1] == p[j-1] or p[j-1] == "?":
                        dp[i][j] = dp[i-1][j-1]
                    elif p[j-1] == "*":
                        dp[i][j] = dp[i-1][j] | dp[i][j-1]
            return dp[m][n]

72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
# 编辑距离问题
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        if n * m == 0:
            return n + m
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for i in range(n+1):
            dp[0][i] = i
        for i in range(1, m+1):
            for j in range(1, n+1):
                # 1与2的编辑距离等于2在末尾添加1的尾字符
                condition1 = dp[i-1][j]
                # 1与2的编辑距离等于1在末尾添加2的尾字符
                condition2 = dp[i][j-1]
                # 直接修改1的最后一个字符与2最后一个字符相同
                condition3 = dp[i-1][j-1]
                # 最后一个字符相同直接都前进一位
                if word1[i-1] == word2[j-1]:
                    condition3 = condition3 - 1
                dp[i][j] = 1 + min(condition1, condition2, condition3)
        return dp[m][n]

96. 不同的二叉搜索树

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

G(n): 长度为 nn 的序列能构成的不同二叉搜索树的个数。
F(i,n): 以 i 为根、序列长度为 nn 的不同二叉搜索树个数(1≤i≤n)。
G(n) = (i=1..n)F(i,n)
F(i,n) = G(i-1)*G(n-i)
G(n) = (i=1..n)G(i-1)G(n-i)
# 晕死
class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0]*(n+1)
        G[0], G[1] = 1, 1

        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]

        return G[n]

单调栈

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
# 构建单调递增的栈结构，当遇到比栈顶的小的元素时，就栈顶出栈，右边界是当前元素，左边界是栈顶的前一元素
1 2 3 | 5 | 4 此时5出栈
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = list()
        stack.append(-1)
        max_size = 0
        for i in range(len(heights)):
            while len(stack) > 1 and heights[i] < heights[stack[-1]]:
                max_size = max(max_size, heights[stack.pop()] * (i - stack[-1] - 1))
            stack.append(i)
        while len(stack) > 1:
            max_size = max(max_size, heights[stack.pop()] * (len(heights) - 1 - stack[-1]))
        return max_size

85. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
# 利用上题的函数
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        heights = [0 for _ in range(len(matrix[0]))]
        max_size = 0
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if matrix[i][j] == "1":
                    heights[j] += 1
                else:
                    heights[j] = 0
            max_size = max(max_size, self.largestRectangleArea(heights))
        return max_size

739. 每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
# 要点是需要维护一个单调递减的堆栈，当当前元素大于栈顶时，需要推出栈顶，并把当前元素下标减去栈顶下标作为输出值，并继续比较当前元素与新栈顶的大小
class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        stack = list()
        stack.append(-1)
        new_t = [0 for _ in range(len(T))]
        for i in range(len(T)):
            while len(stack) > 1 and T[i] > T[stack[-1]]:
                index = stack[-1]
                new_t[index] = i - stack.pop()
            stack.append(i)
        return new_t

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
class Solution:
# 1 暴力法
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        rain = 0
        for i in range(1, len(height)-1):
            left_max = 0
            for m in range(i):
                left_max = max(left_max, height[m])
            right_max = 0
            for n in range(i + 1, len(height)):
                right_max = max(right_max, height[n])
            if min(left_max, right_max) - height[i] > 0:
                rain += min(left_max, right_max) - height[i]
        return rain
# 2 暴力法优化
        left_max_list = [0]
        for i in range(1, len(height)-1):
            left_max_list.append(max(left_max_list[i-1], height[i-1]))
        left_max_list = left_max_list[1:]
        right_max_list = [0]
        for i in range(1, len(height)-1):
            right_max_list.append(max(right_max_list[i-1], height[len(height)-i]))
        right_max_list[1:]
        right_max_list.reverse()
        for i in range(1, len(height)-1):
            if min(left_max_list[i-1], right_max_list[i-1]) - height[i] > 0:
                rain += min(left_max_list[i-1], right_max_list[i-1]) - height[i]
        return rain
# 3 双指针
        i = 0
        j = len(height)-1
        max_left = 0
        max_right = 0
        while True:
            if i >= j:
                return rain
            if height[i] <= height[j]:
                max_left = max(max_left, height[i])
                i += 1
                if max_left - height[i] > 0:
                    rain += max_left - height[i]
            else:
                max_right = max(max_right, height[j])
                j -= 1
                if max_right - height[j] > 0:
                    rain += max_right - height[j]
# 4 单调栈
        stack = []
        idx = 0
        res = 0
        while idx <= len(height) - 1:
            while stack and height[stack[-1]] < height[idx]:
                top = stack.pop()
                if not stack:
                    break
                h = min(height[idx], height[stack[-1]]) - height[top]
                length = idx - stack[-1] - 1
                res += h * length
            stack.append(idx)
            idx += 1
        return res

排序

面试题40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
# 利用快速排序的思想 每调用一次快排，会进行一次排序，把小于index的放左边，大于index的放右边，如果index=k-1，那么这时候的arr的前k个已经是前k个最小的了
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        def quick_sort(arr, start, end):
            low = start
            high = end
            temp = arr[start]
            while low < high:
                while low < high and arr[high] >= temp:
                    high -= 1
                arr[low] = arr[high]
                while low < high and arr[low] < temp:
                    low += 1
                arr[high] = arr[low]
            arr[low] = temp
            return low
        if not arr or k == 0:
            return []
        start = 0
        end = len(arr) - 1
        index = quick_sort(arr, start, end)

        while index != k - 1:
            if index > k - 1:
                end = index - 1
                index = quick_sort(arr, start, end)
            elif index < k - 1:
                start = index + 1
                index = quick_sort(arr, start, end)
        return arr[:k]

快速排序

# 快速排序在一次循环中首先选取一个基准值，一次排序后将比基准值小的放左边，比基准值大的放右边，然后继续讲基准值左边的数组与基准值右边的数组分别再次递归，定义递归出口，最后原地排序得到结果
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def quick_sort(array, left, right):
            if left >= right:
                return
            low = left
            high = right
            key = array[left]
            while left < right:
                while left < right and array[right] > key:
                    right -= 1
                array[left] = array[right]
                while left < right and array[left] <= key:
                    left += 1
                array[right] = array[left]
            array[left] = key
            quick_sort(array, low, left - 1)
            quick_sort(array, left + 1, high)

        quick_sort(nums, 0, len(nums)-1)

堆排序

# 堆排序是维护了一个最大堆，是一个完全二叉树，特点是他的根节点比左右节点都要大，因此第一步是先建立最大堆，再每次将堆中第一个元素与最后一个元素交换，堆顶元素就是最大值，再重新交换后的树整理成最大堆，继续交换，直到最后一个元素为止
class Solution:
    def heapify(self, arr, n, i):
        left = 2*i+1
        right = 2*i+2
        max_index = i
        if left < n and arr[left] > arr[max_index]:
            max_index = left
        if right < n and arr[right] > arr[max_index]:
            max_index = right
        if max_index != i:
            arr[max_index], arr[i] = arr[i], arr[max_index]
            self.heapify(arr, n, max_index)

    def heapSort(self, arr):
        n = len(arr)-1
        # 构建大顶堆
        for i in range(n, -1, -1):
            self.heapify(arr, n, i)
        # 交换元素
        for i in range(n, 0, -1):
            arr[i], arr[0] = arr[0], arr[i]
            self.heapify(arr, i, 0)
        return arr

并查集

547. 朋友圈

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
输入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
输出: 2 
# DFS
class Solution:
    def findCircleNum(self, M: List[List[int]]) -> int:
        used = []
        def dfs(M, i, used):
            for j in range(len(M[0])):
                if M[i][j] == 1 and j not in used:
                    used.append(j)
                    dfs(M, j, used)
        count = 0
        for i in range(len(M)):
            if i not in used:
                dfs(M, i, used)
                count += 1
        return count
# BFS
        def bfs(x):
            q.appendleft(x)
            while q:
                x_ = q.pop()
                used.add(x_)
                for y in range(len(M[0])):
                    if M[x_][y] == 1 and y not in used:
                        q.appendleft(y)
        count = 0
        for i in range(len(M)):
            if i not in used:
                bfs(i)
                count += 1
        return count
# 并查集 定义一个一唯数组，存入x与x的父节点
        def find(parent, i):
            if parent[i] != -1:
                return find(parent, parent[i])
            else:
                return i

        def union(parent, x, y):
            x_parent = find(parent, x)
            y_parent = find(parent, y)
            if x_parent != y_parent:
                parent[x_parent] = y_parent

        parent = [-1 for _ in range(len(M))]
        for i in range(len(M)):
            for j in range(len(M[0])):
                if M[i][j] == 1:
                    union(parent, i, j)
        count = 0
        for i in range(len(parent)):
            if parent[i] == -1:
                count += 1
        return count

684. 冗余连接

输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
输入: [[1,2], [1,3], [2,3]]
输出: [2,3]
class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

        def find(parent, index):
            if parent[index] != -1:
                return find(parent, parent[index])
            else:
                return index

        parent = [-1 for _ in range(len(edges))]
        def can_union(parent, x, y):
            x_parent = find(parent, x)
            y_parent = find(parent, y)
            if x_parent != y_parent:
                parent[x_parent] = y_parent
                return True
            else:
                return False

        for i in range(len(edges)):
            if not can_union(parent, edges[i][0]-1, edges[i][1]-1):
                return edges[i]

分治法

241. 为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:
输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2

# 分治法
1. 分解：按运算符分为左右两部分
2. 解决：实现递归
3. 合并：合并左右两边结果
class Solution:
    def diffWaysToCompute(self, input: str) -> List[int]:

        if input.isdigit():
            return [int(input)]
        res = []
        for i, char in enumerate(input):
            if char in ["+", "-", "*"]:
                left = self.diffWaysToCompute(input[:i])
                right = self.diffWaysToCompute(input[i+1:])
                for l in left:
                    for r in right:
                        if char == "+":
                            res.append(l+r)
                        elif char == "-":
                            res.append(l-r)
                        elif char == "*":
                            res.append(l*r)
        return res

滑动窗口

lo, hi = 0, 0
while hi < n:
    window += grumpy[hi] * customers[hi]        # 右值进入窗口
    while hi - lo + 1 > X:                      # 维护大小为X的窗口
        window -= grumpy[lo] * customers[lo]    # 左值退出窗口
        lo += 1                                 # 左指针前进1
    <do...>                                     # 任务1
    hi += 1                                     # 右指针前进1

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例: 
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        import sys
   
        j = -1
        current_sum = 0
        min_len = sys.maxsize
        is_over = False
        is_find = False
        for i in range(len(nums)):
            if current_sum >= s:
                current_len = j - i + 1
                min_len = min(current_len, min_len)
                is_find = True
            else:
                while True:
                    j += 1
                    if j >= len(nums):
                        is_over = True
                        break
                    current_sum += nums[j]
                    if current_sum >= s:
                        current_len = j - i + 1
                        min_len = min(current_len, min_len)
                        is_find = True
                        break
            if is_over:
                break
            current_sum -= nums[i]
        if not is_find:
            return 0
        return min_len

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        j = 0
        max_len = 1
        is_over = False
        for i in range(len(s)):
            while True:
                j += 1
                if j >= len(s):
                    is_over = True
                    break
                if len(s[i: j+1]) == len(list(set(list(s[i: j+1])))):
                    current_len = j - i + 1
                    max_len = max(current_len, max_len)
                else:
                    break
            if is_over:
                break

        return max_len
   # 王氏解法
   class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        if len(set(list(s))) == 1:
            return 1
        j = 1
        i = 0
        length_max = 0
        window = [s[0]]
        while True:
            if s[j] not in window:
                window.append(s[j])
                j += 1
            else:
                index = window.index(s[j])
                length_max = max(length_max, len(window))
                window = window[index+1:]
                window.append(s[j])
                j += 1
            if j == len(s):
                length_max = max(length_max, len(window))
                break
        return length_max

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans = ''
        minLen = float('Inf')
        lo, hi = 0, 0
        window = Counter()
        t = Counter(t)
        while hi < len(s):
            # 入窗
            window[s[hi]] += 1
            # 维护窗口大小
            while all(map(lambda x: window[x] >= t[x], t.keys())):
                # 筛选符合条件的最短长度
                if hi - lo + 1 < minLen:
                    ans = s[lo:hi+1]
                    minLen = hi - lo + 1
                # 出窗
                window[s[lo]] -= 1
                lo += 1
            # 窗口右端右移
            hi += 1
        return ans

正则

8. 字符串转换整数 (atoi)

请你来实现一个 atoi 函数，使其能将字符串转换成整数。
# 一行 搞个毛线
class Solution:
    def myAtoi(self, s: str) -> int:
        # *表示闭包 将列表传入函数
        return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)

双指针

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        max_value = 0
        while True:
            if i >= j:
                break
            current_index_distance = j - i
            if height[i] <= height[j]:
                min_index_value = height[i]
                i += 1
            else:
                min_index_value = height[j]
                j -= 1
            max_value = max(max_value, current_index_distance*min_index_value)
        return max_value

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
# 确实想不到 二分
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        nums_list = []

        for i in range(len(nums)):
            if nums[i] > 0:
                return nums_list
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                if nums[l] + nums[i] + nums[r] == 0:
                    current_list = [nums[i], nums[l], nums[r]]
                    nums_list.append(current_list)
                    while(l<r and nums[l]==nums[l+1]):
                        l=l+1
                    while(l<r and nums[r]==nums[r-1]):
                        r=r-1
                    l=l+1
                    r=r-1

                elif nums[l] + nums[i] + nums[r] < 0:
                    l = l + 1
                else:
                    r = r - 1
        return nums_list

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        save_node = head
        l = head
        r = head
        for i in range(n):
            r = r.next
        # 说明l就是那个应该被删的元素 并且是第一个
        if not r:
            return l.next
        while True:
            if not r.next:
                l.next = l.next.next
                break
            l = l.next
            r = r.next
        return save_node

30. 串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
# 1
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        import copy
        words_dict = {}
        for word in words:
            words_dict[word] = words_dict.get(word, 0) + 1
        s_len, w_len = len(s), len(words[0])
        sub_len = w_len * len(words)
        results = []
        for i in range(s_len-sub_len+1):
            current_dict = copy.copy(words_dict)
            begin = i
            while s[begin: begin+w_len] in current_dict and current_dict[s[begin: begin+w_len]] != 0:       
                current_dict[s[begin: begin+w_len]] -= 1
                begin += w_len
            if sum(current_dict.values()) == 0:
                results.append(i)
        return results
# 2 思路：迭代每一个子串 从后向前迭代
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not words:
            return []
        words_dict = {}
        for word in words:
            words_dict[word] = words_dict.get(word, 0) + 1
        s_len, w_len = len(s), len(words[0])
        sub_len = w_len * len(words)
        results = []
        for offset in range(w_len):
            l, r = offset, s_len - sub_len
            while l <= r:
                current_dict = words_dict.copy()
                is_match = True
                for i in range(l + sub_len, l, -w_len):
                    if s[i-w_len: i] in current_dict and current_dict[s[i-w_len: i]] != 0:
                        current_dict[s[i-w_len: i]] -= 1
                    else:
                        is_match = False
                        break
                if is_match:
                    results.append(l)
                l = i
        return results

80. 删除排序数组中的重复项 II

给定一个增序排列数组 nums ，你需要在 原地 删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i, count = 1, 1.
        while i < len(nums):
            if nums[i] == nums[i - 1]:
                count += 1
                if count > 2:
                    nums.pop(i)
                    # 删除数组元素后需要后退索引，因为后面会统一加1位
                    i-= 1
            else:
                count = 1
            i += 1    
        return len(nums)

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
# 哑节点使用
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """

        dummy = ListNode(-1)
        a = dummy
        b = head
        dummy.next = head
        while b and b.next:
            if a.next.val != b.next.val:
                a = a.next
                b = b.next
            else:
                while b and b.next and a.next.val == b.next.val:
                    b = b.next
                a.next = b.next
                b = b.next
        return dummy.next

堆，优先队列

23. 合并K个升序链表

# 堆队列
import heapq
nums = [14, 20, 5, 28, ...]
heapq.nlargest(3, nums) # [28, 28, 22] 最大最小K个元素
heapq.nsmallest(3, nums) # [1, 5, 14]
# heapq实现优先队列
class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0
    def push(self, item, priority):
        # heapq是最小堆 优先级取负数
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1
    def pop(self):
        return heapq.heappop(self._queue)[-1]
q = PriorityQueue()
q.push("lenovo", 1)
q.push("mac", 5)
q.push("surface", 3)
q.pop() # mac
q.pop() # surface
# 自带优先级队列 具有锁开销
from queue import PriorityQueue
q = PriorityQueue()
q.put((2, "code"))
q.put((1, "eat"))
while not q.empty():
    next_item = q.get()
    print(next_item)
    
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        list_q = []
        for i in range(len(lists)):
            while lists[i]:
                heapq.heappush(list_q, lists[i].val)
                lists[i] = lists[i].next
        list_node = save_node = ListNode(-1)
        while list_q:
            list_node.next = ListNode(heapq.heappop(list_q))
            list_node = list_node.next
        return save_node.next

链表

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
# 难
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:

        def reverse(node_head, node_tail):
            prev = node_tail.next 
            p = node_head
            while True:
                if prev == node_tail:
                    break
                current_next = p.next
                # p指向p前一个
                p.next = prev
                # 更新prev
                prev = p
                # 更新p
                p = current_next
            return node_tail, node_head

        prev = tail = save = ListNode(-1)
        prev.next = head
        tail.next = head
        while True:
            tail = prev
            for i in range(k):
                if not tail.next:
                    return save.next
                tail = tail.next
            save_tail = tail.next
            current_head, current_tail = reverse(head, tail)
            prev.next = current_head
            current_tail.next = save_tail
            prev = current_tail
            head = prev.next
        return save.next

位运算

29. 两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        sign = (dividend>0) ^ (divisor>0)
        count = 0
        dividend = abs(dividend)
        divisor = abs(divisor)
        while dividend >= divisor:
            count += 1
            divisor = divisor << 1
        result = 0
        while count > 0:
            count -= 1
            divisor = divisor >> 1
            if dividend >= divisor:
                result += 1 << count
                dividend = dividend - divisor
        if sign:
            result = -1 * result
        if result > 2 ** 31 - 1 or result < -1 * 2 ** 31:
            return 2 ** 31 - 1
        return result

67. 二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。
输入为 非空 字符串且只包含数字 1 和 0。
输入: a = "11", b = "1"
输出: "100"
    
# 位运算替换加减乘除
class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            # 异或求无进位结果
            answer = x ^ y
            # carry求每一位的进位情况
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]

区间问题

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        # 以第一位排序
        intervals.sort(key=lambda x: x[0])
        merged = []
        for interval in intervals:
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])
        return merged

1111