PowerLZY's Blog

本博客主要用于记录个人学习笔记（测试阶段）

发表于 更新于 分类于 ， 本文字数： 2.6k 阅读时长 ≈ 5 分钟

图论算法从入门到放下

https://leetcode.cn/circle/discuss/FyPTTM/

主要内容一览

graph_mind.png

岛屿问题

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1:

img

输入: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出: 6 解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 深度优先搜索 空间复杂度o(m*n)
        m, n = len(grid), len(grid[0])
        res = 0
        def dfs(x, y) -> int:
            s = 1
            grid[x][y] = 0
            for i, j in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
                if i < 0 or j < 0 or i == m or j == n or grid[i][j]!=1:
                    continue
                s += dfs(i, j)
            return s

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

有 n 个网络节点，标记为 1 到 n。给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

  • 图最短路径【优先队列】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]
        for x, y, time in times:
            g[x - 1].append((y - 1, time))

        dist = [float('inf')] * n
        dist[k - 1] = 0
        q = [(0, k - 1)]
        while q:
            time, x = heapq.heappop(q)
            if dist[x] < time:
                continue
            for y, time in g[x]:
                if (d := dist[x] + time) < dist[y]:
                    dist[y] = d
                    heapq.heappush(q, (d, y))

        ans = max(dist)
        return ans if ans < float('inf') else -1

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给定一个二维数组 graph ，表示图，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

示例 1：

img

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输出：false 解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

  • DFS【染色问题】、并查集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 广度优先遍历 [推荐]
        n = len(graph)
        uncolor, red, green = 0, 1, 2
        color = [0] * n
        for i in range(n):
            if color[i] == uncolor:
                color[i] = red
                q = deque([i])
                while q:
                    node = q.popleft()
                    nei = green if color[node] == red else red
                    for j in graph[node]:
                        if color[j] == uncolor:
                            color[j] = nei
                            q.append(j)
                        elif color[j] != nei:
                            return False
        return True
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 深度优先遍历 【不推荐】
        def dfs(i: int, c: int):
            nonlocal res
            nei = green if c == red else red
            for j in graph[i]:
                if color[j] == uncolor:
                    color[j] = nei
                    dfs(j, nei)
                elif color[j] != nei:
                    res = False

        n = len(graph)
        uncolor, red, green = 0, 1, 2
        color = [0] * n
        res = True
        for i in range(n):
            if color[i] == uncolor and res:
                dfs(i, red)
        return res
    
    # def isBipartite(self, graph: List[List[int]]) -> bool:
    #     # 并查集 【了解】

发表于 更新于 分类于 ， 本文字数： 8.5k 阅读时长 ≈ 15 分钟

回溯 - 子集、组合、排列、岛屿

result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择

39.组合总和

40. 组合总和 II

46. 全排列

47. 全排列 II

78. 子集

90. 子集 II

给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans = []
        def backtrace(idx, tmp):
            ans.append(tmp[:])
            for j in range(idx, n):
                tmp.append(nums[j])
                backtrace(j + 1, tmp)
                tmp.pop()
        backtrace(0, [])
        return ans
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # import itertools.combinations
        ans = []
        for i in range(len(nums) + 1):
            for tmp in itertools.combinations(nums, i):
                ans.append(tmp)
        return ans

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

img 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def exist(self, board: List[List[str]], word: str) -> bool:
      m = len(board)
      n = len(board[0])
      def dfs(x, y, index):
           if index == len(word):
           		return True
           for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
               nx, ny = x + dx, y + dy
               if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == word[index]:
                   board[nx][ny] = '/'
               		 if dfs(nx, ny, index + 1):
                       return True
                   board[nx][ny] = word[index]
            return False
      for i in range(m):
          for j in range(n):
              if board[i][j] == word[0]:
                  board[i][j] = '/'
              		if dfs(i, j, 1):
                  		return True
               		board[i][j] = word[0]
      return False

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

  • bfs、bfs、岛屿面积
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        # bfs
        def sum_(x, y):
            return x%10 + x//10 +  y%10 + y//10
        que = collections.deque()
        que.append((0, 0))
        s = set()
        s.add((0, 0))
        while que:
            x, y = que.popleft()
            for i, j in [(x + 1, y), (x, y + 1)]:
                if 0 <= i < m and 0 <= j < n and (i, j) not in s and sum_(i,j) <= k:
                    que.append((i, j))
                    s.add((i, j))
        return len(s)
    def movingCount(self, m: int, n: int, k: int) -> int:
        # dfs【向下向右】
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n or sum_(i, j) > k or f[i][j] == 1:
                return 0
            f[i][j] = 1
            return 1 + dfs(i + 1, j) + dfs(i, j + 1)

        def sum_(x, y):
            return x%10 + x//10 +  y%10 + y//10
        
        f = [[0 for i in range(n)] for j in range(m)]
        return dfs(0, 0)

    def movingCount(self, m: int, n: int, k: int) -> int:
        # 回溯: 岛屿面积  
        def sumGrid(x, y):
            return x%10 + x//10 +  y%10 + y//10
        visited = set()
        def backtrace(x, y):
            visited.add((x, y))
            for i, j in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
                if 0 <= i < m and 0<= j < n and (i, j) not in visited and sumGrid(i, j) <= k:
                    backtrace(i, j)
        backtrace(0, 0)
        return len(visited)

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出==所有==从根节点到叶子节点 路径总和等于给定目标和的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def pathSum(self, root: TreeNode, target: int) -> List[List[int]]:
        def backtrace(root, tmp, target):
            if not root:
                return
            if not root.left and not root.right and target == root.val:
                ans.append(tmp[:] + [root.val])
                return
            tmp.append(root.val)
            backtrace(root.left, tmp, target - root.val)
            backtrace(root.right, tmp, target - root.val)
            tmp.pop()
        ans = []
        backtrace(root, [], target)
        return ans

  • https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/solution/dai-ma-sui-xiang-lu-jian-zhi-offer-38-zi-gwt6/

输入一个字符串，打印出该字符串中字符的所有排列。

  • 还要强调的是==去重一定要对元素经行排序==，这样我们才方便通过相邻的节点来判断是否重复使用了。
  • 组合问题和排列问题是在树形结构的叶子节点上收集结果，而子集问题就是取树上所有节点的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
  	def permutation(self, s: str) -> List[str]:
        # itertools.permutations(s)
        return list(set("".join(t) for t in itertools.permutations(s)))
    
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums: 
            return []
        res = []
        used = set() # [0] * len(nums)
        def backtracking(path):
            if len(path) == len(nums):
                res.append(path[:])
                return
            for i in range(len(nums)):
                if i not in used:
                    if i>0 and nums[i] == nums[i-1] and i-1 not in used:
                      	# 重复剪枝
                        continue
                    used.add(i)
                    path.append(nums[i])
                    backtracking(path)
                    path.pop()
                    used.remove(i)
        # 记得给nums排序
        nums.sort()
        backtracking([])
        return res

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。

输入: candidates = [2,3,6,7], target = 7 输出: [[7],[2,2,3]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 回溯，无重复元素，根据剩余值凑成目标
        ans = []
        path = []
        candidates.sort() # 预先排序，
        # 收集逻辑为target == 0

        def backtracking(index,path,target):
            if index >= len(candidates) or target < 0:
                return 
            if target == 0: # 收集条件
                ans.append(path[:])
                return    
            for i in range(index,len(candidates)):  # 注意可以重复收集          
                path.append(candidates[i])  # 做选择
                backtracking(i,path,target-candidates[i])
                path.pop() # 取消选择
         
        backtracking(0,[],target)
        return ans

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

candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        ans, n = [], len(candidates)
        candidates.sort()
        def backtrace(idx, tmp, target):
            if idx > n or target < 0:
                return
            if target == 0:
                ans.append(tmp[:])
                return
            for i in range(idx, n):
                if i > idx and candidates[i] == candidates[i - 1]:
                    # 去重：让递归的同一级不出现相同元素、递归的不同级可以出现相同元素
                    continue
                tmp.append(candidates[i])
                backtrace(i + 1, tmp, target - candidates[i])
                tmp.pop()
        backtrace(0, [], target)
        return ans

给定一个不含重复数字的整数数组 nums ，返回其 所有可能的全排列 。可以 按任意顺序 返回答案。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # 库函数[数组交换]、回溯模版
        # return list(itertools.permutations(nums))
        ans, n = [], len(nums)
        visited = set()
        def backtrace(idx, tmp):
            if len(tmp) == n:
                ans.append(tmp[:])
                return 
            for i in range(n):
                if i not in visited:
                    visited.add(i)
                    tmp.append(nums[i])
                    backtrace(i + 1, tmp)
                    tmp.pop()
                    visited.remove(i)
        backtrace(0 ,[])
        return ans

给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # visited 记录访问节点的集合
        n = len(nums)
        ans = []
        vis = set()
        def backtrace(tmp):
            if len(tmp) == n:
                ans.append(tmp[:])
                return 
            for i in range(n):
                if i in vis:
                    continue
                if i > 0 and nums[i] == nums[i - 1] and i - 1 not in vis:
                    # not in 保留顺序剪枝 
                    continue
                vis.add(i)
                backtrace(tmp + [nums[i]])
                vis.remove(i)
        nums.sort()
        backtrace([])
        return ans

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        # 回溯
        # 第一步：得到全部 2^(2n) 种组合，然后再根据我们刚才总结出的合法括号组合的性质筛选出合法的组合
        # 第二步：剪枝  1、可用左括号大于右括号 2、括号可用小于0
        ans = []
        def backtrace(left, right, tmp):
            if left > right:
                return
            if left < 0  or right < 0:
                return
            if left == 0 and right == 0:
                ans.append("".join(tmp[:]))
                return
            tmp.append('(')
            backtrace(left - 1, right, tmp)
            tmp.pop()

            tmp.append(')')
            backtrace(left, right - 1, tmp)
            tmp.pop()
        backtrace(n, n, [])
        return ans

给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。回文串 是正着读和反着读都一样的字符串。

输入：s = "google" 输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

  • 动态规划预处理 + 回溯全排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        # 动态规划预处理 + 回溯全排列条件
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = True
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    if j - i <= 1 or dp[i + 1][j - 1]:
                        dp[i][j] = True
        ans = []
        def backtrace(idx, tmp):
            if idx == n:
                ans.append(tmp[:])
                return
            for i in range(idx, n):
                if dp[idx][i]:
                    tmp.append(s[idx: i + 1])
                    backtrace(i + 1, tmp)
                    tmp.pop()
        backtrace(0, [])
        return ans

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]

「力扣」第 93 题：复原 IP 地址-1.png

  • 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯;
  • 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        SEG_COUNT = 4
        ans = list()
        segments = [0] * SEG_COUNT
        def dfs(segId: int, segStart: int):
            # 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if segId == SEG_COUNT:
                if segStart == len(s):
                    ipAddr = ".".join(str(seg) for seg in segments)
                    ans.append(ipAddr)
                return
            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if segStart == len(s):
                return
            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[segStart] == "0":
                segments[segId] = 0
                dfs(segId + 1, segStart + 1)
            # 一般情况，枚举每一种可能性并递归
            addr = 0
            for segEnd in range(segStart, len(s)):
                addr = addr * 10 + (ord(s[segEnd]) - ord("0"))
                if 0 < addr <= 0xFF:
                    segments[segId] = addr
                    dfs(segId + 1, segEnd + 1)
                else:
                    break
        dfs(0, 0)
        return ans

发表于 更新于 分类于 ， 本文字数： 2.5k 阅读时长 ≈ 4 分钟

位运算

  • https://www.runoob.com/python/python-operators.html

a 为 60，b 为 13

1
2
a = 0011 1100
b = 0000 1101

image-20220603165450958

一、位运算技巧

  • n &= n - 1: 把 n 的二进制位中的最低位的 1 变为 0.
1
2
3
4
5
6
def countOnes(x: int) -> int:
		ones = 0
  	while x > 0:
				x &= (x - 1)
        ones += 1
    return ones

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # 快速幂
        if x== 0:
            return 0
        res = 1
        if n < 0:
            x, n = 1 / x, -n
        while n:
            if n & 1:
                res *= x
            x *= x
            n >>= 1 # n // 2
        return res

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= n - 1
        return res
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            if n&1 == 1:
                res += 1
            n >>= 1
        return res

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

1
2
3
4
5
6
7
class Solution:
    def add(self, a: int, b: int) -> int:
        # 无进位和: 异或运算^ 规律相同
        # 进位: 与运算& 规律相同（并需左移一位）
        if b == 0:
            return a
        return add(a ^ b, (a & b) << 1)

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

如果除了一个数字以外，其他数字都出现了两次，那么如何找到出现一次的数字？

全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。

那么这一方法如何扩展到找出两个出现一次的数字呢？

如果我们可以把所有数字分成两组，使得：

  • 两个只出现一次的数字在不同的组中；

  • 相同的数字会被分到相同的组中

那么对两个组分别进行异或操作，即可得到答案的两个数字。这是解决这个问题的关键。

那么如何实现这样的分组呢？

  • 在异或结果中找到任意为 11 的位。
算法：
  • 先对所有数字进行一次异或，得到两个出现一次的数字的异或值。
  • 在异或结果中找到任意为 1 的位。
  • 根据这一位对所有的数字进行分组。
  • 在每个组内进行异或操作，得到两个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        ret = functools.reduce(lambda x, y: x ^ y, nums)
        div = 1
        while div & ret == 0:
            div <<= 1
        a, b = 0, 0
        for n in nums:
            if n & div:
                a ^= n
            else:
                b ^= n
        return [a, b]

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

  • 有限状态机、遍历统计
算法：
  • 首先，将所有数字都看成 32位 的二进制数；
  • 接着，将数组中的所有数字相加。那么，对于"某一位"来说，数值一定是 3N或3N+1 ；
  • 为什么？所有出现3次的数字对该位置的贡献，和一定是0或3，出现一次的数字对该位置的贡献，一定是0或1
  • 所以，对该位置的和，用3取余，结果就是出现一次的数字在该位置的值。

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counts = [0] * 32
        for num in nums:
            for j in range(32):
                counts[j] += num & 1
                num >>= 1
        res, m = 0, 3
        for i in range(32):
            res <<= 1
            res |= counts[31 - i] % m
        return res if counts[31] % m == 0 else ~(res ^ 0xffffffff)

给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def countBits(self, n: int) -> List[int]:
        # o(nlogn)
        def countbits(x: int) -> int:
            ones = 0
            while x > 0:
                x &= (x - 1)
                ones += 1
            return ones
        return [countbits(i) for i in range(n + 1)]
    def countBits(self, n: int) -> List[int]:
        bits, high = [0], 0
        for i in range(1, n + 1):
            if i&(i - 1) == 0:
                high = i
            bits.append(bits[i - high] + 1)
        return bits

发表于 更新于 分类于 ， 本文字数： 11k 阅读时长 ≈ 20 分钟

排序

一、快速排序

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

（最小）堆排序算法：https://docs.python.org/zh-cn/3/library/heapq.html

  • ==快速选择、堆排序==
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # 堆排序
        if k == 0:
            return list()
        hp = [ -x for x in arr[:k]]
        heapq.heapify(hp)
        for i in range(k, len(arr)):
            if -hp[0] > arr[i]:
                heapq.heappop(hp)
                heapq.heappush(hp, -arr[i])
        arr = [-x for x in hp]
        return arr   
        
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        # 快速选择
        if k == 0:
            return []
        def quickSelect(low, high, k):
            pvoit = random.randint(low, high)
            arr[pvoit], arr[low] = arr[low], arr[pvoit]
            base = arr[low] 
            i = low
            for j in range(low+1, high+1):
                if arr[j] < base:
                    arr[i+1], arr[j] = arr[j], arr[i+1]
                    i += 1
            arr[low], arr[i] = arr[i], arr[low] 
            if i == k - 1:
                return arr[:k]
            elif i < k - 1:
                return quickSelect(i+1, high, k)
            else: 
                return quickSelect(low, i-1, k)

        return quickSelect(0, len(arr) - 1, k)

https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/cpython3java-1da-gen-dui-diao-ku-2shou-l-xveq/

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

  • 小根堆调库、快速选择
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = []
        for num in nums:
            if len(heap) >= k:
                if num > heap[0]: # 注意替换条件
                    heapq.heapreplace(heap, num)
            else:
                heapq.heappush(heap, num)
        return heap[0]
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # 快速选择
        def findTopk(low, high):
            pvoit = random.randint(low, high)
            nums[pvoit], nums[low] = nums[low], nums[pvoit]
            base = nums[low]
            i = low 
            for j in range(low + 1, high + 1):
                if nums[j] > base:
                    nums[i + 1], nums[j] = nums[j], nums[i + 1]
                    i += 1
            nums[i], nums[low] = nums[low], nums[i]
            if i == k - 1:
                return nums[i]
            elif i < k - 1:
                return findTopk(i + 1, high)
            else:
                return findTopk(low, i - 1)
        return findTopk(0, len(nums) - 1)

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

  • 【基于快排】+【拼接字符串】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def minNumber(self, nums: List[int]) -> str:
        n = len(nums)
        def _smallA(a, b):
            return True if a + b < b + a else False
        def partition(l, r):
            pivot = random.randint(l, r)
            nums[pivot], nums[l] = nums[l], nums[pivot]
            base = nums[l]
            i = l
            for j in range(l+1, r+1): # r+1 遍历到r
                if _smallA(nums[j], base):
                    nums[j], nums[i+1] = nums[i+1], nums[j] # i + 1 与i前面的换
                    i += 1
            nums[l], nums[i] = nums[i], nums[l]
            return i
        def quick_sort(l, r):
            if r - l <= 0:
                return
            mid = partition(l, r)
            quick_sort(l, mid - 1)
            quick_sort(mid + 1, r)
        nums = [str(num) for num in nums]
        quick_sort(0, len(nums) - 1)
        return "".join(nums).lstrip()
  • 内置函数：cmp_to_key，单个元素并没有一个绝对的大小的情况
1
2
3
4
5
class Solution:    
  def largestNumber(self, nums: List[int]) -> str:
        nums.sort(key=cmp_to_key(lambda x,y: int(str(y)+str(x)) - int(str(x)+str(y))))
        ans = ''.join([str(num) for num in nums])
        return str(int(ans))

从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

  • 集合 Set + 遍历，排序 + 遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def isStraight(self, nums: List[int]) -> bool:
        pset = set()
        mi, ma = 14, -1
        for num in nums:
            if num == 0:
                continue
            if num in pset:
                return False
            mi = min(mi, num)
            ma = max(ma, num)
            pset.add(num)
        return ma - mi < 5
    def isStraight(self, nums: List[int]) -> bool:
        joker = 0
        nums.sort() # 数组排序
        for i in range(4):
            if nums[i] == 0: joker += 1 # 统计大小王数量
            elif nums[i] == nums[i + 1]: return False # 若有重复，提前返回 false
        return nums[4] - nums[joker] < 5 # 最大牌 - 最小牌 < 5 则可构成顺子

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

  • 大小堆排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
heappush(self.B, -heappushpop(self.A, num))class MedianFinder:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.minheap = []
        self.maxheap = []

    def addNum(self, num: int) -> None:
        if len(self.minheap) != len(self.maxheap):
          	# heappush(self.B, -heappushpop(self.A, num))
            heappush(self.minheap, num)
            heappush(self.maxheap, -heappop(self.minheap))
        else: # 【len等于时，min多】
            heappush(self.maxheap, -num)
            heappush(self.minheap, -heappop(self.maxheap))

    def findMedian(self) -> float:
        return self.minheap[0] if len(self.minheap) != len(self.maxheap) else (self.minheap[0] - self.maxheap[0] ) / 2.0

二、归并排序

「归并排序」是分治思想的典型应用。

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

那么求逆序对和归并排序又有什么关系呢？

两个已排序的序列等待合并，记录计算逆序对的数量；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        def mergeSort(nums, low, high):
            if low >= high:     # 递归终止
                return 0        
            ans = 0             # 记录当前逆序对数目
            '''递归排序'''
            mid = low+(high-low)//2     
            ans += mergeSort(nums, low, mid)        # 左半部分逆序对数目
            ans += mergeSort(nums, mid+1, high)     # 右半部分逆序对数目

            '''nums[low, mid] 和 nums[mid+1, high] 已排序好'''
            tmp = []        # 记录nums[low, high]排序结果
            left, right = low, mid+1
            while left<=mid and right<=high:
                if nums[left] <= nums[right]:
                    tmp.append(nums[left])
                    left += 1
                else:       # 后半部分值较小，出现了逆序
                    tmp.append(nums[right])
                    right += 1
                    ans += mid+1-left       # 当前值 nums[right] 贡献的逆序对个数为 mid+1-left
                    '''解释：若nums[left] > nums[right]，
                       则nums[left, mid] > nums[right]均成立，共 mid+1-left 项'''
            
            '''左或右数组需遍历完（最多只有一个未遍历完）'''
            while left<=mid:
                tmp.append(nums[left])
                left += 1

            while right<=high:
                tmp.append(nums[right])
                right += 1
                # ans += mid+1-left     # 此时，前半部分一定已经遍历完了，即left=mid+1，因此无需再更新结果
            nums[low:high+1] = tmp
            return ans
        '''主程序'''
        return mergeSort(nums, 0, len(nums)-1)

给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

img

输入：head = [4,2,1,3] 输出：[1,2,3,4]

  • 归并排序 + 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 时间空间复杂度分别为 O(nlogn) 和 O(1) 【归并排序】
        # 【切分数组】
        if not head or not head.next:
            return head
        slow, fast = head, head.next # 快慢指针【如何】初始化
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        mid, slow.next = slow.next, None # None截断
        left, right = self.sortList(head), self.sortList(mid) # 递归
        # 【合并链表】
        h = dummy = ListNode(0) # 新建节点的合并
        while left and right:
            if left.val < right.val:
                h.next = left
                left = left.next
            else:
                h.next = right
                right = right.next
            h = h.next
        h.next = left if left else right
        return dummy.next

给定一个链表数组，每个链表都已经按升序排列。请将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5], [1,3,4], [2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

  • 【优先队列】[推荐] 维护多个链表对象；时间：O(nlog(k))，n 是所有链表中元素总和，k 是链表个数；
  • 【归并排序】链表两两合并，递归占用很多空间；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 优先队列 维护多个链表对象
        h = dummy = ListNode(0)
        heap = []
        for i in range(len(lists)):
            if lists[i]:
                heapq.heappush(heap, (lists[i].val, i))
                lists[i] = lists[i].next
        while heap:
            val, idx = heapq.heappop(heap)
            h.next = ListNode(val)
            h = h.next
            if lists[idx]:
                heapq.heappush(heap, (lists[idx].val, idx))
                lists[idx] = lists[idx].next
        return dummy.next
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
      	# 【归并排序】链表两两合并
        if not lists:return 
        n = len(lists)
        return self.merge(lists, 0, n-1)
    def merge(self,lists, left, right):
        if left == right:
            return lists[left]
        mid = left + (right - left) // 2
        l1 = self.merge(lists, left, mid)
        l2 = self.merge(lists, mid+1, right)
        return self.mergeTwoLists(l1, l2)
    def mergeTwoLists(self,l1, l2):
        if not l1:return l2
        if not l2:return l1
        if l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

三、堆排序

Python 十大排序算法：https://leetcode.cn/problems/sort-an-array/solution/python-shi-xian-de-shi-da-jing-dian-pai-xu-suan-fa/

堆排序是利用堆这个数据结构设计的排序算法。

算法描述：

  • 建堆，从底向上==调整堆==，使得父亲节点比孩子节点值大，构成大顶堆；
  • 交换堆顶和最后一个元素，重新调整堆。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 递归写法
    def adjust_heap(nums, startpos, endpos):
        pos = startpos
        chilidpos = pos * 2 + 1
        if chilidpos < endpos:
            rightpos = chilidpos + 1
            if rightpos < endpos and nums[rightpos] > nums[chilidpos]:
                chilidpos = rightpos
            if nums[chilidpos] > nums[pos]:
                nums[pos], nums[chilidpos] = nums[chilidpos], nums[pos]
                adjust_heap(nums, pos, endpos)
    # 迭代写法
    def adjust_heap(nums, startpos, endpos):
        newitem = nums[startpos]
        pos = startpos
        childpos = pos * 2 + 1
        while childpos < endpos:
            rightpos = childpos + 1
            if rightpos < endpos and nums[rightpos] >= nums[childpos]:
                childpos = rightpos
            if newitem < nums[childpos]:
                nums[pos] = nums[childpos]
                pos = childpos
                childpos = pos * 2 + 1
            else:
                break
        nums[pos] = newitem

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class KthLargest:

    def __init__(self, k: int, nums: List[int]):
        self.heap = []
        self.size = k 
        for num in nums:
            self._push(num)
    def _push(self, num):
        if self.size <= len(self.heap):
            if self.heap[0] < num:
                heapq.heappop(self.heap)
                heapq.heappush(self.heap, num)
        else:
            heapq.heappush(self.heap, num)

    def add(self, val: int) -> int:
        self._push(val)
        return self.heap[0]

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

  • API : return [c[0] for c in Counter(nums).most_common(k)]
  • 快速选择
  • 堆排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        def findTopk(low, high):
            pivot = random.randint(low, high)
            nums_cnt[pivot], nums_cnt[low] = nums_cnt[low], nums_cnt[pivot]
            base = nums_cnt[low][1]
            i = low
            for j in range(low + 1, high + 1):
                if nums_cnt[j][1] > base:
                    nums_cnt[i + 1], nums_cnt[j] = nums_cnt[j], nums_cnt[i + 1]
                    i += 1
            nums_cnt[i], nums_cnt[low] = nums_cnt[low], nums_cnt[i]
            if i == k - 1:
                return nums_cnt[:k]
            elif i < k - 1:
                return findTopk(i + 1, high)
            else:
                return findTopk(low, i - 1)
        
        nums_cnt = list(Counter(nums).items())
        res = findTopk(0, len(nums_cnt) - 1)
        return [r[0] for r in res]
		def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 堆排序
        # heapq.nlargest(n, iterable, key=None)
        # 【val, key】 heapq 中优先比[0]
        conter = Counter(nums)
        heap = []
        for key, val in conter.items():
            if len(heap) >= k:
                if val > heap[0][0]:
                    heapq.heapreplace(heap,(val, key))
            else:
                heapq.heappush(heap,(val, key))
        return [item[1] for item in heap]

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。请找到和最小的 k 个数对 (u1,v1), (u2,v2) ... (uk,vk) 。

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 输出: [1,2],[1,4],[1,6] 解释: 返回序列中的前 3 对数： [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

  • 多路归并【优先队列】、二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        # 【BFS】【优先队列, 排序输出交给堆】【去重】
        m, n = len(nums1), len(nums2)
        heap = [(nums1[0] + nums2[0], 0, 0)]
        res = []
        visited = set()
        while heap:
            val, i, j = heapq.heappop(heap) 
            res.append((nums1[i], nums2[j]))
            visited.add((i, j))
            if len(res) == k:
                return res
            if i + 1 < m and (i + 1, j) not in visited:
                heapq.heappush(heap, (nums1[i + 1] + nums2[j], i + 1, j))
                visited.add((i + 1, j))
            if j + 1 < n and (i, j + 1) not in visited:
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
                visited.add((i, j + 1))
        return res

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        intervals.sort(key = lambda x: x[0])
        ans = []
        ans.append(intervals[0])
        for i in range(1, n):
            if ans[-1][1] >= intervals[i][0]:
                if (t := intervals[i][1]) > ans[-1][1]:
                    ans[-1][1] = t
            else:
                ans.append(intervals[i])
        return ans

给定两个数组，arr1 和 arr2，

  • arr2 中的元素各不相同
  • arr2 中的每个元素都出现在 arr1 中

对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

  • 自定义排序
1
2
3
4
5
6
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        def cmp(k):
            return (0, cmpDict[k]) if k in cmpDict else (1, k) 
        cmpDict = {val:i for i, val in enumerate(arr2)}
        return sorted(arr1, key = cmp)

发表于 更新于 分类于 ， 本文字数： 13k 阅读时长 ≈ 24 分钟

二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

  • 数组切片、字典递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 切片
        if len(preorder) == 0:
            return None
        rootVal = preorder[0]
        rootindex = inorder.index(rootVal)
        leftsize = rootindex
        root = TreeNode(rootVal)
        root.left = self.buildTree(preorder[1:leftsize+1], inorder[:rootindex])
        root.right = self.buildTree(preorder[leftsize+1:], inorder[rootindex+1:])
        return root

    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def recur(root, left, right):
            if left > right: return                               # 递归终止
            node = TreeNode(preorder[root])                       # 建立根节点
            i = dic[preorder[root]]                               # 划分根节点、左子树、右子树
            node.left = recur(root + 1, left, i - 1)              # 开启左子树递归
            node.right = recur(i - left + root + 1, i + 1, right) # 开启右子树递归
            return node                                           # 回溯返回根节点

        dic = {val: i for i, val in enumerate(inorder)}
        return recur(0, 0, len(inorder) - 1)

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

  • 分治、辅助单调栈

辅助单调栈：

Picture10.png

  • 借助一个单调栈 stack 存储值递增的节点；
  • 每当遇到值递减的节点 \(r_i\) ，则通过出栈来更新节点 \(r_i\)的父节点 \(root\) ；
  • 每轮判断 \(r_i和 root\)的值关系：
    • 若 \(r_i > root\)则说明不满足二叉搜索树定义，直接返回 false。
    • 若 \(r_i < root\) 则说明满足二叉搜索树定义，则继续遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if len(postorder) == 0:
            return True
        inorder = sorted(postorder)
        rootval = postorder[-1]
        rootindex = inorder.index(rootval)
        rightsize = len(inorder) - rootindex - 1
        if set(inorder[rootindex+1:]) != set(postorder[-1-rightsize:-1]):
            return False
        if set(inorder[:rootindex]) != set(postorder[:-1-rightsize]):
            return False
        return self.verifyPostorder(postorder[-1-rightsize:-1]) and self.verifyPostorder(postorder[:-1-rightsize])

    def verifyPostorder(self, postorder: [int]) -> bool:
        # 分治递归
        def recur(i, j):
            if i >= j: 
                return True
            p = i
            while postorder[p] < postorder[j]: 
                p += 1
            m = p
            while postorder[p] > postorder[j]: 
                p += 1
            return p == j and recur(i, m - 1) and recur(m, j - 1)

        return recur(0, len(postorder) - 1)
    
    def verifyPostorder(self, postorder: [int]) -> bool:
        # 单调队列
        stack, root = [], float("+inf")
        for i in range(len(postorder) - 1, -1, -1):
            if postorder[i] > root: return False
            while(stack and postorder[i] < stack[-1]):
                root = stack.pop()
            stack.append(postorder[i])
        return True

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def largestValues(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        q = deque([root])
        ans = []
        while q:
            k = len(q)
            tmp = float('-inf')
            for _ in range(k):
                node = q.popleft()
                if (t:= node.val) > tmp:
                    tmp = t
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(tmp)
        return ans

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

  • 深度优先遍历、广度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        curVal = curHeight = 0
        def dfs(node: Optional[TreeNode], height: int) -> None:
            if node is None:
                return
            height += 1
            dfs(node.left, height)
            dfs(node.right, height)
            nonlocal curVal, curHeight
            if height > curHeight:
                curHeight = height
                curVal = node.val
        dfs(root, 0)
        return curVal
		def findBottomLeftValue(self, root: Optional[TreeNode]) -> int:
        q = deque([root])
        while q:
            node = q.popleft()
            if node.right:
                q.append(node.right)
            if node.left:
                q.append(node.left)
            ans = node.val
        return ans

搜索

【层序遍历】

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root: return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            res.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        return res

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        ans, q = [], collections.deque()
        q.append(root)
        while q:
            tmp = []
            for i in range(len(q)):
                node = q.popleft()
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(tmp)
        return ans

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        ans, q = [], collections.deque()
        q.append(root)
        while q:
            tmp = []
            k = len(q)
            for _ in range(k):
                node = q.popleft()
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(tmp[::-1] if len(ans) % 2 else tmp)
        return ans

给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        left_high = self.maxDepth(root.left)
        right_high = self.maxDepth(root.right)
        return max(left_high, right_high)+1
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # 空树，高度为 0
        if root == None:
            return 0
        # 初始化队列和层次
        queue = [root]
        depth = 0
        # 当队列不为空
        while queue:
            # 当前层的节点数
            n = len(queue)
            # 弹出当前层的所有节点，并将所有子节点入队列
            for _ in range(n):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            depth += 1
        # 二叉树最大层次即为二叉树最深深度
        return depth

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        stack = [root]
        while stack:
            node = stack.pop()
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        # 反转左右子树
        if not root:
            return root
        root.left, root.right = root.right, root.left
        root.left = self.mirrorTree(root.left)
        root.right = self.mirrorTree(root.right)
   
        return root

[辅助函数]

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)，B是A的子结构， 即 A中有出现和B相同的结构和节点值。

  • ==对称性递归==：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/solution/yi-pian-wen-zhang-dai-ni-chi-tou-dui-che-uhgs/
1
2
3
4
5
6
7
8
9
10
class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        def recur(A, B):
            if not B: 
              	return True
            if not A or A.val != B.val: 
              	return False
            return recur(A.left, B.left) and recur(A.right, B.right)

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

[辅助函数]

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        def recur(left, right):
            if not left and not right:
                return True
            if not left or not right or left.val != right.val:
                return False
            return recur(left.left, right.right) and recur(left.right, right.left)
        return recur(root.left, root.right)

==输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表==。要求不能创建任何新的节点，只能调整树中节点指针的指向。为了让您更好地理解问题，以下面的二叉搜索树为例：

img

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

img

算法流程：

dfs(cur): 递归法中序遍历；

  • 终止条件： 当节点 cur 为空，代表越过叶节点，直接返回；
  • 递归左子树，即 dfs(cur.left) ；
  • 构建链表：
    • 当 pre 为空时： 代表正在访问链表头节点，记为 head ；
    • 当 pre 不为空时： 修改双向节点引用，即 pre.right = cur ， cur.left = pre ；
    • 保存 cur ： 更新 pre = cur ，即节点 cur 是后继节点的 pre ；
  • 递归右子树，即 dfs(cur.right) ；

treeToDoublyList(root)：

  • 特例处理： 若节点 root 为空，则直接返回；
  • 初始化： 空节点 pre ；
  • 转化为双向链表： 调用 dfs(root) ；
  • 构建循环链表： 中序遍历完成后，head 指向头节点， pre 指向尾节点，因此修改 head 和 pre 的双向节点引用即可；
  • 返回值： 返回链表的头节点 head 即可；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        def dfs(cur):
            if not cur: 
              	return
            dfs(cur.left) # 递归左子树
            if self.pre: # 修改节点引用
                self.pre.right, cur.left = cur, self.pre
            else: # 记录头节点
                self.head = cur
            self.pre = cur # 保存 cur
            dfs(cur.right) # 递归右子树
        
        if not root: return
        self.pre = None
        dfs(root)
        self.head.left, self.pre.right = self.pre, self.head
        return self.head

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

  • 从大到小：倒序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        # 中序遍历是单调的
        def dfs(root):
            nonlocal k, res
            if not root: 
                return
            dfs(root.right)
            k -= 1
            if k == 0: 
                res = root.val
                return
            dfs(root.left)
        res = 0
        dfs(root)
        return res

    def kthLargest(self, root: TreeNode, k: int) -> int:
        if not root: return
        def TreeSize(root: TreeNode):# 求子树节点个数
          	# 子树的深度
            if not root: 
              	return 0
            if not root.left and not root.right: 
             		return 1
            return TreeSize(root.left) + TreeSize(root.right) + 1
        nright = TreeSize(root.right)
        if nright >= k: #在右子树
            return self.kthLargest(root.right, k)
        elif nright == k - 1: return root.val
        else: 
            return self.kthLargest(root.left, k - nright - 1)

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root: return 0
        queue, res = deque([root]), 0
        while queue:
            k = len(queue)
            for i in range(k):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right: 
                    queue.append(node.right)
            res += 1
        return res
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

[辅助函数]

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def height(root: TreeNode) -> int:
            if not root:
                return 0
            leftH = height(root.left)
            rightH = height(root.right)
            if leftH == -1 or rightH == -1 or abs(leftH - rightH) > 1:
                return -1
            else:
                return max(leftH, rightH) + 1
        return height(root) >= 0

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

1
2
3
4
5
class Solution:
    def sumNums(self, n: int) -> int:
        def sumStop(n):
            return n >= 1 and n + sumStop(n-1)
        return sumStop(n)

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

  • 若 root.val < p.val，则 pp 在 root 右子树 中；
  • 若 root.val > p.val ，则 pp 在 root 左子树 中；

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点 2 和节点 8 的最近公共祖先是 6。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
      	# 迭代优化
        if p.val > q.val: p, q = q, p # 保证 p.val < q.val
        while root:
            if root.val < p.val: # p,q 都在 root 的右子树中
                root = root.right # 遍历至右子节点
            elif root.val > q.val: # p,q 都在 root 的左子树中
                root = root.left # 遍历至左子节点
            else: 
              	break
        return root
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
      	# 递归
        if root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        return root

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。深度优先遍历是从下往上返回，所以第一个满足的就是最近公共祖先节点 。

递归解析：
  • 终止条件：
    • 当越过叶节点，则直接返回 null；
    • 当 root等于 p, q ，则直接返回 root；
  • 递推工作：
    • 开启递归左子节点，返回值记为 left；
    • 开启递归右子节点，返回值记为 right ；
  • 返回值：根据 left 和 right ，可展开为四种情况；
    • 当 left 和 right 同时为空 ：说明 root的左 / 右子树中都不包含 p,q ，返回 null；
    • 当 left 和 right 同时不为空 ：说明 p, q分列在 root的 异侧 （分别在 左 / 右子树），因此 root为最近公共祖先，返回 root；
    • 当 left为空 ，right不为空 ：p,q都不在 root的左子树中，直接返回 right。具体可分为两种情况：
      • p,q 其中一个在 root的 右子树 中，此时 right 指向 p（假设为 p ）；
      • p,q 两节点都在 root的 右子树 中，此时的 right指向 最近公共祖先节点 ；
    • 当 left不为空 ， right为空 ：与情况 3. 同理；
1
2
3
4
5
6
7
8
9
class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if not root or root == q or root == p:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if left and right:
            return root
        return left if left else right

给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。计算从根节点到叶节点生成的 所有数字之和 。

  • 深度优先遍历、回溯【没有return】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        # dfs , 回溯
        ans = []
        def dfs(root, prevTotal):
            if not root:
                return 0
            total = prevTotal * 10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return dfs(root.left, total) + dfs(root.right, total)

        def backtrace(root, tmp):
            if not root:
                return root
            tmp.append(str(root.val))
            if not root.left and not root.right:
                ans.append(tmp[:])
                # 【没有return, 就会执行一次 pop() 】
            backtrace(root.left, tmp)
            backtrace(root.right, tmp)
            tmp.pop()
        backtrace(root, [])

        return sum([int("".join(nums)) for nums in ans])

给定一个二叉树 根节点 root ，树的每个节点的值要么是 0，要么是 1。请剪除该二叉树中所有节点的值为 0 的子树。节点 node 的子树为 node 本身，以及所有 node 的后代。

  • 建树【dfs 有返回值】
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def pruneTree(self, root: TreeNode) -> TreeNode:
        def dfs(root):
            if not root:
                return root
            root.left = dfs(root.left)
            root.right = dfs(root.right)
            if not root.left and not root.right and root.val == 0:
                return None
            return root    
        return dfs(root)

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

img

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。

  • 前缀和+回溯 o(n)、深度优先遍历【双重递归 0（n^2) 】

DFS中存在许多重复计算，我们定义节点的前缀和为：

  • curr 由根结点到当前结点的路径上所有节点的和；
  • 利用先序遍历二叉树，记录下根节点 root 到当前节点 p 的路径上除当前节点以外所有节点的前缀和；
  • 在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 curr 减去 targetSum。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # 深度优先遍历
        def dfs(root, total):
            if not root:
                return 0
            ans = 0
            total += root.val
            if total == targetSum:
                ans += 1
            return ans + dfs(root.left, total) + dfs(root.right, total)
        if not root:
            return 0
        return dfs(root, 0) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)
    
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # 前缀和 + 回溯
        pre = collections.defaultdict(int) # 根节点到当前节点和
        pre[0] = 1
        def backstace(root, curr):
            if not root:
                return 0
            curr += root.val # 根节点到当前节点和
            ans = 0
            ans += pre[curr - targetSum]
            # 回溯
            pre[curr] += 1
            ans += backstace(root.left, curr)
            ans += backstace(root.right, curr)
            pre[curr] -= 1
            return ans
        return backstace(root, 0)

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

给定一个二叉树的根节点 root ，返回其 最大路径和，即所有路径上节点值之和的最大值。

示例 2：

img

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

  • 节点贡献值 root + max(left, right) / 最大路径和：当前节点 + 左子树max + 右子树max
  • 动态过程保存：ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        ans = -inf
        def pathSum(root):
            nonlocal ans
            if not root:
                return 0
            left = max(pathSum(root.left), 0)
            right = max(pathSum(root.right), 0)
            if (t := root.val + left + right) > ans:
                ans = t
            return root.val + max(left, right)
        pathSum(root)
        return ans

给你一棵二叉搜索树，请 按中序遍历 将其重新排列为一棵递增顺序搜索树，使树中最左边的节点成为树的根节点，并且每个节点没有左子节点，只有一个右子节点。

发表于 更新于 分类于 ， 本文字数： 3.1k 阅读时长 ≈ 6 分钟

双指针

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

  • 双指针、队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 回溯 + set
        n = len(s)
        que = collections.deque()
        if len(s) == 0:
            return 0
        que.append(s[0])
        res = 1
        tmp = 1
        for i in range(1, n):
            if s[i] not in que:
                tmp += 1
            else:
                while que and que.popleft() != s[i]:
                    tmp -= 1
            que.append(s[i])
            res = max(res, tmp)
        return res
    def lengthOfLongestSubstring(self, s: str) -> int:
      	# 双指针 + 哈希表
        dic, res, i = {}, 0, -1
        for j in range(len(s)):
            if s[j] in dic:
                i = max(dic[s[j]], i) # 更新左指针 i
            dic[s[j]] = j # 哈希表记录
            res = max(res, j - i) # 更新结果
        return res

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if not head:
            return head
        cur = dummy = ListNode(0, head)
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
                break
            else:
                cur = cur.next
        return dummy.next

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

1
2
3
4
5
6
7
8
9
class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        fast, slow = head, head
        for _ in range(k):
            fast = fast.next
        while fast:
            fast = fast.next
            slow = slow.next
        return slow

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        while l1 and l2:
            if l1.val > l2.val:
                cur.next, l2 = l2, l2.next
            else:
                cur.next, l1 = l1, l1.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummy.next

输入两个链表，找出它们的第一个公共节点。

1
2
3
4
5
6
7
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p1, p2 = headA, headB
        while p1 != p2:
            p1 = p1.next if p1 else headB
            p2 = p2.next if p2 else headA
        return p1

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        left, right = 0, len(nums)-1
        while left < right:
            while nums[left]%2 == 1 and left < right: 
              	left += 1
            while nums[right]%2 == 0 and left < right: 
              	right -= 1
            nums[left], nums[right] = nums[right], nums[left]
        return nums
    def exchange(self, nums: List[int]) -> List[int]:
    		return sorted(nums, key = lambda x: x%2, reverse = True)

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

解题思路：

  • 利用 HashMap 可以通过遍历数组找到数字组合，时间和空间复杂度均为 O(N)；

  • 注意本题的 nums 是排序数组 ，因此可使用 双指针法 将空间复杂度降低至 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ndict = defaultdict(int)
        for i in range(len(nums)):
            if target-nums[i] in ndict:
                return [target-nums[i], nums[i]]
            ndict[nums[i]] = 1
        return []
        
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums)-1
        while left < right:
            s = nums[left] + nums[right]
            if s > target:
                right -= 1
            elif s < target:
                left += 1
            else:
                return [nums[left], nums[right]]
        return []

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def reverseWords(self, s: str) -> str:
        return " ".join(reversed(s.strip().split()))

    def reverseWords(self, s: str) -> str:
        s = s.strip() # 删除首尾空格
        i = j = len(s) - 1
        res = []
        while i >= 0:
            while i >= 0 and s[i] != ' ': i -= 1 # 搜索首个空格
            res.append(s[i + 1: j + 1]) # 添加单词
            while s[i] == ' ': i -= 1 # 跳过单词间空格
            j = i # j 指向下个单词的尾字符
        return ' '.join(res) # 拼接并返回

发表于 更新于 分类于 ， 本文字数： 3.2k 阅读时长 ≈ 6 分钟

栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

  • self.smin = [] 存储最小栈元素，记录当前最小值是什么。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MinStack:
    def __init__(self):
        self.sdata = []
        self.smin = []
        
    def push(self, x: int) -> None:
        self.sdata.append(x)
        if not self.smin or self.smin[-1] >= x:
            self.smin.append(x)

    def pop(self) -> None:
        if self.sdata.pop() == self.smin[-1]:
            self.smin.pop()

    def top(self) -> int:
        return self.sdata[-1]

    def min(self) -> int:
        return self.smin[-1]

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意 两个整数之间的除法只保留整数部分。

示例 1：

输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

  • 函数字典，isdigit只能判断正整数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        n = len(tokens)
        op = {
                '+': add,
                '-': sub,
                '*': mul,
                '/': lambda x, y: int(x / y)
        }
        stack = []
        for t in tokens:
            try:
                num = int(t)
            except ValueError:
                b = stack.pop()
                a = stack.pop()
                num = op[t](a, b)
            finally:
                stack.append(num)
        return stack[0]

单调栈

给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

img 
1
2
3
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights = [0] + heights + [0] # 哨兵
        stack, res = [0], 0
        for i in range(1, len(heights)):
            while stack and heights[i] <= heights[stack[-1]]:
                tmp = stack.pop()
                if stack:
                    weith = i - stack[-1] - 1
                    if (t := heights[tmp] * weith) > res:
                        res = t
            stack.append(i)
        return res

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

示例 1：

img 
1
2
3
输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def maximalRectangle(self, matrix: List[str]) -> int:
        def maximalhist(heights):
            heights = [0] + heights + [0]
            res, stack = 0, [0]
            for i in range(1, len(heights)):
                while stack and heights[i] <= heights[stack[-1]]:
                    tmp = stack.pop()
                    if stack:
                        weith = i - stack[-1] - 1
                        if (t := heights[tmp] * weith) > res:
                            res = t 
                stack.append(i)
            return res
        
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        pre = [0] * n
        ans = 0
        for i in range(m):
            for j in range(n):
                # if else 缩减
                if matrix[i][j] != '0':
                    pre[j] += int(matrix[i][j])
                else:
                    pre[j] = 0
            ans = max(ans, maximalhist(pre))
        return ans

给定一个整数数组 asteroids，表示在同一行的小行星。对于数组中的每一个元素，其绝对值表示小行星的大小，正负表示小行星的移动方向（正表示向右移动，负表示向左移动）。每一颗小行星以相同的速度移动。找出碰撞后剩下的所有小行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

示例 1：

输入：asteroids = [5,10,-5] 输出：[5,10] 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def asteroidCollision(self, asteroids: List[int]) -> List[int]:
        n = len(asteroids)
        stack = [0]
        for i in range(1, n):
            while stack and asteroids[stack[-1]] > 0 and asteroids[i] < 0:
                a = asteroids[stack[-1]]
                b = asteroids[i]
                if a + b < 0:
                    stack.pop()
                elif a + b > 0:
                    break
                elif a + b == 0:
                    stack.pop()
                    break
            else:
                stack.append(i)
        return [asteroids[i] for i in stack]

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        stack, ans = [0], [0] * n
        for i in range(1, n):
            while stack and temperatures[stack[-1]] < temperatures[i]:
                tmp = stack.pop()
                ans[tmp] = i - tmp
            stack.append(i)
        return ans

发表于 更新于 分类于 ， 本文字数： 2.7k 阅读时长 ≈ 5 分钟

队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

  • 初始化两个栈（s1输入栈、s2输出栈）
  • 将输入栈导出到输出栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class CQueue:
    def __init__(self):
        self.s1 = [] # 输入栈
        self.s2 = [] # 输出栈

    def appendTail(self, value: int) -> None:
        self.s1.append(value)

    def deleteHead(self) -> int:
        if self.s2:
            return self.s2.pop()
        if not self.s1:
            return -1
        while self.s1: # 清空输入栈
            self.s2.append(self.s1.pop())
        return self.s2.pop()

优先队列

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

  • 单调队列 0(1) 线性时间算出滑动窗口最大值
  • 优先队列（大根堆） 时间复杂度：O(nlogn) 空间复杂度：O(n) 【注意 Python 默认的优先队列是小根堆】
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 单调队列 0(1) 线性时间算出滑动窗口最大值 
        n = len(nums)
        q = collections.deque() # 保存最大索引
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                # 较小的备用,交大的删除前面小的
                q.pop()
            q.append(i)
        ans = [nums[q[0]]] # 第一个窗口初始化
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]:
                # 较小的备用,交大的删除前面小的
                q.pop()
            q.append(i)
            while q[0] <= i-k: # 最大的退役了
                q.popleft()
            ans.append(nums[q[0]])
        return ans
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        # 优先队列（大根堆） 时间复杂度：O(nlogn) 空间复杂度：O(n)
        n = len(nums)
        # 注意 Python 默认的优先队列是小根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q) #list2最小堆
        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k: # 弹出历史最大值的索引
                heapq.heappop(q)
            ans.append(-q[0][0])
        return ans

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

实现 MovingAverage 类：

  • MovingAverage(int size) 用窗口大小 size 初始化对象。
  • double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MovingAverage:
    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """
        self.nums = deque()
        self.total = 0
        self.size = size
        self.len = 0

    def next(self, val: int) -> float:
        if self.len >= self.size:
            self.total -= self.nums.popleft()
            self.len -= 1
        self.nums.append(val)
        self.total += val
        self.len += 1
        return self.total / self.len

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请实现 RecentCounter 类：

  • RecentCounter() 初始化计数器，请求数为 0 。

  • int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

  • 优先队列、二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class RecentCounter:
    """
    def __init__(self):
        self.q = deque()

    def ping(self, t: int) -> int:
        while self.q and (self.q[0] + 3000) < t:
            self.q.popleft()
        self.q.append(t)
        return len(self.q)
    """
    def __init__(self):
        self.ping_list = []

    def ping(self, t: int) -> int:
        self.ping_list.append(t)
        left = bisect_left(self.ping_list, t-3000) 
        return len(self.ping_list) - left

单调队列