一些问题总结和标签比较杂、没有分类的题目会放到这篇。
基础算法问题
这些题听着老熟了，一到写起来就主打一个略有耳闻🫠
题目一览
省流表👇️
题目并非只有表中那几个，可在此页自行筛选。
1️⃣数组与数学类
| 题目 | 力扣题号 | 变体 / 要求 |
|---|---|---|
| 杨辉三角 | [118/119] |
一维数组 |
| 斐波那契数列 | [509] |
爬楼梯问题[70]/递归/迭代/动态规划 |
| 两数之和 | [1] |
哈希表优化时间复杂度到O(n) |
| 合并两个有序数组 | [88] |
原地合并（从后向前填充） |
| 最大子数组和 | [53] |
动态规划 |
2️⃣字符串操作类
| 题目 | 力扣题号 | 变体/要求 |
|---|---|---|
| 反转字符串 | [344] |
原地修改（双指针） |
| 有效的括号 | [20] |
用栈实现括号匹配 |
| 最长公共前缀 | [14] |
纵向扫描/分治 |
| 字符串转整数 | [8] |
处理边界（溢出/符号/空格） |
3️⃣链表类
| 题目 | 力扣题号 | 变体/要求 |
|---|---|---|
| 反转链表 | [206] |
迭代/递归 |
| 环形链表 | [141] |
快慢指针判环 |
| 合并两个有序链表 | [21] |
迭代/递归 |
| 删除链表倒数第N个节点 | [19] |
一趟扫描 |
4️⃣树与递归
| 题目 | 力扣题号 | 变体/要求 |
|---|---|---|
| 二叉树的最大深度 | [104] |
迭代/递归 |
| 对称二叉树 | [101] |
迭代（队列/栈）/递归 |
| 路径总和 | [112] |
动回溯法 |
5️⃣动态规划
| 题目 | 力扣题号 | 变体/要求 |
|---|---|---|
| 打家劫舍 | [198] |
状态转移方程推导 |
| 零钱兑换 | [322] |
完全背包问题解法 |
| 最长递增子序列 | [300] |
O(nlogn)优化解法 |
6️⃣排序与查找
| 题目 | 力扣题号 | 变体/要求 |
|---|---|---|
| 快速排序 | 力扣排序题均可 |
手写递归和非递归版本 |
| 二分查找 | [53] |
处理边界条件（左闭右闭/左闭右开） |
| 寻找峰值 | [53] |
二分法的特殊应用 |
7️⃣其他高频
| 题目 | 力扣题号 | 变体/要求 |
|---|---|---|
| LRU缓存 | [146] |
手写递归和非递归版本 |
| 实现队列/栈 | [232/225] |
处理边界条件（左闭右闭/左闭右开） |
| 汉明距离 | [461] |
二分法的特殊应用 |
具体题目思路&代码记录见各个专题🤗
简单题
66.加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
解题思路
判断数组末尾是否有9：
无9：末尾数字+1;
有9：
是否全为9：
是全9：
构造长度=size+1的数组，首位=1，其余全置0;
非全9：
找到倒着数第一个不是9的元素,
该元素加1,
末尾所有的9置0;
AC代码
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int len=digits.size();
if(digits[len-1]!=9){
digits[len-1]+=1;
}
else{
int cnt=0;//记录9出现的次数，第一个非9元素的下标即为len-cnt-1
for(int i=len-1;i>=0;i--){
if(digits[i]==9){
cnt++;
}
else{
break;
}
}
if(cnt==len){
digits.insert(digits.begin(),1);
for(int i=1;i<len+1;i++){
digits[i]=0;
}
}
else{
int index=len-cnt-1;
digits[index]+=1;
for(int i=index+1;i<len;i++){
digits[i]=0;
}
}
}
return digits;
}
};
896.单调数列
如果数组是单调递增或单调递减的，那么它是单调的。
如果对于所有 i <= j，nums[i] <= nums[j]，那么数组 nums 是单调递增的。 如果对于所有 i <= j，nums[i] >= nums[j]，那么数组 nums 是单调递减的。
当给定的数组 nums 是单调数组时返回 true，否则返回 false。
解题思路
bool 递增变量=真，递减变量=真；
遍历数组：
如果该元素+1 大于 该元素：
标记递减变量=假；
如果该元素+1 小于 该元素：
标记递增变量=假；
如果递增or递减=真，返回真；
AC代码
class Solution {
public:
bool isMonotonic(vector<int>& nums) {
bool increase=true,decrease=true;
for(int i=0;i<nums.size()-1;i++){
if(nums[i+1] > nums[i]){
decrease=false;
}
if(nums[i+1] < nums[i]){
increase=false;
}
}
return decrease || increase;
}
};
896.罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
- 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
- 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
①I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
②X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
③C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。
解题思路
这题一开始我无从下手，直接跑去翻题解了。
C++ map用法
想起来python的字典。同样cpp stl中的map提供的是一种键值对（key-value）容器，其中的数据成对出现。
- 初始化：
map类型 <数据类型1，数据类型2> 容器名
对于map类型：
| 键值对容器 | 实现方式 | 键值 | 时间复杂度 | 是否有序 | 使用场景 |
|---|---|---|---|---|---|
unordered_map |
哈希表 | 键-值对 | 平均O(1) | 无序 | 快速查找键对应的值 |
map |
红黑树 | 键-值对 | O(logn) | 有序 | 需要有序键值对 |
unordered_set |
哈希表 | 键 | 平均O(1) | 无序 | 快速查找元素是否存在 |
set |
红黑树 | 键 | O(logn) | 有序 | 需要排序的集合 |
unordered_multimap |
哈希表 | 键-值 | 平均O(1) | 无序 | 有重复键且不关心顺序 |
对于本题
引用评论区大佬的解释：当前位置的元素比下个位置的元素小，就减去当前值，否则加上当前值。
定义键值对容器 <字符，整型>
分别对应罗马数字的字符和数值(注意字符变量加单引号);
int 结果变量；
int 罗马数字长度；
遍历罗马数字：
如果元素 当前位置<下一个位置：（注意使用值时加方括号[]）
结果变量-=值变量；
否则：
结果变量+=值变量；
返回结果；
AC代码
class Solution {
public:
unordered_map<char,int>mymap={
{'I',1},
{'V',5},
{'X',10},
{'L',50},
{'C',100},
{'D',500},
{'M',1000},
};
int romanToInt(string s) {
int ans=0;
int len=s.length();
for(int i=0;i<len;i++){
if(mymap[s[i]]<mymap[s[i+1]]){
ans-=mymap[s[i]];
}
else{
ans+=mymap[s[i]];
}
}
return ans;
}
};
58.最后一个单词的长度
给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词是指仅由字母组成、不包含任何空格字符的最大子字符串。
解题思路
【方法一】
我的思路是从后向前遍历字符串时：如果它的后一个是空格或空，自己不是空格，意味着句尾有空格，该下标是倒着数第一个不为空格的字母；如果前一个是空格或空，自己不是空格，代表这是词的开头，记录下标直接退出循环。最后长度就是二者相减。
但是这样写大多数样例不通过（悲
（二编）卧槽我改对了！！！
【方法二】
不对那就改呗：直接从字符串的尾部开始遍历，跳过所有尾部空格，直到遇到第一个非空格字符，并计算其长度。能够更好的处理边界情况。
int 长度=字符串长度;
int i=长度-1;
int 结果长度=0
当i大于等于0并且s的第i个字符为空格时：
i--；（倒着循环遍历）
*本题设定s不为空，若无此条件需在此判断：当i<0时直接返回（s为空）
当i大于等于0并且s的第i个字符不为空格时：
结果长度++；
i--；
返回结果长度;
AC代码
【方法一】
class Solution {
public:
int lengthOfLastWord(string s) {
int len=s.length();
int m=0,n=0;
for(int i=len-1;i>0;i--){
if(s[i]!=' ' && (s[i+1]==' ' || s[i+1]=='\0')){
m=i;
}
if((s[i-1]==' ' || s[i-1]=='\0') && s[i]!=' '){
n=i;
break;
}
}
return m-n+1;
}
};
【方法二】
class Solution {
public:
int lengthOfLastWord(string s) {
int len=s.length();
int ans=0;
int i=len-1;
while(i>=0 && s[i]==' '){
i--;
}
while(i>=0 && s[i]!=' '){
ans++;
i--;
}
return ans;
}
};
9.回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
解题思路
关键点
- 回文数是正整数
- 负数不是回文数
- 一个数的最后一位是0且这个数不为0，不是回文数
将数字的后半部分反转，用反转数字存储。最后的反转数字包含原始x的后半部分，x包含原始x的前半部分。
最后返回时：若原始x是偶数，那么对于回文数，x一定=反转数字。若原始x是奇数，那么反转数字会比x多一位，这一位是反转数字的个位并且是原始x的中位数，不影响回文数判断。所以先去掉个位再与当前的x比较。
如果（x小于0，或者x的个位不等于0且x不等于0）：
不是回文数；
定义反转数字=0；
当（x > 反转数字）：
反转数字=反转数字*10+x%10；
x/=10；
x = 反转数字
返回x = 反转数字 或者 x = 去掉个位的反转数字；
AC代码
class Solution {
public:
bool isPalindrome(int x) {
if(x<0 || (x%10==0 && x!=0)){
return false;
}
int num=0;
while(x>num){
num=num*10+x%10;
x/=10;
}
return x==num || x==num/10;
}
};
14.最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
解题思路
区区小简单，真是难倒我了。
这里总结力扣官方题解的纵向扫描方法。我一开始想的也是类似思路，奈何憋不出来代码。
关键点
- 最长公共前缀的长度不可能超过任何一个字符串的长度
- 数组strs的大小即为字符串的总个数
- 二维数组形式可以直接表示第i个字符的第j位
- 如果
i超出某个字符串的长度或**第j个字符串的第i个字符不等于c**时，直接返回当前的公共前缀。 - 循环结束说明所有字符串的所有字符都匹配，那么第一个字符串本身就是最长公共前缀，返回第一个字符串
strs[0]。
如果数组为空：
返回""；
int 长度变量=数组第一个字符串元素的长度；
int 计数变量=数组大小；
遍历i，从0到长度变量：
char 字符变量=第一个字符串的第i个字符；
遍历j，从1到计数变量：
如果（i==第j个字符串的大小 || 第j个字符串的第i个字符 ！= 字符变量）：
返回 第一个字符串的第一个字符~第i个字符；
返回 第一个字符；
AC代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(!strs.size()){
return "";
}
int len=strs[0].size();
int cnt=strs.size();
for(int i=0;i<len;i++){
char c=strs[0][i];
for(int j=1;j<cnt;j++){
if(i==strs[j].size() || strs[j][i]!=c){
return strs[0].substr(0,i);
}
}
}
return strs[0];
}
};
682.棒球比赛
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
- 整数 x - 表示本回合新获得分数 x
- “+” - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
- “D” - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
- “C” - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
解题思路
用int动态数组ans记录得分，但是不用i做索引来查询，而是用begin、end、size、back等方法来防止发生越界访问。
- 注意
string类型为字符串，用双引号””括起来，char类型为字符，用单引号’’。
前两次得分之和：size-1 +size-2
前一次得分：back
最近一次得分移除->出栈->pop_back
加入得分：压栈->push_back
字符串转整型：stoi
计算动态数组的和：accumulate
另外，我一开始想用unordered_map，做题做迷了。后来发现动态数组完全可以解决：C++ 标准库中的 vector 支持动态调整大小，可以方便地模拟栈的行为。而unordered_map 是用来存储键值对（key-value pairs）的哈希表。
本问题中不需要映射关系，所以并不需要用到 unordered_map。
还有，stack.push()和.pop()也可，但是vector.push_back()和.pop_back()也同样可以。那就选更常用的vector，何乐而不为呢？
AC代码
用时击败7%，悲。之后滚回来优化算法。
class Solution {
public:
int calPoints(vector<string>& operations) {
vector<int>ans;
for(string ch:operations){
if(ch=="+"){
ans.push_back(ans[ans.size()-1]+ans[ans.size()-2]);
}
else if(ch=="D"){
ans.push_back(ans.back()*2);
}
else if(ch=="C"){
ans.pop_back();
}
else{
ans.push_back(stoi(ch));
}
}
return accumulate(ans.begin(),ans.end(),0);
}
};
26.删除有序数组中的重复项
给你一个非严格递增排列的数组nums,请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回nums中唯一元素的个数。
考虑nums的唯一元素的数量为k，你需要做以下事情确保你的题解可以被通过：
- 更改数组nums，使nums的前k个元素包含唯一元素，并按照它们最初在nums中出现的顺序排列。nums的其余元素与nums的大小不重要。
- 返回 k 。
解题思路
int 最终数组长度=1;
遍历nums：
如果第i个元素不等于第i-1个元素：
nums[最终数组长度]=nums[i]；
最终数组长度++；
返回最终数组长度；
AC代码
妈呀这题一提交发现每ms都有解法…密密麻麻(ΩДΩ)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int ans=1;
for(int i=1;i<nums.size();i++){
if(nums[i]!=nums[i-1]){
nums[ans]=nums[i];
ans++;
}
}
return ans;
}
};
1922.统计好数字的数目
我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。
比方说，”2582” 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 “3245” 不是 好数字，因为 3 在偶数下标处但不是偶数。
给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 10^9 + 7 取余后返回 。
一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。
提示：
- 1 <= n <= 1015
解题思路
🤔一开始就被范围吓到了，这完全穷举不了啊，悲。
这道题不超时的话只能用数学方法了，快来和我一起看题解!
总结一下 对于长度为n的好数字字符串：
- 偶数下标个数
a=⌈n/2⌉=⌊(n+1)/2⌋
- 下标有五种可能：0、2、4、6、8
- 方案数
5^a*注意这里⌈ ⌉是向上取整，⌊ ⌋是向下取整。我也是最近才学到
- 奇数下标个数
b=⌊n/2⌋
- 下标有四种可能：2、3、5、7
- 方案数
4^b
- 可得总方案数为
(5^a)*(4^b)
到这里涉及到两个问题：
👉️快速幂
直接暴力pow必定超时/爆栈，所以需要快速幂。方法太神了…趁热打铁把50.Pow(x,n)一起拿下
x^n怎么快速算？
n转二进制后，从右往左遍历，遇到1就乘对应x的幂次。
比如13 = 1101：
那么x^13=x^(2^0)*x^(2^2)*x^(2^3)=x*x^4*x^8。
👉️取模
因为题目要算的答案特别大以至于超出64位整数的范围，所以要求对
10^9 + 7取模。
这里好多数学公式😫先把代码总结copy过来
MOD = 1_000_000_007
// 加
(a + b) % MOD
// 减
(a - b + MOD) % MOD
// 把任意整数 a 取模到 [0,MOD-1] 中，无论 a 是正是负
(a % MOD + MOD) % MOD
// 乘（注意使用 64 位整数）
a * b % MOD
// 多个数相乘，要步步取模，防止溢出
a * b % MOD * c % MOD
// 除（MOD 是质数且 b 不是 MOD 的倍数）
a * qpow(b, MOD - 2, MOD) % MOD
完整代码
class Solution {
public:
const long long mod=1e9+7;
//快速幂：计算base^exp
long long ModPow(long long base,long long exp){
long long res=1;
while(exp){
if(exp%2==1){//当前位是1
res=(res*base)%mod;
}
base=(base*base)%mod;//base^2是base的下一步幂
exp/=2;
}
return res;
}
//主函数
int countGoodNumbers(long long n) {
long long a,b;
a=(n+1)/2;
b=n/2;
return (ModPow(5,a)*ModPow(4,b))% mod;
}
};
50.Pow(x,n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。
提示：
- -100.0 < x < 100.0
- 231 <= n <= 231-1
- n 是一个整数
- 要么 x 不为零，要么 n > 0 。
- -104 <= xn <= 104
解题思路
详见上一题~这里还涉及到：
- n为负数
把n变成-n，x变为1/x。 - n=(−2)^31
此时n取反会超出int最大值，可以转为64位int。
另外，关键代码灵神的更简洁，放在这里学习一下：
while (n) { // 从低到高枚举 n 的每个比特位
if (n & 1) { // 这个比特位是 1
ans *= x; // 把 x 乘到 ans 中
}
x *= x; // x 自身平方
n >>= 1; // 继续枚举下一个比特位
}
完整代码
class Solution {
public:
double myPow(double x, int N) {
double res=1;
long long n=N;
while(n){
if(n<0){
n=-n;
x=1/x;
}
if(n%2==1){
res=(res*x);
}
x=x*x;
n/=2;
}
return res;
}
};
