Day 19。
今天两道题分别是 Count and Say 和 Combination Sum。
一道是 字符串模拟构造题，一道是 经典回溯组合题。

今天的关键词：读串构造、分组统计、回溯、组合枚举、剪枝、重复选取。

🧠 LeetCode 38 – Count and Say

💡 思路总结

这题的题意一开始看着有点绕，但本质其实很简单：

把上一个字符串“读出来”，生成下一个字符串

比如：

  • 1 读作 “一个 1” → 11
  • 11 读作 “两个 1” → 21
  • 21 读作 “一个 2，一个 1” → 1211

所以这题不是数学题，而是：

字符串按连续段统计，再重新拼接

你的整体思路很清晰：

  1. countAndSay(n) 从 "1" 开始迭代
  2. 每次调用 count_num(result) 生成下一项
  3. 重复 n-1 次

这就是很标准的“迭代构造”思路。

💻 代码实现

class Solution {
public:
    //默认是从1开始迭代的

    string countAndSay(int n) {
        if(n == 1)return "1";

        else {
            string result = "1";
            for(int i = 0; i < n-1;i++){
                result = count_num(result);
            }
            return result;
        }
    }

    string count_num(string s){
        int s_len = s.size();
        int count = 1;
        int slow = 0;
        string new_s = "";

        for(int i = 1; i < s_len; i++){
            if(s[i] == s[slow]){
                count++;
            }else{
                new_s += to_string(count);
                new_s += s[slow];
                slow = i;
                count = 1;
            }
        }

        new_s += to_string(count);
        new_s += s[slow];

        return new_s;
    }
};

📌 知识点总结

1️⃣ 这题本质是“连续分组统计”

你这里的 count_num 实际上在做一件事：

  • 找连续相同字符的一段
  • 统计这段长度
  • 按“数量 + 字符”拼接到新字符串里

这和很多字符串压缩题、游程编码题的思路很像。

2️⃣ slow 的作用

你这里的 slow 表示：

当前这一段连续字符的起点

然后 i 一直往后扫：

  • 如果 s[i] == s[slow]，说明还在同一段里
  • 如果不同，说明这一段结束了，要把这一段写入答案

这种“分组扫描”思路很常见。

3️⃣ 最后别忘了补最后一段

这个点很关键。
因为循环里只有“遇到变化时”才会把上一段写入字符串，所以最后一段不会自动处理。

所以你补了：

new_s += to_string(count);
new_s += s[slow];

这一步不能漏。

4️⃣ 这里有一个小细节可以优化

你在 countAndSay 里写的是：

for(int i = 0; i < n-1; i++)

如果 n = 2，会从 "1" 迭代 1 次，没问题。
如果 n = 1，前面已经提前返回了，也没问题。

所以逻辑是对的。
不过博客里可以顺手理解成：

已经有第 1 项 "1" 了，再往后生成 n-1 次

这样思路会更顺。

🔥 LeetCode 39 – Combination Sum

💡 思路总结

这题要求找出所有和为 target 的组合。
每个数可以被重复选取，而且组合不能重复。

看到这种题，第一反应就该想到：

回溯 / DFS

因为我们需要：

  • 枚举所有可能组合
  • 记录当前路径
  • 尝试加入一个数
  • 如果超了就停止
  • 如果刚好等于目标就收集答案

你的写法就是非常典型的回溯框架。

💻 代码实现

class Solution {
    //回溯
public:
    vector <int> path;
    vector<vector<int>> result;

    void dfs(vector<int>& candidates, int target,int sum , int pos){
        if(sum == target){
            result.push_back(path);
            return ;
        }
        else if(sum > target )return;
        else{
            for(int i = pos;i<candidates.size();i++ ){
                path.push_back(candidates[i]);
                dfs(candidates,target,sum+candidates[i],i);
                path.pop_back();
            }
        }
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0,0);
        return result;
    }
};

📌 知识点总结

1️⃣ 这是经典的“选 or 继续选”型回溯

这题和前面的括号生成、数独不太一样。
这里不是在固定位置填字符，而是在不断决定：

  • 当前选哪个数
  • 选了之后还能不能继续选这个数

因为题目允许重复使用，所以递归时你写的是：

dfs(candidates, target, sum + candidates[i], i);

注意这里传的还是 i，不是 i + 1。

这正是“可以重复选”的关键。

2️⃣ pos 的作用很重要

这个参数表示：

当前这一层从哪个位置开始枚举

作用有两个：

  • 避免组合顺序不同但本质相同的重复解
  • 保证路径是按固定顺序构造的

比如 [2,3,3] 和 [3,2,3] 本质是同一个组合，
通过 pos 控制搜索起点，就能避免这种重复排列式答案。

3️⃣ 剪枝条件非常清晰

你这里有两个终止条件：

if(sum == target)

说明当前路径刚好是一个合法答案，加入结果。

else if(sum > target) return;

说明当前路径已经超了，不可能再成功，直接停止。

这就是非常标准的回溯剪枝。

4️⃣ 回溯的标准动作完整写出来了

你这里已经完整体现了回溯模板：

选择

path.push_back(candidates[i]);

递归

dfs(candidates,target,sum+candidates[i],i);

撤销选择

path.pop_back();

这个结构非常值得记住。

5️⃣ 这题还能继续优化

你当前这版已经可以正确表达回溯框架。
如果后面想优化，可以考虑先排序，然后在：

if(sum + candidates[i] > target)

时直接 break，这样能更早剪枝。

不过在当前阶段，先把“回溯框架本身”真正吃透，比一上来追求最优剪枝更重要。

🧩 今日总结

题目核心思想
LeetCode 38连续字符分组统计 + 迭代构造
LeetCode 39回溯 + 路径记录 + 剪枝 + 重复选取

今天两题类型差别挺大：

  • 38 偏字符串模拟和构造
  • 39 偏搜索和组合枚举

但它们都有一个共同点：

不是直接算答案，而是一步一步把答案“长出来”

🧠 今日收获

今天最值得记住的两个模型：

1. 字符串分组构造模型

如果题目是“根据当前串生成下一个串”，而且规则和连续字符段有关，就要想到：

  • 扫描连续段
  • 统计个数
  • 拼接新字符串

2. 可重复选取的组合回溯模型

如果题目里有：

  • 组合
  • 目标和
  • 元素可重复选

那就要想到：

  • 回溯
  • pos 控制起点
  • 递归时继续传 i，表示当前数还能再选

💬 写给自己的话

Day 19 了。

现在你已经能明显感觉到，自己接触的题越来越有“模块感”了：

  • 字符串题有字符串题的套路
  • 回溯题有回溯题的框架
  • 链表题有链表题的常见操作
  • 二分题有二分题的边界思维

这就是积累的意义。

你现在不是在一题一题地“碰运气”，
而是在慢慢搭一套自己的解题体系。

继续保持。
别急，别乱，别断。
只要你一直这样刷下去、总结下去，后面的题会越来越顺。

阿玉，Day 19，继续冲。

—— 刷题第 19 天