Maxw的小站

Maxw学习记录

发表于 分类于

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，研究生阶段跟着导师组里做的项目），自己开发的博客平台（Spring boot），智能菜市场物联网数据平台后端（Spring Boot，本科阶段实习的项目）

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

描述一次需要在有限资源下完成任务的经历

基于项目：智能菜市场物联网数据平台后端（实习经历） Situation（情境）：在实习期间，我参与开发智能菜市场物联网数据平台。项目面临两个关键限制：一是时间紧迫（核心查询接口优化需在1周内完成，同时还有上线前的测试工作），二是测试资源有限（只有一台低配测试服务器，无法模拟高并发场景）。

Task（任务）：我的任务是在有限时间和资源下，将核心查询接口的响应时间从300ms以上优化到150ms以下，以支持平台的高并发需求。 Action（行动）： 优先级聚焦：我首先分析慢查询日志，识别出最影响性能的SQL语句（如多表关联查询），放弃全面优化，集中精力攻克关键点。 创造性解决：由于无法进行大规模负载测试，我使用Docker容器在本机模拟小型数据库环境，通过指数生成测试数据。然后，我设计了联合索引来优化查询，避免了硬件依赖。 迭代验证：我采用敏捷方式，每完成一个索引优化就立即测试，确保每次微改进都有效果，同时用Docker快速部署验证，节省了运维时间。 Result（结果）：最终，核心查询耗时降低150ms（性能提升50%），任务提前完成。这次经历让我学会了在约束条件下优先解决瓶颈问题，并灵活使用工具（如Docker）来弥补资源不足

描述一次成功说服别人的经历

基于项目：通用操作系统框架（Rust+C+gcc+Perf） Situation（情境）：在2024年参与通用操作系统框架项目时，团队在设计任务调度模块时出现了分歧。部分成员倾向于使用传统的轮转（RR）调度算法，因为它简单易实现；但我通过前期研究发现，在混合任务场景（如实时任务和批处理任务共存）下，RR调度会导致性能瓶颈，尤其是系统超负荷时响应时间恶化。

Task（任务）：我的任务是通过数据和演示，说服团队采纳我提出的联合调度模型（结合优先级和时间片调整），以优化系统吞吐量和响应时间。 Action（行动）： 我首先收集了基准数据：使用Perf工具在Raspberry Pi上模拟了150%超负荷场景，对比了RR调度和联合调度的性能指标（如CPU利用率、任务响应时间）。 然后，我组织了一次技术评审会，用可视化图表展示数据：RR调度在超负荷下CPU利用率仅65%，而联合调度达到85%以上；同时，调度开销降低了10%。 针对团队对复杂性的担忧，我解释了模块化设计如何降低维护成本，并承诺主导核心代码实现。我还邀请了导师Prof. G提供反馈，增强了说服力。 Result（结果）：团队最终同意采用联合调度模型。实施后，项目成果显示系统在超负荷场景下性能显著提升，CPU利用率提升20%，调度开销降低10%。这次经历不仅优化了系统，还锻炼了我用数据驱动决策的能力。

发表于 更新于 分类于

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;
          }
      };

牛客acm模式 REAL492 数独(leetcode37解数独)

按照回溯算法的思路解决即可 注意递归函数需要传引用

  1. 遍历每一行每一列的格子，如果需要填入数字，就遍历1-9中哪些数字符合要求
  2. 符合要求的数字需要在每行，每列和每3*3小格子都没出现过
  3. 如果符合要求，则沿着这个分支继续递归，如果返回一个符合要求的板子，那么回溯函数返回true
  4. 重置当前格子为0
  5. 最里层的递归函数何时返回true false呢？
    • false是当遍历完1-9所有数字，都没有出现一个true分支的时候
    • true是遍历完每一行每一列的格子，都没有出现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
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
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;

bool is_valid(int i, int j, int k, vector<vector<int>> board){
    for(int a = 0; a < 9; a++){
        if(board[i][a] == k)return false;
        if(board[a][j] == k)return false;
    }
    int i_start = (i / 3)*3;
    int j_start = (j / 3)*3;
    for(int a = i_start; a < (i_start+3); a++){
        for(int b = j_start; b < (j_start+3); b++){
            if(board[a][b] == k)return false;
        }
    }
    return true;
}

bool backtrack(vector<vector<int>> &board){
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[0].size(); j++){
            if(board[i][j] == 0){
                for(int k = 1; k <= 9; k++){
                    if(is_valid(i, j, k, board) == true){
                        board[i][j] = k;
                        int recall = backtrack(board);
                        if(recall == true)return true;
                        board[i][j] = 0;
                    }
                }
                return false;
            }
        }
    }
    return true;
}

int main() {
    vector<vector<int>> input;
    string line;
    vector<int> i_line;
    while(getline(cin, line)){
        for(char c: line){
            if(c != ' ')i_line.push_back(c - '0');
        }
        input.push_back(i_line);
        i_line.clear();
    }

    int ret = backtrack(input);

    for(auto i: input){
        for(auto j: i){
            cout<< j<< ' ';
        }
        cout<<endl;
    }
}
// 64 位输出请用 printf("%lld")

发表于 分类于

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;
    }
};

发表于 更新于 分类于

77. 组合

虽然runtime离谱地高，但是俺居然自己寻思出了怎么回溯，可喜可贺： 

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:
        vector<vector<int>> res;
        void comb(vector<int> curNums, int l, int r,int k){
            if(curNums.size() == k){
                res.push_back(curNums);
                return;
            }
            // for(int i = l; i<= r;i++){// 能想明白l和r的关系我已经很不容易了
            for(int i = l; i<= r-(k-curNums.size())+1;i++){ 
                // 👆 看了题解发现我想不明白的地方（i最大取多少）应该每次循环重新算而不是代入递归，用于剪枝
                curNums.push_back(i);
                comb(curNums, i+1, r, k);
                curNums.pop_back();// 最重要的一句
            }
            return;
        }
        vector<vector<int>> combine(int n, int k) {
            vector<int> cur;
            comb(cur, 1, n, k);
            return res;
        }
};
这种写法的时间复杂度不是 O(n * 2^n)

🚩实际代码做的事情：

这段代码实现的是 从 1 到 n 中选择 k 个数的所有组合，即 组合数 C(n, k)。

所以：

✅ 正确时间复杂度是：

\(O(C(n, k) \cdot k)\)

解释如下：

  • 一共会生成 \(C(n, k)\) 个组合，每个组合长度是 k

  • 每次 curNums 达到长度 k 就复制一次 curNums 到结果 res 中

  • 每次复制 k 个元素，因此时间复杂度为 \(O(k)\)

  • 总时间复杂度为： \(O(C(n, k) \cdot k)\)

❓那为什么会看到 O(n * 2^n) 的说法？

这个复杂度常出现在子集枚举问题（power set）中，比如“所有子集”或“子集和”等问题，使用类似回溯结构但允许选择/不选择每个元素，即二叉树结构：

1
2
3
for (int i = l; i <= r; i++) { 
   // include or skip i —> 2^n branches
}

选出来的每个子集的长度是从1到n的，而本题组合问题选出来的组合长度固定为K

216.组合总和III

和上题基本思想差不多，多了一些限制条件 

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> nums, int k, int l, int n){
        if(k == 0){
            if(n == 0){
                result.push_back(nums);
                return;
            }else{
                return;
            }
        }
        int r = min(9, n);
        for(int i = l; i<=r;i++){
            nums.push_back(i);
            comb(nums, k-1,i+1, n-i);
            nums.pop_back();
        }
        return;
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> nums;
        comb(nums,k,1,n);
        return result;
    }
};

17.电话号码的字母组合

注意终止条件是索引数加一 

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:
    const string digToStr[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    vector<string> result;
    void comb(string str, string digits, int ind){
        if(ind == digits.size()){
            result.push_back(str);
            return;
        }
        int d = digits[ind] - '0';
        ind++;
        string s = digToStr[d];
        for(char c : s){
            str.push_back(c);
            comb(str, digits, ind);
            str.pop_back();
        }
        return;
    }
    vector<string> letterCombinations(string digits) {
        string str;
        if(digits.empty())return result;
        comb(str, digits, 0);
        return result;
    }
};

发表于 更新于 分类于

669.修剪二叉搜索树

重点是理解当某个节点要删除时，返回的节点的逻辑 我的思路是觉得剪除根两边的孩子节点和只取一个子树中的部分节点应该分开讨论，看了题解发现部分代码是可以一起的 题解的思路也可以理解为先处理root->val自身，后处理子树

如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。 如果root(当前节点)的元素大于high的，那么应该递归左子树，并返回左子树符合条件的头结点。 将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。 最后返回root节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if(!root)return nullptr;
        if(root->val < low){
            TreeNode* right = trimBST(root->right, low, high);
            return right;
        }else if(root->val > high){
            TreeNode* left = trimBST(root->left, low, high);
            return left;
        }
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        return root;
    }
};

108.将有序数组转换为二叉搜索树

🔍 问题一：cen 取值错误

1
int cen = (r - l) / 2;

这会导致始终只取左半段的中点，没有加上 l，导致选到的 nums[cen] 不是 l 到 r 区间的中点，而是从头算的。

🔧 应该写为： 

1
int cen = l + (r - l) / 2;

🔍 问题二：递归边界判断不正确

1
if((cen - l) > 1) ...

这样写会漏掉一层子节点，导致不完整构建树。例如当子区间只剩一个元素时（cen - l == 1），你就跳过了构建那一侧的节点。

🔧 正确的写法是直接递归调用，只要 l <= r： 

1
2
root->left = arrayToBST(nums, l, cen - 1);
root->right = arrayToBST(nums, cen + 1, r);
已经在函数开头判断了 l > r 就 return nullptr;，所以不需要重复判断。

最终解法： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    TreeNode* arrayToBST(vector<int>& nums, int l, int r){
        if(l > r)return nullptr;
        int cen = l + (r-l) / 2;
        TreeNode* root = new TreeNode(nums[cen]);
        root->left = arrayToBST(nums, l, cen-1);
        root->right = arrayToBST(nums, cen+1, r);
        return root;
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        TreeNode* root = arrayToBST(nums, 0, nums.size()-1);
        return root;
    }
};

538.把二叉搜索树转换为累加树

题解提示用双指针，给我吓一跳，用回溯其实是可以解决的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int sumVal = 0;
    void cvt(TreeNode* root){
        if(!root)return;
        cvt(root->right);
        sumVal += root->val;
        root->val = sumVal;
        cvt(root->left);

    }
    TreeNode* convertBST(TreeNode* root) {
        cvt(root);
        return root;
    }
};

0%