算法刷题笔记

链表

参考答案 
1
hello
双指针法题型总结

  • 合并链表

    • 合并k个升序列表

    • 有序矩阵第k小元素：也是优先队列，不过要记录(i,j)(i, j)对，这里记一下priority_queue的用法，下面定义了一个存储vector<int>类型的堆。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq; 
      // 最小堆，默认是最大堆。模板参数含义:<Type, Composer, Comparer>

      // 也可以用自定义比较函数
      auto cmp = [](const vector<int>& a, const vector<int>& b) -> bool {
          return a[0] > b[0];  // 按照 vector 中的第一个元素升序排列
      }; 
      // 创建优先队列，使用自定义比较函数
      priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);

    • 附：自己实现二叉堆

    • 查找和最小的K对数字：两两一对想象成是有序矩阵，合并即可

    • 【★】丑数[1]

      • 参考答案

        质因子包括2,3,5，并非因子只包括质数2,3,5！
        令所有丑数的有序序列为 a1,a2,a3,...,an ，则序列中的每一个数都必然能够被以下三个序列（中的至少一个）覆盖： 由丑数 ×2 所得的有序序列：1×2、2×2、3×2、4×2、5×2、6×2、8×2 ...
        由丑数 ×3 所得的有序序列：1×3、2×3、3×3、4×3、5×3、6×3、8×3 ...
        由丑数 ×5 所得的有序序列：1×5、2×5、3×5、4×5、5×5、6×5、8×5 ...
        因此可以等价为三条链表。

      • 空间复杂度是否可以优化到O(1)O(1)？

    • 【扩展】链表相交

  • 分解链表

    • 【★】删除链表中的重复元素。关键在如何删除所有相同元素，如[1 2 3 3] → [1 2]

  • 反转链表

    • 递归方式 思想：子问题分解。reverseList(1->2->3->4) = 1->reverseList(2->3->4)，即1-> 2<-3 <- 4<-... 每次要反转“1”节点 
      1
      2
      3
      4
      5
      6
      7
      8
      ListNode* reverseListR(ListNode* head){
          // head -> pk+1<-pk+2<-...
          if(!head || !head->next) return head;
          auto newHead = reverseListR(head->next);
          head->next->next = head;
          head->next = nullptr;
          return newHead;
      }

    • 反转链表的一部分 <=> 反转链表的K个节点（注意记录反转段的后驱节点）

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      ListNode *reverseN(ListNode *head, int n){
          ListNode *cur = head, *pre = nullptr;
          while(n--){ //循环n次
              auto nxt = cur->next;
              cur->next = pre;
              pre = cur;
              cur = nxt;
          }
          head->next = cur;
          return pre;
      }
      ListNode* reverseBetween(ListNode* head, int left, int right) {
          ListNode *dummyHead = new ListNode(0);
          ListNode *pre = dummyHead; dummyHead->next = head;
          for(int i = 1; i < left; ++i) // 不要改变left!! 之前用的是left--
              pre = pre->next;
          pre->next = reverseN(pre->next, right-left+1);
          return dummyHead->next; // 不要返回head，因为head可能被反转（当left=1时）
      }

  • 删除链表

  • 【★】重排链表

  • 寻找倒数第k个节点

  • 判断环

常见报错

  • ERROR: AddressSanitizer: heap-use-after-free on address xxx
  • Line 16: Char 29: runtime error: member access within null pointer of type ‘ListNode’ (solution.cpp)

数组

  • 第k大元素

    参考答案 桶排

  • nSum模板，重点在先排序+去重

    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:
        // 15min
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> res;
            sort(nums.begin(), nums.end(), [](int a, int b){return a < b;});
            for(int i = 0; i < nums.size(); ++i){
                auto ans = twoSum(nums, -nums[i], i+1, nums.size());
                for(auto &vec: ans)
                    res.push_back({nums[i], vec[0], vec[1]});
                while(i < nums.size()-1 && nums[i] == nums[i+1])++i;
            }
            return res;
        }
        vector<vector<int>> twoSum(vector<int> &nums, int target, int left, int right){
            vector<vector<int>> ans;
            int i = left, j = right-1;
            while(i < j){
                if(nums[i] + nums[j] == target){
                    ans.push_back({nums[i], nums[j]});
                    i++, j--;
                    while(i < j && nums[i] == nums[i-1]) ++i;
                    while(i < j && nums[j] == nums[j+1]) --j;
                }else if(nums[i] + nums[j] < target){
                    i++;
                }else{
                    j--;
                }
            }
            return ans;
        }
    };

常见报错

  • Line 1122: Char 34: runtime error: addition of unsigned offset to 0x502000000170 overflowed to 0x50200000016c (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/lib/gcc/x86_64-linux-gnu/14/…/…/…/…/include/c++/14/bits/stl_vector.h:1131:34：vector越界

双指针

  • 去除有序数组中的重复元素
1
2
3
4
5
6
7
8
int fast = 0, slow = 0;
while (fast < nums.size()) {
	if (nums[fast] != nums[slow]) {
        slow++;
    	nums[slow] = nums[fast];
     }
     fast++;
}
  • 移除数组中等于指定值的元素
1
2
3
4
5
6
7
8
int fast = 0, slow = 0;
while (fast < nums.size()) {
	if (nums[fast] != val) {
		nums[slow] = nums[fast]; //slow 代表结束位置的下一个位置
		slow++;
	}
	fast++;
}

以上两题都是用快慢指针法，但逻辑有细微区别。去重是先slow再赋值，而去除指定值是先赋值再slow。是因为前者我们要用到slow，因此slow标志的是结束位置，为了不覆盖，就得先加；而后者标志的是结束位置的下一个位置。

但其实前者也可以换同样的写法：如果我们想slow标注的是结束位置的下一个位置，那就用slow-1来访问结束位置。现在就可以先赋值再自增了。这样slow就得从1开始，于是fast也从1开始。

1
2
3
4
5
6
7
8
int fast = 1, slow = 1;
while (fast < nums.size()) {
	if (nums[fast] != nums[slow-1]) {
		nums[slow] = nums[fast];
		slow++;
	}
	fast++;
}

此外上面的写法第3行也可以改成if (nums[fast] != nums[fast-1])，因为slow是结束位置的下一个位置，因此指向下一个（还未去重）的数字，而fast也指向还未去重的数字，因此nums[fast-1]和nums[slow-1]其实相等。

而反过来，移除元素很难改成去除重复元素的写法，这是因为移除元素中，数组的第0个元素可能会被移除，这样slow和fast初始必须指向第0个元素，我们就不能用slow-1。

排序

排序都用左闭右闭区间，好控制。

快排模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// partition 函数，进行元素的划分
int partition(vector<int>& nums, int lo, int hi) {
    int pivot = nums[lo];  // 选择 nums[lo] 作为 pivot
    int i = lo + 1, j = hi;
    while (true) {
        while (i <= j && nums[i] <= pivot) i++;
        while (i <= j && nums[j] > pivot) j--;
        if (i >= j) break;
        swap(nums[i], nums[j]);
    }
    // 将 pivot 放到正确的位置
    swap(nums[lo], nums[j]);
    return j;  // 返回 pivot 的正确位置
}

// 快速排序函数
void quickSort(vector<int>& nums, int lo, int hi) {
    if (lo < hi) {
        int p = partition(nums, lo, hi);  // 获取 pivot 的位置
        quickSort(nums, lo, p - 1);
        quickSort(nums, p + 1, hi);
    }
}

非递归快排：用栈模拟递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void quickSort(vector<int>& nums, int lo, int hi) {
    // 使用栈来模拟递归调用
    stack<pair<int, int>> s;
    s.push({lo, hi});
    
    while (!s.empty()) {
        auto [low, high] = s.top(); // 注意语法
        s.pop();

        if (low < high) {
            // 获取分区点
            int p = partition(nums, low, high);
            // 将左侧子数组和右侧子数组的边界压入栈中
            s.push({low, p - 1});
            s.push({p + 1, high});
        }
    }
}

归并排序

二叉树

LCA：

贪心

买卖股票的最佳时机

最大区间和

暴力

暴力穷举的两种思路：【遍历】和【分解问题】，前者着眼于子节点，后者着眼于子树。而后者可以优化为动态规划。

DP

DP技巧

  • 从【分解问题】的角度考虑。即考虑：是否具有最优子结构（子问题最优=>父问题最优）。

  • 状态：能确定出子问题的量。

  • 确定之后，思考怎么由子问题转移到父问题。如打家劫舍、编辑距离。

  • 最后确定初始条件

例题讲解

子序列问题

  1. 最长公共子序列（LCS）

    • 解法。注意细节循环的i, j要从1开始。这是因为Pull形dp中，转移方程要用到dp(i-1, j-1)，而数组没有-1下标，因此dp递推下标要从1开始，这样数组才从0开始。因此我们让dp(i, j)表示的是s1, s2分别取前i, j个字符时，最长公共子序列长度（即s1[0...i-1]和s2[0...j-1]。而不是表示s1[0...i], s2[0...]

    • vector<vector<int>> dp(m+1, vector<int>(n+1, 0));二维vector的定义方法（隐含了dp的初始条件，即dp(i,0)=dp(0,j)=0,∀i,jdp(i, 0) = dp(0, j) = 0, \forall i, j。

    • 【★】字符串删除操作

    • 最小ASCII码删除

  2. 编辑距离

    • 枚举法（问题：为什么不能由短的->长的，不需要【删除】操作）
    • 解法2：LCS法

  3. 最大子数组

背包

01背包

  1. 经典01背包

    • 考虑状态为什么要如此定义

  2. 分割等和子集

    • 如何转换为背包 && 转移方程不要漏掉装不下当前数的情况！
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(int i = 1; i <= nums.size(); ++i){
        for(int j = 1; j <= sum/2; ++j){
            if(nums[i-1] > j){
        	// 这种情况不要漏掉，我之前写的j从nums[i-1]开始，这样会漏掉一些状态
                dp[i][j] = dp[i-1][j];
            }else{
                dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
            }
        }
    }
    • 【★】压缩为1D时要反向遍历！（原地更新1D数组时注意的事情）

完全背包

  1. 零钱兑换II

其它

打家劫舍

杂项

用Rand7()实现Rand10()

重要结论：(rand_X() - 1) × Y + rand_Y() ==> 可以等概率的生成[1, X * Y]范围的随机数，即实现了 rand_XY()

参考

  1. https://leetcode.cn/problems/ugly-number-ii/solutions/714340/gong-shui-san-xie-yi-ti-shuang-jie-you-x-3nvs ↩
#数据结构与算法
算法刷题笔记
https://mfqwq.cn/2025/02/21/ds-and-algorithms-md/
作者
murphyqwq
发布于
2025年2月21日
许可协议