Maxw的小站

Maxw学习记录

发表于 更新于 分类于

509. 斐波那契数

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int fib(int n) {
        if(n == 0)return 0;
        if(n == 1){
            return 1;
        }else if(n > 1 ){
            return fib(n-1)+fib(n-2);
        }
        return -1;
    }
};

70. 爬楼梯

递归超时了，得用数组算。如果用两个有效数字的数组重复计算还能再省空间 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int climbStairs(int n) {
        if(n <= 2){
            return n;
        }
        vector<int> dp(n+1, 1);
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=n;i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

746. 使用最小花费爬楼梯

重点是跟着输出的dp数组看推导过程哪里有错 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int stairs = cost.size();
        if(stairs == 1)return 0;
        if(stairs == 2)return min(cost[0], cost[1]);
        vector<int> dp(cost.size(), -1);
        dp[stairs-1] = cost[stairs-1];//back()
        dp[stairs-2] = cost[stairs-2];
        for(int i = (stairs-3); i>=0; i--){
            dp[i] = cost[i]+ min(dp[i+1], dp[i+2]);
        }
        // for(auto i: dp){
        //     cout<<i<<" ";
        // }
        return min(dp[0], dp[1]);
    }
};

发表于 更新于 分类于

56. 合并区间

错误分析

  1. 合并逻辑错误（关键问题）： 
    1
    intervals[i] = (intervals[i-1][0], intervals[i][1]); // 错误写法
    • 语法错误：使用逗号运算符 (a, b) 实际返回 b，导致区间被错误赋值为 [0, intervals[i][1]]（起始点丢失）。
    • 逻辑错误：合并时结束点未取两者最大值。正确做法：结束点应为 max(intervals[i-1][1], intervals[i][1])，否则可能丢失覆盖范围（如合并 [1,5] 和 [2,3] 会得到 [1,3] 而非 [1,5]）。
  2. 重叠条件不精确： 
    1
    if(intervals[i-1][1] >= intervals[i][0]) // 边界情况处理不当
    • 题目要求：若前区间结束点 等于 后区间起始点（如 [1,2] 和 [2,3]），应合并为 [1,3]。当前条件 >= 正确，但合并操作错误导致结果异常。
  3. 性能问题：
    • 拷贝开销：cmp 函数参数为传值（vector<int> a, b），应改为 传引用（const vector<int>& a, b）避免不必要的拷贝。
    • 额外空间：使用 incl 标记数组非必需，经典解法可优化空间复杂度。
  4. 边界处理缺失：
    • 当输入为空时，应直接返回空数组，但代码未显式处理 intervals.size() == 0 的情况（依赖 size <= 1 返回，逻辑正确但不够清晰）。

比较合并贪心解法（可以ac）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) { // 传引用
        return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        if (intervals.size() <= 1) return intervals;
        vector<bool> incl(intervals.size(), true);
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i-1][1] >= intervals[i][0]) {
                // 正确合并：起始点取前一个，结束点取两者最大值
                intervals[i][0] = intervals[i-1][0];
                intervals[i][1] = max(intervals[i-1][1], intervals[i][1]);
                incl[i-1] = false;
            }
        }
        vector<vector<int>> result;
        for (int j = 0; j < intervals.size(); j++) {
            if (incl[j]) result.push_back(intervals[j]);
        }
        return result;
    }
};

经典贪心解法思路

  1. 按起始点排序区间。
  2. 动态合并：
    • 初始化结果数组 merged。
    • 遍历每个区间：
      • 若 merged 为空 或 当前区间与 merged 最后一个区间不重叠（current[0] > merged.back()[1]），直接加入。
      • 否则，更新 merged 最后一个区间的结束点：max(merged.back()[1], current[1])。

经典贪心解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (const auto& interval : intervals) {
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            } else {
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }
        return merged;
    }
};

738.单调递增的数字

题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。 例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。 > 这一点如果想清楚了，这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢？ 从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。 这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。 那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299

处理逻辑易错

  • 当发现 digits[i-1] < digits[i] 时，代码只修改了当前低位（设为9）和当前高位（减1），但没有处理更高位的影响
    • 高位减1后可能破坏与更前高位的单调性（例：100 的处理）
    • 未将所有受影响低位置为 9（例：100 的个位未置9）
  • 示例验证（输入 n=100）： 分解 digits = [0, 0, 1] # 个位=0, 十位=0, 百位=1 遍历 i=1：0==0 → 跳过 遍历 i=2：0<1 → 十位置9, 百位减1 → digits=[0,9,0] 结果 = 010⁰ + 910¹ + 0*10² = 90 # 预期应为99

数字组合计算易错

  • 错误代码：res += 10 * (i-1) * digits[i-1]
  • 问题：
    • 错误使用乘法 10*(i-1) 而非指数 10^(i-1)
    • 导致计算结果完全错误（如个位贡献 10*0*digits[0]=0）
  • 正确计算：应使用 pow(10, i-1) * digits[i-1]

💡 黄金法则：需要修改数字的每一位时，优先考虑 to_string → 字符串处理 → stoi 流程，比数学运算更直观可靠！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string str = to_string(n);
        int flag = str.size();
        for(int i = (str.size() - 1);i>0;i--){
            if(str[i-1] > str[i]){
                flag = i;
                str[i-1]--;
            }
        }
        for(int i = 0; i<str.size();i++){
            if(i >= flag){
                str[i] = '9';
            }
        }
        return stoi(str);
    }
};

968.监控二叉树

其实我的思路和题解的想法已经很接近了，但是总结地没有那么到位，导致缺漏数量的情况

确定遍历顺序

在二叉树中可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。 

1
2
3
4
5
6
7
8
int traversal(TreeNode* cur) {
    // 空节点，该节点有覆盖
    if (终止条件) return ;
    int left = traversal(cur->left);    // 左
    int right = traversal(cur->right);  // 右
    逻辑处理                            // 中
    return ;
}

返回状态类型

  • 0：该节点不在摄像头覆盖范围
  • 1：本节点有摄像头
  • 2：本节点在摄像头覆盖范围

递归的终止条件应该是遇到了空节点，此时应该返回2（有覆盖），这样就可以在叶子节点的父节点放摄像头了。 

1
2
// 空节点，该节点有覆盖
if (cur == NULL) return 2;
完整代码： 
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
class Solution {
public:
    int cmr = 0;
    int coverStat(TreeNode* root){
        if(!root)return 2;
        int left = coverStat(root->left);
        int right = coverStat(root->right);
        if(left == 2 && right == 2){
            return 0;
        }
        if(left == 0 || right == 0){
            cmr++;
            return 1;
        }
        if(left == 1 || right == 1){
            return 2;
        }
        return -1;
    }
    int minCameraCover(TreeNode* root) {
        int rcv = coverStat(root);
        if(rcv == 0)cmr++;
        return cmr;
    }
};

发表于 分类于

452. 用最少数量的箭引爆气球

💡 题解逻辑如下：

  • 如果当前气球的 起点 > 上一个交集的最右端点，说明它不能和之前的箭共用，需要再发一支箭。
    • 更新 end 为当前气球的 end，建立新的交集窗口。
  • 否则，当前气球和前面的箭是重叠的，它们能一起被射中。
    • 更新 end = min(end, points[i][1]) 是为了缩小交集范围，因为未来能共用这支箭的气球，必须跟所有已合并气球都有交集。 
      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:
          static bool cmp(vector<int> a, vector<int> b){
              return a[0] < b[0];
              
          }
          int findMinArrowShots(vector<vector<int>>& points) {
              sort(points.begin(), points.end(), cmp);
              int arr = 1;
              if(points.size() == 0)return 0;
              int end = points[0][1];
              for(int i = 1; i<points.size();i++){
                  if(end < points[i][0]){
                      end = points[i][1];
                      arr++;
                  }else{
                      end = min(end, points[i][1]);
                  }
              }
              return arr;
          }
      };

435. 无重叠区间

思路步骤：

  1. 排序区间（预处理）：
    • 使用自定义比较器 cmp 对所有区间进行排序。
    • 排序规则：按起始点升序（优先比较 intervals[i][0]）。若起始点相同，则按结束点升序（比较 intervals[i][1]）。
    • 按结束点排序效率可以更高
  2. 初始化关键变量：
    • 最大不重叠区间计数器 intv = 1（至少包含第一个区间）。
    • 当前覆盖的结束点 end = intervals[0][1]（以第一个区间的结束点作为初始基准）。
  3. 遍历处理每个区间（从第二个区间开始，即 i = 1）：
    • 检查重叠：比较当前区间起始点 intervals[i][0] 与当前结束点 end。
      • 情况1：有重叠（intervals[i][0] < end）：
        • 更新 end = min(end, intervals[i][1])（关键贪心选择：取最小结束点）。
        • 不增加计数器 intv（因为重叠区间不能同时保留，这里隐含选择了结束点更小的区间以正确计算无重叠区间个数）。
      • 情况2：无重叠（intervals[i][0] >= end）：
        • 更新 end = intervals[i][1]（将结束点设为当前区间的结束点）。
        • 增加计数器 intv++（表示成功添加一个新的不重叠区间）。
  4. 计算结果：
    • 需要移除的最小区间数 = 总区间数 intervals.size() - 最大不重叠区间数 intv。
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:
    static bool cmp(vector<int> a, vector<int>b){
        if(a[0] < b[0]){
            return true;
        }else if(a[0] == b[0] && a[1] < b[1]){
            return true;
        }
        return false;
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        // for(auto i: intervals){
        //     cout<<i[0]<<" "<<i[1]<<", ";
        // }
        int intv = 1;
        int end = intervals[0][1];
        if(intervals.size() <= 1)return 0;
        for(int i = 1; i< intervals.size();i++){
            if(intervals[i][0] < end){
                end = min(end, intervals[i][1]);
            }else{
                end = intervals[i][1];
                intv++;
            }
        }
        return intervals.size() - intv;
    }
};

763.划分字母区间

由题解： 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。 可以分为如下两步：

  • 统计每一个字符最后出现的位置
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27] = {0};
        for(int i = 0;i<s.size();i++){
            hash[s[i] - 'a'] = i;
        }
        vector<int> result;
        int right = 0;
        int end = 0;
        for(int i = 0;i<s.size();i++){
            right = max(right, hash[s[i] - 'a']);
            if(right == i){
                result.push_back(right - end +1);
                right++;
                end = right;
            }
        }
        return result;
    }
};

发表于 更新于 分类于

134. 加油站

初始思路：

  1. 先找一段正收益连续区间（油量盈余最大的起点）
    • 用 curMax 累加正收益段，记录最大盈余时的起点 maxSt。
    • 如果遇到油不够的站点，就重置 curMax 并将 start 改为下一个站点。
    • 如果到最后一站没找完，循环一圈回来继续查找。
  2. 再从 maxSt 模拟绕一圈
    • 从 maxSt 出发，逐站加减油量，确认是否能绕完整圈。
    • 只要中途油量不足就返回 -1。

⚠️ 存在的问题：

其实这种逻辑完善完善也是可以做出来的，题解中有，就是比较繁琐

✅ 更优的做法（贪心 + 一次遍历）：

只要 总油量 ≥ 总花费，一定有解。解的起点是：当前累加油量一旦为负，就从下一个站点重启。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tank = 0;
        int startInd = 0;
        int total = 0;
        for(int i = 0; i < gas.size(); i++){
            int store = gas[i] - cost[i];
            total += store;
            tank += store;
            if(tank < 0){
                startInd = i + 1;
                tank = 0;
            }
        }
        return total < 0 ? -1 : startInd;
    }
};

135. 分发糖果

这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。 题解采用了两次贪心的策略： * 一次是从左到右遍历，只比较右边孩子评分比左边大的情况。 * 一次是从右到左遍历，只比较左边孩子评分比右边大的情况。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int candy(vector<int>& ratings) {
        vector<int> candy;
        candy.push_back(1);
        for(int i = 1;i<ratings.size();i++){
            if(ratings[i] > ratings[i-1]){
                candy.push_back(candy[i-1] + 1);
            }else{
                candy.push_back(1);
            }
        }
        int total = 0;
        for(int i = (ratings.size()-1); i>0;i--){
            if(ratings[i-1] > ratings[i] && candy[i-1] <= candy[i]){
                candy[i-1] = candy[i] + 1;
            }
            total += candy[i];
        }
        total += candy[0];
        return total;
    }
};

860.柠檬水找零

这题不用map,用两个整数表示5和10的钞票数也是可以的 

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
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        map<int, int> changes;
        changes[5] = 0;
        changes[10] = 0;
        for(int i = 0; i<bills.size();i++){
            int exc = bills[i] - 5;
            if(exc == 0){
                changes[5]++;
            }else if(exc == 5){
                changes[5]--;
                changes[10]++;
            }else if(exc == 15){
                if(changes[10] >= 1){
                    changes[10]--;
                    changes[5]--;
                }else{
                    changes[5] -= 3;
                }
            }
            if(changes[5] < 0)return false;
        }
        return true;
    }
};

406.根据身高重建队列

看题解可知，当身高是按照从高到矮，第二个数字从小到大排列的时候，按顺序插入即可满足条件 

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
class Solution {
public:
    static bool cmp(const vector<int> a, const vector<int> b){
        if(a[0] > b[0]){
            return true;
        }else if(a[0] == b[0] && a[1] < b[1]){
            return true;
        }
        return false;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que;
        for(int i = 0; i<people.size();i++){
            int insPos = people[i][1];
            std::list<vector<int>>::iterator p = que.begin();
            while(insPos > 0){
                p++;
                insPos--;
            }
            que.insert(p, people[i]);
        }
        return vector<vector<int>>(que.begin(), que.end());
    }
};

发表于 更新于 分类于

122.买卖股票的最佳时机II

和之前的贪心算法题目一样，注意到局部最佳和整体的关系 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int prof = 0;
        for(int i = 0; i < prices.size(); i++){
            if(i > 0){
                int left = prices[i] - prices[i-1];
                if(left > 0)prof += left;
            }
        }
        return prof;
    }
};

55. 跳跃游戏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxi = 0;
        for(int i = 0;i<nums.size();i++){
            if(i < nums.size()-1 && nums[i] == 0 && maxi <= i)return false;
            int fari = i + nums[i];
            maxi = max(maxi, fari);
        }
        if(maxi >= nums.size() - 1){
            return true;
        }else{
            return false;
        }
    }
};

45.跳跃游戏II

最开始的思路：

  • 定义了一个 minJumps 数组，其中 minJumps[i] 表示到达位置 i 所需的最少跳跃次数。
  • 初始用 minJumps[i] = i，默认每一步都跳一步。
  • 然后你从前向后遍历每个位置 i，对于它可以跳到的最远位置 reach = i + nums[i]，尝试用 minJumps[i] + 1 来更新 minJumps[reach]。
  • 最后返回的是 minJumps[n - 1]。

❌ 问题和可改进点：

  1. 只更新了 reach，没更新从 i+1 到 reach 的所有中间位置：
    • 你只更新了 minJumps[reach]，但跳到 [i+1, reach] 的每一个点其实都可能是通过 i 达到的，因此都可能能更新为 minJumps[i] + 1。
  2. 时间复杂度仍是 O(n^2) 的最坏情况：
    • 因为如果要更新 [i+1, reach] 中的所有点需要嵌套循环。

✅ 题解思路遍历过程：

每次跳跃的起点在哪里不重要，关键是这次最远跳跃是否可以次数内完成 * 对每个位置 i，更新 far = max(far, i + nums[i])，表示当前范围内下一跳能跳到的最远位置。 * 当遍历到边界 i == beg 时，说明当前跳跃结束，需要再跳一次，并更新新的边界 beg = far。 * 如果新的 beg 已经到达或超过数组末尾，则可以提前 break。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int jump(vector<int>& nums) {
        int minJump = 0;
        int beg = 0;
        int far = 0;
        if(nums.size() == 1)return 0;
        for(int i = 0; i<nums.size();i++){
            far = max(far, i + nums[i]);
            if(i == beg){
                minJump++;
                beg = far;
                if(beg >= nums.size()-1)break;
            }
        }
        return minJump;
    }
};

1005.K次取反后最大化的数组和

最开始的思路

用了一个递归函数 lsum(nums, k) 来处理问题，思路如下： 1. 遍历数组找出最小值 minN 及其下标 minI； 2. 将 nums[minI] 取反（也就是对当前最小值执行一次取反操作）； 3. 继续递归调用 lsum(nums, k - 1)； 4. 递归终止条件：k == 0，此时返回整个数组的和； 5. 优化点尝试：当数组中最小值已经 ≥ 0，尝试用 k % 2 代替多余的取反操作（只取反一次或不取反）以减少递归次数。

❌ 当前实现存在的问题：

  1. 每次递归都重新遍历整个数组，效率低：
    • 时间复杂度接近 O(k * n)，最坏情况下可能是 10^5 * 10^3，会超时。
  2. 递归开销大：
    • 每次递归都复制 nums 数组（因为是传引用再递归），可能带来严重的性能瓶颈。
  3. 贪心策略不够高效：

✅ 推荐的优化思路：

采用排序 + 贪心策略来完成任务，流程如下： 1. 先将数组按绝对值从大到小排序； 2. 从左到右遍历数组，把负数取反，直到 k 用完或者没有负数了； 3. 如果还有剩余的 k 且是奇数，说明还有一次取反机会，把当前最小值（绝对值最小的数）再取反一次； 4. 最后返回数组的总和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), [](int a, int b){return abs(a) > abs(b);});
        for(int i = 0; i<nums.size(); i++){
            if(k == 0)break;
            if(nums[i] < 0){
                nums[i] = 0 - nums[i];
                k--;
            }
        }
        if(k % 2 == 1)nums[nums.size()-1] = 0 - nums[nums.size()-1];
        int sum = 0;
        for(int n: nums){
            sum += n;
        }
        return sum;
    }
};

发表于 分类于

455.分发饼干

这题题解上两个思路：

  • 思路1：优先考虑饼干，小饼干先喂饱小胃口
  • 思路2：优先考虑胃口，先喂饱大胃口

我这里优先考虑饼干 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findC(vector<int>& g, vector<int>& s, int gStart, int sStart){
        int count = 0;
        if(gStart == g.size() || sStart == s.size())return count;
        for(int i = sStart; i<s.size();i++){
            if(s[i] >= g[gStart]){
                count += 1;
                count += findC(g, s, gStart+1, i+1);
                break;
            }
        }
        return count;
    }
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());
        int cnt = findC(g, s, 0, 0);
        return cnt;
    }
};

376. 摆动序列

按题解思路，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度） 这就是贪心所贪的地方，让峰值尽可能的保持峰值，然后删除单一坡度上的节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int waveCnt = 1;
        vector<bool> isPos;
        if(nums.size() == 1)return waveCnt;
        for(int i = 1; i<nums.size();i++){
            if(nums[i-1] == nums[i])continue; // 需要跳过相等的情况，不计入后面的判断条件中
            if(nums[i-1] < nums[i]){
                isPos.push_back(true);
            }else if(nums[i-1] > nums[i]){
                isPos.push_back(false);
            }
            if(i >= 1 && !isPos.empty() && isPos.size() == 1)waveCnt++;
            if(!isPos.empty() && isPos.size() >= 2){
                if(isPos[isPos.size()-1] != isPos[isPos.size()-2])waveCnt++;
            }
        }
        return waveCnt;
    }
};

53.最大子序和

由题解可以得知 如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！

  • 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素“连续和”只会越来越小。
  • 全局最优：选取最大“连续和”

区间的终止位置，其实就是如果 count 取到最大值了，及时记录下来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxCnt = nums[0];
        int cnt = 0;
        for(int i=0; i<nums.size();i++){
            cnt = cnt + nums[i];
            if(cnt > maxCnt){// 要先赋值，再判断是否小于零，不然全是负数的情况会不正确
                maxCnt = cnt;
            }
            if(cnt < 0){
                cnt = 0;
                continue;
            }
        }
        return maxCnt;
    }
};

发表于 更新于 分类于

把面试可能遇到的题目和回答存一下，面完来看看有哪些问到了

更新： 面完了，全在拷问项目，一点八股没问，凉了。迭代一下模拟面试题目

我的简历项目有四个：通用操作系统框架（Rust，研究生阶段跟着导师组里做的项目），多线程 TCP 服务器开发（Rust），基于贝叶斯优化的系统参数自动化调优框架（Python），智能菜市场物联网数据平台后端（Spring Boot，本科阶段实习的项目）

模拟面试题目：

一、 自我介绍与简历深挖

1. 请用3分钟左右的时间介绍一下你自己 (考察总结和表达能力，引导面试官关注你的亮点)

面试官您好！我是来自XX大学计算机科学专业的硕士研究生XX，非常荣幸能参加贵公司云架构平台部后台开发岗位的面试。

(背景 & 核心项目 - 1 min) 在研究生阶段，我的核心研究聚焦于构建高性能、可扩展的**操作系统框架**。我主导了其中**调度算法模块**的设计与实现。我的任务是将导师提出的新型**联合调度模型**落地到基于Rust开发的**微内核**框架中。该模型的核心是根据任务的**CPU占用**特征（高/低利用率）**动态匹配**最优调度策略（如EDF或Rate-Monotonic），以提升系统在超负荷以及**实时调度**场景下的整体效用。

为了实现并验证该模型：
充分利用**Rust的所有权机制**实现安全高效的**任务状态管理**
我设计了模块化的调度器接口，支持灵活集成和对比不同策略，并通过Linux内核工程实践（在Raspberry Pi上进行**内核模块定制**、交叉编译） 搭建了真实的测试环境。
我利用**perf**等工具采集并分析任务响应时间、CPU利用率等指标，量化验证了该联合调度模型在极端负载下的性能优势，达到了理论预期。这个项目不仅锻炼了我系统级编程（Rust）、内核原理和性能调优的能力，也让我深刻理解了高并发、实时性保障的挑战。

(其他项目经验 - 突出相关技术 - 45 sec) 除了研究项目，我也积极将技术应用于实践：
我独立设计并开发了一个高性能多线程TCP服务器（Rust）。采用Reactor模式和**非阻塞I/O**处理并发连接，精心设计了**线程安全的任务队列**和共享数据模型，降低了系统调度开销。通过优化，服务器在压力测试下峰值处理能力达到300+请求/秒，并保持了99.9%的运行时间可靠性。这强化了我对网络编程、并发控制和系统稳定性的理解。

在XX公司实习期间，我参与了智能菜市场物联网数据平台后端（Spring Boot/Java） 的开发。针对日均5000+设备数据的高并发接入场景，我参与了**分库分表方案设计**，并通过优化复杂查询（使用联合索引）降低关键接口耗时。我还负责了服务的Docker容器化部署，实现了资源的有效利用和快速扩容。这让我熟悉了企业级Java开发、数据库性能优化（MySQL/MyBatis）和容器化技术。

(技能总结 & 匹配岗位 - 30 sec) 通过这些经历，我熟练掌握**C++、Python**，并具备扎实的**Rust系统级开发**经验；深入理解操作系统、网络、并发编程原理；在分布式系统设计（分库分表）、高并发优化等方面有实际项目积累；并具备良好的问题定位和解决能力。

(结尾 - 表达热情与匹配 - 15 sec) 我了解到贵部门专注于**构建和优化云平台**的核心服务与基础设施，这正是我的兴趣所在。我的系统底层经验、性能优化意识、对分布式和云原生技术的热情，以及扎实的后端开发技能，都与这个岗位高度契合。我非常渴望能加入团队，贡献我的力量，并持续学习成长。谢谢

2. 通用操作系统框架（Rust）：

*   你提到“**使用联合调度模型，为不同资源占用的任务匹配调度方式**”。能具体解释一下这个模型的设计思路吗？如何定义“不同资源占用”？调度策略具体有哪些？如何“匹配”？
*   “**Rust异步I/O机制优化任务处理速度，减少20%-40%系统调用开销**”：请详细说明你是如何使用Rust异步I/O（比如`async/await` + `tokio`/`async-std`）来实现优化的？具体减少了哪些类型的系统调用？如何测量和验证这个20-40%的提升？
*   “**实现调度策略对比测试...完成内核恐慌日志分析与修复**”：你测试了哪些调度策略？对比的指标是什么？遇到了什么样的内核恐慌（Kernel Panic）？你是如何定位和修复的？请描述调试过程。
*   这个框架的“**适应性**”和“**扩展性**”具体体现在哪些方面？架构上是如何设计的？
*   为什么选择Rust而不是C/C++来做这个项目？Rust在系统编程中的优势（所有权、生命周期、无畏并发）在你的项目中是如何体现的？

1. 多线程 TCP 服务器开发（Rust）：

*   “**采用Reactor模式实现非阻塞I/O**”：请解释一下你实现的Reactor模式的核心组件（Reactor, Demultiplexer, Event Handlers）是如何工作的？你使用了哪个库（如`mio`, `tokio`）？
*   “**设计线程安全的任务队列和数据共享**”：你具体采用了什么机制来保证线程安全？（如`Arc<Mutex<T>>`, `Arc<RwLock<T>>`, `crossbeam-channel`, `tokio::sync::mpsc`等）选择它们的理由？有没有考虑无锁队列？
*   “**峰值处理能力达300+请求/秒**”：这个测试是在什么环境下进行的（硬件配置、并发客户端数、请求类型/大小）？瓶颈主要在哪里？CPU、内存、网络I/O？
*   “**解决竞争条件**”：你遇到了什么样的竞争条件？是如何发现（如死锁、数据错乱）和解决的？
*   “**分层架构实现模块解耦**”：具体分成了哪几层？层与层之间如何通信？这样设计的好处？
*   如何确保“**99.9% 运行时间**”（高可用）？做了哪些容错或恢复机制？
  1. 基于贝叶斯优化的系统参数自动化调优框架（Python）：
    • 这个框架是用来优化什么系统的参数？目标性能指标是什么？（如延迟、吞吐量、资源利用率）
    • “提高贝叶斯优化的超参数搜索效率”：你具体采用了什么技术或策略来提高效率？（如代理模型选择、采集函数优化、并行化、热启动等）
    • “数据变换和核函数优化，使 BIC 评分优化30%”：具体做了哪些数据变换？优化了哪个贝叶斯优化模型的核函数？为什么这些优化能提升BIC评分？BIC评分在这里代表什么？
    • 对比贝叶斯优化和随机搜索，在学习曲线和均值差距上具体有哪些显著差异？说明了什么问题？
  2. 智能菜市场物联网数据平台后端（Spring Boot）：
    • “针对高并发数据接入场景（日均5000+条设备数据）...采用分库分表策略”：日均5000+条数据并不算特别大，当时为什么决定采用分库分表？是基于对未来增长的预估吗？具体如何设计分片键（Sharding Key）？采用了什么分库分表中间件（如ShardingSphere）还是自研？
    • “通过联合索引将查询耗时从300-400ms降低至80-150ms”：请描述这个慢查询的具体场景（SQL语句片段、表结构、数据量）？你创建的联合索引是哪些字段？为什么这个索引有效？（结合最左前缀原则、覆盖索引等解释）
    • “设计模块化分层架构（Controller-Service-DAO）”：在“设备管理、数据管理、告警处理等模块”的抽象过程中，如何保证模块间的边界清晰？有没有使用到设计模式（如工厂模式、策略模式）？
    • “Docker容器化部署...单节点资源占用减少30%”：相比传统部署方式，容器化是如何实现资源占用减少的？（资源隔离、更轻量级、避免环境差异等）有使用编排工具（如K8s）吗？
    • 作为实习生，你在整个项目中承担的具体职责和贡献的比例大概是多少？遇到的最大的挑战是什么？

二、 核心技术基础 (重点考察“必须具备的”和“加分项”)

  1. 编程语言：
    • C++： 你熟悉到什么程度？了解RAII、智能指针、移动语义、多态、模板元编程吗？能简单举例说明。
    • Rust： 所有权和生命周期机制的核心思想是什么？它们如何帮助解决内存安全和数据竞争问题？Send和Sync trait的作用？你在项目中遇到的最典型的借用检查器挑战是什么，如何解决的？
    • Java： Spring Boot的核心优势是什么？IoC和AOP是如何工作的？你了解的垃圾回收算法有哪些？（如G1, CMS, ZGC的特点）
    • Python： 主要用在什么地方？（脚本、数据分析、框架）了解GIL吗？对多线程编程有什么影响？
  2. 网络：
    • TCP和UDP的核心区别是什么？各自适用于什么场景？
    • 详细描述TCP三次握手和四次挥手的过程。为什么需要三次握手？TIME_WAIT状态的作用是什么？
    • 什么是TCP粘包/拆包？常见的解决方案有哪些？（如消息头包含长度、特定分隔符）
    • 在Rust TCP服务器项目中，如何处理大量并发连接？（Reactor/Proactor, 线程池）
    • HTTP协议是基于TCP还是UDP？HTTP/1.1, HTTP/2, HTTP/3的主要区别？
    • 了解常见的RPC框架（如gRPC, Thrift）吗？它们解决了什么问题？
  3. 操作系统：
    • 进程和线程的区别？协程（Coroutine）呢？Rust的async/await底层可以看作协程吗？
    • 进程间通信（IPC）有哪些方式？（管道、消息队列、共享内存、信号量、Socket）各有什么优缺点？你在项目中用过哪些？
    • 线程同步机制有哪些？（互斥锁、读写锁、条件变量、信号量、原子操作）解释死锁及其必要条件、预防/避免方法。
    • 虚拟内存是什么？有什么作用？（内存管理、内存保护、内存共享）
    • 系统调用（System Call）是什么？用户态和内核态切换的代价是什么？为什么Rust异步I/O能减少系统调用开销？（批处理、用户态调度）
    • 你理解的“微内核”架构和“宏内核”（如Linux）的主要区别是什么？各自的优缺点？
  4. 数据结构与算法：
    • 数组和链表的区别？各自的适用场景？
    • 哈希表（Hash Table）的原理是什么？如何解决哈希冲突？（开放寻址法、链地址法）影响哈希表性能的关键因素？
    • 常见的树结构有哪些？（二叉树、二叉搜索树、平衡二叉树如AVL/红黑树、B树/B+树）MySQL索引通常用什么结构？（B+树）为什么？
    • 描述快速排序（QuickSort）的思想和平均/最坏时间复杂度。如何优化最坏情况？
    • 写一个简单的算法题（面试官现场出题，可能涉及数组、字符串、链表、树、二分查找、简单DP等）。
  5. 数据库：
    • 数据库事务的ACID特性是什么？
    • MySQL的InnoDB存储引擎有哪些特性？（事务、行锁、MVCC）
    • 数据库索引的作用？什么情况下索引会失效？（如对索引列进行函数操作、使用!=或NOT IN、未满足最左前缀原则等）
    • 解释一下MVCC（多版本并发控制）是如何工作的？
    • 数据库锁有哪些类型？（共享锁、排他锁、意向锁）什么是死锁？如何避免？
    • 分库分表是为了解决什么问题？（水平扩展、性能瓶颈）会带来哪些挑战？（分布式事务、跨库查询、全局唯一ID）
    • NoSQL数据库（如Redis, MongoDB）的特点和适用场景？Redis常用数据类型及其应用场景？
  6. 软件工程 & 设计模式：
    • 你如何理解面向对象编程（OOP）的四大特性（抽象、封装、继承、多态）？
    • 了解哪些设计模式？能在你的项目经历中找到应用吗？（如Spring Boot项目中的分层架构体现了关注点分离，工厂模式可能用于创建对象，策略模式可能用于选择不同算法/策略）
    • 什么是SOLID设计原则？能简要解释每个原则吗？
    • 如何保证代码质量？（单元测试、集成测试、代码评审、静态代码分析、CI/CD）
  7. 分布式系统 & 高可用 & 云原生 (加分项重点)：
    • 解释一下CAP定理和BASE理论。
    • 什么是分布式事务？常见的解决方案有哪些？（两阶段提交2PC、三阶段提交3PC、TCC、基于消息队列的最终一致性）
    • 如何设计一个高可用（High Availability）的服务？有哪些常用手段？（冗余/集群、负载均衡、故障转移Failover、熔断、降级、限流）
    • 负载均衡有哪些常见的算法？（轮询、加权轮询、最少连接、源IP哈希）
    • 什么是服务发现？为什么在微服务架构中需要它？
    • 你提到了“系统容灾设计”，谈谈你的理解？常见的容灾方案？（同城多活、异地多活、备份与恢复）
    • “对云原生相关技术有所了解”：你理解的云原生是什么？它的关键技术包括哪些？（容器化Docker、编排Kubernetes、服务网格Istio、微服务、声明式API、不可变基础设施）你用过哪些？
    • 你在简历中提到Amazon EC2，主要用它来做什么？（部署、测试）了解其他AWS服务吗？（如S3, RDS, Lambda）

三、 系统设计与场景题 (重点考察分析和设计能力) 1. 设计一个短链接生成系统（类似TinyURL）： * 核心功能：将长URL转成短URL；访问短URL重定向到原始长URL。 * 需要考虑：高并发生成与访问、短URL的生成算法（如何保证不重复、长度短）、存储设计（用什么数据库？如何设计表？）、重定向性能（缓存？）、如何防止恶意攻击（刷接口）？ 2. 设计一个简单的消息队列： * 核心功能：生产者发送消息、消费者订阅并消费消息、消息持久化（可选）。 * 需要考虑：如何保证消息不丢失？如何保证消息顺序（如果需要）？消费者如何处理失败的消息（重试、死信队列）？如何实现多消费者？如何扩展？ 3. 你开发的Rust TCP服务器，如果流量突然增长10倍（3000+ req/s），可能遇到哪些瓶颈？你会如何优化？ (结合你的项目经验) 4. 智能菜市场平台的后端，如果数据库写入成为瓶颈（比如大量设备同时上报数据），除了分库分表，还有哪些优化思路？ (如消息队列削峰填谷、批量写入、优化数据库配置、使用更快的存储硬件/SSD、考虑时序数据库TSDB)

四、 问题排查与性能优化 (考察实战能力) 1. 线上服务突然响应变慢，甚至部分超时，你会如何一步步排查定位问题？ (思路：监控指标查看 - CPU/内存/磁盘IO/网络带宽、日志分析 - 错误/慢查询日志、链路追踪分析、数据库状态检查、代码Review最近变更、压测复现等) 2. 数据库查询变慢，如何排查和优化？ (思路：EXPLAIN分析SQL执行计划、检查索引是否有效/缺失、优化SQL语句、调整数据库配置参数、考虑读写分离、升级硬件) 3. 在Rust项目中解决内核恐慌（Kernel Panic）的经历，体现了你的问题排查能力。能再举一个你解决过的复杂线上或开发中问题的例子吗？描述现象、分析过程和最终解决方案。

模拟面试题目v2：

面试官： 微内核架构… 经典话题了。你选择微内核，核心驱动力是什么？特别是在Rust的语境下。是为了极致的安全性和可靠性，还是看中了模块化带来的灵活性？在性能损耗这个老大难问题上，你的联合调度模型具体是怎么权衡的？(直击架构选型核心动机和最大痛点 - 性能损耗，要求小明阐述设计决策的深层原因和具体解决方案)

小明： (需要清晰解释动机和调度模型的设计思路) 面试官，核心驱动力确实是安全性和模块化隔离。Rust的所有权机制和零成本抽象，让我们能在语言层面就构建更强的隔离边界，减少内核态因内存安全问题崩溃的风险。性能方面，联合调度模型是我们应对损耗的关键。它允许我们根据任务特性（CPU密集型、I/O密集型、实时性要求）动态选择调度策略，比如对实时任务用截止日期调度保证时限，对后台任务用更宽松的调度器。同时，我们严格限制进程间通信(IPC)的开销，优化消息传递路径...

面试官： (点头，但立刻追问) IPC优化… 具体点？共享内存？消息队列的序列化开销怎么控制的？另外，你提到用perf做效用边界分析。超负荷场景下，你量化出的“边界”，是指系统开始拒绝服务(DoS)的临界点，还是说服务质量(SLA)开始不可接受的下滑点？这个边界对实际部署的指导意义是什么？(深入到具体实现细节和指标定义的精确性，考察工程严谨性和对业务影响的理解)

小明： (需要展示技术细节和指标定义的思考) 目前主要优化消息队列路径，减少拷贝次数，并利用Rust的零拷贝序列化库(如rkyv)降低开销。共享内存用于特定高吞吐场景，但需严格管控。关于效用边界，我们定义的是SLA开始不可接受下滑的点，比如关键任务的响应时间超过其截止期限的阈值比例。这对系统容量规划和过载保护策略的设计至关重要，比如在接近边界时启动降级或拒绝新任务。

面试官： 嗯，思路清晰。(话锋一转) 我看你还有个Rust的TCP服务器项目，用Reactor模式做到300+ QPS。这个性能数字是在什么硬件配置、并发连接数下测出来的？Reactor模式处理长连接、慢客户端时，有没有遇到线程池工作线程被阻塞的风险？你的“线程安全的任务队列”具体用了什么同步原语？Mutex? Channel? 有没有测过它们在极端争抢下的性能差异？(对性能指标要求上下文，质疑常见陷阱，深挖并发实现的底层选择及其考量)

小明： (必须明确测试环境，解释潜在风险及应对方案，展示对同步机制的理解) 测试环境是4核8G的云主机，模拟了1000个并发连接。对于慢客户端阻塞工作线程的风险，我们严格限制每个连接的处理逻辑不能有阻塞操作，所有I/O都是非阻塞的，并通过设置超时。任务队列使用的是crossbeam库的无锁队列，在Rust的async/await生态下配合tokio的mpsc channel传递任务，避免了传统Mutex在高争抢下的瓶颈。我们对比过，在极端压力下，无锁队列和channel的吞吐量和延迟显著优于Mutex保护的队列。

面试官： 不错，看来对异步和并发模型理解到位。(转向另一个领域) 你那个贝叶斯优化调参框架，BIC评分优化30%的结果很亮眼。我好奇的是，这个优化效果是在特定数据集和特定系统上取得的，还是说你验证过它的泛化能力？另外，数据变换和核函数优化是关键，你能举个具体例子说明哪种数据变换在什么场景下最有效吗？以及，你认为贝叶斯优化在哪些类型的系统参数调优场景下可能不如更简单的方法（比如网格搜索）？(质疑结果的普适性，要求具体案例分析，考察对方法适用边界的理解)

小明： (需要坦诚说明局限性，举例说明技术细节，分析优劣边界) 面试官，30%的优化是在我们目标数据库系统的特定负载下取得的。泛化能力我们通过多个不同负载profile进行了交叉验证，效果有波动但普遍正向。数据变换方面，例如对于具有指数分布特征的响应时间数据，进行对数变换(log-transform)后能显著提升高斯过程模型的拟合效果。至于贝叶斯优化的劣势，在参数维度非常高(>20维)且评估成本极低时，或者参数空间存在大量离散、非连续跳跃时，网格搜索或随机搜索可能更简单有效。贝叶斯在高维稀疏空间和代理模型不准时也可能表现不佳。

面试官： 很实在。(看向实习经历) 你实习做的那个物联网平台，用分库分表应对日均5000+数据。5000+这个量级，单库单表在MySQL上其实远没到瓶颈。当时选择分库分表是基于对未来增长的预期，还是有其他考量？你们的分片键是怎么选的？按设备ID哈希？按时间范围？如果遇到某个设备突然成为热点（比如频繁上报），产生数据倾斜（Hotspotting），你们的架构如何应对？(质疑过早优化的必要性，深挖分片策略细节及对关键风险的处理方案)

小明： (解释决策背景，展示对分片策略和风险的认识) 您说得对，5000+单表确实轻松。当时选择分库分表主要是基于两点：一是业务预期未来设备量会增长10倍以上；二是历史数据累积快，需要长期存储和快速查询。分片键我们采用的是“设备ID哈希” + “时间月份”的复合分片策略，将数据分散到多个库和表。对于热点设备，我们当时在应用层做了短时间内的限流和缓冲，但更彻底的方案需要引入读写分离、甚至对特定热点数据做缓存隔离或单独分片，这是我们当时设计考虑不足的地方，也是宝贵的经验。

面试官： (露出赞许的笑容) 很好，能认识到不足就是进步的空间。最后一个问题，跨度比较大：你既有Rust系统级开发、内核定制的经验，又有Java Spring Boot高并发微服务、DevOps的经验。在你看来，这两个技术栈（系统级 vs 云原生应用级）在解决高并发、高性能问题时，核心的哲学和工具链的差异在哪里？如果让你为一个全新的、对延迟极其敏感的交易系统做技术选型，你会更倾向于Rust还是Java（比如虚拟线程）？为什么？(考察宏观技术视野、对不同层级技术的理解深度以及技术选型的逻辑)

小明： (需要提炼核心理念差异，进行有依据的技术选型) 面试官，我觉得核心差异在于控制权和抽象层级。系统级/Rust追求极致的性能、确定性和资源控制，开发者需要深入理解硬件和OS，工具链更偏向底层（如perf, eBPF, 内核调试）。云原生/Java Spring Boot则强调开发效率、快速迭代和生态整合，通过容器化、服务网格等抽象底层复杂性，工具链围绕CI/CD、监控、治理。对于延迟极其敏感的交易系统，如果延迟要求是微秒级且需要绝对可控，我会首选Rust，因为它能提供更确定性的GC-free执行和更低的运行时开销。如果是毫秒级且业务逻辑复杂、需要快速开发，Java虚拟线程（Loom）提供了非常好的并发模型和成熟的生态，可能更合适。最终选择需要权衡延迟SLA、团队技能、开发周期和运维成本。

发表于 更新于 分类于

491.递增子序列

题解说这里用数组做哈希，效率会更高 

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:
    vector<vector<int>> result;
    void findSS(vector<int>& nums, vector<int> path, int left){
        unordered_set<int> used; // 当前层去重
        for(int i = left; i<nums.size();i++){
            if(used.find(nums[i]) != used.end())continue;
            if(path.empty()){
                path.push_back(nums[i]);
                used.insert(nums[i]);
                findSS(nums, path, i+1);
                path.pop_back();
            }else if(!path.empty() && nums[i]>=path.back()){
                // if(i>left && nums[i-1] == nums[i])continue; // 重复元素不一定相邻
                path.push_back(nums[i]);
                result.push_back(path);
                used.insert(nums[i]);
                findSS(nums, path, i+1);
                path.pop_back();
            }
        }
        return;
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        vector<int> path;
        findSS(nums, path, 0);
        return result;
    }
};

46.全排列

  1. 索引限制错误：
    • 使用 left 参数限制选择范围，导致只能生成索引递增的子序列而非全排列
    • 例如输入 [1,2,3] 时，代码只能生成 [1,2,3]，无法生成 [2,1,3] 等排列
  2. 缺少元素使用状态跟踪：
    • 排列需要从所有未使用元素中选择，而不仅仅是当前索引后的元素
    • 没有记录哪些元素已被使用，导致：
      • 无法重新选择左侧元素
      • 无法避免重复使用同一元素
  3. 递归逻辑错误：
    • 每次递归都从 i+1 开始，使得路径只能向右扩展
    • 排列需要任意顺序组合，需能回头选择左侧元素
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
class Solution {
public:
    vector<vector<int>> result;
    
    void perm(vector<int>& nums, vector<int>& path, vector<bool>& used) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {  // 必须遍历所有元素
            if (used[i]) continue;  // 跳过已用元素
            used[i] = true;
            path.push_back(nums[i]);
            perm(nums, path, used);  // 注意：这里递归时不限制索引
            path.pop_back();
            used[i] = false;  // 回溯
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(), false);  // 添加使用状态数组
        perm(nums, path, used);
        return result;
    }
};

47.全排列 II

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:
    vector<vector<int>> result;
    void perm(vector<int>& nums, vector<int> path, vector<bool>& used){
        if(path.size() == nums.size()){
            result.push_back(path);
            // return;
        }
        for(int i = 0; i< nums.size(); i++){
            if(used[i] == true)continue;
            // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
            // used[i - 1] == false，说明同一树层nums[i - 1]使用过
            // 👇同一层使用过则跳过
            if(i>0 && nums[i] == nums[i-1] && used[i-1] == false)continue;
            path.push_back(nums[i]);
            used[i] = true;
            perm(nums, path, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<int> path;
        vector<bool> used(nums.size(),false);
        sort(nums.begin(), nums.end());
        perm(nums, path, used);
        return result;
    }
};

51. N皇后

问题分析：

  1. 列起始位置错误： 

    1
    for(int i = l; i<n; i++)  // 错误：每行都应从0开始尝试所有列

  2. 赋值操作符错误： 

    1
    li[i] == 1;  // 应该是 =，不是 ==

  3. 皇后位置检查逻辑错误：

    • 检查时使用continue导致死循环，应记录检查结果后设置皇后位置 
      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
      class Solution {
      public:
          vector<vector<string>> result;
          void solve(vector<vector<int>>& cur, int n, int row) {
              if (row == n) {
                  vector<string> solution;
                  for (auto& line : cur) {
                      string s;
                      for (int p : line) {
                          s.push_back(p == 1 ? 'Q' : '.');
                      }
                      solution.push_back(s);
                  }
                  result.push_back(solution);
                  return;
              }
              for (int col = 0; col < n; col++) {  // 每行都尝试所有列
                  bool valid = true;
                  // 检查正上方
                  for (int r = 0; r < row; r++) {
                      if (cur[r][col] == 1) {
                          valid = false;
                          break;
                      }
                  }
                  if (!valid) continue;
                  // 检查左上对角线
                  int r = row - 1, c = col - 1;
                  while (r >= 0 && c >= 0) {
                      if (cur[r][c] == 1) {
                          valid = false;
                          break;
                      }
                      r--;
                      c--;
                  }
                  if (!valid) continue;
                  // 检查右上对角线
                  r = row - 1;
                  c = col + 1;
                  while (r >= 0 && c < n) {
                      if (cur[r][c] == 1) {
                          valid = false;
                          break;
                      }
                      r--;
                      c++;
                  }
                  if (!valid) continue;
                  // 放置皇后
                  vector<int> new_row(n, 0);
                  new_row[col] = 1;  // 正确赋值
                  cur.push_back(new_row);
                  // 递归下一行（列从0开始）
                  solve(cur, n, row + 1);
                  // 回溯
                  cur.pop_back();
              }
          }
          vector<vector<string>> solveNQueens(int n) {
              vector<vector<int>> cur;
              solve(cur, n, 0);  // 从第0行开始
              return result;
          }
      };

发表于 分类于

93.复原IP地址

手动写了to_string()和stoi(),发现字符串给整反了，改过来了也发现效率不如用现有函数 这题需要注意的限制条件确实很多 

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> result;
    string pathToIp(vector<int> path){
        string ip;
        for(int i = 0;i<path.size();i++){
            ip += to_string(path[i]);
            if(i != (path.size()-1))ip.push_back('.');
        }
        return ip;
    }
    void resIp(string s, vector<int> path, int div){
        if(path.size() == 4){
            if(div == s.size())result.push_back(pathToIp(path));
            return;
        }
        for(int i = div; i<s.size();i++){
            string cur = s.substr(div, i-div+1);
            if(cur.size() > 3)continue;
            int curN = stoi(cur);
            if(cur.size()>1 && cur[0] == '0')continue;
            if(curN > 255)continue;
            path.push_back(curN);
            resIp(s, path, i+1);
            path.pop_back();
        }
    }
    vector<string> restoreIpAddresses(string s) {
        if (s.size() > 12) return result;
        vector<int> path;
        resIp(s, path, 0);
        return result;
    }
};

78. 子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> result;
    void ssets(vector<int>& nums, vector<int> path, int left){
        for(int i = left; i < nums.size();i++){
            // if(i>left && nums[i] == nums[i-1])continue;
            path.push_back(nums[i]);
            result.push_back(path);
            ssets(nums, path, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> path;
        result.push_back(path); // 带上空集
        ssets(nums, path, 0);
        return result;
    }
};

90.子集II

和上一篇中的40题一样，题解的used数组和i>left去重都可以，不过这回似乎i>left去重runtime也不低 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> result;
    void ssets(vector<int>& nums, vector<int> path, int left){
        for(int i = left; i < nums.size();i++){
            if(i>left && nums[i] == nums[i-1])continue;
            path.push_back(nums[i]);
            result.push_back(path);
            ssets(nums, path, i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<int> path;
        result.push_back(path); // 带上空集
        sort(nums.begin(), nums.end());
        ssets(nums, path, 0);
        return result;
    }
};

发表于 更新于 分类于

39. 组合总和

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
#include<algorithm>
using namespace std;
class Solution {
public:
    vector<vector<int>> result;
    void combSum(vector<int> path, int left, vector<int>& candi, int t){
        if(t == 0){
            result.push_back(path);
            return;
        }else if(candi[0] > t){
            return;
        }
        for(int i = left;i< candi.size();i++){
            if(candi[i] <= t){
                path.push_back(candi[i]);
                combSum(path, i, candi, t-candi[i]);
                path.pop_back();
            }else{
                break;
            }
        }
        return;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) { // candidate不是递增的
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        combSum(path, 0, candidates, target);
        return result;
    }
};

✅ Introsort（IntroSort）

C++ 中的 std::sort()（定义在 <algorithm> 中）默认使用的是一种由 三种排序算法组合而成的混合排序算法

🔧 Introsort 的组成：

  1. 快速排序（Quicksort）：在数据量大、分布均匀时使用，速度快，期望时间复杂度是 O(n log n)。

  2. 堆排序（Heapsort）：当递归深度超过一定阈值（防止最坏情况 O(n²)）时退化为堆排序，保证最坏时间复杂度也是 O(n log n)。

  3. 插入排序（Insertion Sort）：在小数据范围（如 <16）时使用，性能优于快速排序。

40.组合总和II

i > left && candi[i] == candi[i-1]和题解中创建candidate长度的i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false都可以达到剪去重复，代码AC的效果 如果使用i > left && candidates[i] == candidates[i - 1] && used[i - 1] == false可以提高代码效率

注意题解中used数组只用来剪去同一层的重复数字，所以递归调用后used[i]要设置回false 

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
class Solution {
public:
    vector<vector<int>> result;
    void comb(vector<int>& candi, int left, vector<int> path, int t){
        if(t == 0){
            result.push_back(path);
            return;
        }else if(t < 0){
            return;
        }
        for(int i = left; i< candi.size();i++){
            if(candi[i] > t)return;
            if(i > left && candi[i] == candi[i-1])continue;
            path.push_back(candi[i]);
            comb(candi, i+1, path, t-candi[i]);
            path.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<int> path;
        comb(candidates, 0, path, target);
        return result;
    }
};

131.分割回文串

如题解所说，难点在于认识到切割问题和组合问题类似——每个位置是否“切”——每种切法就是一条树枝，还有求是否是回文串部分的优化 

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
class Solution {
public:
    vector<vector<bool>> pal;
    void isPal(string s){
        pal.resize(s.size(), vector<bool>(s.size(), false));
        for(int i = (s.size()-1); i>=0;i--){
            for(int j = i; j<= (s.size()-1);j++){
                if(j == i){
                    pal[i][j] = true;
                }else if((j - i) == 1){
                    pal[i][j] = s[i] == s[j] ? true : false;
                }else{
                    pal[i][j] = (s[i] == s[j] && pal[i+1][j-1]);
                }
            }
        }
    }
    vector<vector<string>> result;
    void partPal(vector<string> path, string s, int div){
        if(div == s.size()){
            result.push_back(path);
            return;
        }
        for(int i = div; i < s.size();i++){
            if(pal[div][i] == true){
                path.push_back(s.substr(div, i-div+1));
                partPal(path, s, i+1);
                path.pop_back();
            }else{
                continue;
            }
        }
        return;
    }
    vector<vector<string>> partition(string s) {
        vector<string> path;
        isPal(s);
        partPal(path, s, 0);
        return result;
    }
};

0%