数据结构

顺序表

1
2
3
4
5
6
7
8
// 动态数组
vector<int> a;
a.push_back(x);                      // 添加元素 
// 以下方法均不包含右端点
sort(a.begin(),a.end());             //从a.begin()到a.end()从小到大排列
reverse(a.begin(),a.end());          //从a.begin()到a.end()的元素倒置，但不排列
copy(a.begin(),a.end(),b.begin()+1); //从a.begin()到a.end()的元素复制到b中，从b.begin()+1的位置（包括它）开始复制，覆盖掉原有元素
find(a.begin(),a.end(),10);          //从a.begin()到a.end()的元素中查找10，存在则返回其位置
1
2
3
4
5
# Python列表的定义方式
#（1）一维数组：
list = [0]*n
#（2）二维数组：
list = [[0]*m for _ in range(n)]

118. 杨辉三角

1
2
3
4
5
6
def generate(self, numRows):
    ret = [[1]*i for i in range(1, numRows+1)]
    for i in range(2, numRows):
        for j in range(1, i):
            ret[i][j] = ret[i-1][j-1] + ret[i-1][j]
    return ret

总之，！！！善用哈希表！！！

链表

注：以下图源参考链接 1

单链表

双指针、快慢指针等 （双指针中等难度例题点这里）
（1）链表节点的定义
单链表
带头指针的链表

1
2
3
4
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

（2）链表节点的删除
链表删除节点的过程图示
面试题 02.03. 删除中间节点

1
2
3
def deleteNode(self, node):
    node.val = node.next.val
    node.next = node.next.next

删除 中间节点 好写，一旦涉及 头尾元素 就有点麻烦了……比如下面这个题 👇👇👇

203. 移除链表元素

输出 head.val 发现头节点指向的是第一个元素，因此需要添加一个虚拟头结点 dummy 来指向头结点

1
2
3
4
5
6
7
8
9
10
11
12
def removeElements(self, head: ListNode, val: int) -> ListNode:
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy
    node = head
    while(node):
        if node.val == val:
            prev.next = node.next
        else:
            prev = node
        node = node.next
    return dummy.next

2181. 合并零之间的节点

1
2
3
4
5
6
7
8
9
10
11
def mergeNodes(self, head):
    end, last, cur = None, head, head.next
    while cur:
        if not cur.val:
            end,last = last,cur
        else:
            last.val += cur.val
            last.next = cur.next
        cur = cur.next
    end.next = None
    return head

（3）链表节点的插入
链表插入节点的过程图示
（4）链表的合并
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
25
26
27
28
29
30
31
32
33
34
def mergeTwoLists(self, list1, list2):
    if list1 == None and list2 == None or list2 == None and list1:
        return list1
    elif list2 and list1 == None:
        return list2
    head = ListNode(0)
    if list1.val <= list2.val:
        head.next = list1
        node1 = list1.next
        node2 = list2
    else:
        head.next = list2
        node1 = list1
        node2 = list2.next
    node = head.next
    while(node1 and node2):
        if node1.val > node2.val:
            node.next = node2
            node2 = node2.next
        else:
            node.next = node1
            node1 = node1.next
        node = node.next
    if node1 == None:
        while(node2):
            node.next = node2
            node2 = node2.next
            node = node.next
    else:
        while(node1):
            node.next = node1
            node1 = node1.next
            node = node.next
    return head.next

别人的代码—简洁明了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mergeTwoLists(self, list1, list2):
    head = ListNode(None)
    node = head
    while list1 and list2:
        if list1.val < list2.val:
            node.next, list1 = list1, list1.next
        else:
            node.next, list2 = list2, list2.next
        node = node.next
    if list1:
        node.next = list1
    else:
        node.next = list2
    return head.next

但是我的效率反而更高？？？

双链表

循环链表

剑指 Offer II 029. 排序的循环链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def insert(self, head, insertVal):
    insertNode = Node(insertVal)
    if not head:
        insertNode.next = insertNode
        return insertNode
        
    pre = cur = head
    while pre.next != head:
        pre = cur
        cur = cur.next
        if pre.val <= insertVal and cur.val >= insertVal:
            break
        if pre.val > cur.val and (insertVal >= pre.val or insertVal <= cur.val):              
            break        
    pre.next = insertNode
    insertNode.next = cur
    return head

栈

stack：先进后出

栈的实现

队列

queue：先进先出

队列的实现

232. 用栈实现队列

双栈实现队列：stack1 为输入栈，stack2 为输出栈。当 stack2 为空时，将 stack1 中的元素挨个弹出压入至 stack2 中，从 stack2 中进行 pop 和 peek 操作。

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

    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, x):
        self.stack1.append(x)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2[-1]

    def empty(self):
        return self.stack1 == [] and self.stack2 == []

双端队列

deque相比于list实现的队列，deque 实现拥有更低的时间和空间复杂度。 list 实现在出队 （pop） 和插入 （insert） 时的空间复杂度大约为 O(n)，deque 在出队 （pop） 和入队 （append） 时的时间复杂度是 O(1)。

1
2
3
4
5
6
7
8
import collections
deque = collections.deque()
# 入列
deque.append(value)     # 默认右侧入列
deque.appendleft(value) # 左侧入列
# 出列
deque.popleft()          # 左侧出列
deque.popright()         # 右侧出列

优先队列

1
2
import queue
priority_queue = queue.PriorityQueue()
1
2
3
4
5
6
7
8
9
10
11
// 一般类型：
priority_queue<int>  q;
// 指定类型：
priority_queue<int, vector<int>, greater<int> > q;   // 小顶堆
priority_queue<int, vector<int>, less<int> > q;      // 大顶堆
// 自定义优先队列运算符
priority_queue<pair<int, int> > q;
q.push(make_pair(exist[i], i));                      // 压入
pair<int, int> temp = q.top();                       // 弹出
a = temp.first;  
b = temp.second;

循环队列

用列表实现循环队列，关键有两点：
（1）队空和队满的判断（考研知识点的温习）

队空：self.front == self.rear
队满：若列表填满的情况下，队满时同样有 self.front == self.rear，因此需要区分。可以使用额外的一个空间，约定 “队头指针在队尾指针的下一位置即为队满的标志”。

图源《2020王道数据结构》

（2）首尾指针的移动

入队：队尾指针加 1，self.rear = (self.rear+1) % self.MAX_SIZE
出队：队首指针加 1，self.front = (self.front+1) % self.MAX_SIZE

622. 设计循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class MyCircularQueue:

    def __init__(self, k: int):
        self.MAX_SIZE = k+1
        self.front, self.rear = 0, 0
        self.queue = [0]*(k+1)

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.queue[self.rear] = value
        self.rear = (self.rear+1) % self.MAX_SIZE
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front+1) % self.MAX_SIZE
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.front]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.rear-1]

    def isEmpty(self) -> bool:
        return self.front == self.rear

    def isFull(self) -> bool:
        return (self.rear+1) % self.MAX_SIZE == self.front


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

二叉树

写在最前：有关于二叉树，不超时的情况下尽量用递归做吧，迭代太费脑子了

不同类型的二叉树

从左至右依次为：完满二叉树，完全二叉树，满二叉树
（1）满二叉树（完美二叉树）

满二叉树：每一层的结点数目都达到最大值，即第 i 层有 $2^{i-1}$ 个结点。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
    if not root:
        return root
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node.left:
            node.left.next = node.right
            if node.next:
                node.right.next = node.next.left

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

（2）完全二叉树

完全二叉树：由满二叉树而引出来的。对于深度为 K的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应。满二叉树是一种特殊的完全二叉树。

（3）二叉搜索树（Binary Searc Tree, BST，也称二叉排序树）

性质：任意结点都保证 左儿子 < 根节点 < 右儿子

  • 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
  • 它的左右子树也分别为二叉搜索树

701. 二叉搜索树中的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
    if not root:
        return TreeNode(val)
    if root.val < val:
        if root.right == None:
            root.right = TreeNode(val)
        else:
            self.insertIntoBST(root.right, val)
    elif root.val > val:
        if root.left == None:
            root.left = TreeNode(val)
        else:
            self.insertIntoBST(root.left, val)
    return root

（4）平衡二叉树（Balance Tree, BT，也称 AVL 树）

平衡二叉树：任意结点的左右两个子树的高度差的绝对值不超过 1。
平衡因子：指的是该结点的左子树和右子树的高度差，即用左子树的高度减去右子树的高度。

在对平衡二叉树进行插入操作时，有可能造成平衡二叉树失衡，则需要通过 左旋 / 右旋 对其进行修正，保证任意结点的平衡因子的绝对值不超过 1，修正方法包括 LL、RR、LR 和 RL 平衡旋转。
（以下图源：https://blog.csdn.net/jarvan5/article/details/112428036）

（5）线索二叉树

二叉树的遍历

（1）前序遍历

访问顺序：根节点 -> 左子树 -> 右子树

144. 二叉树的前序遍历

递归算法

1
2
3
4
5
6
7
8
def preorderTraversal(self, root):
    ret = []
    if root == None:
        return ret
    ret += [root.val]
    ret += self.preorderTraversal(root.left)
    ret += self.preorderTraversal(root.right)
    return ret

迭代算法（用栈实现，左、右链入栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def preorderTraversal(self, root):
    ret = []
    if root == None:
        return []

    stack = [root]
    while(stack):
        node = stack.pop()
        ret.append(node.val)            
        if node.right:                 # 先压入右子树使其后出栈
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return ret

（2）中序遍历

访问顺序：左子树 -> 根节点 -> 右子树

94. 二叉树的中序遍历

递归算法

1
2
3
4
5
6
7
8
def inorderTraversal(self, root):
    ret = []
    if root == None:
        return ret
    ret += self.inorderTraversal(root.left)
    ret += [root.val]
    ret += self.inorderTraversal(root.right)
    return ret

迭代算法（用栈实现，左链入栈）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def inorderTraversal(self, root):
    ret = []
    if root == None:
        return ret

    stack = []
    node = root
    while(stack or node):
        if node:
            stack.append(node)    # 左子树不为空则始终压入左儿子
            node = node.left
        else:
            node = stack.pop()    # 否则弹出当前节点
            ret.append(node.val)  # 再遍历根节点的值
            node = node.right     # 访问右子树
    return ret

（3）后序遍历

访问顺序：左子树 -> 右子树 -> 根节点

145. 二叉树的后序遍历

递归算法

1
2
3
4
5
6
7
8
def postorderTraversal(self, root):
    ret = []
    if root == None:
        return ret
    ret += self.postorderTraversal(root.left)
    ret += self.postorderTraversal(root.right)
    ret += [root.val]
    return ret

迭代算法（用栈实现，有亿点点难度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def postorderTraversal(self, root):
	ret = []
    if root == None:
        return ret
    
    stack = []
    prev = None                                   # 记录上一次访问的位置，若为右子树则弹出当前子树的根节点

    while root or stack:
        while root:                               # 当前节点不为空时压入，并一直移动直至左子树为空
            stack.append(root)
            root = root.left
        root = stack.pop()                        # 当前节点为空则弹出，转入其右子树
        if not root.right or root.right == prev:  # 若右子树为空或当前从右子树访问后返回
            ret.append(root.val)
            prev = root
            root = None
        elif root.right != prev:                  # 若当前从左子树访问后返回，则访问右子树，并将prev设定为右子树
            stack.append(root)
            root = root.right
    return ret

迭代算法（评论区看到的题解，用栈实现，按中右左前序遍历，反转遍历结果即可，妙啊！！！！！！）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def postorderTraversal(self, root):
    if root == None:
        return []

    ret = []
    stack = [root]
    while(stack):
        node = stack.pop()
        ret.append(node.val)            
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return ret[::-1]

（4）层次遍历
102. 二叉树的层序遍历

迭代算法（用队列实现，分层输出正确解）
自己写的跟官方题解不一样，区别在于用变量存储了层级，然后遍历的时候直接加入到对应的层级列表中！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def levelOrder(self, root):
    if root == None:
        return []

    ret = [[]]
    queue = [[root, 1]]
    while(queue):
        node, depth = queue.pop(0)
        ret[depth-1].append(node.val)
        if node.left:
            queue.append([node.left, depth+1])
            if len(ret) < depth+1:
                ret += [[]]
        if node.right:
            queue.append([node.right, depth+1])
            if len(ret) < depth+1:
                ret += [[]]
    return ret

迭代算法（BFS 模板的意思）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def levelOrder(self, root):
    if root == None:
        return []

    ret = []
    queue = [root]
    while(queue):
        temp = []
        n = len(queue)
        for i in range(n):
            node = queue.pop(0)
            temp.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        ret.append(temp)
    return ret

迭代算法（用队列实现，不分层输出，不适用于解本题，仅供参考）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def levelOrder(self, root):
    ret = []
    if root == None:
        return ret
    
    queue = [root]
    while(queue):
        node = queue.pop(0)
        ret.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return ret

哈夫曼树

并查集

图

基本概念

（1）邻接矩阵
（2）邻接表
（3）十字链表
（4）邻接多重表

广度优先遍历

深度优先遍历

最小生成树

最短路径

拓扑排序

拓扑排序的实现：对于有向图 G，每次访问 G 中入度为 0 的节点，访问得到的序列即为拓扑排序的结果。
（注意：每一轮中入度为 0 的节点不唯一，因此拓扑排序的结果也不唯一。）

剑指 Offer II 115. 重建序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import defaultdict
class Solution:
    def sequenceReconstruction(self, nums: List[int], sequences: List[List[int]]) -> bool:
        n = len(nums)
        inDegrees = [0]*(n+1)
        dst = defaultdict(list)

        for sequence in sequences:
            for i in range(len(sequence)-1):
                dst[sequence[i]].append(sequence[i+1])
                inDegrees[sequence[i+1]] += 1

        queue = [i for i in range(1, n+1) if not inDegrees[i]]
        while queue:
            if len(queue) >= 2:
                return False
            u = queue.pop(0)
            for v in dst[u]:
                inDegrees[v] -= 1
                if not inDegrees[v]:
                    queue.append(v)
        return True

拓扑排序的应用：若访问结束后若还存在入度不为 0 的节点，则 G 中必有环。

6135. 图中的最长环

第 304 场周赛的压轴题，题解：https://svyj.github.io/2022/07/10/032-Leetcode/

关键路径

查找

顺序查找

折半查找（二分查找）

（二分查找例题点这里）

分块查找

排序

Python内置排序方法

一维列表

1
2
3
list.sort(cmp=None, key=None, reverse=False)
# 或
sorted(list, key=None, reverse=False)

二维列表

1
2
3
4
5
6
7
list = [[ 'A', -1, 99], [ 'J', 0, 86], [ 'T', 1, 65], [ 'S', -2, 100], ['B', -4, 77], ['L', 2, 59]]

# 按第一个元素排序
list.sort(key=(lambda x:x[0]), reverse=False)

# 按第二个元素的绝对值排序
list.sort(key=lambda x:(abs(x[1]),x[1]), reverse=True)  # 先按绝对值（第一关键词），再按本身大小（第二关键词）  如果绝对值相同，则正数在前面

内部排序和外部排序

排序算法中各种与初始序列无关
（1）元素的移动次数与关键字的初始排列次序无关的是：基数排序
（2）元素的比较次数与初始序列无关是：选择排序、折半插入排序
（3）算法的时间复杂度与初始序列无关的是：选择排序、堆排序、归并排序、基数排序
（4）算法的排序趟数与初始序列无关的是：插入排序、选择排序、基数排序

插入排序

（1）直接插入
（2）折半插入
（3）希尔排序

交换排序

（1）冒泡排序
（2）快速排序

选择排序

（1）简单选择排序
（2）堆排序

归并排序

基数排序

算法

二分查找

（详细图解）

必要条件：
（1）查找的内容逻辑有序；
（2）查找元素数量为 1。

704. 二分查找

左闭右闭区间查找

1
2
3
4
5
6
7
8
9
10
11
def search(self, nums, target, n):
    left, right = 0, n-1                # right初始值为 n-1
    while(left <= right):               # 取等号, 当 left==right 时, 区间[left, right]有意义
        mid = (left + right) // 2
        if nums[mid] > target:
            right = mid - 1             # target 在左区间, 右端点减 1 以排除
        elif nums[mid] < target:
            left = mid + 1              # target 在右区间, 左端点加 1 以排除
        else:
            return mid
    return -1                           # 查找失败

左闭右开区间查找

1
2
3
4
5
6
7
8
9
10
11
def search(self, nums, target, n):
    left, right = 0, n                  # right初始值为 n
    while(left < right):                # 不取等号, 当 left==right 时, 区间[left, right)无意义
        mid = (left + right) // 2     
        if nums[mid] > target:        
            right = mid                 # target 在左区间, 右端点自动排除, 无需减 1 
        elif nums[mid] < target:
            left = mid + 1
        else:
            return mid
    return -1                           # 查找失败

278. 第一个错误的版本

双指针

简单双指针

189. 轮转数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def rotate(self, nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    n = len(nums)
    k = k % n
    count = gcd(k, n)
    for start in range(count):
        cur = start
        pre = nums[start]
        while(True):
            next = (cur + k) % n
            nums[next], pre = pre, nums[next]
            cur = next
            if start == cur:
                break

快慢双指针

141. 环形链表

快指针 fast 先走 n 步，慢指针 slow 再开始移动，当快指针到达链表末尾时，慢指针所在位置即为所求

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

1
2
3
4
5
6
7
8
9
10
11
12
13
def removeNthFromEnd(self, head, n):
    if head == None or head.next == None:   # 链表元素个数小于等于 1
        return None
    fast, slow = head, head
    for i in range(n):                      # 快指针先移动 n 步
        fast = fast.next
    if fast == None:                        # 若快指针遍历至链表末尾,倒数第 n 个则为链表第一个元素  
        return head.next
    while(fast.next):                       # 快慢指针同时移动,直至快指针移动到链表末尾
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return head

逆向双指针

由于 num1 中末尾均为 0，因此从后往前填

88. 合并两个有序数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    i, j, index = m-1, n-1, m+n-1
    while(index >= 0):
        if i == -1:
            nums1[index] = nums2[j]
            j -= 1
        elif j == -1:
            nums1[index] = nums1[i]
            i -= 1
        elif nums1[i] > nums2[j]:
            nums1[index] = nums1[i]
            i -= 1
        elif nums1[i] <= nums2[j]:
            nums1[index] = nums2[j]
            j -= 1
        index -= 1
    return nums1

首尾指针

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

双指针从左右两侧移动，若当前和值偏大则右指针左移，偏小则左指针右移

1
2
3
4
5
6
7
8
9
def twoSum(self, numbers, target:):
    i, j = 0, len(numbers)-1
    while(i < j):
        if numbers[i] + numbers[j] == target:
            return [i+1, j+1]
        elif numbers[i] + numbers[j] > target:
            j -= 1
        else:
            i += 1

滑动窗口

567. 字符串的排列

解题思路：设定一个固定长度（与 s1 等长）的窗口在 s2 上移动，利用哈希表记录 s1 和该滑动窗口内各字母的数量。
窗口每向右移动一次，左侧抛弃一个字母，右侧一个字母，维护统计滑动窗口的哈希表，移动过程中判断两个哈希表是否相同即可。

时间复杂度： $O(M \times N)$，$M=26$，空间复杂度： $O(M)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def checkInclusion(self, s1: str, s2: str) -> bool:
    n, m = len(s1), len(s2)
    cnt1 = [0]*26
    cnt2 = [0]*26
    for i in range(n):
        cnt1[ord(s1[i])-ord('a')] += 1
    for i in range(m-n+1):
        if i == 0:
            for j in range(n):
                cnt2[ord(s2[i+j])-ord('a')] += 1
            if cnt1 == cnt2:
                return True
        else:
            cnt2[ord(s2[i-1])-ord('a')] -= 1
            cnt2[ord(s2[i+n-1])-ord('a')] += 1
            if cnt1 == cnt2:
                return True
    return False

209. 长度最小的子数组

究极模板题！！！

1
2
3
4
5
6
7
8
9
10
11
12
# 模板题
def minSubArrayLen(self, target, nums)
    left, right, curSum, maxlen = 0, 0, 0, len(nums)+1 # 初始化左右端点
    while(right < len(nums)):                          # while(右端点可移动): 移动右端点
        curSum += nums[right]                          # 窗口加入右端点元素
        while(curSum >= target):                       # while(满足题目条件): 移动左端点
            if right - left + 1 < maxlen:                 # 更新窗口值
                maxlen = right - left + 1
            curSum -= nums[left]                       # 窗口删除左端点元素
            left += 1                                  # 左端点右移
        right += 1                                     # 右端点右移
    return maxlen

按照上面的模板 👆👆👆， 做下面这题 👇👇👇，尝尝秒解的快感……（照着模板往里套内容即可）
注：翻了翻 ASCII 码表（ASCII码中文站），有一个做字符串题目都能用的小 trick，比如这道题，涉及到的打印字符一共 95 个（已经算是最多的情况了），此时用数组来标记出现过的字符比官方题解的哈希表 set() 效率高很多。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def lengthOfLongestSubstring(self, s: str) -> int:
    n = len(s)
    dicts = [0]*95
    left, right = 0, 0
    maxLen = 0
    while right < n:
        dicts[ord(s[right])-ord(' ')] += 1

        if dicts[ord(s[right])-ord(' ')] > 1:
            while(left <= right):
                if s[left] == s[right]:
                    dicts[ord(s[left])-ord(' ')] -= 1
                    left += 1
                    break
                dicts[ord(s[left])-ord(' ')] -= 1
                left += 1

        curLen = right - left + 1
        if curLen > maxLen:
            maxLen = curLen
        right += 1
    return maxLen

深度优先搜索

508. 出现次数最多的子树元素和

很基本的 DFS 模板题……DFS 往往通过递归调用实现

513. 找树左下角的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 递归深度搜索
def findBottomLeftValue(self, root):
    ret = maxdep = 0
    def dfs(node, depth):
        if node is None:
            return
        nonlocal ret, maxdep
        if depth > maxdep:
            ret = node.val
            maxdep = depth
        dfs(node.left, depth+1)   # 递归搜索左子树
        dfs(node.right, depth+1)  # 递归搜索右子树
    dfs(root, 1)
    return ret

515. 在每个树行中找最大值

广度优先搜索

又是一个模板题，BFS 中最常见的求最大连通区域问题，**BFS 通常用队列实现**

695. 岛屿的最大面积

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 maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    self.m, self.n = len(grid), len(grid[0])
    self.dire = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    self.flag = [[0]*self.n for _ in range(self.m)]
    self.grid = grid
    ret = 0
    for i in range(self.m):
        for j in range(self.n):
            if self.grid[i][j] == 1 and self.flag[i][j] == 0:
                area = self.bfs(i, j)
                if area > ret:
                    ret = area
    return ret
    
def bfs(self, x, y):
    area = 0
    queue = [[x, y]]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            dstX = x + self.dire[i][0]
            dstY = y + self.dire[i][1]
            if dstX >= 0 and dstX < self.m and dstY >= 0 and dstY < self.n:
                if self.grid[dstX][dstY] == 1 and self.flag[dstX][dstY] == 0:
                    area += 1
                    queue.append([dstX, dstY])
                    self.flag[dstX][dstY] = 1
    return area if area else 1

优化一下：不用 HashTable，直接将 grid 中搜索到过的位置置 0 即可 👇👇👇
内存消耗：15 MB, 在所有 Python3 提交中击败了99.14%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
def bfs(self, x, y):
    area = 0
    queue = [[x, y]]
    while queue:
        x, y = queue.pop(0)
        for i in range(4):
            dstX = x + self.dire[i][0]
            dstY = y + self.dire[i][1]
            if dstX >= 0 and dstX < self.m and dstY >= 0 and dstY < self.n and self.grid[dstX][dstY] == 1:
                area += 1
                queue.append([dstX, dstY])
                self.grid[dstX][dstY] = 0
    return area if area else 1

下面是一道经典的题目，可以参考994. 腐烂的橘子 👇👇👇
BFS 解法不是该题的最优解，但 BFS 的思想非常经典

解题思路：将所有 0 视作腐烂的橘子，1 视作正常的橘子，每个腐烂的橘子每天会导致其周围四个方向的橘子腐烂，则求每一个 1 到最近的 0 的距离，等价于求该位置的橘子会在第几天腐烂？将所有 0 当作一个整体 0，每一轮往外扩散，搜索与该整体 0 相邻的 1， 初始 step = 0，每一轮 BFS 后 step 加 1，即“天数加1”。

542. 01 矩阵

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 updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
    m, n = len(mat), len(mat[0])
    ret = [[-1]*n for _ in range(m)]
    queue = []
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                queue.append([i, j])
                ret[i][j] = 0

    step = 1
    while queue:
        k = len(queue)
        temp = []
        for i in range(k):
            x, y = queue.pop(0)
            for dx, dy in [[x, y-1], [x, y+1], [x-1, y], [x+1, y]]:
                if dx >= 0 and dx < m and dy >= 0 and dy < n:
                    if mat[dx][dy] == 1:
                        ret[dx][dy] = step
                        mat[dx][dy] = 0
                        temp.append([dx, dy])
        queue = temp
        step += 1

    return ret

递归

递归的题目一般很简单，关键是找出正确的递推公式……比如斐波那契数列（剑指 Offer 10- I. 斐波那契数列）、汉诺塔问题（面试题 08.06. 汉诺塔问题）、青蛙跳台阶问题（剑指 Offer 10- II. 青蛙跳台阶问题 ）
二叉树中也常见 👇👇👇

6116. 计算布尔二叉树的值

上来就想着用迭代法，傻傻的用栈实现，结果不熟练搞半天硬是没过……还是老老实实用递归写吧

1
2
3
4
5
6
7
8
9
def evaluateTree(self, root: Optional[TreeNode]) -> bool:
    if root.val == 0:
        return False
    elif root.val == 1:
        return True
    elif root.val == 2:
        return self.evaluateTree(root.left) or self.evaluateTree(root.right)
    elif root.val == 3:
        return self.evaluateTree(root.left) and self.evaluateTree(root.right)

112. 路径总和

递归思路：减去当前节点的值，递归查询左子树或右子树

1
2
3
4
5
6
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    if root == None:
        return False
    if root.left == None and root.right == None:
        return targetSum == root.val
    return self.hasPathSum(root.left, targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

226. 翻转二叉树

一眼递归：调换所有节点的左右子树即可

1
2
3
4
5
6
7
8
9
def invertTree(self, root: TreeNode) -> TreeNode:
    if root == None:
        return root
    temp = root.right
    root.right = root.left
    root.left = temp
    self.invertTree(root.left)
    self.invertTree(root.right)
    return root

优化一下，利用 Python 的多元赋值特性 👇👇👇

1
2
3
4
5
def invertTree(self, root: TreeNode) -> TreeNode:
    if root == None:
        return root
    root.right, root.left = self.invertTree(root.left), self.invertTree(root.right)
    return root

回溯

以下为回溯法的模板

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

照着模板写题 👇👇👇

46. 全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
def permute(self, nums: List[int]) -> List[List[int]]:
    self.ret = []
    self.backtrack(nums, [])
    return self.ret

def backtrack(self, nums, path):
    if not nums:
        self.ret.append(path)  # nums 已被选择完，则返回结果
        return
    for i in range(len(nums)): # 利用 for 循环来进行选择和撤销选择的操作
    	# 进入循环，选择 nums[i]，从 nums 中移除并加入 path
        self.backtrack(nums[:i]+nums[i+1:], path+[nums[i]])
        # 跳出循环，对下一个元素进行选择操作

会了模板题目再写其他题目就很就很简单了
回溯三要素：路径、选择列表、结束条件！！！

77. 组合

1
2
3
4
5
6
7
8
9
10
11
12
def combine(self, n: int, k: int) -> List[List[int]]:
    self.nums = [i for i in range(1, n+1)]
    self.k = k
    self.ret = []
    self.backtrack(self.nums, [])
    return self.ret

def backtrack(self, nums, path):
    if len(path) == self.k:
        self.ret.append(path)
    for i in range(len(nums)):
        self.backtrack(nums[i+1:], path+[nums[i]])

优化一下，其实生成 nums 数组是多此一举，因为本题回溯用不到列表中被选择元素之前的元素
然后再剪枝， path 中组合数个数足够则停止

1
2
3
4
5
6
7
8
9
10
11
12
13
def combine(self, n: int, k: int) -> List[List[int]]:
        self.n = n
        self.k = k
        self.ret = []
        self.backtrack(1, [])
        return self.ret

    def backtrack(self, num, path):
        if len(path) == self.k:
            self.ret.append(path)
        for i in range(num, self.n+1):
            if len(path) < self.k:            # 当前组合数个数小于 k 则继续
                self.backtrack(i+1, path+[i])

贪心算法

870. 优势洗牌

这是一道周赛题，拿到手没思路，还是贪心写少了，也可以说没怎么练过，看了题解才会……题目的意思有点田忌赛马的味道，目的是使 nums1 中的元素尽最可能多的大于 nums2 中同位置的元素。

解题思路：
1、将 nums1 和 nums2 排好序；
2、从小到大遍历 nums1，对于任意最小元素 nums1[i]，有以下情况：
（1）若 nums1[i] 比 nums2 中的当前最小元素 nums2[j] 更大，则代表 nums1 中所有未匹配元素都比 nums2[j] 大，此时将 nums1[i] 视为 “上等马”，将其匹配至 nums2[j] 即可，再更新 nums2 中的最小元素为当中的次小元素。
（2）若 nums1[i] 比 nums2 中的任意元素都要小，则将其视为 “下等马”，反正都比不过，待后续随机匹配即可。
3、遍历匹配的集合，若存在 nums2 中元素未被匹配成功的，将 “下等马” 数组的元素弹出与其匹配即可。

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 advantageCount(self, nums1, nums2):
    n = len(nums1)
    nums1.sort()
    sort2 = sorted(nums2)                     # nums2需要用另外空间排序，因为要保持其顺序用于对应

    good = {num: [] for num in nums2}         # 上等马出战对应~
    inferior = []                             # 下等马集合！
    index = 0
    for num1 in nums1:
        if num1 > sort2[index]:               # 找到最小的“上等马”
            good[sort2[index]].append(num1)   # 用数组存储避免 num2 中有相同元素
            index += 1                        # 更新 num2 的最小元素
        else:
            inferior.append(num1)             # 否则视为“下等马”

    for key in good.keys():
        if good[key] == []:
            good[key].append(inferior.pop(0)) # 下等马按顺序弹出匹配
            
    for i in range(n):                        # 按照匹配结果更新 num1 的排序
        if good[nums2[i]]:                   
            nums1[i] = good[nums2[i]].pop(0)
        else:
            nums1[i] = inferior.pop(0)

    return nums1

动态规划

基础动态规划

（1）序列型
300. 最长递增子序列

状态转移方程：
若 $num[j] > num[i]$，则 $L_{i} = \max \limits_{1<=j< i}(L_{j}+1, L_{i})$

1
2
3
4
5
6
7
8
9
10
11
def lengthOfLIS(self, nums):
    dp = [0]*(len(nums))
    ret = 1
    for i in range(len(nums)):
        dp[i] = 1
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[j]+1, dp[i])
                if dp[i] > ret:
                    ret = dp[i]
    return ret

（2）双序列型
（3）划分型
（4）区间型
（5）背包型

以上为常见类型

（6）状态压缩型
（7）树型

记忆化搜索

2327. 知道秘密的人数

常规的动态规划思想是：直接用 dp 数组记录每天知道秘密的人数，最后返回 dp[n]，但由于 forget 的存在实现起来有点困难。

尝试改变思路：用 dp 数组 记录每天新增的人数，最后再统计第 n 天知道秘密的人数。由此可得状态转移方程：
第 i 天新增得知秘密的人数: $N_{i} = \sum\limits_{j=i-forget+1}^{i-delay}N_j$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def peopleAwareOfSecret(self, n, delay, forget):
    dp = [0]*(n+1) # 记录第index天能够得知秘密的人数
    ret = 0
    dp[1] = 1
    for i in range(1, n+1):
    	# 第 i 天知道秘密的人只能在[i+delay, i+forget)的区间内传播秘密
        for j in range(i+delay, i+forget):  
            if j <= n:
                dp[j] += dp[i]
                dp[j] %= (10 ** 9 + 7)
    
    # 统计在第 n 天还没有忘记的人的数量即可
    for i in range(n+1-forget, n+1):
        ret += dp[i]
        ret %= (10 ** 9 + 7)
    return ret

其他动态规划

53. 最大子数组和 （看清楚这道题与滑动窗口的区别）

位运算

二进制表示

任意整数 $n$ 都可以表示成 $(a_{1}a_{2}···a_{k})_{2}$的形式，其中 $a_{i}={0, 1}$, $(1 \leq i \leq k)$

不妨设 $n$ 的二进制串为
$$n = (a10···0)_{2} \tag{1}$$
其中 $a$ 表示若干个高位，$1$ 表示最低位的 $1$，其后为若干个 $0$。

  • 与运算（&）：遇 0 得 0

（1）$n-1$ 的二进制表示为：
$$n-1 = (a01···1)_{2}, \tag{2}$$
该二进制串在式 $(1)$ 的基础上将最低位的 $1$ 及其后的 $0$ 进行了反转，将 $n$ 和 $n-1$ 按位与运算，即将 $(a10···0)_{2}$ 和 $(a01···1)_{2}$ 按位与，可以得到:
$$n \And (n-1) = (a00···0)_{2}, \tag{3}$$
其中 $n$ 的二进制串中最低位的 $1$ 被移除。
若 $n$ 是正整数，且 $n \And (n-1) = 0$，则 $n$ 为 $2$ 的幂。
（2）$-n$ 的二进制表示：（在计算机中，负数按照补码规则存储，$-n$ 为 $n$ 的二进制表示的每一位取反再加上 $1$）
$$-n = (\overline{a}01···1)_{2} + (1)_{2} = (\overline{a}10···0)_{2}, \tag{4}$$
其中 $\overline{a}$ 为取反操作。将 $n$ 和 $n-1$ 按位与运算，即将 $(a10···0)_{2}$ 和 $(a01···1)_{2}$ 按位与，则可以得到:
$$n \And (-n) = (b10···0)_{2}, \tag{5}$$
其中 $a \And \overline{a} = b = 0$。
若 $n$ 是正整数，且 $b = 0$，也即 $n \And (-n) = n$，则 $n$ 为 $2$ 的幂。

191. 位1的个数

容易想到的是利用 $2$ 的幂对该32位二进制串进行按位与，若某一位为 $1$，则按位与的结果必不为 $0$。

1
2
3
4
5
6
7
8
class Solution:
    def hammingWeight(self, n: int) -> int:
        ret = 0
        for i in range(32):
            if n & (1 << i):
                ret += 1
        return ret

优化一下，由于 $n-1$ 与 $n$ 的二进制串按位与运算可以移除最低位的 $0$，根据这一运算特点，我们可以：
（1）将 $n$ 与 $n-1$ 进行式 $(3)$ 中的与运算操作；
（2）消除最低位后将值重新赋给 $n$；
（3）重复以上步骤直至 $n$ 为 $0$。

1
2
3
4
5
6
7
class Solution:
    def hammingWeight(self, n: int) -> int:
        ret = 0
        while n:
            n = n & n-1
            ret += 1
        return ret

190. 颠倒二进制位

对于二进制串 n = 11000010100101000001111010011101，对 n 的每一位进行以下操作：
1）初始化 ret = 0；
2）将 ret 左移空出最后一位；
3）通过按位 或 运算将 n 的最后一位（n & 1）加到 ret 的最后一位上；
4）再将 n 右移去掉最后一位。
00000000000000000000000000000000 or 1 = 00000000000000000000000000000001
00000000000000000000000000000010 or 0 = 00000000000000000000000000000010
00000000000000000000000000000100 or 1 = 00000000000000000000000000000101
00000000000000000000000000001010 or 1 = 00000000000000000000000000001011
00000000000000000000000000010110 or 1 = 00000000000000000000000000010111
……
01011100101111000001010010100000 or 1 = 01011100101111000001010010100001
10111001011110000010100101000010 or 1 = 10111001011110000010100101000011

1
2
3
4
5
6
7
8
class Solution:
    def reverseBits(self, n: int) -> int:
        ret = 0
        for i in range(32):
            lastBit = n & 1
            ret = ret << 1 | lastBit
            n = n >> 1                
        return ret

分治法
注：在 Python3 中，int 具有任意长度。 因此，如果要获取 32 位数字，则必须使用 0xffffffff（即 32 个设置位，因此是 0b11111111111111111111111111111111）进行掩码：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def reverseBits(self, n: int) -> int:
        M1 = 1431655765 # 01010101010101010101010101010101
        M2 = 858993459  # 00110011001100110011001100110011
        M4 = 252645135  # 00001111000011110000111100001111
        M8 = 16711935   # 00000000111111110000000011111111

        n = n >> 1 & M1 & 0xffffffff | (n & M1) << 1 & 0xffffffff
        n = n >> 2 & M2 & 0xffffffff | (n & M2) << 2 & 0xffffffff
        n = n >> 4 & M4 & 0xffffffff | (n & M4) << 4 & 0xffffffff
        n = n >> 8 & M8 & 0xffffffff | (n & M8) << 8 & 0xffffffff

        return n >> 16 & 0xffffffff | n << 16 & 0xffffffff

  • 或（|）运算：遇 1 得 1

  • 异或（^）运算：同得 0，异得 1

（1）n ^ n = 0
（2）m ^ n = n ^ m
（3）0 ^ n = n
由以上可推知（4）n ^ n ^ n = n

136. 只出现一次的数字

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ret = 0
        for num in nums:
            ret ^= num
        return ret

参考链接

[1] 链表（单链表）的基本操作及C语言实现