算法能力提升计划 Algorithm Capability Enhancement Program

写在前面：
督促自己学习，顺便记录题解

更新记录

目录

（手动更新好累，暂时不更新了吧~）

211. 添加与搜索单词 - 数据结构设计

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
# 添加与搜索单词 - 数据结构设计

class WordDictionary:
    class TrieNode:
        def __init__(self):
            self.children = {}
            self.isEndOfWord = False
    # 这个题目应该是要使用字典树来实现的

    def __init__(self):
        self.root = self.TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = self.TrieNode()
            node = node.children[char]
        node.isEndOfWord = True

    def search(self, word: str) -> bool:
        # 使用dfs进行遍历
        def dfs(node: self.TrieNode, i: int) -> bool:
            if i == len(word):
                return node.isEndOfWord
            if word[i] == '.':
                return any(dfs(child, i+1) for child in node.children.values())
            if word[i] in node.children:
                return dfs(node.children[word[i]], i+1)
            return False
        return dfs(self.root, 0)

52. N 皇后 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# N 皇后 II

def totalNQueens(self, n: int) -> int:
    # 经典dfs问题
    # 需要创建visit数组（这里不固定所以很难做到）
    # 通过比较对角线上的和和差判断是否冲突
    result = [0]

    def dfs(queens, xyDiff, xySum):
        p = len(queens)
        if p == n:
            result[0] += 1
            return
        for q in range(n):
            if q not in queens and p-q not in xyDiff and p+q not in xySum:
                dfs(queens + [q], xyDiff+[p-q], xySum+[p+q])
    dfs([], [], [])
    return result[0]

918. 环形子数组的最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxSubarraySumCircular(self, nums: List[int]) -> int:
    # 虽然数组变成了环形
    # 但是我觉得还是可以用动态规划的思想来解决
    # 对于数组中环状连续子数组的最大和问题，实际上可以分为两种情况考虑：
    # 非环形子数组的最大和：这可以通过常规的动态规划（Kadane算法）来解决。遍历一次数组，找到非环形子数组可能的最大和。
    # 跨越环形边界的子数组的最大和：这一部分稍微复杂一点，可以通过计算总和减去非环形子数组的最小和来得到。为此，需要再次应用动态规划来找到非环形子数组的最小和。
    def kadane(nums):
        dp = [nums[0]] * len(nums)
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        return max(dp)

    # 首先求正常数组的最大值
    maxNormal = kadane(nums)
    if maxNormal < 0:
        return maxNormal
    maxCircular = sum(nums) + kadane([-x for x in nums])
    return max(maxNormal, maxCircular)

97. 交错字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 交错字符串
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    # 既然是动态规划的题目
    # 那就考虑创建dp数组
    l1, l2, l3 = len(s1), len(s2), len(s3)
    if l1 + l2 != l3 : return False
    # 创建一个l1+1xl2+1大小的数组
    # dp[i][j]表示s3的前i+j个字符是否能被s1的前i个字符和s2的前j个字符交错组成。
    dp = [[False] * (l2 + 1) for _ in range(l1 + 1)]
    dp[0][0] = True
    # 如果当前字符s3[i+j-1]等于s1[i-1]且dp[i-1][j]是true，那么dp[i][j]也应该是true；
    # 如果当前字符s3[i+j-1]等于s2[j-1]且dp[i][j-1]是true，那么dp[i][j]也应该是true。
    for i in range(1,l1+1):
        dp[i][0] = dp[i-1][0] and s1[i-1] == s3[i-1]
    for j in range(1, l2 +1):
        dp[0][j] = dp[0][j-1] and s2[j-1] == s3[j-1]

    for i in range(1, l1+1):
        for j in range(1, l2+1):
            if s1[i-1] == s3[i+j-1]:
                dp[i][j] |= dp[i-1][j]
            if s2[j-1] == s3[i+j-1]:
                dp[i][j] |= dp[i][j-1]
    return dp[l1][l2]

221. 最大正方形

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
# 最大正方形

def maximalSquare(self, matrix: List[List[str]]) -> int:

    # 这个题目的状态转移方程大致如下
    # 检查点dp[i][j] 需要检测左边、上边、左上边

    if not matrix or not matrix[0]:
        return 0

    maxSide = 0

    rows, cols = len(matrix), len(matrix[0])
    dp = [[0] * cols for _ in range(rows)]

    # 遍历dp数组
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1],
                                   dp[i-1][j-1]) + 1
                maxSide = max(maxSide, dp[i][j])
    return maxSide ** 2

289. 生命游戏

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
# 生命游戏
def gameOfLife(self, board: List[List[int]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    # 为了原地更新 board，但同时需要访问原始 board 状态，您可以使用额外的变量来表达更多状态。例如，可以规定：
    # -1 表示这个细胞之前是活的，现在死了。 （这样才能用abs进行状态判断！！！）
    # 3 表示这个细胞之前是死的，现在活了。

    rows, cols = len(board), len(board[0])

    # 方向向量
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    
    # 计算周围活着的邻居的数量
    def countLiveNeighbor(r, c):
        count = 0
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # 确保在合法区域内，并取绝对值判断原始状态
            if 0 <= nr < rows and 0 <= nc < cols and abs(board[nr][nc]) == 1:
                count += 1
        return count
    
    # 第一遍遍历：基于原始状态更新为中间状态（2和3）
    for r in range(rows):
        for c in range(cols):
            liveNeighbor = countLiveNeighbor(r, c)
            if board[r][c] == 1 and (liveNeighbor < 2 or liveNeighbor > 3):
                board[r][c] = -1  # 编码死亡状态
            if board[r][c] == 0 and liveNeighbor == 3:
                board[r][c] = 3  # 编码新生状态
    
    # 第二遍遍历：将中间状态解码为新状态
    for r in range(rows):
        for c in range(cols):
            if board[r][c] == -1:
                board[r][c] = 0  # 解码死亡状态
            elif board[r][c] == 3:
                board[r][c] = 1  # 解码新生状态

230. 二叉搜索树中第K小的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 二叉搜索树中第K小的元素
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
    # 这个题目需要利用二叉搜索树的性质
    # 即node.left.val < node.val < node.right.val
    # 所以最小的绝对差
    # 一定是相邻的节点
    # 为了找到给定二叉搜索树中任意两节点的最小绝对差值，您可以对二叉搜索树进行中序遍历。由于二叉搜索树的中序遍历结果是一个递增的序列，那么任意两个相邻节点的差值将会是节点间的最小差值。
    inOrder = []

    def inOrderTraverse(node):
        if len(inOrder) >= k:
            return
        if not node:
            return
        inOrderTraverse(node.left)
        inOrder.append(node.val)
        inOrderTraverse(node.right)

    inOrderTraverse(root)

    return inOrder[k-1]

530. 二叉搜索树的最小绝对差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 二叉搜索树的最小绝对差
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
    # 这个题目需要利用二叉搜索树的性质
    # 即node.left.val < node.val < node.right.val
    # 所以最小的绝对差
    # 一定是相邻的节点
    # 为了找到给定二叉搜索树中任意两节点的最小绝对差值，您可以对二叉搜索树进行中序遍历。由于二叉搜索树的中序遍历结果是一个递增的序列，那么任意两个相邻节点的差值将会是节点间的最小差值。
    inOrder = []
    self.minDiff = float('inf')

    def inOrderTraverse(node):
        if not node:
            return
        inOrderTraverse(node.left)
        if inOrder:
            self.minDiff = min(self.minDiff, node.val - inOrder[-1])
        inOrder.append(node.val)
        inOrderTraverse(node.right)

    inOrderTraverse(root)

    return self.minDiff

98. 验证二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 验证二叉搜索树
def isValidBST(self, root: Optional[TreeNode]) -> bool:
    # 上述解法是狭隘的
    def validate(node, low=float('-inf'), high=float('inf')):
        if not node:
            return True

        if not (low < node.val < high):
            return False

        # 递归检查
        return (validate(node.left, low, node.val) and
                validate(node.right, node.val, high))
    return validate(root)

127. 单词接龙

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
# 单词接龙
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:

    # 首先建图
    bankSet = set(wordList)
    if endWord not in bankSet:
        return 0

    def canTransform(word1, word2):
        count = 0
        for c1, c2 in zip(word1, word2):
            if c1 != c2:
                count += 1
        return count == 1

    # 初始化队列
    queue = deque([(beginWord, 1)])

    while queue:
        currentWord, stepCount = queue.popleft()
        if currentWord == endWord:
            # 第一个找到的一定是最小的
            return stepCount
        # 继续寻找
        for i in range(len(currentWord)):
            # 按照26个英文字母进行遍历
            # 对当前的word进行构造，如果能够构造出一个在bankset中的单词就加入队列
            # 由于只能使用一次，所以删除bankset中的单词
            for c in 'abcdefghijklmnopqrstuvwxyz':
                nextWord = currentWord[:i] + c + currentWord[i+1:]
                if canTransform(nextWord, currentWord) and nextWord in bankSet:
                    bankSet.remove(nextWord)
                    queue.append((nextWord, stepCount + 1))

    return 0

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

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
# 随机链表的复制

def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
    # 这个题目的难点就在于随机节点的复制
    # 目前想到的方法就是使用一个dict去存储映射关系
    if not head:
        return None

    # 创建对应关系
    o2n = {}

    # 第一次遍历,创建新的链表
    current = head
    while current:
        copy = Node(current.val)
        o2n[current] = copy
        current = current.next

    # 再次遍历,建立random的对应关系
    current = head
    while current:
        if current.next:
            o2n[current].next = o2n[current.next]
        if current.random:
            o2n[current].random = o2n[current.random]
        current = current.next

    return o2n[head]

25. 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
# K 个一组翻转链表
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # 思路就是先分解成子问题,再按照标准的反转方法进行反转
    dummy = ListNode(0)
    dummy.next = head
    prev, end = dummy, dummy

    def reverse(start):
        prev = None
        curr = start
        while curr:
            nextTemp = curr.next
            curr.next = prev
            # 移动到下一个位置
            prev = curr
            curr = nextTemp
        return prev

    while end.next:
        # 找到每组的k个节点
        for i in range(k):
            end = end.next
            if not end:
                return dummy.next
        # 记录next
        start = prev.next
        next = end.next

        end.next = None
        # 反转当前k个节点
        prev.next = reverse(start)
        start.next = next
        # 重新确定prev的位置
        prev = start
        end = prev
    return dummy.next

210. 课程表 II

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
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    # 这个题目依然是拓扑排序
    # 先把1的代码抄过来
    graph = defaultdict(list)
    indegrees = [0 for _ in range(numCourses)]

    # 构建图
    for cur,pre in prerequisites:
        graph[pre].append(cur)
        indegrees[cur] += 1
    
    # 进行拓扑排序
    queue = deque([i for i in range(numCourses) if indegrees[i] == 0] )

    # 结果数组
    res = []
    finishedCourse = 0

    while queue:
        course = queue.popleft()
        # 课程数+1
        finishedCourse += 1
        res.append(course)
        # 入度-1
        for nextCourse in graph[course]:
            indegrees[nextCourse] -= 1
            if indegrees[nextCourse] == 0:
                queue.append(nextCourse)
    return res if finishedCourse == numCourses else []

207. 课程表

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
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    # 这就是一个图的拓扑排序问题
    graph = defaultdict(list)
    indegrees = [0 for _ in range(numCourses)]

    # 构建图
    for cur,pre in prerequisites:
        graph[pre].append(cur)
        indegrees[cur] += 1
    
    # 进行拓扑排序
    queue = deque([i for i in range(numCourses) if indegrees[i] == 0] )

    finishedCourse = 0

    while queue:
        course = queue.popleft()
        # 课程数+1
        finishedCourse += 1
        # 入度-1
        for nextCourse in graph[course]:
            indegrees[nextCourse] -= 1
            if indegrees[nextCourse] == 0:
                queue.append(nextCourse)
    return finishedCourse == numCourses

433. 最小基因变化

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
# 最小基因变化

def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
    # 这个题目的想法就是先建图
    # 基因库中的基因是可以相互转换的，并且start可以转换到基因库中的基因
    # 因此建图后可以通过bfs，找到最小的转变次数
    # 一次基因变化就意味着这个基因序列中的一个字符发生了变化
    def isValidMutation(gene1, gene2):
        count = 0
        for i in range(len(gene1)):
            if gene1[i] != gene2[i]:
                count += 1
            if count > 1:
                return False
        return count == 1

    bankSet = set(bank)
    if endGene not in bankSet:
        return -1

    queue = deque([(startGene, 0)])
    while queue:
        currGene, mutations = queue.popleft()
        if currGene == endGene:
            return mutations
        for gene in bankSet.copy():
            if isValidMutation(currGene, gene):
                bankSet.remove(gene)
                queue.append((gene, mutations + 1))
    return -1

909. 蛇梯棋

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
# 蛇梯棋
def snakesAndLadders(self, board: List[List[int]]) -> int:
    # 读题读了半天
    # 感觉可以用一个模拟解决
    # 但这个是放在bfs里面的
    # 先抄一下
    # 因此，BFS策略天然适合用于解决在无权图（即所有边的权重都相同的图）中找到最短路径的问题
    n = len(board)

    def get(s):
        quot, rem = divmod(s - 1, n)
        row = n - 1 - quot
        col = rem if row % 2 != (n % 2) else n - 1 - rem
        return row, col

    queue = deque([1])
    visited = set()
    step = 0

    while queue:
        size = len(queue)
        s = queue.popleft()
        for _ in range(size):
            if s == n * n:
                return step
            # 模拟骰子🎲
            for s2 in range(s + 1, min(s+6, n*n) + 1):
                # 因为是平方，所以需要转换一下坐标
                r, c = get(s2)
                if board[r][c] != -1:
                    s2 = board[r][c]
                if s2 not in visited:
                    visited.add(s2)
                    queue.append(s2)
        step += 1
    # 如果还没有到达终点说明无法到达
    return -1

399. 除法求值

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
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    # 替换成有向图的遍历问题
    # 除法的算式作为节点和边
    # 建立图
    self.graph = defaultdict(dict)
    # 将算式和结果加入（倒数也要加入）
    for (dividend, divisor), value in zip(equations, values):
        self.graph[dividend][divisor] = value
        self.graph[divisor][dividend] = 1.0 / value

    # 进行dfs遍历
    def dfs(start, end, visited):
        if start not in self.graph:
            return -1.0
        if start == end:
            return 1.0
        visited.add(start)

        for neighbor, value in self.graph[start].items():
            if neighbor in visited:
                continue

            visited.add(neighbor)

            temp = dfs(neighbor, end, visited)
            if temp != - 1.0:
                return value * temp
        return - 1.0

    return [dfs(Cj, Dj, set()) for Cj, Dj in queries]

133. 克隆图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
    # 需要深拷贝
    # 使用dfs进行遍历
    if not node:
        return None

    visited = {}

    def dfs(node):
        if node in visited:
            return visited[node]

        clonedNode = Node(node.val)
        visited[node] = clonedNode

        for neighbor in node.neighbors:
            clonedNodeNeighbor = dfs(neighbor)
            clonedNode.neighbors.append(clonedNodeNeighbor)

        return clonedNode
    return dfs(node)

130. 被围绕的区域

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
# 被围绕的区域
def solve(self, board: List[List[str]]) -> None:
    # 感觉和岛屿数量差不多 只是需要稍微修改一下代码
    # 但是实际上的解决思路应该是
    if not board or not board[0]:
        return

    def dfs(i, j):
        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != 'O':
            return
        board[i][j] = 'A'
        dfs(i, j+1)
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j-1)
    # 对边界的O进行处理
    for i in range(len(board)):
        dfs(i, 0)
        dfs(i, len(board[0])-1)
    for j in range(len(board[0])):
        dfs(0, j)
        dfs(len(board)-1, j)
    # 现在情况下，与边界O相连的区域已经全是A了，只需要将剩下的O替换成X即可，A替换成O
    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == 'O':
                board[i][j] = 'X'
            if board[i][j] == 'A':
                board[i][j] = 'O'

200. 岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 岛屿数量
def numIslands(self, grid: List[List[str]]) -> int:
    def dfs(i, j):
        # 如果触碰到岛屿的边界或者是地图的边界，直接返回，不会进行下一步的操作了
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
            return
        # 核心思路就是每次找到一个1 就把它和他周围的1标记成0 记录为一块岛屿
        grid[i][j] = '0'
        # 探查周围的岛屿数量
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
    if not grid:
        return 0

    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
    return count

103. 二叉树的锯齿形层序遍历

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
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    # 应该是需要加个flag记录是否翻转
    res = []
    queue = deque()
    isFlip = False
    # 首先加入队列
    if not root:
        return res

    queue.append(root)

    while len(queue) > 0:
        # 首先需要记录当前层的长度
        levelLen = len(queue)
        levelRes = []
        # 层序遍历
        for i in range(levelLen):
            node = queue.popleft()
            if isFlip:
                # 应该是改变元素插入的顺序，而不是遍历方式
                levelRes.insert(0, node.val)
            else:
                levelRes.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        isFlip = not isFlip
        res.append(levelRes)
    return res

102. 二叉树的层序遍历

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
# 二叉树的层序遍历

def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
    res = []
    queue = deque()
    # 首先加入队列
    if not root:
        return res

    queue.append(root)

    while len(queue) > 0:
        # 首先需要记录当前层的长度
        levelLen = len(queue)
        levelRes = []
        # 层序遍历
        for i in range(levelLen):
            node = queue.popleft()
            levelRes.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # 计算平均值
        res.append(levelRes)
    return res

637. 二叉树的层平均值

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
# 二叉树的层平均值

def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
    res = []
    queue = deque()
    # 首先加入队列
    if not root:
        return res

    queue.append(root)

    while len(queue) > 0:
        # 首先需要记录当前层的长度
        levelLen = len(queue)
        levelSum = 0
        # 层序遍历
        for i in range(levelLen):
            node = queue.popleft()
            # 如果是最后一个节点
            levelSum += node.val
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        # 计算平均值
        res.append(levelSum/levelLen)
    return res

199. 二叉树的右视图

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

# 二叉树的右视图

def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
    # 右视图
    # 多分析几个情况
    # 应该可以用递归解决
    # 还和层高有关系，那么应该用层序遍历，将每一层的最后一个节点加入res
    res = []
    queue = deque()
    # 首先加入队列
    if not root:
        return res

    queue.append(root)

    while len(queue) > 0:
        # 首先需要记录当前层的长度
        levelLen = len(queue)

        # 层序遍历
        for i in range(levelLen):
            node = queue.popleft()
            # 如果是最后一个节点
            if i == levelLen - 1:
                res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    return res

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

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
# 二叉树中的最大路径和
def maxPathSum(self, root: Optional[TreeNode]) -> int:
    # 这个题目感觉有点像动态规划的思路
    self.maxSum = float('-inf')

    def dfs(node):
        if not node:
            return 0

        leftGain = max(dfs(node.left), 0)
        rightGain = max(dfs(node.right), 0)

        # 当前节点所在的路径最大值
        pathSum = node.val + leftGain + rightGain

        # 判断当前和全局最大值的大小关系
        self.maxSum = max(self.maxSum, pathSum)
        # 为什么只返回其中一边的gain呢？ 避免重复

        # 一个节点要么自身成为边的根节点，要么成为贡献者
        # 所以他的返回值应该是单边的gain
        return node.val + max(leftGain, rightGain)

    dfs(root)
    return self.maxSum

173. 二叉搜索树迭代器

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 BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        # 初始化一个空栈
        self.stack = []
        # 将左子树节点加入
        self.leftmostInorder(root)

    def leftmostInorder(self, root):
        while root:
            self.stack.append(root)
            root = root.left

    def next(self) -> int:
        topmostNode = self.stack.pop()

        if topmostNode.right:
            self.leftmostInorder(topmostNode.right)

        return topmostNode.val

    def hasNext(self) -> bool:
        return len(self.stack) > 0

222. 完全二叉树的节点个数

  • 优化版
    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
    # 完全二叉树的节点个数

    def countNodes(self, root: Optional[TreeNode]) -> int:
        def countHeight(node):
            height = 0
            while node:
                node = node.left
                height += 1
            return height

        if not root:
            return 0

        # 分别求左右子树的高度
        leftHeight = countHeight(root.left)
        rightHeight = countHeight(root.right)

        # 判断左右子树的高度关系
        if leftHeight == rightHeight:
            # 如果左右子树高度相等
            # 说明现在左子树是满二叉树，需要递归判断右子树的情况
            return (1 << leftHeight) - 1 + self.countNodes(root.right) + 1
        else:
            # 说明现在右子树是满的，需要递归判断左子树
            return (1 << rightHeight) - 1 + self.countNodes(root.left) + 1
  • 普通版
    1
    2
    3
    4
    5
    # 普通版
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

236. 二叉树的最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 二叉树的最近公共祖先
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    # 感觉可以转换一下思路
    # 与其说是找最近公共祖先,不如说在当前root下能否找到p和q
    if not root:
        return None
    if root == p or root == q:
        return root

    # 在左子树中找pq
    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

112. 路径总和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 路径总和
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

    def dfs(node, sum):
        if not node:
            return False

        sum += node.val

        if not node.left and not node.right:
            return sum == targetSum

        # 递归判断左右子树
        return dfs(node.left, sum) or dfs(node.right, sum)
    return dfs(root, 0)

129. 求根节点到叶节点数字之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 求根节点到叶节点数字之和

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    # 递归（循环）思路
    # root * 10 + val
    def dfs(node, currentNumber):
        if not node:
            return 0
        currentNumber = currentNumber * 10 + node.val

        # 如果是叶子节点，就直接返回
        if not node.left and not node.right:
            return currentNumber

        # 递归计算左右zishu
        leftSum = dfs(node.left, currentNumber)
        rightSum = dfs(node.right, currentNumber)

        return leftSum + rightSum

    return dfs(root, 0)

114. 二叉树展开为链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 二叉树展开为链表
def flatten(self, root: Optional[TreeNode]) -> None:
    """
    Do not return anything, modify root in-place instead.
    """
    if root is None:
        return 
    
    self.flatten(root.left)
    self.flatten(root.right)

    # 暂时保存右子树
    tempRight = root.right

    # 将flatten以后的进行操作
    root.right = root.left
    root.left = None
    # 一路遍历到叶子节点
    while root.right:
        root = root.right
    # 将原来的右子树拼接在最后
    root.right = tempRight

117. 填充每个节点的下一个右侧节点指针 II

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

# 填充每个节点的下一个右侧节点指针 II
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next

def connect(self, root: 'Node') -> 'Node':
    # 看到题目的要求 想到了二叉树的层序遍历
    # 层序遍历需要使用队列
    if not root:
        return None
    # 初始化队列，将根节点加入
    queue = deque([root])

    while queue:
        size = len(queue)
        # 遍历当前层的节点
        for i in range(size):
            node = queue.popleft()
            # 如果不是最右边的节点，则将next指针指向右边的
            if i < size - 1:
                node.next = queue[0]

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return root

105. 从前序与中序遍历序列构造二叉树

  • 这两个题都利用了一个性质，左右子树的元素个数是一致的
    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
    # 从前序与中序遍历序列构造二叉树

    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        # 给定的输入如下：
        # 前序遍历：[3, 9, 20, 15, 7]
        # 中序遍历：[9, 3, 15, 20, 7]
        # 首先，根据前序遍历，我们知道根节点是3。
        # 对于中序遍历[9, 3, 15, 20, 7]：
        # 根节点3之前的所有节点[9]构成左子树。
        # 根节点3之后的所有节点[15, 20, 7]构成右子树。
        # 接下来，我们就有了两个子问题：
        # 左子树的前序遍历是[9]，中序遍历是[9]。
        # 右子树的前序遍历是[20, 15, 7]，中序遍历是[15, 20, 7]。
        # 确定根节点：在前序遍历中找到树的根节点（序列的第一个元素）。
        # 划分树的左右子树：在中序遍历序列中找到根节点，这样就可以确定左子树和右子树的节点。
        # 递归构造子树：对于根节点的左侧和右侧序列，重复以上过程，构造左子树和右子树。
        if not preorder or not inorder:
            return None
        # 第一个一定是根节点
        root = TreeNode(preorder[0])
        mid = inorder.index(preorder[0])

        root.left = self.buildTree(preorder[1:mid+1], inorder[:mid])
        root.right = self.buildTree(preorder[mid+1:], inorder[mid+1:])
        return root

106. 从中序与后序遍历序列构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
# 从中序与后序遍历序列构造二叉树
def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
    # 需要注意的是，后序遍历的最后一个节点一定是根节点，所以这个题目就很简单了
    if not inorder or not postorder:
        return None
    # 最后一个一定是根节点
    root = TreeNode(postorder[-1])
    mid = inorder.index(postorder[-1])

    root.left = self.buildTree(inorder[:mid+1], postorder[:mid])
    root.right = self.buildTree(inorder[mid+1:], postorder[mid:-1])

    return root

101. 对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 对称二叉树
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    if not root:
        return True
    # 判断对称这个简单
    # 只需要递归的判断左右子树是否对称即可

    def dfs(left, right):
        if not (left or right):
            return True
        if not (left and right):
            return False
        if left.val != right.val:
            return False
        return dfs(left.left, right.right) and dfs(left.right, right.left)

    return dfs(root.left, root.right)

226. 翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 翻转二叉树

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    # 需要翻转二叉树的左右子树
    if not root:
        return None
    # 翻转左子树
    left = self.invertTree(root.left)

    # 翻转右子树
    right = self.invertTree(root.right)

    # 交换翻转后的节点
    root.left, root.right = right, left

    return roots

100. 相同的树

1
2
3
4
5
6
7
8
9
10
11
12
13
# 相同的树
# 关键点还是在于遍历
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    # 还得是题解
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    # 递归检查左右子树
    return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

104. 二叉树的最大深度

1
2
3
4
5
6
7
8
9
10
11
12
# 二叉树的最大深度
# 很简单的一道二叉树的遍历题，帮我回顾二叉树
def maxDepth(self, root: Optional[TreeNode]) -> int:
    # 创建一个变量记录最大深度
    def dfs(node: Optional[TreeNode]):
        if not node:
            return 0
        leftDepth = dfs(node.left)
        rightDepth = dfs(node.right)

        return max(leftDepth, rightDepth) + 1
    return dfs(root)

86. 分隔链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
    # 创建两个附加头节点
    head1 = ListNode()
    head2 = ListNode()
    cur1 = head1
    cur2 = head2
    while head:
        if head.val < x:
            cur1.next = ListNode(head.val)
            cur1 = cur1.next
        else:
            cur2.next = ListNode(head.val)
            cur2 = cur2.next
        head = head.next
    # 拼接两个链表
    # 注意拼接的位置
    cur1.next = head2.next
    return head1.next

61. 旋转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # 这个题实际上不是翻转链表 而是旋转链表
    if not head or not head.next or k == 0:
        return head

    cur = head
    length = 1
    while cur.next:
        cur = cur.next
        length += 1
    # 形成环
    cur.next = head

    # 找到旋转后的链表的尾巴，从尾巴处切开就是新的链表
    tail = head
    steps = length - k % length
    for i in range(steps - 1):
        tail = tail.next

    newHead = tail.next
    tail.next = None
    return newHead

71. 简化路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 简化路径

def simplifyPath(self, path: str) -> str:
    # 创建一个栈
    stack = []
    # 首先去掉多余的/
    # 使用正则表达式进行匹配
    path = re.sub(r'/+', '/', path)
    # 将path转换成数组
    paths = path.split('/')
    for item in paths:
        if item == '.' or item == '':
            continue
        if item == '..':
            if stack:
                stack.pop()
            continue
        stack.append(item)
    # 不需要对字符串进行翻转
    return '/' + '/'.join(stack)

155. 最小栈

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 MinStack:

    def __init__(self):
        # 用一个变量维护最小值的方式不太可取，因为pop时总是需要找到下一个最小值，是否能够满足在常数时间复杂度内完成这个操作
        # 但是可以创一个辅助的栈来帮助我们完成
        self.stack = []
        self.minStack = []

    def push(self, val: int) -> None:
        # 常规push
        self.stack.append(val)
        # 最小栈的维护
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)
        else:
            # 为什么要再次加入最小元素
            # 因为始终保持了同步
            self.minStack.append(self.minStack[-1])

    def pop(self) -> None:
        self.stack.pop()
        self.minStack.pop()

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

    def getMin(self) -> int:
        return self.minStack[-1]

452. 用最少数量的箭引爆气球

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 用最少数量的箭引爆气球
def findMinArrowShots(self, points: List[List[int]]) -> int:
    # 感觉这个题也是合并区间
    # 找到最后不能合并的区间的个数
    if not points:
        return 0
    nums = len(points)
    # 注意:由于至少需要一只箭,所以初始化为1
    res = 1
    # 首先points按照第一个元素的顺序排序
    points.sort(key=lambda x: x[1])
    # 然后遍历point
    i = 0
    # 可以只记录一个end即可
    end = points[0][1]
    for i in range(1, len(points)):
        if points[i][0] > end:
            res += 1
            end = points[i][1]
    return res

57. 插入区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 插入区间

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    res = []
    i = 0

    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        res.append(intervals[i])
        i += 1

    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval = [min(newInterval[0], intervals[i][0]),
                       max(newInterval[1], intervals[i][1])]
        i += 1
    res.append(newInterval)

    while i < len(intervals):
        res.append(intervals[i])
        i += 1

    return res

🌟76. 最小覆盖子串

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
# 最小覆盖子串
def minWindow(self, s: str, t: str) -> str:
    if not s or not t:
        return ""

    # 创建字典记录字母的出现次数
    tDict = Counter(t)

    # 创建滑动窗口的边界
    left, right = 0, 0
    # formed 用于记录当前窗口中满足 t_dict 条件的字符数
    formed = 0
    # 需要满足的字符数
    required = len(tDict)

    windowDict = {}

    # ans 用于记录最小覆盖子串的位置信息和长度
    # (子串长度, 左边界索引, 右边界索引)
    ans = float("inf"), None, None

    while right < len(s):

        character = s[right]
        windowDict[character] = windowDict.get(character, 0) + 1

        if character in tDict and windowDict[character] == tDict[character]:
            formed += 1

        # 缩小滑动窗口
        while left <= right and formed == required:
            character = s[left]
            # 判断是否更新答案
            if right - left + 1 < ans[0]:
                ans = (right - left + 1, left, right)
            windowDict[character] -= 1
            if character in tDict and windowDict[character] < tDict[character]:
                formed -= 1
            left += 1
        right += 1

    return "" if ans[0] == float("inf") else s[ans[1]:ans[2]+1]

🌟30. 串联所有单词的子串

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
# 串联所有单词的子串

def findSubstring(self, s: str, words: List[str]) -> List[int]:
    if not words or not s:
        return []
    # 每个单词的长度都是相同的
    wordLen = len(words[0])
    wordCount = len(words)
    totalLen = wordLen * wordCount
    # 使用哈希表存储words中单词的出现次数
    wordFreq = Counter(words)
    # 结果列表
    indices = []

    for i in range(wordLen):
        left = i
        right = i
        currentFreq = Counter()

        while right + wordLen <= len(s):
            word = s[right:right + wordLen]
            right += wordLen
            if word in wordFreq:
                currentFreq[word] += 1
                # 如果当前单词频率超过所需频率，则移动左指针直到频率正常
                while currentFreq[word] > wordFreq[word]:
                    leftWord = s[left:left + wordLen]
                    currentFreq[leftWord] -= 1
                    left += wordLen
                if right - left == totalLen:
                    indices.append(left)
            else:
                # 当前单词不在 word_freq 中，重置 left 和 current_freq
                currentFreq.clear()
                left = right
    return indices

🌟373. 查找和最小的 K 对数字

  • 使用堆
  • 掌握的不是很牢，需要巩固
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    # 查找和最小的 K 对数字
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        # 不会做，抄一下
        if not nums1 or not nums2:
            return []

        minHeap = []

        for i in range(min(k, len(nums1))):
            heapq.heappush(minHeap, (nums1[i]+nums2[0], i, 0))

        result = []

        while k > 0 and minHeap:
            sumVal, i, j = heapq.heappop(minHeap)
            result.append([nums1[i], nums2[j]])

            if j + 1 < len(nums2):
                heapq.heappush(minHeap, (nums1[i]+nums2[j + 1], i, j+1))
            k -= 1
        return result

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 数组中的第K个最大元素
def findKthLargest(self, nums: List[int], k: int) -> int:
    # 获取第k大的元素，一个符合直觉的方法就是排序
    # 但是这个是在 堆 这个系列里面的
    # 说明如果使用排序
    # 肯定会超过时间
    # 而且存在问题,因为可能有重复元素(这个题似乎没有这个限制)
    nums.sort(reverse=True)
    return nums[k-1]

def findKthLargest(self, nums: List[int], k: int) -> int:
    # 定义一个最小堆
    heap = []
    # 维护一个包含k个元素的最小堆
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

300. 最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
# 最长递增子序列
def lengthOfLIS(self, nums: List[int]) -> int:
    # 创建dp数组
    # 由于输出的是最长递增子序列的长度，所以dp数组表示的含义是到第i个字符时的序列长度
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
        # 这里存在一个问题，就是没有比较i之前的所有元素
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    # 最后返回的应该是dp子数组的最大值
    return max(dp)

198. 打家劫舍

  • 普通dp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 打家劫舍
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        elif len(nums) == 1:
            return nums[0]
        # 首先创建dp数组
        dp = [0] * len(nums)
        dp[0] = nums[0]
        # 在计算 dp[1] 的值时，您应该考虑抢第一家和不抢第一家、
        # 只抢第二家之间的选择，即 dp[1] 应该是 nums[0] 和 nums[1] 中的较大者，
        # 而不是直接赋值 nums[1]
        dp[1] = max(nums[1], nums[0])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        return dp[len(nums)-1]
  • 状态压缩dp
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 使用状态压缩进行优化
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        elif len(nums) == 1:
            return nums[0]
        # 创建两个状态
        prev, cur = nums[0], max(nums[0], nums[1])
        for i in range(2, len(nums)):
            # 先保存好cur
            temp = cur
            cur = max(cur, nums[i] + prev)
            prev = temp
        return cur

74. 搜索二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 搜索二维矩阵

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    # 目前的思路是将二维数组展平，然后用二分查找的方法
    rows, cols = len(matrix), len(matrix[0])

    # 对于一个元素i、j来说有这样的关系
    # 一维表示i * rows + cols
    # 那么反过来也是可以找到二维数组的索引的
    left, right = 0, rows * cols - 1
    while left <= right:
        mid = (left + right) >> 1
        x, y = divmod(mid, cols)
        if matrix[x][y] == target:
            return True
        elif matrix[x][y] < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

162. 寻找峰值

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 findPeakElement(self, nums: List[int]) -> int:
    # 使用二分查找加速
    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) >> 1
        if nums[mid] > nums[mid + 1]:
            right = mid
        else:
            left = mid + 1
    return left

def findPeakElement(self, nums: List[int]) -> int:
    if len(nums) <= 1:
        return 0
    # 首先写一个简单的算法
    # 遍历数组，找到第一个峰值元素
    for i in range(len(nums)):
        if i == 0:
            if nums[i] > nums[i+1]:
                return i
        elif i == len(nums) - 1:
            if nums[i] > nums[i-1]:
                return i
        else:
            if nums[i] > nums[i-1] and nums[i] > nums[i+1]:
                return i

148. 排序链表

  • 链表中点的寻找
  • 实际上是对链表进行归并排序
    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
    # 排序链表
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 使用快慢指针技术来找到链表的中点
        # 利用他们的速度是二倍的关系
        # 奇数：fast == end slow == mid
        # 偶数：fast == end + 1 slow == mid
        if not head or not head.next:
            return head

        slow, fast = head, head.next
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # 切分
        # 解耦链表
        mid, slow.next = slow.next, None

        # 递归的机型排序
        left, right = self.sortList(head), self.sortList(mid)

        return self.merge(left, right)

    def merge(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        tail = dummy

        while l1 and l2:
            if l1.val < l2.val:
                tail.next, l1 = l1, l1.next
            else:
                tail.next, l2 = l2, l2.next
            tail = tail.next

        tail.next = l1 if l1 else l2

        return dummy.next

108. 将有序数组转换为二叉搜索树

  • 递归程序的编写
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 将有序数组转换为二叉搜索树

    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        # 这个题目就是很经典的分治算法
        # 由于是排好序的数组，所以可以直接二分，进行树的构建
        # 先找mid值
        if not nums:
            return None

        mid = len(nums) // 2
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums=nums[0:mid])
        # nums[mid+1:-1] 从索引 mid+1 处开始截取，但是最后一个元素（索引为 -1 的那个元素）不包括在内。
        # 列表的切片操作是左闭右开的，因此 -1 表示停在倒数第一个元素之前。
        root.right = self.sortedArrayToBST(nums=nums[mid+1:])
        return root

64. 最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 最小路径和

def minPathSum(self, grid: List[List[int]]) -> int:
    # 按照直觉，这个也可以直接对原始数组进行操作
    rows, cols = len(grid), len(grid[0])
    # 按行进行更新
    for row in range(rows):
        for col in range(cols):
            if row == 0:
                if col != 0:
                    grid[row][col] += grid[row][col-1]
                continue
            if col == 0:
                grid[row][col] += grid[row-1][col]
                continue

            grid[row][col] += min(grid[row][col-1], grid[row-1][col])
    return grid[rows-1][cols-1]

120. 三角形最小路径和

  • 经典动态规划问题
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # 三角形最小路径和
    # 二维动态规划
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        # 自底向上更新triangle数组，这样能够节省空间
        n = len(triangle)
        # 注意：最后一行不需要更新，所以起始是n-1行
        for row in range(n-2, -1, -1):
            for col in range(len(triangle[row])):
                triangle[row][col] += min(triangle[row+1]
                                          [col], triangle[row+1][col+1])
        return triangle[0][0]

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
# 爬楼梯
def climbStairs(self, n: int) -> int:
    # 创建dp数组
    dp = [0] * (n+1)
    # 初始化dp数组
    dp[0] = 1
    dp[1] = 1
    for i in range(2,n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

35. 搜索插入位置

  • 注意右边边界的初始索引应该是length - 1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 搜索插入位置
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0

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

191. 位1的个数

  • 利用位检查或者位消除法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # 位检查
    def hammingWeight(self, n: int) -> int:
        # 每次右移一位
        count = 0
        while n:
            # 这里是按位与，1 的前面部分都是0
            count += n & 1
            n = n >> 1
        return count
    # 位清除

    def hammingWeight(self, n: int) -> int:
        # 利用n & n-1去清除最低位的1
        # 可以用这个方法来统计有多少个1（有多少1就要操作多少次）
        count = 0
        while n:
            n = n & (n-1)
            count += 1
        return count

201. 数字范围按位与

  • 这个题目的解题角度比较刁钻
  • 例如两个数11100b和11011b两个数
  • 他们有公共的前缀11，而一个连续的数值区间，一定会有后面的值为0的数，所以按位与之后的结果就是11000b
  • 那么就变得简单了，只需要记录下向右移动的次数，和最后剩下的前缀，就可以恢复得到最后的结果，bingo~
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    # 数字范围按位与
    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        # 这个代码理解起来有点复杂
        shift = 0
        # 找到共同前缀（移动的部分，至少有一个位为0，所以可以直接忽略）
        while left < right:
            left >>= 1
            right >>= 1
            shift += 1
        # 恢复结果（因为向右边移动了）
        return left << shift

136. 只出现一次的数字

  • 简单的方法：哈希表
    1
    2
    3
    4
    5
    6
    7
    8
    def singleNumber(self, nums: List[int]) -> int:
        # 看上去可以用哈希表解决
        numDict = dict()
        for i in range(len(nums)):
            numDict[nums[i]] = numDict.get(nums[i], 0) + 1
        # 获取只出现了一次的数字
        keys = [key for key, value in numDict.items() if value == 1]
        return keys[0]
  • 高效的办法：异或运算的性质
    1
    2
    3
    4
    5
    6
    7
    8
    # 利用异或运算快速操作
    def singleNumber(self, nums: List[int]) -> int:
        # 利用一个数如果与自身异或的结果是0
        # 0与任何数的异或结果都是那个数
        res = 0
        for num in nums:
            res ^= num
        return res

137. 只出现一次的数字 II

  • 简单的方法：哈希表
  • 高效的办法：32位统计每一位出现的次数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # 只出现一次的数字 II
    def singleNumber(self, nums: List[int]) -> int:
        # 这个题目可以换一种方式来思考
        # 首先转换成二进制的位
        res = 0
        for i in range(32):
            count = 0
            for num in nums:
                # 检查第i位是否位1
                # 1 << i表示将1左移i位，即在第i位上的值为1，其他位上的值为0。然后，我们用这个值和num做与操作，如果结果不为0，表明num在第i位上的值为1。
                if num & (1 << i):
                    count += 1
            # 对3取余
            # 主要是为了正确设置结果的值
            res |= (count % 3) << i 
        # 处理负数
        # 实际上不是32位的，但是人为限定成了32位
        if res >= 2**31:
            res -= 2**32
        return res
  • 超高效的办法：使用真值表求数字电路的表达式（饶了我吧）

190. 颠倒二进制位

  • 一种低效的算法
    1
    2
    3
    4
    5
    6
    7
    8
    def reverseBits(self, n: int) -> int:
        # 把数字转换成二进制字符串，去除0b
        binN = bin(n)[2:].zfill(32)
        # 翻转二进制字符串
        # 切片操作的格式是 [start:stop:step]
        reverseBinN = binN[::-1]
        # 转换成整数
        return int(reverseBinN, 2)
  • 一种高效的算法：分组位翻转算法（解释见[[分组位翻转算法]]）
    1
    2
    3
    4
    5
    6
    7
    def reverseBits(self, n: int) -> int:
        n = (n >> 16) | (n << 16)
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
        return n

67. 二进制求和

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
# 二进制求和
def addBinary(self, a: str, b: str) -> str:
    # 创建结果字符串
    res = ''
    lenA, lenB = len(a), len(b)
    # 一种简单的思路，为了简化计算，向较短的字符串中添加0
    if lenA > lenB:
        b = '0' * (lenA - lenB) + b
    else:
        a = '0' * (lenB - lenA) + a
    # 进位
    carry = 0
    for i in range(max(lenA,lenB) - 1, -1 , -1):
        sum = carry + int(a[i]) + int(b[i])
        if sum == 2:
            carry = 1
            res = '0' + res
        elif sum == 3:
            carry = 1
            res = '1' + res
        else:
            carry = 0
            res = str(sum) + res
    if carry == 1:
        res = '1' + res
    return res

22. 括号生成

  • 这个题目是一个比较经典的回溯算法题目
  • 两个条件
  • （括号的数量如果小于n，说明可以再加
  • ）括号的数量如果小于左括号，说明可以再加
  • 终止条件：当括号字符串的长度=2 * n
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 伪代码(默写复习)
    def xxx(n: int):
    	res = []
    	def backTrack(s, left, right):
    		if s == 2 * n:
    			res.append(s)
    			return
    		if left < n:
    			backTrack(s+'(', left + 1, right)
    		if right < left:
    			backTrack(s+')', left, right + 1)
    	backTrack('',0,0)
    	return res
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def generateParenthesis(self, n: int) -> List[str]:
        # 使用回溯法解决问题
        res = []

        def backTrack(s: str, left: int, right: int):
            if len(s) == 2 * n:
                res.append(s)
                return
            # 如果左边括号未达到n个，说明还能再加括号
            if left < n:
                backTrack(s + "(", left + 1, right)
            # 如果右边括号没有左边的多，说明需要加闭括号
            if right < left:
                backTrack(s + ")", left, right + 1)

        backTrack('', 0, 0)
        return res

17. 电话号码的字母组合

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

# 电话号码的字母组合

def letterCombinations(self, digits: str) -> List[str]:
    if not digits:
        return []
    # 首先创建一个字母和号码的对应表
    digit2letter = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz"
    }
    res = []

    def backTrack(s: str, digits: str):
        if len(digits) == 0:
            res.append(s)
            return

        for letter in digit2letter[digits[0]]:
            # 回溯后面的字符串
            backTrack(s+letter, digits[1:])

    backTrack('', digits)
    return res

77. 组合

  • 4/17复习
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # 组合
    def combine(self, n: int, k: int) -> List[List[int]]:
        # 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
        if k == 0:
            return []
        res = []

        def backTrack(current: List[int], start: int):
            if len(current) == k:
                # 使用切片复制一份
                res.append(current[:])
                return
            for i in range(start, n + 1):
                current.append(i)
                backTrack(current, i + 1)
                # 恢复状态
                current.pop()

        backTrack([], 1)
        return res

79. 单词搜索

  • 4/17复习 
    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
    # 单词搜索
    def exist(self, board: List[List[str]], word: str) -> bool:
        if not board:
            return False

        col, row = len(board[0]), len(board)

        # 定义一下搜索方向
        direct = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        # 创建visited数组
        visited = [[False] * col for _ in range(row)]

        def dfs(x, y, index):

            if index == len(word):
                return True
            # 判断是否越界
            # 判断条件有点多呀
            if x < 0 or x >= row or y < 0 or y >= col or board[x][y] != word[index] or visited[x][y]:
                return False

            # 检查下一个
            visited[x][y] = True
            for item in direct:
                if dfs(x+item[0], y+item[1], index + 1):
                    return True
            visited[x][y] = False
            return False

        for i in range(row):
            for j in range(col):
                if dfs(i, j, 0):
                    return True
        return False

39. 组合总和

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
# 组合总和

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    if not candidates:
        return []

    res = []
    candidates.sort()

    def backTrack(start, target, path):
        if target == 0:
            res.append(path[:])
            return
        if target < 0:
            return

        for i in range(start, len(candidates)):
            if candidates[i] > target:
                break
            path.append(candidates[i])
            backTrack(i, target - candidates[i], path)
            path.pop()

    backTrack(0, target, [])

    return res

    pass

  • 下面的代码有问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 下面的代码有问题不能去除重复
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    if not candidates:
        return []
    res = []

    def backTrack(cur, candidates):
        # 判断是否到了target
        sum = 0
        for i in cur:
            sum += i
        if sum == target:
            if cur not in res:
                res.append(cur[:])
            return
        elif sum > target:
            return
        else:
            for i in candidates:
                cur.append(i)
                backTrack(cur, candidates)
                cur.pop()
    backTrack([], candidates)
    return res

46. 全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 全排列

def permute(self, nums: List[int]) -> List[List[int]]:
    if not nums:
        return []

    res = []

    def backTrack(cur, last):
        if len(cur) == len(nums):
            res.append(cur[:])
            return

        for i in last:
            cur.append(i)
            # 回溯
            nextRemain = last[:]
            nextRemain.remove(i)
            backTrack(cur, nextRemain)
            cur.pop()

    backTrack([], nums)
    return res

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 删除排序链表中的重复元素 II
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # 一看就是双指针
    # 创建一个附加头节点
    dummy = ListNode(-1,head)
    prev = dummy
    # prev始终是head的前一个结点
    while head:
        if head.next and head.val ==head.next.val:
            # 跳过所有重复节点
            while head.next and head.val == head.next.val:
                head = head.next 
            # 再跳一个
            head = head.next
            prev.next = head
        else:
            prev = prev.next 
            head = head.next
    return dummy.next

92. 反转链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 反转链表 II

def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    if not head or left == right:
        return head

    dummy = ListNode(0, head)
    prev = dummy

    for _ in range(left - 1):
        prev = prev.next

    # start
    start = prev.next
    then = start.next

    for _ in range(right - left):
        # 反转链表
        start.next = then.next
        then.next = prev.next
        prev.next = then
        then = start.next
    return dummy.next

21. 合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 合并两个有序链表
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # 处理空表情况
    if not list1:
        return list2
    if not list2:
        return list1
    # 定义新的链表
    # 定义新的链表的伪头节点
    dummy = ListNode(-1)
    res = dummy

    # 当两个链表都不为空时，比较当前节点，并连接值较小的节点
    while list1 and list2:
        if list1.val < list2.val:
            res.next = list1
            list1 = list1.next
        else:
            res.next = list2
            list2 = list2.next
        res = res.next
    # 如果某一个链表已为空，直接将非空链表的剩余部分连接到新链表
    res.next = list1 if list1 else list2
    return dummy.next

141. 环形链表

  • 4/17复习
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 环形链表
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        # 如何检测链表中有没有环
        # 使用快慢指针！一个移动1个，一个移动2个，如果他们总会相遇，则说明有环
        if not head:
            return False

        slow = head
        fast = head.next()

        while slow != fast:
            # 如果快指针走到头了 说明没必要走了
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

322. 零钱兑换

  • 4/17复习
  • 为什么贪心不行？因为可能使用最大的面值最大数量导致最后不够分了，并不是最优解
  • 什么时候贪心可以？
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # 零钱兑换
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 这个题目一眼动态规划 二眼贪心

        # 创建dp数组
        # 含义 要达到i金额最小的硬币数量
        dp = [float('inf')] * (amount + 1)
        # 初始化dp数组
        dp[0] = 0
        # 按照硬币来遍历
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x-coin] + 1)
        # 最后返回最后一个值
        return dp[amount] if dp[amount] != float('inf') else -1

139. 单词拆分

  • 4/17复习
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 一个简单的动态规划问题
        # 首先初始化dp数组和dict集合
        wordSet = set(wordDict)
        dp = [False] * (len(s) + 1)
        dp[0] = True
        for i in range(1,len(s) + 1):
            for j in range(i):
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break
        return dp[len(s)]
  • 原始代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    # 单词拆分
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        # 一个简单的动态规划问题
        # 初始化dp数组
        # 建议将wordDict转换为集合，这样在查找时可以实现更快的操作，集合的查找时间复杂度是O(1)。
        wordSet = set(wordDict)
        dp = [False] * (len(s) + 1)

        dp[0] = True
        for i in range(1, len(s)+1):
            for j in range(i):
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True
                    break
        return dp[len(s)]

56. 合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 合并区间
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    # 这个题的目的是合并重叠的区间
    # 感觉可以先对数组进行一次排序，然后再根据情况合并
    intervals.sort(key=lambda x: x[0])
    start, end = intervals[0][0], intervals[0][1]
    res = []
    for i in range(1, len(intervals)):
        if intervals[i][0] <= end:
            if intervals[i][1] >= end: 
                end = intervals[i][1]
        else:
            res.append([start, end])
            start = intervals[i][0]
            end = intervals[i][1]
    # 对最后一个进行特判
    res.append([start, end])
    return res

228. 汇总区间

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
# 汇总区间
def summaryRanges(self, nums: List[int]) -> List[str]:
    if not nums:  # 处理空数组
        return []

    res = []
    start, end = 0, 0  # 初始化为第一个元素的下标
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
            end = i  # 更新范围的结束
        else:
            # 如果当前数字不是连续的，保存到目前为止的范围
            if start == end:  # 单个元素的范围
                res.append(str(nums[start]))
            else:  # 连续元素的范围
                res.append(str(nums[start]) + "->" + str(nums[end]))
            start, end = i, i  # 更新范围到新的开始地点

    # 循环结束后，检查并添加最后一个范围
    if start == end:  # 单个元素的范围
        res.append(str(nums[start]))
    else:  # 连续元素的范围
        res.append(str(nums[start]) + "->" + str(nums[end]))

    return res

73. 矩阵置零

  • 这个题目
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # 矩阵置零
    # 性能比较差的解法
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 感觉这个题的思路是：先记录下需要改变的行和列，最后统一置0
        rowSet = set()
        colSet = set()
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    rowSet.add(i)
                    colSet.add(j)
        for item in rowSet:
            for i in range(len(matrix[item])):
                matrix[item][i] = 0
        for item in colSet:
            for j in range(len(matrix)):
                matrix[j][item] = 0

48. 旋转图像

  • 开始想复杂了，实际上比较简单
  • 就是一个转置+水平翻转
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 旋转图像
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 原来旋转=转置+翻转行
        for i in range(len(matrix)):
            for j in range(i, len(matrix[0])):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # 翻转行
        for i in range(len(matrix)):
            matrix[i].reverse()

219. 存在重复元素 II

  • 两种解法：哈希表（和两数之和有点像）、滑动窗口+set
    1
    2
    3
    4
    5
    6
    7
    8
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 创建一个记录坐标的哈希表
        posDict = {}
        for i in range(len(nums)):
            if nums[i] in posDict and i - posDict[nums[i]] <= k:
                return True
            posDict[nums[i]] = i
        return False
  • 滑动窗口的解法（很巧妙呀）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 滑动窗口
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if len(nums) == 0:
            return False

        s = set()
        for i, x in enumerate(nums):
            # 超过窗口就移除之前那个
            if i > k:
                s.remove(nums[i-k-1])
            if x in s:
                return True
            s.add(x)
        return False

290. 单词规律

  • 和205简直一模一样
  • 也是需要创建双向映射
    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
    # 单词规律
    def wordPattern(self, pattern: str, s: str) -> bool:
        # 创建一个映射哈希表
        sArr = s.split(' ')
        sLen, tLen = len(sArr), len(pattern)
        if sLen != tLen:
            return False

        # 创建两个哈希表
        s2t = {}
        t2s = {}

        for i in range(sLen):
            charS, charT = pattern[i], sArr[i]

            if charS in s2t and s2t[charS] != charT:
                return False
            if charT in t2s and t2s[charT] != charS:
                return False

            s2t[charS] = charT
            t2s[charT] = charS

        return True

205. 同构字符串

  • 注意读题啊！
  • 首先需要理解什么是同构字符串—两个字符串中的单词映射应当是唯一的，而不是相差的距离一样
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 同构字符串
    def isIsomorphic(self, s: str, t: str) -> bool:
        sLen, tLen = len(s), len(t)
        if sLen != tLen:
            return False
        
        # 创建两个哈希表
        s2t = {}
        t2s = {}

        for i in range(sLen):
            charS,charT = s[i],t[i]

            if charS in s2t and s2t[charS] != charT:
                return False
            if charT in t2s and t2s[charT] != charS:
                return False
            
            s2t[charS] = charT
            t2s[charT] = charS
        
        return True

392. 判断子序列

  • 乍一看很简单，两个指针，一个指向s，一个指向t，慢慢遍历。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def isSubsequence(self, s: str, t: str) -> bool:
        # 创建两个指针分别指向s、t
        sPointer, tPointer = 0,0
        while sPointer < len(s) and tPointer < len(t):
            if s[sPointer] == t[tPointer]:
                sPointer += 1
                tPointer += 1
            else:
                tPointer += 1
        if sPointer == len(s):
            return True
        return False
    进阶：
    如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

167. 两数之和 II - 输入有序数组

  • 一个非常简单的双指针
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 两数之和 II - 输入有序数组
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 感觉可以用双指针
        left, right = 0, len(numbers) - 1
        while left < right:
            if numbers[left] + numbers[right] == target:
                return [left+1, right+1]
            elif numbers[left] + numbers[right] > target:
                right -= 1
            else:
                left += 1
        return []

149. 直线上最多的点数

  • 注意点：斜率的处理（特殊情况、正负数）
  • 思考点：只考虑斜率，不考虑截距不会出问题吗？
    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
    # 直线上最多的点数
    def maxPoints(self, points: List[List[int]]) -> int:
        # 两点确定一条直线，所以可以计算两两之间的斜率？
        # 使用哈希表计算所有可能的斜率？
        # 斜率计算函数
        def getSlope(p1, p2):
            dx, dy = p2[0] - p1[0], p2[1] - p1[1]
            # 特殊情况
            # 斜率无穷大
            if dx == 0:
                return 'inf'
            # 斜率为0
            if dy == 0:
                return 0
            # 约分，保持精度
            # 同时除以最大公约数
            d = gcd(dx, dy)
            # 如果是负数，需要统一，防止-1 / 2 和 1 / -2 不一样
            if dy < 0:
                dy = -dy
                dx = -dx
            return (dy // d, dx // d)

        result = 0
        for i in range(len(points)):
            slopeDict = defaultdict(int)
            duplicate = 1
            for j in range(i + 1, len(points)):
                if points[i] == points[j]:
                    duplicate += 1
                    continue
                slope = getSlope(points[i], points[j])
                slopeDict[slope] += 1
            # 当前的最大值为重复点+max 斜率value
            result = max(result, (max(slopeDict.values())
                         if slopeDict else 0) + duplicate)
        return result

172. 阶乘后的零

  • 找质因子10的个数，转换为2*5的个数，由于5比2的多，所以直接找5的
  • 首先从5开始数，找5的倍数，5的倍数进行分解，看看有多少个因子5
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # 阶乘后的零
    def trailingZeroes(self, n: int) -> int:
        # 思路很难想到 质因子为10的个数
        # 10 = 2 x 5
        ans = 0
        for i in range(5, n + 1, 5):
            while i % 5 == 0:
                i //= 5
                ans += 1
        return ans

151. 反转字符串中的单词

  • 思路：去除前后空格 -> 翻转整个串 -> 按’ ‘进行split -> 翻转每个单词 -> 重新整合成串
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 反转字符串中的单词
    # 不优雅版本

    def reverseWords(self, s: str) -> str:
        import re
        sPie = re.sub(r'\s+', ' ', s).strip()[::-1]
        sReverse = sPie[::-1]
        sArr = sReverse.split(' ')
        sArrAfter = []
        for i in sArr:
            sArrAfter.append(i[::-1])
        res = ' '.join(sArrAfter)
        return res
        pass
    # 优雅版

    def reverseWords(self, s: str) -> str:
        import re
        sPie = re.sub(r'\s+', ' ', s).strip()
        word = sPie.split(' ')
        wordReverse = [item[::-1] for item in word]
        return ' '.join(wordReverse)

380. O(1) 时间插入、删除和获取随机元素

  • 数组+哈希表
  • 各司其责，主要的难点在于删除
  • 删除的时候，移动要删除的元素到数组末尾，再pop，时间复杂度降到最低！
    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
    # O(1) 时间插入、删除和获取随机元素
    class RandomizedSet:
        # Your RandomizedSet object will be instantiated and called as such:
        # obj = RandomizedSet()
        # param_1 = obj.insert(val)
        # param_2 = obj.remove(val)
        # param_3 = obj.getRandom()
        def __init__(self):
            # 创建数组和哈希表
            self.numList = []
            self.numDict = {}

        def insert(self, val: int) -> bool:
            # 插入元素直接插入到数组
            if val in self.numDict:
                return False

            self.numDict[val] = len(self.numList)
            self.numList.append(val)
            return True

        def remove(self, val: int) -> bool:
            # 删除元素比较难
            if val not in self.numDict:
                return False

            # 思路是什么？
            # 将要删那个数变成数组中的最后一个数！~太妙了
            # 获取要删除的值的索引，并将其与列表中的最后一个元素交换
            index = self.numDict[val]
            lastVal = self.numList[-1]
            self.numList[index] = lastVal
            self.numDict[lastVal] = index
            # 删除数组中最后一个元素
            self.numList.pop()
            del self.numDict[val]
            return True

        def getRandom(self) -> int:
            return random.choice(self.numList)

274. H 指数

  • 一个朴素的思想
    1
    2
    3
    4
    5
    6
    7
    8
    9
    def hIndex(self, citations: List[int]) -> int:
        # 看了之后就是先排序
        citations.sort(reverse=True)
        print(citations)
        for i in range(len(citations)):
            # 找到一个index+1 < citations[index]的值
            if i + 1 > citations[i]:
                return i
        return len(citations)

122. 买卖股票的最佳时机 II

  • 思考一下我的代码为什么这么拉跨（想必答案就是缺乏思考哈哈哈哈 形成了闭环）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def maxProfit(self, prices: List[int]) -> int:
        # 感觉是找上升序列的问题
        # 找出所有的上升序列即可
        # 标记上升序列的长度
        start,end = 0,0
        isUp = 0
        res = 0
        for i in range(1, len(prices)):
            if prices[i] >= prices[i-1]:
                isUp = 1
                end += 1
            else:
                res += prices[end] - prices[start]
                start = end+1
                end = start
                isUp = 0
        res += prices[end] - prices[start]
        return res
  • 优雅的代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 优雅的代码就是不一样
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        # 遍历价格数组
        for i in range(1, len(prices)):
            # 如果今天的价格比昨天高，就认为可以进行一次交易
            if prices[i] > prices[i-1]:
                profit += prices[i] - prices[i-1]
        return profit

121. 买卖股票的最佳时机

  • 看了以前写的代码写出来了
  • 核心思想是维护两个变量
  • 如果有多只股票呢
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def maxProfit(self, prices: List[int]) -> int:
        # 关键就是遍历与维护变量
        cost = sys.maxsize
        profit = 0
        for item in prices:
            if item < cost:
                cost = item
            if item - cost > profit:
                profit = item - cost
        return profit

16. 最接近的三数之和

  • 思考这和传统“三数之和”有什么区别？
  • 本题说明：最后只包含一个解，所以不需要考虑去重
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    # 最接近的三数之和
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        # 三数之和的简化版
        if len(nums) < 3:
            return 0
        # 首先对数组进行排序
        nums.sort()
        minSub = nums[0] + nums[1] + nums[2] - target

        # 首先固定一个元素 然后进行双指针
        for i in range(len(nums)):
            left, right = i + 1, len(nums) - 1
            while left < right:
                sumThree = nums[i] + nums[left] + nums[right]
                minSub = sumThree-target if abs(sumThree - target) <= abs(minSub) else minSub
                if sumThree > target:
                    right -= 1
                elif sumThree < target:
                    left += 1
                else:
                    return minSub + target
        return minSub + target

10. 正则表达式匹配

这个问题是一个经典的动态规划（Dynamic Programming，DP）问题，你正在尝试实现一个匹配字符串 s 和模式 p 的函数。在这种情况下，模式 p 可以包含普通字符和两个特殊字符:

  1. . - 可以匹配任何单个字符
  2. * - 匹配零个或多个前面的那一个元素
    ![[Pasted image 20240402211458.png]]
    这种情况下：dp[i][j] = dp[i-2][j]
    ![[Pasted image 20240402211440.png]]
    这种情况下：dp[i][j] = dp[i][j-1]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def isMatch(self, s: str, p: str) -> bool:
        l1, l2 = len(s), len(p)
        dp = [[False] * (l1+1) for _ in range(l2+1)]
        # 初始化dp数组
        dp[0][0] = True
        for i in range(2, l2+1):
            if p[i-1] == '*':
                dp[i][0] = dp[i-2][0]
        # 开始dp过程
        for i in range(1, l2+1):
            for j in range(1, l1+1):
                if p[i-1] == '*':
                    if p[i-2] == s[j-1] or p[i-2] == '.':
                        # a * 出现1次或多次
                        dp[i][j] = dp[i][j-1]
                    # a * 可匹配0次
                    # 如果之前 dp[i][j] 已经是 True，或者如果消掉 *（和它前面的字符）后能够匹配 (dp[i-2][j] 是 True), 那么 dp[i][j] 应该为 True
                    # 等价于dp[i][j] = dp[i][j] or dp[i-2][j]
                    dp[i][j] |= dp[i-2][j]
                elif p[i-1] == '.' or p[i-1] == s[j-1]:
                    dp[i][j] = dp[i-1][j-1]
        return dp[l2][l1]

14. 最长公共前缀

  • 简单题
  • 注意边界条件的判定
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:  # 检查 strs 是否为空
            return ""
        for i in range(len(strs[0])):
            cur = strs[0][i]
            for item in strs[1:]:
                # 需要判断长度是否合适
                if i >= len(item) or item[i] != cur:
                    return strs[0][: i]
        return strs[0]

72. 编辑距离

  • 一步一步递推的公式编辑距离 - 动态规划解法 Edit Distance - Dynamic Programming_哔哩哔哩_bilibili
    ![[Pasted image 20240401142732.png]]
  • 注意：
    dp = [[0] * l1] * l2
    这行代码创建了一个二维数组 dp，但方式不正确。因为 [[0] * l1] * l2 这种方式复制的是同一个列表的引用。当你修改任意一个 dp[j][i] 的值时，dp 的每一行都会被改变，因为它们实际上是同一个列表的引用。
    应该用这个dp = [[0] * l1 for _ in range(l2)]
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    def minDistance(self, word1: str, word2: str) -> int:
        # 创建dp数组
        l1, l2 = len(word1)+1, len(word2)+1

        dp = [[0] * l1 for _ in range(l2)]
        # 初始化dp数组的第一行和第一列
        for i in range(1, l1):
            dp[0][i] = dp[0][i-1] + 1
        for j in range(1, l2):
            dp[j][0] = dp[j-1][0] + 1

        # 进行dp
        for i in range(1, l2):
            for j in range(1, l1):
                # 这里需要考虑边界条件，因为i和j包含了空字符串的情况，因此需要-1
                if word2[i-1] == word1[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # 两个不相同
                    dp[i][j] = min(dp[i-1][j] + 1, dp[i]
                                   [j-1] + 1, dp[i-1][j-1]+1)
        return dp[l2-1][l1-1]

42. 接雨水

  • 左右数组进行分别遍历
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    def trap(self, height: List[int]) -> int:
        left, right = [0] * len(height), [0] * len(height)
        # 首先遍历左边，看左边的最大高度
        maxLeft = height[0]
        for i in range(1, len(height)):
            if maxLeft < height[i - 1]:
                maxLeft = height[i - 1]
            left[i] = maxLeft
        maxRight = height[len(height) - 1]
        for j in range(len(height) - 2, -1, -1):
            if maxRight < height[j + 1]:
                maxRight = height[j + 1]
            right[j] = maxRight

        # 遍历
        res = 0
        for k in range(1, len(height) - 1):
            res += max(0, min(right[k], left[k]) - height[k])
        return res
  • 双指针？

15. 三数之和

  • 这个题目特别的经典
  • 但是我已经忘了怎么做了
  • 参考一下coze的思路
  • 首先进行排序，固定第一个数的index
  • 然后使用双指针l、r对剩下的数进行筛选
    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
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 和为0的话
        # 原地排序
        nums.sort()
        result = []
        # 我的思路是先固定一个数
        for i in range(len(nums) - 2):
            # 剩下的就是两数之和问题了
            # 如果不是第一个数
            if i > 0 and nums[i] == nums[i-1]:
                # 跳过重复值
                continue
            # 双指针
            l, r = i + 1, len(nums) - 1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                if total < 0:
                    l += 1
                elif total > 0:
                    r -= 1
                else:
                    result.append([nums[i],nums[l],nums[r]])   
                    # 去重复
                    while l < r and nums[l] == nums[l + 1]: l+=1
                    while l< r and nums[r] == nums[r-1]:r-=1
                    l+=1
                    r-=1
        return result

3083. 字符串及其反转中是否存在同一子字符串

1
2
3
4
5
6
7
8
def isSubstringPresent(self, s: str) -> bool:
    # 创建一个set
    st = set()
    for x, y in pairwise(s):
        st.add((x, y))
        if (y, x) in st:
            return True
    return False

3084. 统计以给定字符开头和结尾的子字符串总数

1
2
3
4
5
6
7
def countSubstrings(self, s: str, c: str) -> int:
    # 遍历一次 查看c出现的次数
    count = 0
    for item in s:
        if item == c:
            count += 1
    return (count*(count+1))//2

2697. 字典序最小回文串

  • 朴素的想法
  • 实际上不是我的想法，而是灵神的想法哈哈哈
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # 字典序最小回文串
    def makeSmallestPalindrome(self, s: str) -> str:
        # 朴素的想法 使用哈希表 找到出现次数不是单数的（中间的不算）
        # 然而事实证明 想得太复杂了
        # 只需要一次遍历就好了
        sList = list(s)
        for i in range(len(s) // 2):
            if sList[i] > sList[len(s) - i - 1]:
                sList[i] = sList[len(s) - i - 1]
            elif sList[i] < sList[len(s) - i - 1]:
                sList[len(s) - i - 1] = sList[i]
        return ''.join(sList)

2375. 根据模式串构造最小数字

  • 先回忆一下灵神讲得东西
  • 实际上采用的策略是贪心
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 根据模式串构造最小数字
    # 下面是抄的
    def smallestNumber(self, pattern: str) -> str:
        # 根据灵神的思路
        n = len(pattern)
        # digits = '0123456789'
        print(digits)
        ans = list(digits[1:n+2])
        i = 0
        while i < n:
            # 如果处于升序
            if pattern[i] == 'I':
                i += 1
                continue
            i0 = i
            i += 1
            while i < n and pattern[i] == 'D':
                i += 1
            # 反转
        
            ans[i0:i+1] = ans[i0:i+1][::-1]
        return ''.join(ans)

2374. 边积分最高的节点

  • 使用一种优雅的做法（来自灵神）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 边积分最高的节点
    # 一下子从吊车尾的时空占有情况提升到前面，果然代码还得是要优化啊
    def edgeScore(self, edges: List[int]) -> int:
        # 定义一个score数组 和 最后的maxKey
        maxKey,maxVal, score = 0,0, [0]* len(edges)
        # 一次遍历搞定
        for i in range(len(edges)):
            to = edges[i]
            score[to] = score[to] + i
            if score[to] > maxVal or (score[to]==maxVal and to < maxKey):
                maxKey = to 
                maxVal = score[to]
        return maxKey
  • 有点脱裤子放屁的做法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # 边积分最高的节点
    def edgeScore(self, edges: List[int]) -> int:
        # 首先明确边积分的定义:
        # 指向节点i的所有边的起始编号之和
        # 朴素的想法是使用map
        degree = OrderedDict()
        for i in range(len(edges)):
            degree[edges[i]] = i + degree.get(edges[i], 0)

        # 取最大的key,但是这里的key其实是没有排序的,所以会有问题
        maxKey = 0
        for key in degree.keys():
            if degree.get(maxKey, -1) < degree[key] or (degree.get(maxKey, -1) == degree[key] and maxKey > key):
                maxKey = key

        return maxKey

2373. 矩阵中的局部最大值

  • 实际上就是深度学习中的Maxpooling操作
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    # 矩阵中的局部最大值
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        # 基本思想是将每次计算的值放在左上角
        for i in range(len(grid) - 2):
            for j in range(len(grid) - 2):
                # 计算3 * 3矩阵的最大值
                # 请我不要犯傻了，这么简单的问题都要错
                # 首先不要重复使用循环变量♻️
                # 其次，不要只在内层最大值求整行的最大值，而是窗口内的最大值
                # 都没有使用到变量j,怎么会得到正确答案呢?
                grid[i][j] = max(max([item for item in grid[k][j:j+3]])
                                 for k in range(i, i+3))
            grid[i].pop()
            grid[i].pop()
        grid.pop()
        grid.pop()
        return grid

200. 岛屿数量

  • 使用dfs深度优先遍历，本质上是递归
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 不含连续1的非负整数
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(i, j):
            # 请注意i和j的索引范围，一定要包含等号！！！
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
                return
            grid[i][j] = '0'
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        # 如果grid = null直接返回
        if not grid:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    # 这一步会把所有临近的陆地标记成为海洋，一举两得
                    dfs(i, j)
                    count += 1
        return count

135. 分发糖果

  • 好久没做了，想到了解法的一半（纯纯凭直觉做的）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 分发糖果
    def candy(self, ratings: List[int]) -> int:
        # 看到相邻问题 直接使用左右两个数组
        # 需要注意的是 左右两边只能计算一次 而不能考虑得过于周全
        # 基础糖果数量
        baseVal = len(ratings)
        # 由于相邻的两个孩子有一个要求是评分更高的糖果更多
        left = [1] * baseVal
        right = [1] * baseVal

        for i in range(1, len(ratings)):
            if ratings[i-1] < ratings[i]:
                left[i] = left[i-1] + 1

        for i in range(len(ratings)-2, -1, -1):
            if ratings[i] > ratings[i+1]:
                right[i] = right[i+1] + 1

        res = 0
        for i in range(0, baseVal):
            res += max(right[i], left[i])
        return res
  • 常数级别遍历
    ![[Pasted image 20240323203335.png]]
    ![[Pasted image 20240323203347.png]]
    需要注意的是，评分相同时，后面的那个孩子应该给1个糖果（因为题目中没有说评分一致时糖果也应该一致），同时增加序列长度的记忆功能，当升降序列长度相等时，应该为降序列再增加一个糖果
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def candy(self, ratings: List[int]) -> int:
        # 使用增长序列的方法来做
        # 初始化一些变量
        length = len(ratings)
        dec, inc, pre, res = 0, 1, 1, 1
        for i in range(1, length):
            if ratings[i] >= ratings[i-1]:
                dec = 0
                # 说明在升序序列
                pre = pre + 1 if ratings[i] != ratings[i-1] else 1
                res += pre
                # 升序序列的长度
                inc = pre
            else:
                dec += 1
                if dec == inc:
                    dec += 1
                res += dec
                pre = 1
        return res

1835. 所有数对按位与结果的异或和

  • 优化后的结果（根据分配律进行优化）
  • a&c ^b&c = (a^b) & c
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 考虑优化算法
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        # a&c ^ b&c = (a^b) & c
        # 根据这个公式
        a1 = arr1[0]
        a2 = arr2[0]
        # 注意边界条件,因为一个数与自己做异或的结果是0,所以一定要注意边界条件
        # 0 位置的已经取出来了,所以需要从1开始
        for i in range(1, len(arr1)):
            a1 = a1 ^ arr1[i]
        for i in range(1, len(arr2)):
            a2 = a2 ^ arr2[i]
        return a1 & a2
  • 一个看似正确但是超过内存限制的暴力算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # 下面的算法会超过内存限制 gg
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        # 先写一个试试吧
        andSum = []
        
        for i in range(0,len(arr1)):
            for j in range(0,len(arr2)):
                andSum.append(arr1[i] & arr2[j])
        if len(andSum)<=1: return andSum[0]
        res = andSum[0]
        for i in range(1, len(andSum)):
            res = res ^ andSum[i]
        return res

1840. 最高建筑高度

  • 视频讲解LeetCode LeetCode 1840. Maximum Building Height | Weekly Contest 239
    这个题搞了我半天，最主要的其实是最终高度的计算，视频里的点很关键，如果左右两边的限制高度不一样，则可以人为让他们一样，即让少的一个多爬x个，再直接求两个相同高度的限制中的最高高度。
  • 如果两个高度一样
    ![[Pasted image 20240504231729.png]]
  • 如果不一样呢，那就先让两个变得一样，再按上面的方法计算
    ![[Pasted image 20240504231816.png]]
    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
    # 最大建筑高度
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        # 补充额外限制条件
        restrictions.append([1, 0])
        restrictions.append([n, n-1])
        # 排序
        restrictions.sort()
        # 遍历限制数组
        for i in range(1, len(restrictions)):
            # 有如下限制
            # 相邻两个高度差不能超过1
            # 注意：
            # restrictions[i][0] 表示地的编号
            # restrictions[i][1] 表示地的限制高度
            restrictions[i][1] = min(
                restrictions[i][1], restrictions[i-1][1] + (restrictions[i][0] - restrictions[i-1][0]))
        for i in range(len(restrictions)-2, -1, -1):
            restrictions[i][1] = min(
                restrictions[i][1], restrictions[i+1][1] + (restrictions[i+1][0] - restrictions[i][0]))

        # 遍历得到最大高度
        maxHeight = 0
        for i in range(1, len(restrictions)):
            id1, h1 = restrictions[i-1]
            id2, h2 = restrictions[i]
            maxHeight = max(maxHeight, (h2 + h1 + id2 - id1)//2)
            # 可以除2是因为从一个高度到另一个高度可以先上升后下降
            # 来一个形象的例子
            #  / \
            # /   \
            #      \
        return maxHeight
  • coze写的代码
    补充说明图片（5.4）
    ![[Pasted image 20240504231444.png]]
    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
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        # 这个题不会做啊
        # 只能看题解了

        # 首先补充约束条件
        # 第一块地不能修建筑
        restrictions.append([1, 0])
        # 对建筑进行排序
        restrictions.sort()
        # 最后一块地的限制建筑高度(实际没有这个限制,主要是给n-1号用的)
        restrictions.append([n, n-1])

        # 从左往右遍历,应用限制
        for i in range(1, len(restrictions)):
            # 设置restrictions[i][0]块地的限制高度
            restrictions[i][1] = min(
                restrictions[i][1], restrictions[i-1][1] +
                restrictions[i][0]-restrictions[i-1][0]
            )
        # 从右往左遍历,应用限制(为什么第二个参数是-1？因为0是最后一个需要遍历的值，所以0的下一个就是-1)
        for i in range(len(restrictions)-2, -1, -1):
            restrictions[i][1] = min(
                restrictions[i][1], restrictions[i + 1][1] +
                restrictions[i + 1][0] - restrictions[i][0]
            )

        # 在满足所有限制条件下找最高建筑
        max_h = 0
        for i in range(1, len(restrictions)):
            id1, h1 = restrictions[i - 1]
            id2, h2 = restrictions[i]
            max_h = max(max_h, (h2 - h1 + id2 - id1) // 2 + h1)
        return max_h
  • 复习写的代码
    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
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        # 首先添加虚拟建筑
        restrictions.append([1, 0])
        restrictions.append([n, n-1])
        restrictions.sort()

        # 从左到右遍历
        for i in range(1, len(restrictions)):
            restrictions[i][1] = min(
                restrictions[i][1], restrictions[i-1][1]+(restrictions[i][0]-restrictions[i-1][0]))

        # 从右往左遍历
        for i in range(len(restrictions)-2, -1, -1):
            restrictions[i][1] = min(
                restrictions[i][1], restrictions[i+1][1]+(restrictions[i+1][0]-restrictions[i][0]))

        # 找到最大建筑
        maxHeight = 0
        for i in range(1, len(restrictions), 1):
            index1, height1 = restrictions[i-1]
            index2, height2 = restrictions[i]
            maxHeight = max(
                maxHeight, ((index2-index1)+(height2-height1))//2+height1)
        return maxHeight

670. 最大交换

  • 5.4复习
    ![[Pasted image 20240504230333.png]]
  • 3.23复习
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # 3/23最大交换
    def maximumSwap(self, num: int) -> int:
        # 目标：找到x右侧比x大的数
        # 忘了昨天怎么做的了
        # 盲猜从右向左遍历
        # 首先转换int为数组
        numList = [int(digit) for digit in str(num)]
        # 记录每个数字最后出现的位置
        lastSeen = {x: i for i, x in enumerate(numList)}
        for i, x in enumerate(numList):
            # 从9-(x+1)的范围内找数,看看是不是在右边,从大往小找
            for j in range(9, x, -1):
                if lastSeen.get(j, -1) > i:
                    # 说明找到了
                    # 交换
                    numList[i], numList[lastSeen.get(
                        j)] = numList[lastSeen.get(j)], numList[i]
                    return int(''.join(map(str, numList)))
        return num
  • 一种朴素且错误的思维
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # 这个版本有问题
    def maximumSwap(self, num: int) -> int:
        # 一个朴素的想法是把最大的值和第一位交换，得到的总是较大的
        # 遍历一次数组
        # 把num转换成字符串
        listNum = self.intToList(num)
        maxIndex = 0
        for i in range(0, len(listNum)):
            maxIndex = maxIndex if listNum[maxIndex] > listNum[i] else i
        # swap
        listNum[0], listNum[maxIndex] = listNum[maxIndex], listNum[0]
        return self.listToInt(listNum)

    # 想法果然还是太过于朴素了，因为完全没有考虑到最大的值已经在最高位的情况
    # 那应该怎么做？把第二大的放到第二位？也不可行，需要考虑的有点多
    # 比如98368这个数字
    # 第二大的是8 但是8已经在第2位了
    # 继续下去？
    # 复杂度直接进化到O(N^2)了
  • 我愿称coze为yyds
    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 intToList(self, n: int) -> List:
            return [int(digit) for digit in str(n)]

        def listToInt(self, nums: List) -> int:
            return int(''.join(map(str, nums)))
        # coze协作编程代码
        # 方法很巧妙
        def maximumSwap(self, num: int) -> int:
            # 把num转换成数组
            numList = self.intToList(num)
            # 记录每个数字最后出现的位置(用了一个字典，如果有重复值，则会更新位置，由于是从前到后遍历，所以可以保证是最后出现的)
            last = {x: i for i, x in enumerate(numList)}
            # 从左到右遍历数组
            for i, x in enumerate(numList):
                # 从9到x + 1查找可能的最大值（倒序查找，找到x右侧比x大的数）
                for d in range(9, x, -1):
                    # 如果找到更大值，并且该更大值的索引在当前索引的右侧
                    if last.get(d, -1) > i:
                        # 交换这两个值
                        numList[i], numList[last[d]] = numList[last[d]], numList[i]
                        # 由于只允许交换一次，直接返回结果
                        return self.listToInt(numList)
            # 如果没有交换发生，直接返回原数
            return num

53. 最大子数组和

  • 错误的双指针法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    # 最大子数组和
    def maxSubArray(self, nums: List[int]) -> int:
        # 看到题目想到的就是滑动窗口
        if len(nums) < 2:
            return nums[0]
        # 初始化两个指针
        left, right = 0, 1
        maxVal = -sys.maxsize - 1
        while (right < len(nums)):
            # 当前窗口和
            curVal = self.subArraySum(nums, left, right)
            maxVal = maxVal if maxVal >= curVal else curVal
            # 移动指针
            # 做到这里 感觉好像找不到移动指针的方法了...
            # 但是通过思考发现 好像可以用动态规划
            right += 1
            pass
        pass
  • 正确的动态规划法（卡登算法？）
    1
    2
    3
    4
    5
    6
    7
    8
    # 最大子数组和
    def maxSubArray(self, nums: List[int]) -> int:
        # 使用动态规划来解决这个问题
        # 首先初始化dp数组
        dp = [nums[0]] * len(nums)
        for i in range(1, len(nums)):
            dp[i] = max(dp[i-1]+nums[i], nums[i])
        return max(dp)
⚠️思考为什么最后一个值不是最大值?

因为dp[i]的值是以nums[i]结尾的子数组的最大和，所以并不是全局最大和

704. 二分查找

很简单，注意边界条件需要包含等于，否则只有一个元素的情况下会直接返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lens = len(nums)
        l, r = 0, lens - 1
        # 注意边界条件
        while (l <= r):
            m = (l + r) >> 1
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            else:
                r = m - 1
        return -1

27. 移除元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        # 看到这个题的第一眼就是双指针

        slow, fast = 0,0
        l = len(nums)
        # slow指针用来指示目标数组的位置
        # fast指正用来遍历数组，找到目标元素
        while(fast < l):
            # 找到了目标元素
            if nums[fast]==val:
                # slow指针停在原地，等待找到下一个非目标元素替换掉
                fast += 1
            # 如果不是目标元素
            else:
                nums[slow] = nums[fast]
                fast += 1
                slow += 1
        return slow

977. 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # 由于数组是有序的，所有可以考虑使用双指针法，从左右两端分别遍历
        l = len(nums)
        left, right = 0, l - 1
        result = [0] * l
        index = l - 1
        while (left <= right):
            if (abs(nums[left]) >= abs(nums[right])):
                result[index] = (nums[left] * nums[left])
                left += 1
            else:
                result[index] = (nums[right] * nums[right])
                right -= 1
            index -= 1
        return result

414. 第三大的数

  • 一种错误的解法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution:
        # 第三大的数
        def thirdMax(self, nums: List[int]) -> int:
            # 最简单的方法就是排序之后选第3大的
            # 但是进一步思考，如果只需要第3大的，还需要对所有数组排序吗
            # 看上去是不需要的，因此这里使用冒泡排序找到第三大的即可
            # 时间复杂度O(3N)
            length = len(nums)
            for i in range(0, length if length <= 3 else 3):
                for j in range(i + 1, length):
                    if nums[i] > nums[j]:
                        # swap
                        nums[i], nums[j] = nums[j], nums[i]
            print(nums)
            # 事实证明这样的解法是有bug的，因为nums中可能有重复的值，所以还需要进行去重操作
            # 一种想到的思路是维护一个集合，用来去重，但是不如一开始就用集合，所以这样是脱裤子放屁
            return nums[-3] if length >= 3 else nums[-1]

  • 正确的高效解法：运用集合去重（注意事项：边界条件）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def thirdMax(self, nums: List[int]) -> int:
      # 维护一个集合，使得集合中只有3个数，并且超出时删除最小的
      s = set()
      # 遍历数组
      for i in range(0,len(nums)):
        s.add(nums[i])
        if len(s) > 3:
          # 删除集合中最小的值
          minValue = min(s)
          s.remove(minValue)
        print(s)
      return min(s) if len(s) >= 3 else max(s)
#算法学习 #计划
算法能力提升计划 Algorithm Capability Enhancement Program
https://yintel12138.github.io/2024/04/01/Algorithm-Improve/
作者
Yintel
发布于
2024年4月1日
许可协议