Maxw的小站

Maxw学习记录

发表于 分类于

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

发表于 更新于 分类于

235. 二叉搜索树的最近公共祖先

相对二叉树的最近公共祖先简单多了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm> // min 和 max
using namespace std;
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)return nullptr;
        int rt = root->val;
        int minV = min(p->val, q->val);
        int maxV = max(p->val, q->val);
        if(rt>=minV && rt<=maxV){
            return root;
        }else if(rt < minV){
            return lowestCommonAncestor(root->right, p, q);
        }else{
            return lowestCommonAncestor(root->left, p,q);
        }
    }
};

701.二叉搜索树中的插入操作

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* insNode = new TreeNode(val);
        if(!root)return insNode;
        if(root->val > val){
            root->left = insertIntoBST(root->left, val);
        }else{
            root->right = insertIntoBST(root->right, val);
        }
        return root;
    }
};

450.删除二叉搜索树中的节点

我的想法是：先找到应该删除的节点子树-找到它的左子树最右节点-找到最右节点的父节点-将最右节点的值替换给应该删除的节点并删除最右节点 题解虽然也类似地需要分情况讨论，但是简洁地多：

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了
  • 找到删除的节点
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(!root)return nullptr;
        if(root->val == key){
            if(!root->left)return root->right;
            if(!root->right)return root->left;
            TreeNode* minR = root->right;
            while(minR->left)minR = minR->left;
            minR->left = root->left;
            return root->right;
        }
        if(root->val > key){
            root->left = deleteNode(root->left, key);
        }else{
            root->right = deleteNode(root->right, key);
        }
        return root;
    }
};

发表于 更新于 分类于

HTTP中常见的状态码有哪些？

HTTP 状态码用于表明特定HTTP请求是否完成

1xx 信息响应（100–199）

✅“我听到了，继续吧”

表示请求已接收，继续处理

  • 100 Continue：初始部分已接收，客户端应继续发送。
  • 101 Switching Protocols：服务器：同意更改协议。 > - WebSocket：最常见，HTTP 升级为 WebSocket，实现持久化的全双工通信。 > - HTTP/2：部分场景下可以通过 Upgrade 机制从 HTTP/1.1 升级到 HTTP/2。 > - TLS/SSL：早期可以通过 Upgrade 升级到加密连接（现在一般用 HTTPS 直接建立）。
  • 102 Processing：服务器：已收到，正在处理。

2xx 成功响应（200–299）

表示请求已成功接收

🎉“你请求的事我办妥了”

  • 200 OK：请求成功。
  • 201 Created：请求成功并创建了新的资源（例如注册）
  • 202 Accepted：请求已接受，但未响应 -不会有一个异步的响应去表明当前请求的结果，预期另外的进程和服务去处理请求
  • 204 No Content：请求成功，但无返回内容。
  • 206 Partial Content：当从客户端发送Range范围标头以只请求资源的一部分时，使用此响应代码（例如断点续传）

3xx 重定向（300–399）

表示需要进一步操作以完成请求。

🔀“去别处找”

  • 301 Moved Permanently：请求的资源已永久移动到新位置。
  • 302 Found：请求的资源临时从不同的 URI 响应请求。
  • 303 See Other：请求应使用另一个 URI 获取资源。
  • 304 Not Modified：资源未修改，可使用缓存。
  • 307 Temporary Redirect：请求的资源临时从不同的 URI 响应请求，方法不变。
  • 308 Permanent Redirect：请求的资源已永久移动到新位置，方法不变。

4xx 客户端错误（400–499）

表示请求包含语法错误或无法完成

  • 400 Bad Request：请求无效，服务器无法理解。
  • 401 Unauthorized：请求要求客户端身份认证。
  • 403 Forbidden：服务器知道客户端身份，但客户端没有访问权限
  • 404 Not Found：请求的资源未找到。
  • 405 Method Not Allowed：请求方法被禁止。
  • 408 Request Timeout：请求超时。
  • 429 Too Many Requests：客户端发送的请求过多，已被限制。

5xx 服务器错误（500–599）

表示服务器未能完成合法的请求。

  • 500 Internal Server Error：服务器内部错误，无法完成请求。
  • 501 Not Implemented：服务器不支持请求的功能。
  • 502 Bad Gateway：服务器作为网关或代理，从上游服务器收到错误响应。
  • 503 Service Unavailable：服务器当前无法处理请求。
  • 504 Gateway Timeout：服务器作为网关或代理，未及时从上游服务器收到响应。

什么是强缓存和协商缓存

🌟一、强缓存（完全不发请求）

关键词：直接使用缓存，不访问服务器

✅ 特点：
  • 浏览器直接使用本地缓存资源。
  • 不向服务器发请求。
  • 若命中强缓存，浏览器将会本地模拟一个状态码 200 (from memory cache) 或 200 (from disk cache)。
📌 实现方式：
字段 说明
Cache-Control: max-age=秒数 （相对时间，更准确）当前资源在 N 秒内有效✅推荐
Expires: GMT时间 （绝对时间，受本地时间影响）指定资源过期时间❌已过时

  1. 首次访问资源：
    服务器返回资源时在响应头加上 Cache-Control: max-age=秒数，告知浏览器这个资源可以缓存多久。

  2. 再次访问时：
    浏览器会用“当前时间 - 缓存时间”与 max-age 做比较：

    • 没过期 → 直接用缓存，不发请求。
    • 过期 → 发起新请求，向服务器重新获取资源。

  3. 服务器响应更新：
    每次服务器响应时都会更新 Cache-Control，供下一轮缓存使用。

🔄二、协商缓存（发请求，服务器决定是否使用缓存）

关键词：发请求，比较“资源是否改过”

✅ 特点：
  • 请求时会向服务器询问资源是否有更新。
  • 如果没变，返回 304 Not Modified，继续用本地缓存。
  • 如果变了，返回 200 + 新资源。
📌 两种主流方式：
方式 请求头字段 响应头字段 原理 优缺点简析
Last-Modified If-Modified-Since Last-Modified 比较“上次修改时间” ⛔秒级精度、不改内容也可能变时间
ETag If-None-Match ETag 比较“文件指纹/哈希” ✅更精准，内容变才更新

🔁三、常见误区与补充

  • 强缓存命中 → 不发请求
  • 强缓存失效 → 发请求，进入协商缓存阶段
  • 如果协商缓存也失效，才真正下载新资源。

发表于 更新于 分类于

530.搜索树的最小绝对差

遇到在二叉搜索树上求什么最值啊，差值之类的，就把它想成在一个有序数组上求最值，求差值，这样就简单多了 尝试自己写遍历，虽然有很多莫名其妙的值，但是居然写对了 

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:
    TreeNode* maxNode = nullptr;
    int absd  = -1;
    int getMinimumDifference(TreeNode* root) {
        if(!root)return -1;
        int left = -1;
        int right = -1;
        if(root->left)left = getMinimumDifference(root->left);
        if(maxNode != nullptr){
            int maxd = root->val - maxNode->val;
            if(absd == -1){
                absd = maxd;
            }else if(maxd < absd){
                absd = maxd;
            }
        }
        maxNode = root;
        if(root->right)right = getMinimumDifference(root->right);
        return absd;
    }
};

501.二叉搜索树中的众数

如果我自己写，就遍历数组取最大值好了。看题解发现可以中序遍历，按这种方法找： 弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。 而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。 如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组），
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。

注意计数和判定最大值要分开，并且确定好是判定当前节点 

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:
    TreeNode* pre = nullptr;
    int cnt = 0;
    int cntMax = 0;
    void traverse(vector<int> &res, TreeNode* root){
        if(!root)return;
        traverse(res, root->left);
        if(!pre){
            cnt++;
        }else if(pre->val == root->val){
            cnt++;
        }else{ //  if(pre->val != root->val)
            cnt = 1;
        }
        if(cnt == cntMax){
            res.push_back(root->val);
        }else if(cnt > cntMax){
            res.clear();
            cntMax = cnt;
            res.push_back(root->val);
        }
        pre = root;
        traverse(res, root->right);
        return;
    }
    vector<int> findMode(TreeNode* root) {
        vector<int> res;
        traverse(res, root);
        return res;
    }
};

236. 二叉树的最近公共祖先

我的解法就是暴力解，找到p和q的路径并比较路径中不同的节点，前一个就是公共最小祖先了 看了题解发现还可以回溯：

遇到这个题目首先想的是要是能自底向上查找就好了，这样就可以找到公共祖先了。 那么二叉树如何可以自底向上查找呢？ 回溯啊，二叉树回溯的过程就是从底到上。 后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。

搞清楚什么时候返回root也很重要 

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root || root == p || root == q)return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left != nullptr && right != nullptr)return root;
        if(left == nullptr)return right;
        return left;
    }
};

0%