Day 14。
今天两道题分别是 Find the Index of the First Occurrence in a String 和 Divide Two Integers。
一道是 字符串匹配入门题，一道是 位运算 + 倍增思想。
今天的关键词：匹配、暴力搜索、倍增、位移、溢出处理。
🧠 LeetCode 28 – Find the Index of the First Occurrence in a String
💡 思路总结
这题要求在字符串 haystack 中找到 needle 第一次出现的位置。
如果不存在，就返回 -1。
你的做法很直接：
- 枚举
haystack的每一个位置i - 如果
haystack[i] == needle[0]，就从这里开始尝试匹配 - 如果整段
needle都匹配成功，就返回当前位置i
这其实就是最经典的：
暴力字符串匹配
💻 代码实现
class Solution {
public:
int strStr(string haystack, string needle) {
//同样是快慢指针；
for(int i = 0;i < haystack.size();i++){
if(haystack[i] == needle[0]){
//开始配对
int check = i;
int check_right = 0;
for(char c : needle){
if(haystack[check] != c)break;
else{
check++;
check_right++;
}
}
if(check_right == needle.size())return i;
}
}
return -1;
}
};
📌 知识点总结
1️⃣ 这题本质就是暴力匹配
思路可以概括成一句话：
从主串的每个位置出发，试试看能不能完整匹配模式串
这是一种很基础但非常重要的字符串题思路。
2️⃣ 两层逻辑很清楚
你的代码可以拆成两层：
- 外层：枚举起点
- 内层：检查从这个起点开始能否完整匹配
这种写法逻辑非常自然，也很适合刚接触字符串匹配时理解。
3️⃣ 这里有一个边界问题要注意
你这份代码整体思路是对的，但有一个隐藏风险：
if(haystack[check] != c) break;
这里默认 check 一定没有越界。
但如果 needle 比剩余的 haystack 更长，就可能访问到越界位置。
比如：
haystack = "abc"
needle = "cd"
当 i = 2 时，haystack[2] == 'c'，会进入内层，接着 check++ 后就可能访问越界。
✅ 更稳一点的版本
更规范的写法一般会把起点限制在：
i <= haystack.size() - needle.size()
这样后面就不会越界。
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
for (int i = 0; i <= (int)haystack.size() - (int)needle.size(); i++) {
int j = 0;
while (j < needle.size() && haystack[i + j] == needle[j]) {
j++;
}
if (j == needle.size()) return i;
}
return -1;
}
};
4️⃣ 这题是 KMP 的前置题
这题用暴力法完全可以做出来。
不过它还有更高级的做法：
KMP 字符串匹配
但现阶段先把暴力匹配理解透就很不错，因为很多复杂算法都是从基础方法优化出来的。
⚙️ LeetCode 29 – Divide Two Integers
💡 思路总结
这题要求在不能使用乘法、除法和取模的情况下，实现整数相除。
这题看起来有点吓人，但核心思路其实很巧：
用减法模拟除法，但不能一下一下减，要用“倍增”优化
比如想算：
43 / 5
朴素想法是：
- 43 – 5 – 5 – 5 …
- 看能减多少次
但这样太慢。
所以更聪明的方法是：
- 先减
5 - 再减
10 - 再减
20 - 也就是每次尽量减去当前能减的最大
2^k * divisor
这就是你代码里的核心思想。
💻 代码实现
class Solution {
public:
int divide(int dividend, int divisor) {
if (dividend == INT_MIN && divisor == -1) {
return INT_MAX;
}
long long a = dividend;
long long b = divisor;
bool negative = (a < 0) ^ (b < 0);
a = llabs(a);
b = llabs(b);
long long result = 0;
while (a >= b) {
long long temp = b;
long long count = 1;
while ((temp << 1) <= a) {
temp <<= 1;
count <<= 1;
}
a -= temp;
result += count;
}
return negative ? -result : result;
}
};
📌 知识点总结
1️⃣ 为什么不能直接一直减
如果每次只减一个 divisor，比如：
1000000000 / 1
那要减十亿次，显然会超时。
所以必须优化。
2️⃣ 倍增思想是这题灵魂
你这里用了：
while ((temp << 1) <= a) {
temp <<= 1;
count <<= 1;
}
意思是：
- 当前先从
divisor开始 - 能翻倍就一直翻倍
- 直到不能再翻倍为止
这样每次都减去“尽可能大的一块”，效率就高很多。
这和二进制拆分的思想很像。
3️⃣ count 的作用
当 temp 翻倍时：
temp = divisor * 2^k
那么对应商也要加上：
count = 2^k
所以最后：
result += count;
这一句其实就是在累计商。
4️⃣ 先统一转正数很聪明
你这里先用：
bool negative = (a < 0) ^ (b < 0);
判断最后结果是否为负数。
然后：
a = llabs(a);
b = llabs(b);
把两边都转成正数处理。
这样好处很大：
- 主逻辑更统一
- 不需要在循环里反复考虑正负号
- 最后再统一加上符号即可
5️⃣ 溢出特判不能少
这题最经典的坑点就是：
INT_MIN / -1
理论结果是：
2147483648
已经超过 int 范围了，所以必须特判：
if (dividend == INT_MIN && divisor == -1) {
return INT_MAX;
}
这一步非常重要，也几乎是这题的必考点。
🧩 今日总结
| 题目 | 核心思想 |
|---|---|
| LeetCode 28 | 暴力字符串匹配 + 边界控制 |
| LeetCode 29 | 倍增 + 位运算 + 减法模拟除法 |
今天两题风格差别挺大：
28比较偏基础字符串处理29更偏思维转换和数学优化
但它们都在提醒一件事：
题目表面要求是一回事，真正关键是把问题转化成你熟悉的形式。
🧠 今日收获
今天最值得记住的两个模型：
1. 字符串匹配基础模型
看到这种“找子串”的题，先想到：
- 枚举起点
- 逐字符匹配
- 注意边界别越界
这是最基本的字符串匹配框架。
2. 倍增优化模型
如果一个问题本来可以“重复减、重复加、重复操作”来做，
但朴素方法太慢，就要想到：
- 能不能每次翻倍
- 能不能按二进制拆分
- 能不能一大块一大块处理
这类思想在很多题里都特别有用。
💬 写给自己的话
Day 14 了。
两周了。
你现在已经不是刚开始那个“刷题试试看”的状态了，
而是真的在一点点建立自己的算法直觉。
今天这种题很有价值：
- 一题帮你继续巩固基础匹配思维
- 一题逼你做思维转化和优化
这两种能力，后面都会反复用到。
别急着追求全都会。
你现在最重要的，是保持这种稳定的节奏：
- 做题
- 总结
- 发现问题
- 修正思路
时间久了，很多东西真的会内化成直觉。
阿玉，Day 14，已经坚持两周了。继续冲。
—— 刷题第 14 天
