LeetCode刷题记录

(Updated: )
Notes

核心算法框架

动态规划思路和框架:

  • 动态规划问题的核心问题: 找最优解,比如最长递增子序列,最小编辑距离
  • 动态规划问题的核心求解思路: 穷举,也就是说针对一个问题把所有可能的解都找到,那自然最值解也就自然明了了,只是实际的解决方案是针对穷举方案的优化而已
  • 实际解决动态规划问题的三个核心点:
    • 重叠子问题
    • 最优子结构
    • 状态转移方程
  • 写出状态转移方程的几个主要步骤:
    • 确定问题的base case,即明确一个求解问题的最简单情况
    • 问题都有什么状态
    • 对于每个状态能够做出的选择
    • 如何定义DP数组,来表示选择和变化

动态规划的伪代码框架:

1
2
3
4
5
6
7
8
9
10
//初始化base case...

/* 定义DP数组 */
dp[0][0][...] = base case;

//进行状态转移
for 状态1 in 状态1的所有取值:
    for 状态2 in 状态2的所有取值:
        for ...
            dp[状态1][状态2][....] = 求最值{选择1, 选择2, ...}

斐波那契数列的动态规划求解:

对于斐波那契数列可以先使用递归进行求解：

1
2
3
4
5
6
7
int fib(int n) {
    if (n <= 0) return 0;
    if ((n == 1) || (n == 2)) {
        return 1;
    }
    return (fib(n-1) + fib(n-2));
}

其实对于没有时间复杂度限制的求解来说，递归已经满足要求了，但是画出上述递归求解过程对应的递归数就会发现很多求解都是重复的，比如*fib(8) = fib(7) + fib(6)，而fib(7) = fib(6) + fib(5)*，能够看出fib(6)的求解过程被调用了至少2次，所以上述的低柜求解方法不是最优的，优化的过程就是找重叠子问题，在代码上实现的方式就是带备忘录的递归方法了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int fib(int n){
    vector<int> memory(n+1, 0);
    if (n <= 0) return 0;
    return helper(n, memory);
}

int helper(int n, vector<int> &memory) {
    if (n == 1) || (n == 2) {
        return 1;
    }
    /* 已经计算过了 */
    if (memory[n] != 0) return memory[n];
    
    /* 还未计算过 */
    memory[n] = helper[n-1, memory] + helper[n-2, memory];
    return memory[n];
}

只是这种递归的解法是自顶向下的，但是所谓的动态规划正常的解决思路是自底向上的，所以从最简单的base case逐渐向最终解的方向一步步求解的过程才是正宗的胴体啊规划，是由循环迭代完成的动态规划问题求解：

1
2
3
4
5
6
7
8
9
10
11
int fibWithDpTable(int n) {
    if (n <= 0) return 0;
    if (n == 1) || (n == 2) return 1;

    vector<int> dp(n+1, 0); //初始化dp table
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

再进一步，由于斐波那契数列的求解过程，能够发现我们可能不需要一直存储所有已有求解，因为求一个新的解之需要之前的两个即可，那么我们就可以通过状态压缩来对DP table进行简化，从而降低程序的空间复杂度：

1
2
3
4
5
6
7
8
9
10
11
int fibSimpleWithDpTable(int n) {
    if (n <= 0) return 0;
    if (n == 1) || (n == 2) return 1;
    int pre, cur = 1;
    int tmp;
    for (int i = 3; i <= n; i++) {
        cur = cur + pre;
        pre = cur - pre;
    }
    return cur;
}

凑零钱问题

问题的详细描述不展开讲了，就是跟妈妈要钱amount块钱，妈妈最少给你几张就能满足你的要求（假设有n种面值的钱），针对该问题的几个动态规划核心要素：

  • base case：当amount小于0时，直接返回0，因为妈妈不用给你钱
  • 状态，即原问题和子问题中的变量：该问题的求解过程中变化的就只有钱的总数amount，因为妈妈每给你一张，那你的后续需求就少了，即amount变小了
  • 选择，即导致状态产生变化的原因：该问题中能够选择的就是每次妈妈给你钱的面值，她可以给你10元的，也可以给你20元的。。。
  • DP函数或DP数组的定义：对于自顶向下的解法来说就是DP函数就是递归函数；对于自下而上的解法来说就是常规的DP table了

通过上述的分析，能够得到解凑零钱问题的基础伪代码：

1
2
3
4
5
6
7
def coinChange(coins: List[int], amount: int) {
    def dp(amount):
        for coin in coins:
            res = min(res, dp(amount - coin) + 1)
        return res
    return dp(amount)
}

为上述伪代码加上base case，就成为了最基础的递归解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def coinChange(coins: List[int], amount: int):
    def dp(amount):
        # base case:
        if amount < 0: return -1
        if amount == 0: return 0

        int res = MAX_INT;  #因为是求最小值，所以初始化为无限大
        
        for coin in coins:
            #  求解子问题
            subProblem = dp(amount - coin)
            if subProblem == -1: continue;  #子问题无解则跳过，进行下一个选择
            res = min(res, subProblem + 1)   #子问题有解，则进行对应的选择

        if res == MAX_INT:
            return -1
        else:
            return res
    return dp(amount)

为了消除重复子问题，那么就需要引入带备忘录的递归解法了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def coinChange(coins: List[int], amount: int):
    memory = dic()  #定义备忘录
    def dp(amount):
        # 查备忘录
        if amount in memory: return memory[amount]

        # base case:
        if amount < 0: return -1
        if amount == 0: return 0
        int res = MAX_INT;  #因为是求最小值，所以初始化为无限大

        for coin in coins:
            subProblem = dp(amount - coin)  #求解子问题
            if subProblem == -1: continue  #子问题无解则跳过，进行下一个选择
            res = min(res, subProblem + 1)   #子问题有解，则进行对应的选择

        if res == MAX_INT:
            memory[amount] = -1
        else:
            memory[amount] = res
        return memory[amount]
    return dp(amount)

如上是自上而下的解法，自下而上的循环迭代解法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int coinChange(vector<int> &coins, int amount):
    // 定义DP数组
    vector<int> dp(amount+1, amount+1);

    // base case
    if (amount < 0) return -1;
    if (amount == 0) return 0;
    dp[0] = 0;

    // 遍历状态的所有取值
    for (int i = 0; i <= amount; i++) {
        // 求每个选择的最小值
        for (int coin : coins) {
            if ((dp[i] - coin) < 0) continue;
            dp[i] = min(dp[i - coin] + 1, dp[i]);
        }
    }

二叉树

普通二叉树：

DFS-深度优先：

1
2
3
4
5
solition(TreeNode *root) {
    root->val;  //to do something
    solution(root->left);   //遍历左子树
    solution(root->right);  //遍历右子树
}

BFS-广度优先：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void traverse(TreeNode *root) {
    if (root == nullptr) return;

    queue<TreeNode*> q;

    q.push(root);
    while(!q.empty()) {
        TreeNode* curNode  = q.front();
        cout << curNode->val;
        q.pop();

        if (curNode->left != nullptr) q.push(curNode->left);
        if (curNode->right != nullptr) q.push(curNode->right);
    }
}

搜索二叉树BST：

1
2
3
4
5
6
7
8
9
10
11
solition(TreeNode *root, int target) {
    if (root->val == target) {
        //to do something
    }
    if (target < root->val) {
        solution(root->left);   //遍历左子树
    }
    if (target > root->right) {
        solution(root->right);  //遍历右子树
    }
}

例题：

  1. 判断BST的合法性 💔
  2. 二叉树中的搜索 😄
  3. 二叉搜索树中的插入操作 😄
  4. 二叉搜索树删除节点 💔
  5. 计算一颗完全二叉树的节点个数💔
  6. 二叉树的序列话与反序列化 💔

    ⚠️注意：中序遍历能够序列化，但是不能反序列化

  7. 二叉树节点的公共最近祖先💔
  8. 二叉树的最小深度😄
  9. 二叉树的最大深度😄
  10. 496 下一个更大元素 I😄
  11. 剑指 Offer 64. 求1+2+…+n😄
  12. 剑指 Offer 54. 二叉搜索树的第k大节点😄
  13. 剑指 Offer 28. 对称的二叉树😄
  14. 剑指 Offer 26. 树的子结构💔
  15. 剑指 Offer 27. 二叉树的镜像😄
  16. 剑指 Offer 32 - III. 从上到下打印二叉树 III💔
  17. 剑指 Offer 32 - II. 从上到下打印二叉树 II😄
  18. 剑指 Offer 32 - I. 从上到下打印二叉树😄

LRU&LFU缓存淘汰算法

LRU淘汰算法

LRU（Last recently used），也即是最近使用过的是有用的，最近未使用过的是没用的
LRU缓存机制就是设计一个数据结构，这个数据结构有capacity，用以表示该数据结构的最大元素个数，接口put(key, val)用来向该数据结构存入键值对，get(key)用来获取key对应的val值，如果不存在，则返回-1，但是需要注意的是get和put方法的时间复杂度都必须是O(1)

算法思路：

这个数据结构即然要保存key-val，则必定需要一个hash表，但是单纯的hash表又不能满足元素有顺序，所以就需要一个hash和双向连表结合的数据结构hash链表，其中
hash表：{key-Node, key-Node}
双向连表：Node-Node

⚠️：之所以使用双向链表，是因为需要对链表在随机位置进行删除操作，链表中随机删除一个节点，一般情况下需要操作其前驱节点和后续节点，为了能够降低时间复杂度，所以选择双向链表，记住后续如果一个链表需要频繁的删除操作，则可以使用双向链表

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
class Node {
public:
    int key;
    int val;
    Node *next, *pre;
    Node(int key, int val) {
        this->key = key;
        this->val = val;
        next = nullptr;
        pre = nullptr;
    }
};

class DoubleDirectList {
private:
    Node *head;
    Node *tail;
    int size;

public:
    DoubleDirectList() {
        tail = new Node(0, 0);
        head = new Node(0, 0);
        head->next = tail;
        tail->pre = head;
        size = 0;
    }

    /* 在双向连表的尾部新增 */
    void addLast(Node *newNode) {
        if (newNode == nullptr) return;
        tail->pre->next = newNode;
        newNode->pre = tail->pre;
        newNode->next = tail;
        tail->pre = newNode;
        size++;
    }

    /* 双向链表随机删除 */
    void remove(Node *node) {
        if (node == nullptr) return;
        node->pre->next = node->next;
        node->next->pre = node->pre;
        size--;
    }

    /* 在双向链表的头部删除 */
    Node* popFront() {
        if (head->next != tail) {
            Node *tmp = head->next;
            head->next->next->pre = head;
            head->next = head->next->next;
            size--;
            return tmp;
        } else {
            return nullptr;
        }
    }

    int getsSize() {
        return size;
    }
};

class LRUCache {
private:
    DoubleDirectList *doubleList;
    unordered_map<int, Node*> nodeMap;
    int capacity;

public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        doubleList = new DoubleDirectList();
        nodeMap = {};
    }

    /* 如果key不存在，则返回-1，否则返回对应的val，并且将对应的Node从list中拿出来，并且放在链表尾部 */
    int get(int key) {
        if (!nodeMap.count(key)) return -1;

        Node *node = nodeMap[key];
        makeRecent(key);
        return node->val;
    }
    
    /* 如果当前key存在于map中，则需要替换val，即将原来的map和list中的node都删除，重新插入map，并将新node插入List尾部；
    如果key不存在于map中，则需进一步判断size是否超过capacity，如果超过则需要把list的头部node删除，再插入新的node，否则直接插入新的node */
    void put(int key, int value) {
        int val = value;
        if (nodeMap.count(key)) {
            deleteByKey(key);
            addRecent(key, val);
            return;
        }
        if (doubleList->getsSize() >= capacity) {
            removeLeastRecentlyUsed();
        }
        addRecent(key, val);
    }

    void makeRecent(int key) {
        Node *node = nodeMap[key];
        doubleList->remove(node);
        doubleList->addLast(node);
    }

    void addRecent(int key, int val) {
        Node *newNode = new Node(key, val);
        nodeMap[key] = newNode;
        doubleList->addLast(newNode);
    }

    void deleteByKey(int key) {
        Node *node = nodeMap[key];
        doubleList->remove(node);
        nodeMap.erase(key);
    }

    void removeLeastRecentlyUsed() {
        Node *node = doubleList->popFront();
        if (node == nullptr) return;
        int key = node->key;
        nodeMap.erase(key);
    }
};

LRU淘汰算法

LRU(Last frequently used)，最近最少使用，也就是把那些使用频率最低的元素淘汰掉，而且当元素的使用频率相同时，需要删除最早插入的元素，当然put和get方法同样需要O(1)的时间复杂度