Attention 等经典算法手撕

方法论

递归

确定递归函数的参数和返回值
确定终止条件
确定每一层递归的逻辑

回溯

回溯就是穷举出所有可能，一般用来解决不分顺序的组合问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

贪心

如何由局部最优推出全局最优

动态规划

由前一个状态推导而来

确定 dp 数组的下标及含义
递推公式
初始化 dp 数组
确定遍历顺序
举例推导 dp 数组

Python 常用指令

1
2
3


# 最大值
import sys
max_v = sys.maxsize # 9223372036854775807 (2^63 - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


# 字符串排序，返回list
sorted(string)
# 字符串拼接
"sep".join(["hhhh", "iiii", "jjjj"]) # hhhhsepiiiisepjjjj
# 因此获得倒序字符串的指令是：
"".join(sorted(string))
# 获得ascii码
ord('a')
# 获得对应字符
chr(65)

1
2
3
4


# 创建一个字典，当访问不存在的key时，默认创建并将value设为int类型
mp = collections.defaultdict(int) # defaultdict(<class 'int'>, {'a': 3, 'b': 4})
# 同样可创建list类型的
mp = defaultdict(list) # defaultdict(<class 'list'>, {'a': [1, 2], 'b': [3]})

1
2


# 元组可作为哈希的key，list不能
mp[tuple(ls)] = 1

双指针

移动零到数组末尾

左右指针从最左侧为起点

左指针指向处理过的非零序列末尾后的 0，右指针指向待处理序列的头部，两指针之间全部为 0

若右指针指的不是零，则交换左右指针指向的值，将右指针的非零值放到做指针处

二叉树

144 二叉树前序遍历（迭代）

维护一个栈。

（将根节点入栈）
将父节点取出
将右节点放入，再将左节点放入（这样左节点会比右节点先取出）
重复（接下来会将左节点取出并重复操作）
直到栈中没有元素

94 二叉树的中序遍历

同样维护一个栈

根节点作为当前节点
找到最左的节点，并再寻找途中依次将节点放入栈
将栈中的元素取出，该元素的左分支已全部遍历。将该元素放入 res，然后将右节点作为当前节点重复以上操作

145 二叉树的后序遍历

后序遍历顺序：左 - 右 - 中

可以按中 - 右 - 左顺序遍历后将结果反转

二叉树的统一迭代遍历 ***

向栈中添加节点时，按反序添加。这样在出栈时才是正序。

如前序遍历：

出栈：中 -> 左 -> 右

因此入栈顺序：右 -> 左 -> 中

 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
46
47
48
49
50


class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            //
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
                if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。
                
            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop(); //不要忘了
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }
}

class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
    Stack<TreeNode> st = new Stack<>();
    if (root != null) st.push(root);
    while (!st.empty()) {
        TreeNode node = st.peek();
        if (node != null) {
            st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
            if (node.right!=null) st.push(node.right);  // 添加右节点（空节点不入栈）
            st.push(node);                          // 添加中节点
            st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            if (node.left!=null) st.push(node.left);    // 添加左节点（空节点不入栈）
        } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
            st.pop();           // 将空节点弹出
            node = st.peek();    // 重新取出栈中元素
            st.pop();
            result.add(node.val); // 加入到结果集
        }
    }
    return result;
}
}

二叉树层序遍历

List result = [[0], [1, 2], [3, 4, 5, 6]]

递归：递归函数的参数中把深度放进去，递归时获取的节点放入result中对应深度的数组中

迭代：新建一个存储Node的队列，对队列中存入的的每个结点，将其依次取出读取值放入result，并将这些节点下层的结点放入队列。重复直到子节点为null。

106 中后序遍历序列构造二叉树 ***

回溯

77 组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

剪枝

取数是从左到右依次取的。

每层在取下一个数时，不会考虑左边（即之前）已经取过的数。

因此可能存在情况：

靠后的数是没必要取的，因为就算之后的数全取了，也会出现数量不够的问题。

这些分支便是需要剪掉的分支。

47 全排列II

这道题有点意思

创建一个boolean used[]数组来记录数字是否被使用过

剪枝需要剪除同层已经使用过的数字的分支

同层数字已被使用过的条件：i > 0 && nums[i] == nums[i-1] && used[i-1] == false

在向下递归时只挑选没被使用过的数字，即used[i] == false