算法

排序

  • 稳定：值相同的元素相对位置不变，2(1), 2(3), 2(2), 1 排完序之后，1, 2(1), 2(3), 2(2)，在 2 里面的相对位置是没有变化的，这样如果有与 2 关联的数据，他们的排序也不会发生变化

选择排序

在未排序的数据中不断寻找最小值，将最小值与已排序末尾的后一位交换
不稳定，时间复杂度 O(n^2)，空间复杂度 O(1)

冒泡排序

每次从后向前遍历，不断交换逆序对，这样每次就会把未排序里最小（最大）的值移到排序末尾
稳定，时间复杂度 O(n^2)，空间复杂度 O(1)

插入排序

每次从排好序的末尾后一位开始向前遍历，将这个未排序元素不断与前面交换，直到排到他合适的位置
稳定，时间复杂度 O(n^2)，空间复杂度 O(1)
数组初始越有序，所需时间越小

希尔排序

建立在插入排序的基础上，将数组按间隔长度分成若干组，对每一组分别执行插入排序，然后缩小间隔长度，重复上述步骤，直到间隔长度为 1，此时就是插入排序
不稳定，时间复杂度小于等于 O(n^2)，空间复杂度 O(1)
初始化一个大的间隔长度来提升数组的整体有序度

快速排序

先随机选一个元素，把小于它的都放在左边，把大于的都放在右边，再递归地排序左右
不稳定，时间复杂度 O(nlogn)，最坏 O(n^2)，空间复杂度 O(logn)

归并排序

先用递归到边界，把两个元素排序作为一组，把左右两半子数组排好序，然后再二叉树的后序遍历时合并两个有序数组，最后一直合并直到只剩一组
稳定，时间复杂度 O(nlogn)，空间复杂度 O(n)

堆排序

用数组构建最大堆后，通过不断将堆顶最大值交换到数组末尾，并缩小堆的范围，同时维护堆性质，最终使整个数组变为升序
不稳定，时间复杂度 O(nlogn)，空间复杂度 O(1)

计数排序

先建立一个 count 数组，将值映射为索引，存储出现次数，然后再一次 for 循环将 count 数组转换为前缀和数组，每个值就是元素最后出现的位置（保证稳定性），最后从右向左遍历原数组，将元素放到 count 记录的末尾位置，对应 count 减一，最后遍历完得到的新数组就是排好序的
非比较排序，稳定，时间复杂度 O(n + k)，空间复杂度 O(n + k)，O(k)是开数组要的时间和空间
如果用哈希表的话，哈希表 key 无序就不能直接建立前缀和数组了，还得用排序 keys

桶排序

将待排序数组中的元素使用映射函数分配到若干个桶中，对每个桶进行排序，最后合并这些桶
就是用上面这些排序算法（插入排序）的时候先划分成组分别排序，再合并有序数组，效率会更高
桶排序是“按值域分组”，希尔排序是“按位置分组”

基数排序

是计数排序的扩展，就是按位数逐个排序排，先排个位再排十位、百位，拍到最后就完成排序
要用稳定的排序算法，适合用计数排序

哈希表查找逻辑

哈希表的底层是桶数组（一个存放键值对的数组）

  1. 先用 key 通过哈希函数计算出哈希值
  2. 再根据哈希值和桶（bucket）数量确定索引位置
  3. 若该位置的 key 与目标一致，则返回对应 value
  4. 否则按冲突解决策略（如链地址法或开放寻址）继续查找，直到匹配 key 并取出 value。
  • 元素的占到容量的百分比是负载因子（默认 0.75），超过了阈值则扩容
  • HashMap 的扩容是扩大二倍，原来的哈希值会新增 1 个 bit，既不用重新计算又能随机分散到新的桶中

滑动窗口

left 是左边界的索引，是在窗口内的最左元素
定长窗口直接算

1
int left = right - k + 1;//k 是窗口长度

不定长用 while

1
2
3
4
5
6
7
//这个是典型，left初值是0，给0出边界后left进一
//此时left就指向新窗口的左边界了
//窗口长度就是正常的右减左加一，right-left+1
while (n0 > k) {
    if (nums[left] == 0) n0--;
    left++;
}

二分查找

  • 查找 target 第一次出现的索引
  • ranges::lower_bound C++20 里引入了这个函数，找下界，下面这就是他的具体实现
  • 默认比较器用的 less，就是 mid 值 < target，改用 greater 后就是 mid > target
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int n = nums.size();
int left = 0, right = n - 1;//指针初值设为两头
// 循环不变量：整个循环包括结束都会严格满足下面这两个条件
// 循环不变量：看最后左右指针在mid汇合的时候的条件，计算之后左右指针落点
// nums[left-1] < target
// nums[right+1] >= target
// 因为是二分查找，所以最后两指针是相邻的
while ( left <= right ) {//while循环
    int mid = (left + right ) / 2;
    //如果中间值在target左侧，就更新left，缩小左边界
    if (nums[mid] < target) {//这个地方比较的是mid,老错写成left
        //left要设为mid+1，是闭区间最左边界
        left = mid + 1;
    }
    //right要设为mid-1
    else right = mid - 1;
}
return left;//最后返回的是target第一次出现的索引，也等于right+1
//也适用于target不存在的情况，只要记住循环不变量就行
//就比如lower_bound(nums, 0);能返回第一个0的索引
//lower_bound(nums,1);若1不存在能返回第一个大于0的索引

  • lower_bound(nums.begin(),nums.(end),target)，升序，找到第一个>=target 的值的元素，并返回该元素的迭代器

  • lower_bound( begin , end , val , less<type>() )升序，找到第一个>=target 的元素，与上面不写的升序功能相同,官方的自定义比较函数

  • lower_bound( begin , end , val , greater<type>() )降序，找到第一个<=target 的元素

  • 返回的值是迭代器，若要获取索引，需要用- begin

  • ranges::lower_bound(nums2.begin(),nums2.end(), nums1[i], ranges::greater{}) - nums2.begin();//减去开始获取索引

  • upper_bound()也是升序，但是是找到第一个>target 的元素

    4 寻找两个正序数组的中位数

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
class Solution {
public:
    // 真是难题，我用灵神的双指针法先做一遍
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // 约定nums1是哪个小数组，方便操作
        if (nums1.size() > nums2.size()) {
            swap(nums1, nums2);
        }
        // 交换之后获取长度
        int n1 = nums1.size();
        int n2 = nums2.size();
        // 两头插入无穷边界，用来避免越界和保证有结果
        nums1.insert(nums1.begin(), INT_MIN);
        nums2.insert(nums2.begin(), INT_MIN);
        nums1.push_back(INT_MAX);
        nums2.push_back(INT_MAX);

        // 中位数（包含中位数）的左边为第一组，右边为第二组
        // 如果nums1有i个数在第一组，那nums2应该有(n1 + n2 + 1)/2 - i = j个数在第一组
        // 偶数是（n1 + n2)/2 和奇数加一那种可以合并，因为偶数加一也会被截断，不影响
        // 二分的边界应该用1组的范围加负无穷，同时因为头部插入了负无穷所以right不用减一了
        int left = 0;
        int right = n1;
        // 既然知道了要找的边界，i和j又换算关系，那就能用二分去找这个边界
        // 用1组找对应的i和j+1，因为是刚好的，那另一组就不用看了
        while (left <= right) {
            int mid = left + (right - left) / 2;// 先减再加可以防止整型溢出
            // i和j作为临时变量，方便理解
            int i = mid;
            int j = (n1 + n2 + 1)/2 - i;// 用i换算成j就可以找组2里对应数字了
            if (nums1[i] <= nums2[j + 1]) {// 找到刚满足的那个边界
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 最后的right就应该是暴力做法里的i
        int i = right;
        int j = (n1 + n2 + 1)/2 - i;
        // 第一组的最大值
        int first = max(nums1[i], nums2[j]);
        // 第二组的最小值
        int second = min(nums1[i + 1], nums2[j + 1]);
        return (n1 + n2)%2 ? first : (first + second)/2.0;
    }
};

前缀和

s[i]就是前 i 个元素的和
适合求区间和，无论是否有序

1
2
3
4
5
6
7
// 建立前缀和数组
vector<int> s;
s.resize(nums.size() + 1);// 常用resize(n + 1)
for (int i = 0; i < nums.size(); i++) {
    // 第一位就是0，计算[left, right]区间的和就是s[right + 1] - s[left]
    s[i + 1] = s[i] + nums[i];
}

找所有和为 k 的子串

1
2
3
4
5
6
7
for (int i = 0 ; i < pre.size(); i++) {// i是正在遍历的数组，j是要查的
    // 等式变换pre[i] - pre[j] = k; pre[j] = pre[i] - k;
    auto it = map.find(pre[i] - k);// find返回迭代器
    if (it != nullptr) ans += it -> second;
    // 用元素当key，频率当value
    map[pre[i]]++;
}

链表 List

翻转链表

1
2
3
4
5
6
7
8
9
10
ListNode* reverseList(ListNode* node) {
        ListNode* pre = nullptr, *cur = node;
        while (cur != nullptr) {
            ListNode* nxt = cur -> next;// nxt每次重新赋值
            cur -> next = pre;// 一次只改一个next指向
            pre = cur;// 注意顺序，先把cur赋出去，再覆盖cur
            cur = nxt;
        }
        return pre;// 最后返回新链表的头结点
    }

快慢指针法，查看是否存在环型链表

1
2
3
4
5
6
7
8
9
10
11
12
bool hasCycle(ListNode *head) {
    // 定义快慢指针
    ListNode* fast = head, *slow = head;
    // 省略 != nullptr
    while (fast && fast -> next) {
        // 快指针每次走两步，慢指针每次走一步
        slow = slow -> next;
        fast = fast -> next -> next;
        if (fast == slow) return true;// 有环的会一直打转直到相遇
    }
    return false;
}

快慢指针法，找中间节点

1
2
3
4
5
6
7
8
ListNode* middleNode(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast != nullptr && fast -> next != nullptr) {
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    return slow;// 奇数返回中间，偶数返回中间右侧第一个
}

虚拟头结点，头插法，合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0); // 虚拟头节点
    ListNode* tail = &dummy;
    // 直到走空一个链表为止
    while (list1 != nullptr && list2 != nullptr) {
        if (list1 -> val <= list2 -> val) {
            // 比较此时两个链表谁的val大
            tail -> next = list1;
            // 然后链表走一步继续比较
            list1 = list1 -> next;
        }
        else {
            tail -> next = list2;
            list2 = list2 -> next;
        }
        // 上面确定了tail的next，这里走一步到最新节点
        tail = tail -> next;
    }
    // 因为是有序的，所以后面的直连接第一个节点就行，谁存在就连接谁
    tail -> next = list1 ? list1 : list2;
    return dummy.next;
}

二叉树

深度优先搜索(DFS)，用递归或者栈实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 递归中序遍历
void Recursion(TreeNode* root, vector<int> &ans) {
    if (root == nullptr) return;// 终止条件
    Recursion(root->left, ans);// 记得把数组地址传进去
    ans.push_back(root->val);
    Recursion(root->right, ans);
}
// 栈中序遍历，一句话的核心思想：一路向左，走到头；弹出处理，转右再走左。
stack<TreeNode*> stk;
// 只要存在结点或者栈不空就进行，直到结点和栈都空
while (root != nullptr || !stk.empty()) {
    // 先把结点左子树全压进去
    while (root != nullptr) {
        stk.push(root);
        root = root->left;
    }
    // 出来之后的root是空，先把栈里最先结点赋回去
    // 每次while循环都会取出最新的结点
    root = stk.top();
    // 当前结点不存在左子树，把值放进数组，进行中序遍历
    ans.push_back(stk.top()->val);
    stk.pop();
    // 最后root再更新成右子树
    root = root->right;
}

广度优先搜索(BFS)，用队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// BFS广度优先遍历，用队列来打成，先进后出
// 用队列存储指针
queue<TreeNode*> queue;
// 二维向量存储结果
vector<vector<int>> res;
queue.push(root);
while (!queue.empty()) {
    // 构建一行
    vector<int> vals;
    // 每次把上一轮存进来的子节点都遍历完
    for(int n = queue.size(); n > 0; n--) {
        // 获取当前结点
        TreeNode* node = queue.front();
        // 把当前结点的左右子树推进队列
        if (node->left) queue.push(node->left);
        if (node->right) queue.push(node->right);
        // 把结点的值放入向量
        vals.push_back(node->val);
        // 弹出尾结点
        queue.pop();
    }
    // 把构建的一行放入答案
    res.emplace_back(vals);
}
return res;

递归

把原问题化解成一个个和相似的子问题，然后确定好递归的终止条件

数组转换为平衡二叉树

1
2
3
4
5
6
7
8
9
10
11
// 把 nums[left] 到 nums[right-1] 转成平衡二叉搜索树
TreeNode* dfs(vector<int>& nums, int left, int right) {
    if (left == right) return nullptr;
    int m = (left + right) / 2;
    TreeNode* node = new TreeNode(nums[m]);
    node->left = dfs(nums, left, m);
    node->right = dfs(nums, m+1 , right);
    return node;
    // 也可以直接用构造函数写返回值，第一个参数是val，第二个是左子树，第二个是右子树
    // return new TreeNode(m, dfs(nums, left, m), dfs(nums, m+1, right))
}

二叉搜索树，左子树严格小于根节点，右子树严格大于根节点
中序遍历就是升序

回溯

用递归实现

全排列问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 全排列每个数字只能出现一次，所以下一轮应去掉当前选择的数
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;// 建立ans用来存答案
        int n = nums.size();// 获取长度用来设置递归次数
        vector<int> vec(n), select(n);// 存储每个结果，和每一轮能选的数

        // 递归，i代表当前排序结果的索引索引，所以i等于n的时候就终止了
        auto dfs = [&](this auto&& dfs, int i) -> void {
            if (i == n) {位数到n的时候停止
                ans.emplace_back(vec);// 放进全排列的结果
                return;// 终止递归
            }
            // for循环遍历每个数字
            for (int j = 0; j < n; j++) {
                if (select[j] == 0) {// 如果当前的数字为0就可选，不为0就跳过
                    vec[i] = nums[j];// 把数字数字放进数组，同位的直接覆盖就行
                    // 用select来标记能选的数，因为vector初始化值为0，所以约定0为可选，1为不能
                    select[j] = 1;// 给下次遍历做标记，当前的数字不可选
                    dfs(i + 1);// 选择下一位的数字
                    select[j] = 0;// 因为是深度遍历，所以最后恢复现场就能把所有结果遍历出
                }
            }
            // void函数会在执行完最后一条语句后自动返回，可以不用在末尾显示的写return;
            // 但if里面的是必须的，用来终止递归
            // return;
        };
        dfs(0);// 开始遍历
        return ans;
    }
};

问：什么时候需要写恢复现场，什么时候不需要写？

答：下面代码中，如果初始化 path 为空列表，就需要写恢复现场。本题由于所有括号长度都是固定的 2n，我们可以创建一个长为 2n 的 path 列表，在递归时直接写入字符（而不是插入字符），这样做无需写恢复现场。

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
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        string path;
                                        // 左右括号数量
        auto dfs = [&](this auto&& dfs, int l, int r) {
            // 括号数量是对数二倍
            if (r == n) {
                ans.emplace_back(path);
                return;
            }
            if (l < n) {
                path.push_back('(');
                dfs(l + 1, r);// 每个dfs后面都应该邻着现场恢复
                path.pop_back();
            }
            if (l > r) {
                path.push_back(')');
                dfs(l, r + 1);// 每个dfs后面都应该邻着现场恢复
                path.pop_back();
            }
            return;
        };
        dfs(0, 0);
        return ans;
    }
};

string path(2 * n, 0);
// 结果不用取子集都是填满的时候，可以一开始创建初始化好空间的path
// 然后每次直接覆盖对应索引，就不用现场恢复，开销更小
path[l + r] = '(';
dfs(l + 1, r);

79.单词搜索

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
class Solution {
public:
    // 用深度遍历，图论
    bool exist(vector<vector<char>>& board, string word) {
        bool flag = false;
        int n = word.size();
        // 新建一个标记二维向量
        vector<vector<int>> mark(board.size(), vector<int>(board[0].size(), 0));

        // 传横纵坐标                    // 索引和横纵坐标
        auto dfs = [&](this auto&& dfs, int i, int x, int y) -> void {
            // 判断坐标是否合法
            if (x<0 || y<0 || x>=board.size() || y>=board[0].size()) return;
            // 对比字符是否是目标，以及是否走过
            if (board[x][y] != word[i] || mark[x][y] == 1) return;
            // 下面就是找到了的逻辑
            // 标记走过的结点
            mark[x][y] = 1;
            if (i == n - 1) {// i是索引，所以对比的大小要减一
                flag = true;
            }
            dfs(i + 1, x + 1, y);
            dfs(i + 1, x, y + 1);
            dfs(i + 1, x - 1, y);
            dfs(i + 1, x, y - 1);
            // 到这了就说明上面都找完了，当前坐标该回溯了
            mark[x][y] = 0;// 恢复现场
        };
        // 应该一开始用嵌套for循环找最初字符，然后开始递归
        for (int x = 0; x < board.size(); x++) {
            for (int y = 0; y < board[0].size(); y++) {
                dfs(0, x, y);
            }
        }
        return flag;
    }
};

堆(优先队列)

堆(heap)是一种完全二叉树，可分为两种类型

  • 小堆顶：任意节点的值<=其子节点的值
  • 大堆顶：任意节点的值>=其子节节点的值

许多编程语言提供的是优先队列（priority queue），这是一种抽象的数据结构，
定义为具有优先级排序的队列。

完全二叉树适合用数组实现
堆的物理结构

快速查找算法

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
// 堆（优先队列）
class Solution {
    // 在子数组 [left, right] 中随机选择一个基准元素 pivot
    // 根据 pivot 重新排列子数组 [left, right]
    // 重新排列后，<= pivot 的元素都在 pivot 的左侧，>= pivot 的元素都在 pivot 的右侧
    // 返回 pivot 在重新排列后的 nums 中的下标
        // pivot 在 nums 中的下标为 i。
        // 如果 i=n−k，那么答案就是 pivot。
        // 如果 i>n−k，说明答案在 pivot 左侧，我们在其中寻找，重复第一步。
        // 如果 i<n−k，说明答案在 pivot 右侧，我们在其中寻找，重复第一步。
    // 特别地，如果子数组的所有元素都等于 pivot，我们会返回子数组的中心下标，避免退化
    int partition(vector<int>& nums, int left, int right) {
        // 在数组中随机选择一个元素
        int i = left + rand() % (right - left + 1);
        int pivot = nums[i];
        // 把pivot与子数组第一个元素交换，避免它干扰后续划分
        swap(nums[i], nums[left]);

        // 开始划分数组
        i = left + 1;
        int j = right;
        while (true) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            // 此时会卡在第一个大于的元素 nums[i] >= pivot
            while (i <= j && nums[j] > pivot) {
                j--;
            }
            // 此时会卡在第一个小于的元素 nums[i] <= pivot;

            if (i >= j) {
                break;
            }

            // 维持循环不变量
            // 交换第一个卡着的元素之后就能继续划分了
            swap(nums[i], nums[j]);
            i++;
            j--;
        }
        // 划分完之后，左侧都是小于，右侧都是大于
        // 最后交换左侧小于的最后一个元素和left的位置，把left放进正确的位置
        swap(nums[left], nums[j]);// 与j交换才是有效划分
        // 返回 pivot的下标，有点像二分，每次都会把一个元素大于和小于都分出来
        return j;
    }

public:
    // 时间复杂度是n + n/2 + n/4 ... O(n),因为每次都划分了一半
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        int left = 0;
        int right = n - 1;
        while (true) {
            int i = partition(nums, left, right);
            // 如果排完序后的pivot元素正好是第k大就直接返回
            if (i == n - k) {
                return nums[i];
            // 当前pivot比目标小就在右边继续找
            } else if (i < n - k) {
                left = i + 1;
            // 当前pivot比目标大就在左边继续找
            } else if (i > n - k) {
                right = i - 1;
            }
        }
    }
};

动态规划

动态规划（Dynamic Programming，简称 DP）是一种将复杂问题分解为多个简单子问题求解的方法。dp 数组是动态规划中常用的数据结构，用于存储子问题的解，从而避免重复计算。

力扣第 198 题 打家劫舍
一开始用回溯，从 n 开始，每次传 n-1，返回上一个子问题的答案，直到为 0 的时候碰到边界开始归
只保留归的部分，它就能 1 比 1 翻译成下面这样的 dp 数组来递推

用上一次的结果来推下一个结果，这个用于推导的式子叫状态转移方程

记忆化搜索，就是因为相同的入参会有相同的最终结果，所以用一个数组来记录，计算过的结果就直接返回，避免多余的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    // 从左到右递推的算问题，用子问题的答案来推出来下一个问题，直到递推到原问题
    int rob(vector<int>& nums) {
        // 定义一个dp数组（动态规划 dynamic programming）
        int n = nums.size();
        vector<int> dp(n + 1, 0);// 索引就代表偷到第几间，存储子问题的答案
        // 初始偷0间和1间的答案
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            // 当前的dp值要么是不偷当前这个房子，那就是上一个的dp值
            // 要么就偷这个房子，那就是当前房子的钱加上上个dp值
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);// i是房号，i-1才是索引
        }
        // 最后返回原问题的答案
        return dp.back();
    }
};

对上面进行空间优化
其实不需要数组，推到下一个问题的时候原来的 dp[i - 2]就不需要了
所以可以只用两个变量加一个临时变量来递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    // 从左到右递推的算问题，用子问题的答案来推出来下一个问题，直到递推到原问题
    int rob(vector<int>& nums) {
        int n = nums.size();
        // 初始偷0间和1间的答案
        int dp0 = 0;
        int dp1 = nums[0];
        for (int i = 2; i <= n; i++) {
            // 当前的dp值要么是不偷当前这个房子，那就是上一个的dp值
            // 要么就偷这个房子，那就是当前房子的钱加上上个dp值
            int dp_new = max(dp1, dp0 + nums[i - 1]);// i是房号，i-1才是索引
            dp0 = dp1;
            dp1 = dp_new;
        }
        return dp1;
    }
};

力扣第 279 题：完全平方数
用回溯加记忆化搜索来实现动态规划

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
// 写在外面，多个测试数据之间可以共享，减少计算量
int memo[101][10001];

auto init = [] {
    memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
    return 0;
}(); // 立即调用，把二维数组所有数初始化为-1

class Solution {
public:
    // 用递归来尝试每个数选或不选，最后保留次数最少的
    int dfs(int i, int j) {// i是要平方的数，j是当前目标
        // 递归边界解释放后面
        if (i == 0) {
            return j == 0 ? 0 : INT_MAX;
        }

        // 判断当前数是否计算过
        int& res = memo[i][j];// 用的引用，后面用这个变量就能直接记忆
        if (res != -1) {
            return res;
        }

        // 如果当前的数平方大于j，那只能不选
        if (i * i > j) {
            // i从n开始递减着算
            res = dfs(i - 1, j);
        } else {
            // 选或不选，取返回值小的
            // 选的返回值加一，然后里面从减去后的数里再选
            res = min(dfs(i - 1, j), dfs(i, j - i * i) + 1);
        }
        return res;
    }

    int numSquares(int n) {
        // 从n开平方往下减
        return dfs(sqrt(n), n);
    }
};
//递归边界：dfs(0,0)=0，因为没有数可以选了，且要得到的数等于 0，那么答案为 0。如果 j>0，那么 dfs(0,j)=∞，这里用 ∞ 表示不合法的状态，从而保证上式中的 min 取到合法的状态。注意本题是一定有解的，因为 1 是完全平方数。

力扣第 416 题：分割等和子集

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
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // 我先计算 nums 所有数的和
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        // 如果总和是奇数就直接不能分割
        if (sum % 2 == 1) {
            return false;
        }
        // 目标正数和
        int target = sum / 2;

        int n = nums.size();
        // 第一维表示前n位数中选，所以应该是n + 1
        // 第二维表示最后和为target，所以都表示实际的数，不是索引，都要加一
        vector dp(2, vector<bool>(target + 1, false));
        // dp[i][c] 语义为是否可以用前 i 个数（nums[0..i-1]）凑出和为 c
        // 所以第一维应该从0开始，代表前0个数，c为0时为true，其余的c都应该是false，因为没数
        // 然后第二行就该是第一个数的选或不选，0和c为nums[0]为true
        // 然后第三行就该用第二行来这个数的选或不选，依照上一行所有为true的c
        // 不选：上一行为true的这一行也该为true
        // 选：上一行里为true的c坐标加上nums[1]也该为true，就是上一行整体偏移一个nums[1]的量
        // 依照上面的逻辑就能递推了，
        dp[0][0] = true;
        // 第几位数字的选或不选
        for (int i = 1; i <= n; i++) {
            // 当前数 x
            int x = nums[i - 1];
            for (int c = 0; c <= target; c++) {
                // 选和不选最好同时步进，避免出现覆盖问题
                // 只要上一行此时的c为true或者c-x为true一个满足就该为true
                // 不选
                bool flag1 = dp[(i - 1)%2][c];
                bool flag2 = false;
                if (c - x >= 0) {// 避免越界
                    // 选
                    flag2 = dp[(i - 1)%2][c - x];
                }
                dp[i%2][c] = flag1 || flag2;
            }
        }
        return dp[n%2][target];
    }
};

多维动态规划

就是加了维度，然后还是一样回溯加记忆化转成递推
但是递推的时候是一行一行推的，依据上一行来推下一行
空间优化可以给第一维都 % 2，就只用两行存储，下一行覆盖上一行

不同路径

力扣第 62 题

记忆化加递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector memo(m, vector<int>(n, -1));

        auto dfs = [&](this auto&& dfs, int i, int j) -> int {
            if (i == 0 && j == 0) {
                return 1;
            }

            int& res = memo[i][j];
            if (res != -1) {
                return res;
            }

            int x = 0, y = 0;
            if (i != 0) {
                x = dfs(i - 1, j);
            }
            if (j != 0) {
                y = dfs(i, j - 1);
            }
            return res = x + y;
        };

        // 我是用索引当坐标了，所以应该减一
        return dfs(m - 1, n - 1);
    }
};

转成递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int uniquePaths(int m, int n) {
        // 改成递推，初始化成1，因为第一行和第一列都是只有一条路，然后内部就直接覆盖
        vector dp(m, vector<int>(n, 1));

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 从i,j出发的路径数应该就是他从下走和从右走的路径和
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};

递推空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int uniquePaths(int m, int n) {
        // 只用两行来递推，新第一行直接写在上一行里
        vector dp(2, vector<int>(n, 1));

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 所有行都%2
                dp[i%2][j] = dp[(i - 1)%2][j] + dp[i%2][j - 1];
            }
        }
        // 答案也%2
        return dp[(m - 1)%2][n - 1];
    }
};

最长公共子序列

力扣第 1143 题

递归一比一转换成递推

  • 第一次赋值的时候，由于没有上一组来参考，所以手动扩大 dp 数组，初始化为 0 作为参考
  • 同时也是为了避免出现负数下标，在赋值的时候就不是 i = i - 1，而是 i + 1 = i，所以 dp 数组的空间也要跟着加一
  • 所以在 DP 表中，我们把当前字符对应的状态存在 dp[i+1][j+1]

对第一次赋值的理解

  • 题是要最长公共子序列，i = 0, j = 0 时，给 dp[1][1]赋值，一开始就从取前 1 个字符的字符串 1 和前 1 个字符串 2 开始，看他们的公共子序列长度，两个字符相同就加一，本来要加上dp[0][0]上一个最长子序列，但是已经初始化 0 行 0 列都是 0，所以没影响。
  • 然后先看内部循环，i = 0, j = 1 时，还是取前 1 个字符的字符串 1 和前 2 个字符的字符串 2，看此时的text1[i] == text2[j]，也就是字符串 2 新取到的第二个字符是否串 1 的第一个字符相等，如果相等就还是加一，然后加上上一行的结果，但还是由于初始化 0，所以这里还是 0，dp 的 0 行 0 列都是 0，所以第一轮 j 直到加到 m - 1，都是 0 或 1
  • 看第内部第二次循环吧，i = 1, j = [0, m - 1], 这时候还是看是否相等，给dp[i + 1][j + 1]赋值，相等就两个串同时步进，赋成上一行dp[i][j]的结果加一，如果不相等，就是上一个字符截止的串一和上一个字符截止的串 2 中最长子序列长度dp[i + 1][j], dp[i][j + 1]中的大值，这样就得到了串 1 的前两个字符和串 2 每个长度的最长公共子序列长度，第一个匹配，第二个也匹配就是 2，然后从每个字符开始的也都记录了
  • 然后就这么逐渐填，直到填完 m 行 n 列，然后返回 dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        vector dp(n + 1, vector<int>(m + 1, 0));

        // 获取第一行第一列的时候会越界，所以把数组整体向着右下移动一位
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (text1[i] == text2[j]) {
                    // 直接给下一位赋值，这样遍历的就还是索引，不用改变语义
                    dp[i + 1][j + 1] = dp[i][j] + 1; // 都选的结果就是都不选的结果加上一
                } else {
                    dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }

        return dp[n][m];
    }
};

从两行优化到一行

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
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int n = text1.size();
        int m = text2.size();
        vector<int> dp(m + 1, 0);

        // 优化成一维数组
        for (int i = 0; i < n; i++) {
            // 存储用于下一次的左上dp
            int pre = 0;
            for (int j = 0; j < m; j++) {
                // 因为对于下一次来说的左上会在当前循环被覆盖，所以先用临时变量存起来
                int temp = dp[j + 1];
                if (text1[i] == text2[j]) {
                    dp[j + 1] = pre + 1;
                } else {
                    // 第一个j是当前遍历的，也就是左。第二个j + 1是上一行的即将被覆盖的，也就是上
                    dp[j + 1] = max(dp[j], dp[j + 1]);
                }
                // 等覆盖完再赋值回来
                pre = temp;
            }
        }
        return dp[m];
    }
};
算法
http://www.981928.xyz/2025/11/02/算法/
作者
981928
发布于
2025年11月2日
许可协议