力扣hot100+每日一题等
Updated
•42 min read287.寻找重复数
class Solution {
public:
int findDuplicate(vector<int>& nums) {
/*
思路：使用XOR来解决，先XOR所有的数 然后在遍历一遍1-n 然后相同的数会相同的抵消 然后最后抵消就剩下
哪个多出来的重复数
这个方法不行，因为可能存在同一个数但是其重复多次 因此我们这里应该需要判环算法
*/
int slow=nums[0];
int fast=nums[nums[0]];
//先判断是否有环
while(slow!=fast){
slow=nums[slow];
fast=nums[nums[fast]];
}
//然后寻找环的入口
fast=0;
while(fast!=slow){
slow=nums[slow];
fast=nums[fast];
}
return slow;
}
};
为什么会用到判环这样的操作以及为什么这里fast与slow同时走一步就可以在环的入口相遇Floyd判圈算法
31.下一个排列
class Solution {
public:
void nextPermutation(vector<int>& nums) {
/*
题目理解：就是将当前的数据中的所有数据拼成一个数，然后呢？对数组里面的元素作全排列，然后来找到大于它的最小数
如果当前元素已经是最大数了 那么就给出最小的排列
那么这里最优先的办法当然是直接从个位开始看起 如果个位的数大于前一位就与前一位互换 这样我觉得是最接近最小差距的做法
但是上面属于最理想的情况，我觉得一共有这样的几中情况：
1.就是我的最后一位恰好就比前一位大 比如 1 2 3 那么我就直接交换就行 ----->1 3 2
2.那如果我的当前位比前一位小 但是前一位又比前前一位大呢 比如 1 3 2 -->那么这时候如果在直接这样根据刚刚的进行交换 那么就会是3 1 2这样但是实际情况是我们应该得到的最小的下一个排列应该是2 1 3 这里我并没有想到更好的解法 如果进行全排列的话 那么肯定会超市的
*/
for(int i=nums.size()-1;i>0;i--){
if(nums[i-1] < nums[i]){
//记录下来当前的i-1位置 这是我们需要替换的位置
int replace=i-1;
//然后从后面再次遍历，选择一个比当前数据大 但大的最有限的哪个数来做替换
for(int j=nums.size()-1;j>replace;j--){
if(nums[j]>nums[replace]){
swap(nums[replace],nums[j]);
break;
}
}
//然后翻转后面的 让其升序排列
reverse(nums.begin()+replace+1,nums.end());
return;
}
}
reverse(nums.begin(),nums.end());
}
};
73.颜色分类
class Solution {
public:
void sortColors(vector<int>& nums) {
/*
解决思路：这里我在想可以使用这样的方式不 就是使用一个双指针 从前扫描和从后扫描
如果在后面碰见0了 就放前面去 如果在前面碰见2了 就放到后面去 然后如果是已经处于该有的位置就跳过
这样不用管1 因为我觉得他会与0或者2 调换位置 只要0 2 位置合理 那么自然1的位置也合理
如果比如在前面我们想要找到2与后面的0换 那么前面出现了1 那么就在扫描一段 找到一个2来先与1换 然后在与0换
但是这样会出现问题 就是我们交换过来的时候 还会进行检查 这样会出现问题 因此这里如果采用三指针会更好
*/
int left=0,right=nums.size()-1,current=0;
while(current<=right){
if(nums[current]==0){
swap(nums[current++],nums[left++]);
}else if(nums[current]==2){
swap(nums[current],nums[right--]);
}else{
current++;
}
}
}
};
169.多数元素
class Solution {
public:
int majorityElement(vector<int>& nums) {
/*
解法：我在想这里可以这样解决不 就是模仿栈的用法
就是我使用一个pre来记录我目前记录的数组 然后count来记录他的个数 然后最后输出pre
如果遇到相同的则pre不变 count++ 如果遇到不同的 则count-- pre等count减完再减
*/
sort(nums.begin(),nums.end());
int pre=nums[0],count=1;
for(int i=1;i<nums.size();i++){
if(nums[i]==pre){
count++;
}
if(nums[i]!=pre) count--;
if(count<=0) pre=nums[i];
}
return pre;
}
};
//这个解法其实摩尔投票法 其实只需要我for里面的逻辑就可以
class Solution {
public:
int majorityElement(vector<int>& nums) {
// 不需要排序！
int candidate = nums[0];
int count = 1;
for(int i = 1; i < nums.size(); i++) {
// 如果计数器为0，说明前面的都抵消完了，换当前的数为候选人
if(count == 0) {
candidate = nums[i];
count = 1;
}
// 如果遇到相同的数，票数+1
else if(nums[i] == candidate) {
count++;
}
// 如果遇到不同的数，票数-1（抵消）
else {
count--;
}
}
return candidate;
}
};
136.只出现一次的数字
class Solution {
public:
int singleNumber(vector<int>& nums) {
//这里可以使用异或来解决问题 最后剩的那个元素一定就是指出现一次的元素
int xor_num=0;
for(int i=0;i<nums.size();i++){
xor_num^=nums[i];
}
return xor_num;
}
};
32.最长有效括号
你的直觉非常敏锐！简单直接地回答你：
你的思路（暴力解法）确实不可行，一定会超时 (Time Limit Exceeded)。
我来帮你详细分析一下原因，并给出更适合这道题的解法（动态规划或栈）。
1. 为什么你的思路会超时？
你的思路可以归纳为：“遍历所有可能的子串 -> 对每个子串检查有效性 -> 更新最大值”。
子串数量： 一个长度为 $N$ 的字符串，大约有 $N^2/2$ 个子串。
检查耗时： 检查一个子串是否有效（入栈出栈），平均需要 $O(N)$ 的时间。
总复杂度： $O(N^2) \times O(N) = O(N^3)$。
结合题目数据范围： 题目提示中 s.length <= 3 * 10^4。 如果O(n³)的算法：$(30000)^3 = 2.7 \times 10^{13}$次运算。 通常 LeetCode 的时间限制在 1 秒左右，大概只能处理 $10^8$ 次运算。你的算法超出了大概 10万倍，所以必挂无疑。
2. 应该怎么做？（两种主流优选方案）
这道题是经典的 Hard 题目，考察的是线性时间 $O(N)$ 的解法。既然你提到了 DP（动态规划）和栈，这正是解这道题的两个核心方向。
方案一：真正的动态规划 (DP)
你之前的想法其实是“暴力枚举+检查”，而不是利用 DP 的“状态转移”。真正的 DP 不需要重复检查内部的括号，而是利用前面已经算好的结果。
定义： dp[i] 表示 以索引 i 结尾的 最长有效括号子串的长度。
推导公式：
如果
s[i] == '('：以左括号结尾不可能构成有效子串，dp[i] = 0。如果
s[i] == ')'：情况 A：
s[i-1] == '('（形如......()）。这组成了一对，长度至少是 2。
加上这一对之前的有效长度：
dp[i] = dp[i-2] + 2。
情况 B：
s[i-1] == ')'（形如......))）。这说明前面有一段有效子串
......)，长度为dp[i-1]。我们需要去查看这段有效子串 前面那一个字符 是否是
(。如果是，说明把整个包起来了。
dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2](最后这项是把更前面的也连起来)。
代码示例 (C++)：
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.length();
if (n == 0) return 0;
// dp[i] 代表以 s[i] 结尾的最长有效括号长度
vector<int> dp(n, 0);
int maxLen = 0;
for (int i = 1; i < n; i++) {
if (s[i] == ')') {
if (s[i - 1] == '(') {
// 情况 A: ...()
dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
} else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
// 情况 B: ...))，且前面的有效串之前有个 '('
// 这里的逻辑是：内部长度 + 2 (外层这对) + 这一大坨之前的有效长度
dp[i] = dp[i - 1] + 2 + ((i - dp[i - 1] >= 2) ? dp[i - dp[i - 1] - 2] : 0);
}
maxLen = max(maxLen, dp[i]);
}
}
return maxLen;
}
};
方案二：栈 (Stack) - 更符合直觉
这就利用了你提到的“送入一个栈来检查”的思路，但我们不是检查整个子串，而是只存储下标来计算长度。
思路：
栈底垫一个
-1（作为参照物，表示“上一个没被匹配的右括号的下标”）。遇到
(：把下标压入栈。遇到
)：弹出栈顶。
如果栈空了：说明这个
)没匹配到左括号，把它作为新的“参照物”压入栈。如果栈不空：说明匹配成功！当前长度 =
当前下标 i - 栈顶下标。更新最大值。
代码示例 (C++)：
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> st;
st.push(-1); // 放入哨兵，方便计算长度
int maxLen = 0;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '(') {
st.push(i); // 存下标
} else {
st.pop(); // 尝试匹配
if (st.empty()) {
// 栈空了，说明这个 ')' 多余了，它变成了新的分割点
st.push(i);
} else {
// 匹配成功，计算长度：当前位置 - 栈顶位置
maxLen = max(maxLen, i - st.top());
}
}
}
return maxLen;
}
};
总结建议
对于你的思路： 只要看到数据范围是 $10^4$ 级别，算法复杂度必须控制在 $O(N)$ 或 $O(N \log N)$。$O(N^3)$ 的暴力检查法可以直接放弃。
推荐解法： 栈的方法（方案二）通常更容易理解和现场写出来，逻辑也更接近你原本想用栈的直觉。
152.乘积最大数组
class Solution {
public:
int maxProduct(vector<int>& nums) {
/*
解题思路：要非空 要连续 这种怎么搞咧
动态规划思路：
1.首先，明确应该怎样来定义dp数组 $dp[i]$ 必须表示以 nums[i] 这个数 结尾 的连续子数组的最大乘积。
2.确定递推公式：
这里我们需要保证我门记录的乘积最大子数组是连续的 但是又不能一碰到负数就不干了 万一下一个也是负数呢 所以
这里应该怎么办
维护两个状态 一个是以当前nums[i]结尾的最大子数组 一个是以当前nums[i]结尾的最小的子数组
Maxdp Mindp
然后在面临一个nums[i]时我们更新Maxdp数组需要这样来定义递推公式：
（1）如果是nums[i]重开户籍的话，就为nums[i]
（2）如果是nums[i]和前面的最大积相乘【此时我们期待nums[i]为正】
（3）如果是nums[i]和前面的最小积相乘【此时我们期待nums[i]为负】
递推公式为Maxdp[i]=max(nums[i],max(nums[i]*maxdp[i],Mindp[i]*nums[i]))
同理，这里我门也需要更新Mindp
（1）单独成数组
（2）与前面的最大数相乘 此时期望是nums[i]为负
（3）与前面的最小数相乘 此时期望nums[i]为正
3.首先这里初始化：可以dp[i]=nums[i] 因为抛开别的不谈 其首要的最大乘积子数组就是只有自己
*/
int n=nums.size();
vector<int> Maxdp(n,0);
vector<int> Mindp(n,0);
Maxdp[0]=nums[0];Mindp[0]=nums[0];
for(int i=1;i<n;i++){
//更新Maxdp
Maxdp[i]=max(nums[i],max(nums[i]*Maxdp[i-1],Mindp[i-1]*nums[i]));
Mindp[i]=min(nums[i],min(nums[i]*Maxdp[i-1],Mindp[i-1]*nums[i]));
}
//然后便利Maxdp 找出最大
int rel=nums[0];
for(int i=0;i<n;i++){
if(Maxdp[i]>rel) rel=Maxdp[i];
}
return rel;
}
};
139.单词拆分
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
/*
使用动态规划：
1.确定dp数组的含义：dp[i]代表以nums[i]结束的字符串是否能够被wordDict里面的单词拼接而成
2.确定递推公式，这里直接将当前的dp[i]作true就行
3.初始化dp[0]=true 因为空字符串不需要拼
4.遍历顺序这里其实我认为我们应该外围遍历背包 不过我觉得这里我们并不需要在意是不是排列因为这里只是需要求出一种可以让dp[n]=true的解法而已
*/
int n=s.size();
vector<bool> dp(n+1,false);
dp[0]=true;
for(int i=1;i<=n;i++){
for(const string& word : wordDict){
//查找当前的位置是否可以被一个单词拼接上
int len=word.size();
if(i>=len && dp[i-len] && s.substr(i-len,len)==word){
dp[i]=true;
break;
}
}
}
return dp[n];
}
};
这道题是 LeetCode 139. 单词拆分 (Word Break)。你的代码使用的是非常标准的 动态规划 (Dynamic Programming) 解法，逻辑是完全正确的。
下面我为你详细拆解：为什么这么做、这里的 substr 逻辑是怎么回事，以及这道题容易踩的“坑”。
1. 为什么要用动态规划？这道题的核心是一个 “决策问题”（能不能拼出来？），而且具有 “最优子结构”。
我们可以把大问题拆成小问题：
大问题：字符串
s的前 i 个字符能不能被拼出来？（即dp[i]）怎么解决：如果我知道字符串的最后一段是一个字典里的单词（比如长度为
len），那么我只需要知道 “去掉这段单词后，剩下的前面部分” 能不能被拼出来即可。
举个例子： s = "leetcode", wordDict = ["leet", "code"]
你想知道 dp[8] ("leetcode") 是否为 true：
你发现结尾是 "code" (长度4)。
问题转化为：
dp[4]("leet") 是 true 吗？如果
dp[4]是 true，且 "code" 在字典里，那么dp[8]就是 true。
这就是一种 “回望过去” 的思想：站在当前位置 i，回头看一看，能不能切一刀，切下来的后半段是单词，且前半段也是合法的。
2. 这里的 substr 逻辑详解你的核心判断代码如下：
if(i >= len && dp[i-len] && s.substr(i-len, len) == word)
这一行代码其实做了 三件事，我们用图解来解释。
假设 s = "applepen", 当前 i 遍历到了 5 (即对应子串 "apple")，正在尝试匹配单词 word = "apple" (长度 len = 5)。
dp数组定义：dp[i]表示长度为i的前缀是否合法。s的下标：字符串下标是从0开始的。
逻辑拆解：
i >= len:
- 含义：这是边界检查。你要切掉长度为
len的尾巴，首先你当前的字符串长度i得比len大或者相等吧？不然不够切。
s.substr(i - len, len) == word:
含义：检查尾巴。
i是当前考虑的子串长度。i - len是这一段单词在字符串s中的起始下标。这句代码的意思是：从字符串
s的下标i-len开始，截取长度为len的字符，看看它是不是等于当前的word。例子：
i=5,word="apple",len=5。s.substr(5-5, 5)即s.substr(0, 5)，取出来是 "apple"，匹配成功。
dp[i - len]:
含义：检查前面那部分。
就算尾巴匹配上了单词，前面剩下的部分（长度为
i-len）也必须是合法的，当前的i才能合法。这是状态转移的关键。类似于多米诺骨牌，前一块倒了，这一块才能倒。
3. 这道题的“坑”与注意事项虽然你的代码写对了，但这道题在面试或练习中，有几个常见的坑：
坑一：完全背包的“排列”与“组合”误区（你注释里提到的）你在注释里写道：“我认为我们应该外围遍历背包...并不需要在意是不是排列”。
事实是：这道题确实是一个 完全背包问题（单词可以重复使用），而且强调 顺序（即“排列”）。
比如
s = "applepen", 先有apple再有pen。你不能用pen+apple拼出来。循环顺序：
外层遍历背包（
i从 1 到n），内层遍历物品（wordDict）：这是求 排列 的标准写法。因为对于每一个长度i，我们都尝试了所有的单词作为结尾，这就隐含了顺序。你的写法正是这种，完全正确。如果反过来（外层遍历
wordDict，内层遍历i）：那是求 组合。对于字符串拼接来说，这通常是错的，因为这会限制单词出现的相对顺序（比如先处理了 "apple"，这辈子就再也没机会在 "apple" 前面加东西了）。
坑二：下标对齐 (Index Alignment)* dp 数组的大小是 n + 1，而字符串 s 的下标是 0 到 n-1。
dp[i]对应的是s的前i个字符，其最后一个字符的下标是i-1。初学者很容易在这里搞混，导致
substr的参数传错，或者数组越界。你的代码用i-len处理得很好。
坑三：时间复杂度* 你的写法中，内层循环遍历 wordDict，然后做字符串比较。
最坏时间复杂度大约是 O(n \times m \times k)，其中 n 是字符串长度，m 是字典大小，k 是单词平均长度（因为
substr和字符串比较也需要时间）。坑：如果字典非常大，或者单词非常长，这种暴力遍历字典的方法可能会慢。
优化方向（了解即可）：有时候为了加速，会将内层循环改为“枚举分割点
j”，或者使用 字典树 (Trie) 来加速单词匹配，避免每次都遍历整个wordDict。但在 LeetCode 这道题的数据规模下，你的写法是完全可以通过的。
总结你的代码逻辑非常清晰：
初始化：
dp[0]=true（空串默认合法）。推进：从小到大计算每个长度
i是否合法。判断：对于每个长度
i，尝试用字典里的每个单词当作“结尾后缀”，如果 后缀匹配 且 去掉后缀的前面部分也合法，则dp[i] = true。
这也是解决此类字符串分割问题的通用模板。继续保持！
322.零钱兑换
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
/*
零钱兑换：我们要最少硬币数 那么就这样也是一种排列组合的结果 然后我们还是需要外围是背包 内围是coins
然后还是需要使用动态规划：
1.确定dp数组下标以及含义： dp[i]代表当前的金额可以使用最少的coins数来组成 然后这里我们默认为初始化为-1 不能够被零钱兑换
2.确定递推公式：dp[i]=min(dp[i],dp[i-coin]+1)
3.初始化：INT_MAX dp[0]=0
4.遍历顺序应该是外围是背包 内卫是coins
*/
vector<int> dp(amount+1,INT_MAX);
dp[0]=0;
for(int i=0;i<=amount;i++){
for(auto& coin : coins){
if(i >= coin && dp[i-coin]!=INT_MAX){
dp[i]=min(dp[i],dp[i-coin]+1);
}
}
}
return dp[amount]==INT_MAX ? -1:dp[amount];
}
};
279.完全平方数
class Solution {
public:
int numSquares(int n) {
/*
完全平方数：与后面的最小硬币数的解法一样
*/
vector<int> dp(n+1,INT_MAX);
dp[0]=0;
for(int i=0;i<=n;i++){
for(int j=1;j*j <=i ;j++){
if(i>=j*j && dp[i-j*j]!=INT_MAX){
dp[i]=min(dp[i],dp[i-j*j]+1);
}
}
}
return dp[n];
}
};
198.打家劫舍
class Solution {
public:
int rob(vector<int>& nums) {
/*
解题思路：一个房屋有两种的状态，要么被偷要么不被偷，而当前的房屋的状态基于前一个房屋的状态，也就是前一个房屋是否被偷
这里我认为可以定义一个两个空间的dp数组，dp[0]代表偷当前房子，dp[1]代表不偷当前房子的最大金额
动态规划五部曲：
1.定义dp数组含义以及下标的含义，dp[0]代表当前房子被偷的最大金额，dp[1]代表当前房子不被偷的最大金额
2.定义递归公式：当前的dp[0]=之前的dp[1]+当前房子的金额，dp[1]=之前的dp[0],dp[1]中的大值，因为我这一家不透，那么我前一天偷还是不透其实都无所谓 这样交替的进行 最后返回dp[0]与dp[1]中最大的那个值
*/
vector<int> dp(2,0);
dp[0]=nums[0];
dp[1]=0;
for(int i=1;i<nums.size();i++){
int dp_0=dp[1]+nums[i],dp_1=max(dp[0],dp[1]);
dp[0]=dp_0;dp[1]=dp_1;
}
return dp[0]>dp[1]?dp[0]:dp[1];
}
};
118.杨辉三角
class Solution {
public:
vector<vector<int>> generate(int numRows) {
/*
解题思路：这里我我们需要将题意抽象一下 找出左上方和右上角的下标的规律
可以这样的思路吗 就是当前的数值就是当前的dp[i][j]=dp[i-1][j-1%dp[i-1].size()]+dp[i-1][j+1%dp[i-1].size()] 然后如果是第0列以及最后一列就是1
*/
vector<vector<int>> rel(numRows);
for(int i=0;i<numRows;i++){
//先扩展大小
rel[i].resize(i+1);
//然后先定边界
rel[i][0]=1;
rel[i][i]=1;
//然后开始循环
for(int j=1;j<i;j++){
rel[i][j]=rel[i-1][j-1]+rel[i-1][j];
}
}
return rel;
}
};
763.划分字母区间
class Solution {
public:
vector<int> partitionLabels(string s) {
/*
解题思路：第一，我们要把一个字符串划分到尽可能多的片段，然后就是同一个字母最多出现在一个片段中，那么我认为
其实这里就是需要记录一下每一个字母的开始以及结束位置
比如就是在一个片段内，包含有两个字母，那么其结束位置自然是选择较长的那一个，同时还需要按照顺序划分
那么先将数组的下标进行统计，记录每一个下标的位置
不过我觉得这样效率很低，既然是贪心算法，那么我觉得这里确实好像不能通过一次的for循环就能够解决 因为贪心算法是选择局部最优
然后进而全局最优，这里如果一个for循环来进行全局的考虑会丧失对于其他位置的观察我认为
*/
int last[26]={0};
for(int i=0;i<s.size();i++){
last[s[i]-'a']=i;
}
vector<int> rel;
int left=0,right=0;
for(int i=0;i<s.size();i++){
right=max(right,last[s[i]-'a']);
if(i==right){
//表示已经走到当前出现的字符中的最远位置了 可以进行划分了 这里之所以没有维护一个左边界 其实就是我们这里隐含了我门如果在这个片段里包含了假设你认为应该是下一个片段的字符，那么我们的右边界就会更新 因此我们在这里就不需要再显式的维护一个左边界了
rel.push_back(right-left+1);
left=i+1;
}
}
return rel;
}
};
45.跳跃游戏||
class Solution {
public:
int jump(vector<int>& nums) {
/*
解题思路：这个跳跃游戏这里每一步可以达到的最远的跳跃路径 然后这里要求求最小的跳跃数 那么
我们就需要每次尽可能的跳多一点？怎样来设计呢？如果我跳到中间发现有比我现在能够达到的更远的目的地的我就更新吗？
不是，如果是这样的话，那我们中间岂不是每次遇到一个更大的就会去更新吗？这样的话，是不准确的，我认为，我们走的每一步
还没有发挥出最大价值的时候，我们就急于跳出下一步，并且当你在原地想要更新的时候，他们的比较也不是对等的
因此我们应该第一，把每一步发挥出的价值发挥到极致，不走完不罢休
第二，为了防止频繁的更新，我门应该只是维护一个最远边界，代表当前的最优决策
*/
if(nums.size()==1) return 0;
int steps=0;
int curend=0;
int maxpos=0;
for(int i=0;i<nums.size()-1;i++){
maxpos=max(maxpos,i+nums[i]);
if(i==curend){
curend=maxpos;
steps++;
}
}
return steps;
}
};
55.跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
/*
判断能不能达到最后一个位置 就是看我们最后的维护的最远边界是否等于这个nums.size()-1
*/
if(nums.size()==1) return true;
int cuernd=0;
int maxpos=0;
for(int i=0;i<nums.size()-1;i++){
maxpos=max(maxpos,i+nums[i]);
if(i==cuernd){
cuernd=maxpos;
}
}
return cuernd>=nums.size()-1;
}
};
121.买卖股票的最佳时机
你的思考非常敏锐，特别是你意识到了**“顺序”的重要性（即“卖出必须在买入之后”），并且提出了“双指针”**的想法。这完全是在正确的轨道上！
我们可以把你现在的思路稍微梳理一下，就会发现它其实就是这道题的最优解法——贪心算法（或者说是动态规划的一种简化形式）。
1. 深度解析你的疑问
你的疑问： “如果卖股票的最大值出现在了买股票的之前怎么解决？比如这里的[7,1,5,3,6,4]”
回答： 这正是我们需要从左向右遍历的原因。我们不能简单地找整个数组的最大值和最小值。我们需要找的是当前这一天之前出现的那个最小值。
2. 关于你“双指针”的直觉
你说想用双指针，这完全可行！我们可以这样定义这两个指针：
左指针（Buy）：指向历史上（即遍历过的天数里）价格最低的那一天。
右指针（Sell）：指向当前正在考虑卖出的那一天（也就是遍历到的当前元素）。
逻辑推演： 想象你在遍历数组（右指针 i 一直往右走）：
- 如果
prices[i]比prices[buy]还低：
说明你发现了一个更便宜的买入时机！
这时候，你应该更新左指针，把买入价换成这个更低的。因为对于未来的日子来说，从这里买肯定比从之前的那个点买赚得多。
- 如果
prices[i]比prices[buy]高：
说明这时候卖出是能赚钱的。
你计算一下利润
prices[i] - prices[buy]，看看是不是比之前记录的maxProfit还要大，如果是就更新记录。
3. 优化思路：从“双指针”到“一次遍历”
其实，我们在写代码时，不需要真的维护一个 left 指针下标，只需要维护一个变量 minPrice（历史最低价）即可。这其实就是隐式的左指针。
核心逻辑： 我们在遍历每一天的价格时，只做两件事：
你是最低价吗？ 如果当前价格比我之前见过的最低价还低，那我肯定要在今天买入（更新
minPrice）。今天卖能赚大钱吗？ 如果当前价格不比最低价低，那我就算算今天卖能赚多少（
当前价格 - minPrice），如果比之前的历史最高利润还高，我就更新利润。
4. 你的代码实现模板
基于你的思路，代码可以写得非常简洁：
class Solution {
public:
int maxProfit(vector<int>& prices) {
// 1. 初始化
// minPrice 就像你的左指针，时刻记录着目前为止遇到的最低价格
// 初始化为一个最大值，或者 prices[0]
int minPrice = INT_MAX;
int maxProfit = 0;
// 2. 遍历每一天（这就相当于你的右指针在移动）
for (int i = 0; i < prices.size(); i++) {
if (prices[i] < minPrice) {
// 情况一：发现更低的价格，更新买入点
// 这里的含义是：如果我以后要卖，肯定是用这个价格买成本最低
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
// 情况二：当前价格比最低价高，算算利润
// 如果利润比之前记录的还高，就更新最高利润
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
}
};
5. 总结
你的直觉是对的：
必须考虑顺序：通过一次遍历，边走边更新最低价，自然解决了“最高价在最低价之前”的问题（因为我们只拿当前价格去减之前的最低价）。
双指针思想：
minPrice是左指针（固定在历史最低点），循环变量i是右指针（不断探索新的卖出机会）。
你可以试着按照这个逻辑把代码补全，这道题就拿下了！
215.数组中第K个最大的元素
//大顶堆逻辑
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
/*
使用优先级队列来解决问题，这里我们需要的是在自己定义一个比较函数-->来告诉优先级队列我的较大的数值
排前面，然后再依次取出第K个元素就好
*/
priority_queue<int> pre_que;//默认为大顶堆
//然后依次将数组中的数据取出放到pre_que中
for(int i=0;i<nums.size();i++){
pre_que.push(nums[i]);
}
//然后倒序取出第k各元素
int rel=-10001;
while(k--){
rel=pre_que.top();pre_que.pop();
}
return rel;
}
};
//小顶堆逻辑
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
/*
使用优先级队列来解决问题，这里我们需要的是在自己定义一个比较函数-->来告诉优先级队列我的较大的数值
排前面，然后再依次取出第K个元素就好
*/
priority_queue<int,vector<int>,greater<int>> min_pre;
for(auto num:nums){
min_pre.push(num);
if(min_pre.size()>k) min_pre.pop();
}
return min_pre.top();
}
};
347.前K个元素
class Solution {
public:
// 1. 定义一个仿函数（结构体），用于比较逻辑
struct Compare {
bool operator()(pair<int, int>& a, pair<int, int>& b) {
// 我们需要小顶堆，意味着频率小的在堆顶
// C++ priority_queue 默认是大顶堆，根据 comparator 规则：
// 如果返回 true，b 会排在 a 前面（或者理解为 a 的优先级比 b 低）
// 这里我们需要 second (频率) 小的优先级高（浮在堆顶），所以要反着写
return a.second > b.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 使用 map 统计频率
unordered_map<int, int> mymap;
for (int num : nums) {
mymap[num]++;
}
// 2. 定义优先级队列
// 参数：<数据类型, 容器类型, 比较方法>
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> min_que;
// 遍历 map
for (auto& t : mymap) {
min_que.push(t);
// 3. 维护堆的大小为 k
// 如果超过 k，就把堆顶（频率最小的那个）弹出去
// 剩下的自然就是频率最大的 k 个
if (min_que.size() > k) {
min_que.pop();
}
}
// 4. 取出结果
vector<int> rel;
while (!min_que.empty()) {
rel.push_back(min_que.top().first);
min_que.pop();
}
return rel;
}
};
295.数据流的中位数
class MedianFinder {
public:
/*
解题思路：这道题的难点是我取得是中位数，但是中位数是需要数组在排序的前提下进行计算的
因此我们这道题需要的就是维护动态的有序 但是应该怎样维护呢？如果我单纯的维护一个大顶堆或者是一个小顶堆
那么我后面弹出数据也还是需要一个个弹出 这样时间上仍然会超时 不符合困难题对时间开销的要求
因此这里我们需要使用一个大顶堆以及一个小顶堆 而大顶堆里放较小的元素 小顶堆里放较大的元素，这样我们才能够直接从堆顶
拿出中间的元素
*/
priority_queue<int> max_que;
priority_queue<int,vector<int>,greater<int>> min_que;
MedianFinder() {
}
void addNum(int num) {
//这里的放入放顺序很有讲究 先将元素放入大顶堆 然后在将堆顶的元素放到小顶堆 并维持平衡
max_que.push(num);
min_que.push(max_que.top());
max_que.pop();
if(max_que.size() < min_que.size()){
max_que.push(min_que.top());
min_que.pop();
}
}
double findMedian() {
//如果大顶堆多一个
if(max_que.size() > min_que.size()) return max_que.top();
return (max_que.top()+min_que.top())/2.0;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/
20.有效的括号
class Solution {
public:
bool isValid(string s) {
/*
解题思路：使用栈来模拟，我们只将左括号放入到栈中
如果匹配上一个就继续
这里需要记录的是几种异常情况，这些清况下，我们就返回false
1.如果我目前的s[i]是右括号，但是栈中已经没有左括号进行匹配了，那么就false【右括号多】
2.如果匹配完了 栈中还有元素 那么就false【左括号多】
3.还有就是弹出来的不匹配
但是这样来解决这道题我们会限于写一堆的if-else的判断条件，不如这样，在我们遇到左括号的时候，就将右括号压入栈
最后，遇到右括号的时候我们就直接来进行匹配，这样可以简化对比的流程，这样如果不匹配直接下课
*/
if(s.size()%2==1) return false;
stack<char> st;
for(int i=0;i<s.size();i++){
if(s[i]=='(') st.push(')');
else if(s[i]=='[') st.push(']');
else if(s[i]=='{') st.push('}');
else if(st.empty() || st.top()!=s[i]){
return false;
//这里就代表着我说的第一号和第三号清况
}
else{
st.pop();
}
}
return st.empty();//第二号情况
}
};
155.最小栈
class MinStack {
public:
/*
解题思路：这里这个题应该怎么解决？咋一看，是需要在这样minstack里面封装一个
小顶堆，但是这里我们还需要考虑的是什么呢？如果我正常的弹出堆顶的元素，那么我
在小顶堆中如何进行设计，这样只能是一个个弹出了怎么办？
那我只使用一个数字来存储好像也不太行，因为如果我的这个最小值刚好是栈顶，那么就需要进行最小值的更新
这里我干脆就使用一个双端队列吧 最小的一直在前面 大的在后面
经过使用小顶堆的使用，发现AC不了，这里想到的问题是：第一，使用小顶堆固然可以让我们对于最小值有记忆功能，
但是其本身的时间复杂度是我们不能接受的，并且堆（Heap）无法像栈一样“后进先出”地精确撤销操作，导致非最小值的删除会破坏数据一致性。
*/
stack<int> st;
stack<int> min_st;
MinStack() {
min_st.push(INT_MAX);
}
void push(int val) {
//首先将其压入栈
st.push(val);
if(val<=min_st.top())
min_st.push(val);
}
void pop() {
//这里如果是栈顶的元素恰好是最小元素 才对小顶堆进行更新
if(st.top()==min_st.top()){
min_st.pop();
}
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return min_st.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
349.字符串解码
class Solution {
public:
string decodeString(string s) {
/*
对于这一个题，咋一看可能感觉迷糊，但是我们剖析一下
发现这道题就是说如果我出现了k[]这样的组合，那么[]里面的字符串
重复k次 然后有这样的输入我们才进行这样的组合，如果没有就不加
这里我们可以采用一个栈来维持[]的下标，方便给出索引进行子串的分割
但是这里我门在编码上，就不能只是简单的认为下一个出现的不是字母的字符就是] 因为这里还有嵌套的
情况 那么这里我们需要维护两个栈，一个栈维护我们遇到[前的已经构造好的字符串，同时维护这个[]前的数字在一个k_st中
*/
stack<int> nums_st;
stack<string> strs_st;
string current_str="";//记录当前正在处理的字符串
int current_num=0;//记录当前计算的倍数
for(int i=0;i<s.size();i++){
char c=s[i];
if(c>='0' && c<='9'){
//如果是数字我们就可以通过这个来处理多位数的情况
current_num=current_num*10+(c-'0');
}else if(c=='['){
//遇到了左括号，那么我就需要将倍数以及当前已经构造的字符串加入到栈
nums_st.push(current_num);
strs_st.push(current_str);
//然后置为初始状态
current_num=0;
current_str="";
}else if(c==']'){
//那么就是需要将当前的current_str*current_num+pre_str
int k=nums_st.top();nums_st.pop();
string pre_str=strs_st.top();strs_st.pop();
//然后乘以倍数
for(int j=0;j<k;j++){
pre_str+=current_str;
}
//更新current_str
current_str=pre_str;
}else{
//否则就是普通字符 直接加入
current_str+=c;
}
}
return current_str;
}
};
84.柱状图中最大的矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
/*
题意理解：这个柱状图 我们需要勾勒出最大的的矩形 那么就按照木桶原理
应该按照最矮的柱子来进行计算 每次往栈里放进去小的 就是这样的情况
第一，如果当前遍历的元素系小于栈顶元素 那么就弹出栈顶元素 将这个加入进去
第二，如果当前的元素大于栈顶元素 那么就弹出栈顶元素 计算当前的矩形面积 并更新
第三，如果当前的元素等于栈顶元素 那么就更新栈顶元素的下标
其中2和3 可以归结为一类 都需要更新max_rel
*/
int result = 0;
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
// 第一个元素已经入栈，从下标1开始
for (int i = 1; i < heights.size(); i++) {
if (heights[i] > heights[st.top()]) { // 情况一
st.push(i);
} else if (heights[i] == heights[st.top()]) { // 情况二
st.pop(); // 这个可以加，可以不加，效果一样，思路不同
st.push(i);
} else { // 情况三
while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是while
int mid = st.top();
st.pop();
if (!st.empty()) {
int left = st.top();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = max(result, w * h);
}
}
st.push(i);
}
}
return result;
}
};
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
/*
题意理解：在这个题中我们其实可以采用一个中心扩散法，就是假设每一个柱子我们都可以将
其设为高度，然后看以它为高度，我们的矩形面积到底有多大，可以有多大，然后我们又可以
根据木桶原理，决定我们矩形的高度的就是这个矩形中的柱形的最低的那个柱形，因此为了能够
计算出以当前柱子为最低的哪个柱子的矩形面积，我们就需要保持住在这个矩形中，当前的这个矩形
中当前的柱形的高度最低，这时候我们需要维护这个矩形满足这个木桶原理的边界，因此我们使用
两个数组来维护两边的边界
*/
int n=heights.size();
if(n==0) return 0;
vector<int> minleftindex(n);
vector<int> minrightindex(n);
//然后进行左右两边第一个比自己小的柱形下标的统计
minleftindex[0]=-1;
for(int i=1;i<n;i++){
int t=i-1;
while(t>=0 && heights[t]>=heights[i]){
t=minleftindex[t];
}
minleftindex[i]=t;
}
minrightindex[n-1]=n;
for(int i=n-2;i>=0;i--){
int t=i+1;
while(t<n && heights[t]>=heights[i]){
t=minrightindex[t];
}
minrightindex[i]=t;
}
//然后遍历所有柱子 计算最大的矩形的面积
int rel=INT_MIN;
for(int i=0;i<n;i++){
int h=heights[i];
int w=minrightindex[i]-minleftindex[i]-1;//去掉两侧比自己小的柱形，只留这块自己是最小的宽度
rel=max(rel,h*w);
}
return rel;
}
};
74.搜索二维矩阵
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
/*
解题思路：
条件1：每行中的整数从左到右按非严格递增顺序排列--->这代表同一行整数，从左到右，绝对是不会减少的，最次也是相等
条件2：每行的第一个整数大于前一行的最后一个整数--->这说明，每一行之间严格单调递增的 不会出现数字交叉的情况
那么我们怎样来进行这个数组的查找呢？
首先，第一点，我们应该找到这个target应该是属于哪一行，我们在行内去使用二分查找
然后，怎样判断呢？这里我们是需要使用二分查找来解决这个问题的，那么按照一般的二分查找的解题思路，我的左指针应该是指向第一行的第一个元素
然后我的右指针应该是指向最后一行的最后一个元素，我们分别指向这两个地方 当做虚拟的一维数组进行处理
*/
if(matrix.size()==0 || matrix[0].size()==0) return false;
int m=matrix.size();
int n=matrix[0].size();
int left=0;//左指针
int right=m*n-1;
while(left <= right){
//左闭右闭区间 使用<=
int mid=left+(right-left)/2;
//转换回二维坐标 进行判断
int row=mid/n;
int col=mid%n;
int midval=matrix[row][col];
if(midval==target) return true;
else if(midval < target) left=mid+1;
else right=mid-1;
}
return false;
}
};
34.在排序数组中查找元素的第一个位置和最后一个位置
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
/*
题目理解：非递减顺序----> 那么代表的就是其后面的元素要不就是与前一个元素相等，要不就是大于前面的元素
怎样为log n 那不就是2^x=n 必须要x次数内就完成这个操作吗？
那么按照这个题意来看这就是一个山峰类型的数组，保证下一个元素是不下去的
二分查找 先找到这个target 然后两边看一看就行了
*/
int n=nums.size();
vector<int> rel{-1,-1};
if(n==0) return rel;
int start_index=0;
int end_index=n-1;
int mid=-1;
while(start_index <= end_index){
mid=start_index+(end_index-start_index)/2;
if(nums[mid]==target){
break;
}
else if(nums[mid]<target){
start_index=mid+1;
}
else{
end_index=mid-1;
}
}
if(mid==-1 || nums[mid]!=target) return rel;
//然后开始探寻
int left=mid,right=mid;
while(left >0 && nums[left-1]==target) --left;
while(right<n-1 && nums[right+1]==target) ++right;
return {left,right};
}
};
33.搜索旋转排序数组
class Solution {
public:
int search(vector<int>& nums, int target) {
/*
解题思路：按升序排序 并且数组中的值严格的不相同
但是这里进行旋转了-->并且我们并不知道，然后我们需要设计一个O(log n)的算法
首先这里旋转了，我们是不是需要先找出分界点？
然后找到分界之后，根据分界点来我们来进一步的在两边进行二分查找，因为这里我们需要的是
那么具体的找边界的路子可以这样
如果mid>left那么就需要继续在右边找
如果mid<left那么就需要在左边找了 说明走过了
如果mid>left 同时大于right 并且mid+1<mid了 那么就可以退出
但是这样来解题在代码层面需要判断非常多的条件，其实我们可以想一下就是
虽然我们进行了旋转，但是因为之前整体都是有序的 那么旋转之后的数组 其实分界点两侧都也还是有序的
所以我们干脆就在随便找一个分界点 然后通过与left进行判断就知道在之前的前半部分还是后半部分，然后来进行查找就行
*/
int n=nums.size();
if(n==0) return -1;
int l=0,r=n-1;
while(l<=r){
int m=l+(r-l)/2;
if(nums[m]==target) return m;
//1.如果左半侧有序
if(nums[m]>=nums[l]){
//target在左半侧
if(nums[l]<=target && nums[m]>target){
r=m-1;
}else{
l=m+1;
}
}
else{
//如果右半侧有序
if(target>nums[m] && target<=nums[r]){
l=m+1;
}else{
r=m-1;
}
}
}
return -1;
}
};
2054.两个最好的不重叠的活动
class Solution {
public:
int maxTwoEvents(vector<vector<int>>& events) {
/*
解题思路：
1.按时间顺序看活动：先把所有活动按照开始时间拍个序，这样我们从早到晚一个个看
2.维护历史最佳：当我们看到第i个活动时，我们需要指导在这个活动开始之前，所有已经结束的活动里，价值最高的是多少
这样直接就是很直接的思路，就是找两个最大的组合
*/
//1.首先按照开始时间排序
sort(events.begin(),events.end(),[](vector<int>& a,vector<int>& b){
return a[0]<b[0];
});
//2.然后建立一个最小堆，来维护在后面的开始时间前就结束的活动 <结束时间，价值>
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> min_heap;
//3.定义最大值，结果
int max_val=0,ans=0;
//4.然后开始遍历events数组
for(const auto& event : events){
//从堆里取数据出来，更新在本事件开始之前的最大价值max_value
while(!min_heap.empty() && min_heap.top().first<event[0]){
auto temp=min_heap.top();min_heap.pop();
max_val=max(max_val,temp.second);
}
//然后更新结果
ans=max(ans,max_val+event[2]);
//当前数据入堆
min_heap.push(pair<int,int>{event[1],event[2]});
}
return ans;
}
};
这道题（LeetCode 2054. 两个最好的不重叠活动）是一道非常经典的时间调度/区间规划问题。
题目核心限制是：“最多参加两个”。 这大大简化了问题，我们不需要像普通动态规划那样考虑无限多个活动，只需要考虑 “当前这一个” + “前面最好的那一个”。
为了让你通俗易懂地理解，我们可以用 “找搭档” 的思路来拆解。
💡 通俗思路：“寻找最佳前任”
想象你是一个活动策划人，你手里有一堆活动清单。你想通过组合活动赚最多的钱，但你分身乏术，同一时间只能做一个，而且最多只能做两场。
当你决定参加某个活动（我们把它称为 活动 B）时，为了让总价值最大化，你肯定希望：
在所有不耽误活动 B 开始的“已结束活动”中，选一个给钱最多的（称为活动 A）。
所以，解题流程就是：
按时间顺序看活动：先把所有活动按 开始时间 排个序，这样我们从早到晚一个个看。
维护“历史最佳”：当我们看到第 个活动时，我们需要知道 “在这个活动开始之前，所有已经结束的活动里，价值最高的是多少？”
🛠️ 具体的解法（排序 + 最小堆/优先队列）
为了实现上面的思路，我们需要一个工具来帮我们记录那些“正在进行”或者“已经结束”的活动。最小堆（Min-Heap） 是最合适的工具。
步骤演示：
排序：先把所有活动按照 开始时间 从小到大排序。
准备两个变量：
max_value: 记录目前为止所有已结束的活动中，最大的那个价值（这就是“最佳前任”）。ans: 记录最终的答案（最大价值和）。
准备一个堆：用来存放通过了筛选但还没结束的活动。堆里存
(结束时间, 价值)，并按照结束时间从小到大排。遍历每个活动（作为“后一个活动”）：
对于当前活动（假设开始时间是
start）：清理堆：检查堆顶的活动。如果堆顶活动的结束时间 < 当前活动的 start，说明那个活动在当前活动开始前已经彻底结束了！
更新前任：既然它结束了，我们就把它拿出来，看看它的价值是不是比现有的
max_value更大。如果是，更新max_value。计算总价：现在的组合价值 =
当前活动价值+max_value。用这个去更新全局最大值ans。入堆：把当前活动也扔进堆里，因为它可能是未来的某个活动的“最佳前任”。
🧠 为什么这个方法好？
直观：它模拟了时间流逝的过程。一边走，一边把结束的任务归档，选出最好的一个。
高效：
排序需要 。
每个元素进堆一次、出堆一次，也是 。
总体复杂度就是 ，对于题目通常的数据规模（比如 10万条数据）是非常快的。
153.寻找旋转排序数组中的最小值
class Solution {
public:
int findMin(vector<int>& nums) {
/*
这里可以看见的是，他这里旋转一次就等于将最后一个位置的元素，放到数组的开头
这样如果的结果其实可以很显然的得知，就是我们的数组始终是有序的，是有迹可循的
如果我们的开始元素，大于我们的最后的结束元素，这说明我们的旋转次数%n>0 如果等于0要不是已经转过一圈要不就是还没转不需要管
然后就会始终有序，并且我们说是需要寻找最小值 那么就存在找边界问题，又需要O(log n)的时间复杂度，使用二分查找 不能直接排序
排序是O（n）
1.如果是nums[0]<nums[n-1],直接return nums[0]
2.如果nums[0]>nums[n-1]
进行二分查找，nums[mid]>nums[right]【这里说明一下，为什么要与右端比，而不是左端比，是因为如果目前我们的旋转是有效的话，那么我们的右端值是一定小于旋转过来的整体，并且同时大于当前右端的最左端的】 此时说明mid还在左端高端的数据中，放心大胆地left+1
如果nums[mid]<nums[right]---->这里就不能直接的就right-1 必须先探测一下 如果nums[mid]>nums[mid-1]那么在-1否则
直接return
*/
int n=nums.size();
if(n==1) return nums[0];
if(nums[0]<nums[n-1]) return nums[0];
int left=0,right=n-1;
int mid=-1;
while(left<=right){
mid=left+(right-left)/2;
if(nums[mid]>nums[right]){
left=mid+1;
}else{
if(nums[mid]>nums[mid-1]){
right=mid-1;
}
else{
break;
}
}
}
return nums[mid];
}
};
代码精简版：
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0;
int right = nums.size() - 1;
// 循环条件改为 <，这意味着当 left == right 时循环结束
// 此时 left 就是我们要找的最小值下标
while (left < right) {
int mid = left + (right - left) / 2;
// 情况1：中间值 > 右边值
// 说明 mid 在左半段（高坡），断崖（最小值）一定在 mid 的右边
// 且 mid 肯定不是最小值（因为它比 right 还大）
if (nums[mid] > nums[right]) {
left = mid + 1;
}
// 情况2：中间值 < 右边值 (由于元素互不相同，这里其实就是 <)
// 说明 mid 在右半段（低坡），这一段是有序递增的
// 此时 mid 可能是最小值，也可能最小值在 mid 左边
// 所以我们保留 mid，收缩右边界
else {
right = mid; // 注意这里不是 mid - 1
}
}
// 退出循环时 left == right，指向的就是最小值
return nums[left];
}
};
3074.重新分装苹果
class Solution {
public:
int minimumBoxes(vector<int>& apple, vector<int>& capacity) {
/*
解题思路：这里其实就是先将我们的苹果的总数先记录下来，反正可以分开装
然后在从箱子里挑大的装，装满一个箱子记录一下，直到sum==0
*/
// 使用 accumulate 快速求和
int sum = accumulate(apple.begin(), apple.end(), 0);
sort(capacity.begin(),capacity.end());
int ans=0;
for(int i=capacity.size()-1;i>=0;i--){
if(sum<=0) break;
sum-=capacity[i];
ans++;
}
return ans;
}
};
4.寻找两个正序数组的中位数
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
/*
首先我们需要明白中位数的定义，即一个数组排序后的处于中间位置的数，那么如果我的数组
的长度是一个奇数，那么直接就是中间的那个数，如果是偶数，那么就是中间位置的两个数的
平均值，那么我们完全可以是这样，就是求出nums1 nums2的长度，然后得到是不是奇数，然后
计算出得到中间值，我们分别需要从nums1 nums2中合起来拿出多少的元素
不过这样的话，我感觉并没有达到算法O(log(m+n))的要求，我这样做其实相当于是顺序查找的
想一想，我们是想要在两个数组中一起做二分查找，这个应该怎么办，我们实际上是求的是两个数组
合并起来的中间的数值是吧！
既然我们不能真的合并（因为太慢），我们尝试直接在 nums1 和 nums2 上各画一刀，把它们分成左边和右边：nums1: [ ... 左边部分 1 ... | ... 右边部分 1 ... ]nums2: [ ... 左边部分 2 ... | ... 右边部分 2 ... ]我们的目标是找到这两刀的位置，使得：数量平衡： （左边部分1 + 左边部分2）的元素个数 $\approx$ 总元素个数的一半。数值有序： 左边所有的数 $\le$ 右边所有的数。也就是说：nums1 的左边最大值 $\le$ nums2 的右边最小值nums2 的左边最大值 $\le$ nums1 的右边最小值
*/
if(nums1.size()>nums2.size()) return findMedianSortedArrays(nums2,nums1);//保证我们来在小的数组上面进行二分
int m=nums1.size(),n=nums2.size();
int totalleft=(m+n+1)/2;
//处理在nums1中可能出现的分割位置
int left=0,right=m;//可能出现在最左边和最右边，这里代表的是分割线的位置，不是元素下标
while(left <= right){
//处理分割线，并进行交叉验证
int i=left+(right-left)/2;
int j=totalleft-i;
int nums1leftMax=(i==0)?INT_MIN:nums1[i-1];//左边的最大值
int nums1RightMin=(i==m)?INT_MAX:nums1[i];//nums1数组右边的最小值
int nums2leftMax=(j==0)?INT_MIN:nums2[j-1];//nums2数组的左边的最大值
int nums2RightMin=(j==n)?INT_MAX:nums2[j];//nums2数组的右半边最小值
//然后检查是否满足完美分割
//即nums1的左边最大值<nums2的右边最小值，nums2的左边最大值小于nums1的右边最小值，并且i+j的长度为总长度的一半
if(nums1leftMax <= nums2RightMin && nums2leftMax <= nums1RightMin){
//如果总长度是奇数，那么就是两个数组中左边最大值中的那个较大值
if((m+n)%2==1) return max(nums1leftMax,nums2leftMax);
else return (max(nums1leftMax,nums2leftMax)+min(nums1RightMin,nums2RightMin))/2.0;//否则就是最靠中间的两个数的平均
}else if(nums1leftMax > nums2RightMin){
// 说明 nums1 左边分多了 (里面的大数太大了)，分割线 i 需要往左移
right=i-1;
}else{
// 说明 nums1 左边分少了 (导致 nums2 左边被迫分太多，拿到了大数)，分割线 i 需要往右移
left=i+1;
}
}
return 0.0;
}
};
46.全排列
class Solution {
public:
vector<vector<int>> rel;
vector<int> path;
void BackTracking(vector<int>& nums,vector<bool>& used){
//递归出口
if(path.size()==nums.size()){
//入队列
rel.push_back(path);
return;
}
//遍历
for(int i=0;i<nums.size();i++){
if(used[i])
continue;
used[i]=true;
path.push_back(nums[i]);
BackTracking(nums,used);
//回溯
path.pop_back();
used[i]=false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
/*
回溯算法，就是将回溯逻辑在递归中体现，回溯与递归是一块的，当然这个题也可以使用的动态规划来
进行解答，但是这里需要大过年太维护一个是否过这个元素的数组
*/
vector<bool> used(nums.size(),false);
BackTracking(nums,used);
return rel;
}
};
3075.幸福值最大的选择方案
class Solution {
public:
long long maximumHappinessSum(vector<int>& happiness, int k) {
/*
解题思路：这里我们首先完全可以将数据进行排序，然后维护一个全局的随选择次数开始幸福值相减的方案
并且维护一个vector<bool>数组 来记录那些孩子已经被挑选走
*/
int n=happiness.size()-1;
sort(happiness.begin(),happiness.end());
long long sub=0,sum=0;//维护最大的幸福值以及减的方案
while(k--){
sum=sum+((happiness[n]-sub)>=0?(happiness[n]-sub):0);
n--;
sub++;
}
return sum;
}
};
17.号码组合
class Solution {
public:
unordered_map<char,string> mymap={{'2',"abc"},{'3',"def"},{'4',"ghi"},{'5',"jkl"},{'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"}};
vector<string> rel;
string path;
void backtrcaking(string digits,int index){
if(path.size()==digits.size()){
rel.push_back(path);
return ;
}
//然后取数字 以及对应的字母串
char c=digits[index];
string letters=mymap[c];
for(int i=0;i<letters.size();i++){
path.push_back(letters[i]);
backtrcaking(digits,index+1);
path.pop_back();
}
}
vector<string> letterCombinations(string digits) {
/*
这里首先应该将数字与字母串的组合映射先建立起来，然后就是这里
我们没次需要从一个数字代表的一组字母中选出一个来进行排列，这个
组合起来的字符串的最大长度等于digits.size()
然后这里求的是组合，而不是全排列 那么就需要使用一个index控制 但是重要的是我应该怎样将
数字与字母组合对应起来呢？直接使用index即控制组合的长度，也控制深度，同时控制我们该遍历哪个
数字的对应组合，而对于数字对应的组合，我之前想的是需不需要使用比如之前的子集的startindex来控制呢？
我发现根本不必，因为实际上我们的index就已经控制了不是全排列的这种情况，因为这是在不同个体之间的，
而个体之内的我觉得我们就不需要这样纠结的 因为我们就是每次取一个
*/
backtrcaking(digits,0);
return rel;
}
};
2483.商店的最少代价
双数组，维护前缀和+后缀和
class Solution {
public:
int bestClosingTime(string customers) {
/*
解题思路：这里最重要的是需要维护一个每个时间点关门
都需要将所有的状态统计一遍，那么这里绝对不能就是针对
于每一个时间点都真正的单独去计算一遍全部的数组，那样
是O(N^2)的时间复杂度，不用说直接爆炸
这里需要前缀和来计算 那这里是不是需要两个前缀和数组 一个维护此时关门的代价 一个维护此时开门的代价
总代价=开门期间没客人的代价+关门期间有客人的代价
*/
int n=customers.size();
//前缀和 后缀和
vector<int> prefix(n+1,0);
vector<int> surfix(n+1,0);
//统计前缀和---也就是对应与开门期间没有客人的代价，去找N
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]+(customers[i]=='N'?1:0);
}
//处理后缀和 也就是处理关门期间有客人的代价
for(int i=n-1;i>=0;i--){
surfix[i]=surfix[i+1]+(customers[i]=='Y'?1:0);
}
//然后来统计
int min_cost=INT_MAX;
int best_hour=-1;
for(int i=0;i<=n;i++){
int cost=prefix[i]+surfix[i];
if(cost<min_cost){
min_cost=cost;
best_hour=i;
}
}
return best_hour;
}
};
一遍遍历 O（1）的空间复杂度
// O(1) 空间复杂度版本
class Solution {
public:
int bestClosingTime(string customers) {
int penalty = 0;
// 初始代价：假设第0小时就关门，代价就是所有 'Y' 的数量
for (char c : customers) {
if (c == 'Y') penalty++;
}
int min_penalty = penalty;
int best_hour = 0;
for (int i = 0; i < customers.size(); i++) {
if (customers[i] == 'Y') {
penalty--; // 变成开门，Y的代价消除
} else {
penalty++; // 变成开门，N产生代价
}
// 注意：如果代价相等，因为题目要求“最早”关门时间，
// 所以只有严格小于才更新，保持 best_hour 是较小的那个
if (penalty < min_penalty) {
min_penalty = penalty;
best_hour = i + 1;
}
}
return best_hour;
}
};
39.组合总数
class Solution {
public:
vector<vector<int>> rel;
vector<int> path;
void backtracking(vector<int>& candidates,int target,int sum,int index){
//结束条件---如果path中所有数的sum==target了 那么就加入结果 然后并且返回
//遍历条件 这里可以重复选那么每次就可以从0开始遍历
//但是这里我们应该怎样来控制这个递归呢？那么就是通过一个剪枝 看看加进去如果大于目标就不进入了
if(sum==target){
rel.push_back(path);
return;
}
for(int i=index;i<candidates.size();i++){
if(sum+candidates[i]>target) continue;
//否则就加入进去啊
path.push_back(candidates[i]);
backtracking(candidates,target,sum+candidates[i],i);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates,target,0,0);
return rel;
}
};
回溯算法的三种不同模式
| 场景 | 循环起始点 | 递归传入参数 | 含义 |
| 组合（元素不可重复选） | int i = index | backtracking(..., i + 1)" | 只能往后看，且当前这个数用过了就翻篇了。 |
| 组合（元素可重复选 - 本题） | int i = index | "backtracking(..., i)" | 只能往后看，但当前这个数还可以继续用（原地踏步）。 |
| 排列（顺序不同视为不同） | ,int i = 0, | 需要 used 数组辅助, | 每次都从头看，但在同一条树枝上不能重复用同一个位置的数。 |
22.括号生成
class Solution {
public:
vector<string> rel;
string path;
void backtrcking(int n,int left,int right){
/*
使用两个变量来控制左括号与右括号的使用数量以及当前状态，以控制下一步应该怎样走
*/
if(right==left && (right+left)==2*n){
rel.push_back(path);
return;
}
//尝试加括号
if(left<n){
//还可以加左括号
path+='(';
backtrcking(n,left+1,right);
path.pop_back();
}
if(right<left){
//还可以加左括号
path+=')';
backtrcking(n,left,right+1);
path.pop_back();
}
}
vector<string> generateParenthesis(int n) {
backtrcking(n,0,0);
return rel;
}
};
79.单词搜索
class Solution {
public:
//上下左右的进行回溯----这里是方向的设置
int pos[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
bool backtracking(vector<vector<char>>& board,string word,int x,int y,int index){
// 2. 失败基础情况：越界 或者 字符不匹配 x代表行的指针 y代表列移动的指针
if (x < 0 || x >= board.size() || y < 0 || y >= board[0].size() || board[x][y] != word[index]) {
return false;
}
if(index==word.size()-1) return true;
//标记访问
char temp=board[x][y];
board[x][y]='#';//标记已经访问了
// 5. 修正：递归四个方向，只要有一个方向通了，就返回 true
for (int i = 0; i < 4; i++) {
int next_x = x + pos[i][0];
int next_y = y + pos[i][1];
// 递归匹配下一个字符 (k + 1)
// 这里的逻辑就是：如果找到了，直接层层向上传递 true
if (backtracking(board, word, next_x, next_y, index + 1)) {
return true;
}
}
//回溯还原
board[x][y]=temp;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
/*
这里需要使用回溯 但是因为是在一个二维数组里 那么其实这里的递归方向就是需要进行转向
*/
int rows=board.size();
int cols=board[0].size();
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(backtracking(board,word,i,j,0)) return true;
}
}
return false;
}
};
131.分割回文串
class Solution {
public:
vector<vector<string>> rel;
vector<string> path;
//判断是否是回文串的字符
bool loopstring(const string& s,int left,int right){
while(left<right){
if(s[left]!=s[right]){
return false;
}
right--;left++;
}
return true;
}
//递归加回溯
void backtracking(string s,int startindex){
//递归出口
if(startindex>=s.size()){
rel.push_back(path);
return;
}
//然后开始遍历其他
for(int i=startindex;i<s.size();i++){
//先将这部分数据截取下来u
if(loopstring(s,startindex,i)){
string sub=s.substr(startindex,i-startindex+1);
//加入到path
path.push_back(sub);
//然后继续递归
backtracking(s,i+1);
//回溯
path.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
/*
分割回文串：那么这里就需要一边分割 然后同时判断分割下来的字符串是否是回文串
*/
backtracking(s,0);
return rel;
}
};
51.N皇后
class Solution {
public:
vector<vector<string>> rel;
//递归+回溯
void backtrcaking(int n,int row,vector<string>& chessboard){
//递归出口条件---这里我们一行行的来放置
if(row==n){
rel.push_back(chessboard);
return;
}
//如果还没放置够 那么就继续放置
for(int col=0;col<n;col++){
//其实每一行都能够放 就看放在哪里比较合适
//如果放在这里是正确的 那么再继续
if(isValid(chessboard,row,col,n)){
//放在这个位置合法 那么就将其修改 并继续递归
chessboard[row][col]='Q';
backtrcaking(n,row+1,chessboard);
chessboard[row][col]='.';
}
}
}
bool isValid(const vector<string>& chessboard,int row,int col,int n){
//然后来进行判断
//同一行来进行判断
for(int i=0;i<n;i++){
if(chessboard[row][i]=='Q')
return false;
}
//统一列来进行判断
for(int j=0;j<n;j++){
if(chessboard[j][col]=='Q') return false;
}
//然后四十五度来进行判断
for(int i=row-1,j=col-1;i>=0 && j>=0 ;i--,j--){
if(chessboard[i][j]=='Q') return false;
}
//然后145°进行判断
for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){
if(chessboard[i][j]=='Q') return false;
}
return true;
}
vector<vector<string>> solveNQueens(int n) {
/*
N皇后问题---除了判断递归回溯之外 就是需要进行判断，每个位置能否放置皇后
*/
vector<string> chessboard(n,string(n,'.'));
backtrcaking(n,0,chessboard);
return rel;
}
};
840.矩阵中的幻方
class Solution {
public:
bool judge(vector<int>& path){
//来判断这个数组是否是满足的,幻方中每个行每个列以及斜度角的和都是15 然后每一行 每一列 加上两个斜对角一共是8对数字
//我就直接算 最后看满足15的数字的和的个数是不是8
int is_five=0;
//计算列
int sum=0;
for(int i=0;i<9;i++){
sum+=path[i];
if(i==2 || i==5 || i==8){
//检验是否等于15
if(sum==15) is_five++;
sum=0;
}
}
//计算行
for(int i=0;i<3;i++){
if(path[i]+path[i+3]+path[i+6]==15) is_five++;
}
//计算斜对角
//45°
if(path[0]+path[4]+path[8]==15) is_five++;
if(path[2]+path[4]+path[6]==15) is_five++;
return is_five==8;
}
int numMagicSquaresInside(vector<vector<int>>& grid) {
/*
首先，我们如果要看一下这一片数组是不是1-9的数字 如果每个数字只出现了一次 那么在进行进一步的检验是否
是满足幻方的性质
计算每行、每列、对角线的和是否相等----但是要怎样的去每一个位置遍历呢？一次遍历 然后在从每一个起点划出3*3的矩阵
*/
int row=grid.size(),col=grid[0].size();
vector<vector<int>> rel;//用来存储结果
//然后开始遍历
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
//每次以[i,j]为起点，以此划分出一个3*3的矩阵，然后检验是否满足条件
int temp[10] = {0, 1, 1, 1, 1, 1, 1, 1, 1, 1};
vector<int> path;
for(int m=0;m<3 && i+m<row;m++){
for(int n=0;n<3 && j+n<col;n++){
if(grid[i+m][j+n]>=1 && grid[i+m][j+n]<=9){
path.push_back(grid[i+m][j+n]);
temp[grid[i+m][j+n]]-=1;
}
}
}
bool allZero = std::all_of(
std::begin(temp),
std::end(temp),
[](int x) { return x == 0; }
);
if(path.size()==9 && allZero){
//调用条件判断
if(judge(path)){
rel.push_back(path);
}
}
}
}
return rel.size();
}
};
994.腐烂的橘子
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
/*
求需要的最小分钟数，那么就是去求走的步数，而怎么走呢？每次走一段路 并且这里也需要进行记录 最后如果还有剩的孤岛也就是新鲜橘子 那么
就退出-1 或者 就是满足的 直接返回步数
*/
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int rows=grid.size(),cols=grid[0].size();
queue<pair<int,int>> que;
int fresh=0;//统计新鲜橘子
int time=0;//统计时间
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
//统计新鲜橘子 + 将第一层的腐烂的橘子加入进去
if(grid[i][j]==1) fresh++;
if(grid[i][j]==2) que.push({i,j});
}
}
//然后开始进行层序遍历
while(!que.empty() && fresh>0){
int size=que.size();
while(size--){
pair<int,int> cur=que.front();que.pop();
for(int i=0;i<4;i++){
int next_x=cur.first+dir[i][0];
int next_y=cur.second+dir[i][1];
//判断是否已经遍历过了 或者是否超过了界限
if(next_x<0 || next_x>=rows || next_y<0 || next_y>=cols) continue;
//再来判断是否等于1
if(grid[next_x][next_y]==1){
grid[next_x][next_y]=2;
fresh--;
que.push({next_x,next_y});
}
}
}
time++;
}
return fresh==0?time:-1;
}
};
1970.穿过矩阵的最后一天
class Solution {
public:
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool CanCross(int day,const vector<vector<int>>& cells,int row,int col){
//1.先构建全陆地的数组
vector<vector<int>> gird(row+1,vector<int>(col+1,0));
//然后将他们染为水域
for(int i=0;i<day;i++){
gird[cells[i][0]][cells[i][1]]=1;
}
//然后这里使用广度优先搜索
queue<pair<int,int>> que;
vector<vector<bool>> visited(row+1,vector<bool>(col+1,false));
//然后往que里添加第一行 可以作为起始的点
for(int i=1;i<=col;i++){
if(gird[1][i]==0){
que.push({1,i});
visited[1][i]=true;
}
}
//然后开始官渡优先搜索
while(!que.empty()){
auto [r,c]=que.front();que.pop();
if(r==row) return true;//说明可以走通
//然后还没有达到的话 就开始四处走
for(int i=0;i<4;i++){
int nr=r+dir[i][0];
int nc=c+dir[i][1];
//边界检查以及是否是陆地
if(nr<1 || nr > row || nc<1 || nc>col || gird[nr][nc]==1) continue;
//然后看是否访问过了
if(gird[nr][nc]==0 && visited[nr][nc]==false){
visited[nr][nc]=true;
que.push({nr,nc});
}
}
}
return false;
}
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
/*
=这里需要用到二分+递归 取cells的一半mid 然后构建数组 如果发现在第mid天还能过 那么我就去找mid后的天数
*/
int left=0;
int right=cells.size();
int ans=0;
while(left<=right){
int mid=left+(right-left)/2;
if(CanCross(mid,cells,row,col)){
//还可以过 那么就往后看
ans=mid;
left=mid+1;
}else{
right=mid-1;
}
}
return ans;
}
};
207.课程表
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//这里需要先通过prerequisites数组构建一个入度数组 来判断开始节点
vector<int> INdgree(numCourses,0);
//然后统计入度
for(int i=0;i<prerequisites.size();i++){
INdgree[prerequisites[i][0]]+=1;
}
//然后来看这里是否是有入度为0的节点
queue<int> que;
vector<int> resul;
//然后将入度为0的节点加入到que中
for(int i=0;i<numCourses;i++){
if(INdgree[i]==0){
que.push(i);
}
}
//然后开始BFS搜索
while(!que.empty()){
//拿出当前的节点
int cur=que.front();que.pop();
resul.push_back(cur);
//然后将这个节点拿到后 将这个节点指向的节点的入度-1 然后在
for(int i=0;i<prerequisites.size();i++){
if(prerequisites[i][1]==cur){
//那么这个节点的入度就-1 然后如果为0 就加入到que
INdgree[prerequisites[i][0]]--;
if(INdgree[prerequisites[i][0]]==0){
//加入到que
que.push(prerequisites[i][0]);
}
}
}
}
return numCourses==resul.size();
}
};
66.加一
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
/*
解题策略：整个数组就是表示一个整数 然后我们+1的话 就需要判断是否有进位 如果有进位的话 就需要将其向上加1
特别是最后一位如果为9的话 那么还需要进1
先将数组翻转过来，方便最后一位的扩展
然后在翻转过来
*/
reverse(digits.begin(),digits.end());
//然后开始来进行翻转
int up_num=1;//表示进位
for(int i=0;i<digits.size();i++){
//当前位与进位相加 然后除数等于进位 然后余数等于当前位
int num=digits[i]+up_num;
digits[i]=num%10;
up_num=num/10;
}
//然后检验up_num是不是大于1
if(up_num>0) digits.push_back(up_num);
reverse(digits.begin(),digits.end());
return digits;
}
};
208.实现trie前缀树
class Trie {
private:
bool isEnd;
Trie* next[26];
public:
Trie() {
isEnd=false;
memset(next,0,sizeof(next));
}
void insert(string word) {
Trie* node= this;
for(char c: word){
if(node->next[c-'a']==NULL){
node->next[c-'a']=new Trie();
}
node=node->next[c-'a'];
}
node->isEnd=true;
}
bool search(string word) {
Trie* node=this;
for(char c: word){
node=node->next[c-'a'];
if(node==NULL) return false;
}
return node->isEnd;
}
bool startsWith(string prefix) {
Trie* node = this;
for(char c:prefix){
node=node->next[c-'a'];
if(node==NULL) return false;
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
异或的使用场景
除了一个元素出现奇数次，其余元素都出现偶数次（利用 a^a=0、0^a=a 的性质）。
961.找到出现N次的元素
//方法1 直观的哈希表理解
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
unordered_map<int, int> count; // 哈希表统计次数
for (int num : nums) {
if (++count[num] > 1) { // 只要出现2次，就是目标元素
return num;
}
}
return -1; // 题目保证有解，不会执行到这里
}
};
//方法2 利用鸽笼的数学原理
class Solution {
public:
int repeatedNTimes(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
// 检查相邻元素
if (i+1 < n && nums[i] == nums[i+1]) {
return nums[i];
}
// 检查间隔1位的元素
if (i+2 < n && nums[i] == nums[i+2]) {
return nums[i];
}
}
// 特殊情况：N=2且目标元素在首尾（如[1,2,3,1]），直接返回最后一个元素
return nums.back();
}
};
106.二叉树的最大深度
//方法1：深度优先搜索
class Solution {
public:
int maxDepth(TreeNode* root) {
/*
这里如果用广度优先搜素的话，那么就需要额外开辟一个队列来存储节点
那我用深度优先搜索应该怎样？将每个遍历到的节点走当做新节点，然后
返回最大的深度
*/
if(root==nullptr) return 0;
int left=maxDepth(root->left);
int right=maxDepth(root->right);
//返回左右子树中，较深的那棵子树
return 1+max(left,right);
}
};
//方法2：广度优先搜索
class Solution {
public:
int maxDepth(TreeNode* root) {
//记录二叉树的最大深度 最简单的方法那么就是看其层序遍历的次数
int count=0;
if(root==NULL)
return count;
queue<TreeNode*> que;
que.push(root);
while(!que.empty())
{
int size=que.size();
while(size--)
{
TreeNode* cur=que.front();
que.pop();
if(cur->left)
que.push(cur->left);
if(cur->right)
que.push(cur->right);
}
count++;
}
return count;
}
};
226.翻转二叉树
//方法1：DFS
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
/*
这里的翻转二叉树其实就是，对于每一个节点，他的左右孩子节点交换位置
然后在进行比如深度遍历啊 这样的操作 然后在每个节点都这样做
*/
if(root==nullptr) return nullptr;
//然后先交换当前的左右孩子节点
TreeNode* temp=root->left;
root->left=root->right;
root->right=temp;
//然后开始深度遍历左右孩子节点
invertTree(root->left);
invertTree(root->right);
return root;
}
};
//方法2：BFS
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) return nullptr; // 如果根节点为空，直接返回nullptr
queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
int size = que.size();
while (size--) {
TreeNode* cur = que.front();
que.pop();
// 交换当前节点的左右子节点
TreeNode* temp = cur->left;
cur->left = cur->right;
cur->right = temp;
// 将非空的左右子节点加入队列
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
}
return root;
}
};
1411.给 N x 3 网格图涂色的方案数
class Solution {
public:
int numOfWays(int n) {
/*
其实我们只是维持三列 那么为什么不就将这三列看作是一个状态呢？这比分别来
考虑简单一些。
实际上，比如对于一个一行三列的网格图，基于题目条件限制，如果我们需要涂色的话，那么我们其实有两种方案：
第一种，“ABC”方案，那么第一个位置有三种方案，第二个位置就还有两种 第三个位置只能选择剩下的那个 那么3*2*1=6种
第二种，“ABA”方案，那么第一个位置有三种方案（随便选） 第二个位置有来那个两种方案（不能与第一个位置相同）第三个位置只能跟改一个位置相同 6种方案
因此 对于一行三列的网格涂色，那么就有12种方案
那么此时我们在来思考多行的情况：
1.假设我们计算的上一行是ABC方案：那么我们这一行使用ABA模式，一共两种方案
使用ABC模式，那么一共有两种方案 合计4种
2.假设上一行是ABA方案：那么我们这一行如果是ABA方案，就有三种方案
如果是ABC方案，那么就一共有两种方案
因此，根据我们前面的推算，那么我们对于第i行的状态可以通过下面的公式来计算
1.第 i 行的 ABA 数量 =(上一行是ABA的数量 *3) + (上一行是ABC的数量 * 2)
2.第 i 行的 ABC 数量 =(上一行是ABA的数量 * 2) + (上一行是ABC的数量 *2)
*/
long long MOD = 1e9 + 7;
//初始化n=1的情况
long long typeABC=6;
long long typeABA=6;
//从第二行开始推导到n行
for(int i=2;i<=n;i++){
//先保存上一行的值
long long prevABC=typeABC,prevABA=typeABA;
//然后开始按公式计算
typeABA = (prevABA * 3 + prevABC * 2) % MOD;
typeABC = (prevABA * 2 + prevABC * 2) % MOD;
}
return (typeABA+typeABC)%MOD;
}
};
101.对称二叉树
//方法1：深度遍历
class Solution {
public:
bool check(TreeNode* p,TreeNode* q){
//1.两个都为空 那么就返回true
if(!p && !q) return true;
//2.只有一个为空 或者是值不一样
if(!p || !q || p->val!=q->val) return false;
//继续递归
return check(p->left,q->right) && check(p->right,q->left);
}
bool isSymmetric(TreeNode* root) {
/*
什么是轴对称 翻过来一样嘛
那我直接使用一个双端队列 然后每次网里面push元素 然后左边的比较左子树？右边的比较右子树吗？好像也不太对
*/
if(!root) return true;
return check(root->left,root->right);
}
};
//方法2 层序遍历
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if (!root) return true;
// 使用普通队列即可，每次处理两个
std::queue<TreeNode*> q;
q.push(root->left);
q.push(root->right);
while (!q.empty()) {
// 每次取出两个节点进行比较
TreeNode* u = q.front(); q.pop();
TreeNode* v = q.front(); q.pop();
// 逻辑与递归的 Base Case 一样
if (!u && !v) continue; // 都是空，通过，继续看下一对
if (!u || !v || (u->val != v->val)) return false; // 不对称
// 将子节点按“镜像”顺序入队
// 1. 比较 u的左 和 v的右 (外侧)
q.push(u->left);
q.push(v->right);
// 2. 比较 u的右 和 v的左 (内侧)
q.push(u->right);
q.push(v->left);
}
return true;
}
};
543.二叉树的直径
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxdiameter=0;
int backtrack(TreeNode* root){
if(root==NULL) return 0;
int left_num=backtrack(root->left);
int right_num=backtrack(root->right);
//当前节点直径的处理
int curr_nums=left_num+right_num;
maxdiameter=max(curr_nums,maxdiameter);
//当前节点深度的处理
return max(left_num,right_num)+1;
}
int diameterOfBinaryTree(TreeNode* root) {
/*
题意理解：能够看见的是 这里其实就是求左子树的最深边长 以及 右子树的最深边长 他们的总边长
使用递归来完成这个题 使用先序遍历
*/
backtrack(root);
return maxdiameter;
}
};
1304.四因素
这个题思路还是比较简单 重要的是剪枝
class Solution {
public:
int Sum(int num){
int sub_num_count=0;//因素个数
int sum_sub_num=0;//因素的和
for(int i=1;i*i<=num;i++){
if(num%i==0){
//优化1：成对的
if(i*i==num){
sub_num_count++;
sum_sub_num+=i;
}else{
//否则 找到成对的因素
sub_num_count+=2;
sum_sub_num+=i;
sum_sub_num+=num/i;
}
//如果在遍历过程有已经因子大于4的了 就直接返回
if(sub_num_count>4) return 0;
}
}
return sub_num_count==4?sum_sub_num:0;
}
int sumFourDivisors(vector<int>& nums) {
/*
算出所有元素的这些因素 对恰好有四因素的这些数的因素来求和
使用一个辅助函数来求因素的个数与求和
但是目前这样做会超时
*/
int cost=0;
for(const auto& num:nums){
cost+=Sum(num);
}
return cost;
}
};
1975.最大方阵和
class Solution {
public:
long long maxMatrixSum(vector<vector<int>>& matrix) {
/*
这里我想起我们之前使两个序列相等的最小代价了 我是否可以统计负数个数 然后如果是偶数 后面就全需要翻转
然后如果是奇数个 那么就剩最后那个最小的 --- 并且那个最小的绝对值我们可以是看看其是否是整个矩阵最小
整个矩阵最小那么我们就让他成为负数
但是这里我比较疑惑的是 这里需要相邻才可以一起乘----这里我想通了就是 负号是可以传递的
比如 -1 1 1 -1 那么我们完全是可以这样的 1 -1 1 -1 ---> 1 1 -1 -1 中间的每个位置会连续两次乘以-1 那么就恢复原位了就
*/
long long totalsum=0;//总和
long long negCount=0;//负数的个数
int min_val=INT_MAX;//最小的绝对值
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
totalsum+=abs(matrix[i][j]);
if(matrix[i][j]<0) negCount++;
//更新绝对值最小的元素
min_val=min(min_val,abs(matrix[i][j]));
}
}
if(negCount%2==0) return totalsum;
else return totalsum-2*min_val;
}
};
108.将有序数组转换为二叉搜索树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* Creat(const vector<int>& nums,int left,int right){
//出口条件
if(left>right) return nullptr;
//然后开始构造
int index=left+(right-left)/2;
TreeNode* cur=new TreeNode(nums[index]);
//然后开始构造后面的内容
cur->left=Creat(nums,left,index-1);
cur->right=Creat(nums,index+1,right);
return cur;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
/*
平衡二叉树 左右子树的差值不大于1
而这个数组是已经按升序排列的了 这里又是需要构造二叉搜索树
二叉搜索树：根节点大于左子树节点 小于又子树节点
选择一个中间节点 然后每次二分选择一个根节点
*/
return Creat(nums,0,nums.size()-1);
}
};
98.验证二叉搜索树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void DFS(TreeNode* root,vector<int>& rel){
if(root==nullptr) return;
DFS(root->left,rel);
rel.push_back(root->val);
DFS(root->right,rel);
}
bool isValidBST(TreeNode* root) {
/*
验证二叉搜索树-----将其中序遍历输出 判断是不是严格递增的
因为中序遍历的数组就是有序的
中序遍历 左根右
*/
vector<int> rel;
DFS(root,rel);
//然后来判断
for(int i=0;i<rel.size()-1;i++){
if(rel[i+1]<=rel[i]) return false;
}
return true;
}
};
1339.分裂二叉树的最大乘积
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
long long sum=0;
long long mod=1e9+7;
long long rel=INT_MIN;
void DFS(TreeNode* root){
if(root==nullptr) return;
sum+=root->val;
DFS(root->left);
DFS(root->right);
}
long long PostFS(TreeNode* root){
//从叶子节点层开始计算 然后统计每一个节点作为根节点时的最大乘积
if(root==nullptr) return 0;
long long sub_sum=0;
//使用后续遍历
long long left=PostFS(root->left);
long long right=PostFS(root->right);
sub_sum+=(left+right+root->val);
rel=max(rel,sub_sum*(sum-sub_sum));
return sub_sum;
}
int maxProduct(TreeNode* root) {
/*
分裂二叉树的最大乘积
将其通过中序遍历得出全部的有序序列 然后选择中位数来分割两侧 最后返回乘积
不不 应该选择分裂的点是 两侧的和接近的时候 这个时候我们需要的是 就是先统计出来所有元素的和 然后在统计较小的一侧
然后另外一层就是相减 统计所有可能的子树和在 然后动态的进行更新最大可能的乘积值
*/
DFS(root);
//然后去找最接近一半的时候
PostFS(root);
return rel%mod;
}
};
199.二叉树的右视图
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
/*
层序遍历 如果该层的元素个数大于1 那么就输出最后一个
反正就是输出最后一个元素
*/
vector<int> rel;
if(root==nullptr) return rel;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
int size=que.size();
for(int i=0;i<size;i++){
TreeNode* cur=que.front();que.pop();
if(i==size-1) rel.push_back(cur->val);
if(cur->left) que.push(cur->left);
if(cur->right) que.push(cur->right);
}
}
return rel;
}
};55
114.二叉树展开为链表
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* cur = root;
while (cur) {
if (cur->left) { // 有左子树才需要“拆插”
TreeNode* pre = cur->left; // 找左子树最右节点
while (pre->right) pre = pre->right;
// 把原右子树接到左子树最右节点后面
pre->right = cur->right;
// 左子树整体移到右边
cur->right = cur->left;
cur->left = nullptr; // 左指针置空
}
cur = cur->right; // 继续往右走
}
}
};
712.两个字符串的ASCII 的最小删除和
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int n = s1.size(), m = s2.size();
// dp[i][j] 表示 s1[0..i-1] 与 s2[0..j-1] 的最小删除和
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// 边界：其中一个串为空
for (int i = 1; i <= n; ++i) dp[i][0] = dp[i - 1][0] + s1[i - 1];
for (int j = 1; j <= m; ++j) dp[0][j] = dp[0][j - 1] + s2[j - 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (s1[i - 1] == s2[j - 1]) // 字符相等，都不删
dp[i][j] = dp[i - 1][j - 1];
else // 删左边 or 删右边，取小者
dp[i][j] = min(s1[i - 1] + dp[i - 1][j],
s2[j - 1] + dp[i][j - 1]);
}
}
return dp[n][m];
}
};
1266.访问所有节点的最小时间
class Solution {
public:
int Compute(int x1,int y1,int x2,int y2){
//我们先考虑斜边，也就是斜边最多能走多少，如果斜边走完还没到终点，那么就补差值
int diff_x=abs(x2-x1);
int diff_y=abs(y2-y1);
return min(diff_x,diff_y)+abs(diff_x-diff_y);
}
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
/*
需要经过points数组里的点，那么我就直接计算没两个点之间的距离就行
但是不能直接使用距离公式算，这个题我们依然可以是进行简单的贪心策略
先优先走斜边 如果斜边走到了 在考虑走左右
*/
int ans=0;
for(int i=0;i<points.size()-1;i++){
int x1=points[i][0],y1=points[i][1];
int x2=points[i+1][0],y2=points[i+1][1];
ans+=Compute(x1,y1,x2,y2);
}
return ans;
}
};
105.从前序数组和中序数组重构二叉树
//方法1
class Solution {
private:
// 用哈希表存储 inorder 中元素对应的索引，避免每次循环查找
unordered_map<int, int> indexMap;
// 只需要三个参数：
// preorder: 原始前序数组
// pre_root_idx: 当前子树的根节点在 preorder 中的索引（这是我们要不断移动的指针）
// [in_left, in_right]: 当前子树在 inorder 中的范围
TreeNode* build(vector<int>& preorder, int& pre_root_idx, int in_left, int in_right) {
// 1. Base Case: 如果中序遍历的范围不合法，说明没有节点了，返回空
if (in_left > in_right) {
return nullptr;
}
// 2. 获取当前根节点的值
// 在前序遍历中，当前处理的这个点一定是根
int rootVal = preorder[pre_root_idx];
// 3. 创建根节点
TreeNode* root = new TreeNode(rootVal);
// 4. 定位根节点在中序遍历中的位置
int in_root_idx = indexMap[rootVal];
// 关键点：处理完当前根后，pre_root_idx 要向后移一位，指向下一个节点
// 下一个节点肯定是“左孩子”（如果存在的话）
pre_root_idx++;
// 5. 递归构建左右子树
// 左子树的范围：当前中序范围的左边界 -> 根节点位置-1
root->left = build(preorder, pre_root_idx, in_left, in_root_idx - 1);
// 右子树的范围：根节点位置+1 -> 当前中序范围的右边界
root->right = build(preorder, pre_root_idx, in_root_idx + 1, in_right);
return root;
}
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
// 初始化哈希表
for (int i = 0; i < inorder.size(); ++i) {
indexMap[inorder[i]] = i;
}
int pre_root_idx = 0; // 从前序数组的第0个开始处理
return build(preorder, pre_root_idx, 0, inorder.size() - 1);
}
};
437.路径总和|||
class Solution {
public:
// 辅函数：专门计算“以 root 为起点”往下走，和为 target 的路径数
int rootSum(TreeNode* root, long long targetSum) {
if (!root) return 0;
int count = 0;
// 1. 检查当前节点本身是否就等于剩下的目标值
if (root->val == targetSum) {
count++;
}
// 2. 继续往下找（注意：这里不 return，因为可能有负数抵消的情况）
// 下一层需要凑出来的数 = 目标值 - 当前节点值
count += rootSum(root->left, targetSum - root->val);
count += rootSum(root->right, targetSum - root->val);
return count;
}
int pathSum(TreeNode* root, int targetSum) {
if (!root) return 0;
// 逻辑：
// 1. 计算以当前 root 为起点的路径 (调用 rootSum)
// 2. 递归去计算以 root->left 为起点的所有路径 (即把左孩子当作新树的根)
// 3. 递归去计算以 root->right 为起点的所有路径
return rootSum(root, targetSum)
+ pathSum(root->left, targetSum)
+ pathSum(root->right, targetSum);
}
};
3453.分割正方形|
//方法1：二分查找
class Solution {
public:
double check(const vector<vector<int>>& squares,double midY){
double below_area=0;//来计算以midY为分界线，下面的面积
for(auto& s:squares){
double y=s[1],l=s[2];
if(y>=midY) continue;
if(midY>=y+l) below_area+=l*l;
else below_area+=l*(midY-y);
}
return below_area;
}
double separateSquares(vector<vector<int>>& squares) {
/*
首先计算当前的所有正方形的面积之和，然后我们需要选择一个y坐标
可以满足上下的面积相等，这种就是典型的背包问题，我们选择y轴尽量
小的squares[i]来填满二分之一的总和 最后返回最小的y
但是这样的解法不够高效，也不是最佳策略，这里其实更适合
使用二分查找来进行解决
*/
double total_area=0;
double minY=1e9,maxY=-1e9;
for(int i=0;i<squares.size();i++){
double x=squares[i][0],y=squares[i][1],l=squares[i][2];
total_area+=l*l;
minY=min(minY,y);
maxY=max(maxY,y+l);
}
double lowY=minY,higY=maxY;
for(int i=0;i<100;i++){
double midY=lowY+(higY-lowY)/2;
//然后来检查
if(check(squares,midY) < total_area/2.0){
lowY=midY;
}else{
higY=midY;
}
}
return lowY;
}
};
//方法2：排序+扫描
class Solution {
public:
double separateSquares(vector<vector<int>>& squares) {
// 1. 收集所有可能改变“容器宽度”的高度（y坐标）
vector<int> heights;
double totalArea = 0;
for (auto& s : squares) {
heights.push_back(s[1]);
heights.push_back(s[1] + s[2]);
totalArea += (double)s[2] * s[2];
}
// 2. 将高度排序，这样我们就有了从小到大的一层层“水平带”
sort(heights.begin(), heights.end());
// 去重是为了防止处理高度差为 0 的无效层
heights.erase(unique(heights.begin(), heights.end()), heights.end());
double halfArea = totalArea / 2.0;
double currentArea = 0;
// 3. 逐层往上“倒水”
for (int i = 0; i < (int)heights.size() - 1; ++i) {
int h_bottom = heights[i];
int h_top = heights[i + 1];
int layerHeight = h_top - h_bottom;
// 找出这一层有多少个正方形经过，把它们的边长加起来就是这一层的总宽度
long long totalWidth = 0;
for (auto& s : squares) {
int s_bottom = s[1];
int s_top = s[1] + s[2];
// 只要正方形跨越了当前的 [h_bottom, h_top] 区间
if (s_bottom <= h_bottom && s_top >= h_top) {
totalWidth += s[2];
}
}
// 这一层能容纳的面积
double layerArea = (double)totalWidth * layerHeight;
// 4. 关键判断：如果加上这一层就超过一半了，说明 y 就在这一层里！
if (currentArea + layerArea >= halfArea) {
// 此时水已经填到了 h_bottom，还差多少面积？
double neededArea = halfArea - currentArea;
// 在这一层里，宽度是 totalWidth，高度就是 面积 / 宽度
return (double)h_bottom + (neededArea / totalWidth);
}
// 还没满，继续往上一层倒
currentArea += layerArea;
}
return heights.back();
}
};
236.二叉树的最近公共祖先
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
/*
最近公共祖先，深度尽可能大，可以是自己----->我们应该使用后续遍历
从底层来开始逐层的往上遍历 寻找两个节点的第一个祖先节点
*/
//递归的退出逻辑
if(root==p || root==q || root==NULL) return root;
//后续遍历---左右根
TreeNode* left=lowestCommonAncestor(root->left,p,q);
TreeNode* right=lowestCommonAncestor(root->right,p,q);
//然后怎么来处理呢 怎样来处理当前的节点是不是
//如果一边不是NULL 而另一边是NULL 那么其结果就是不是NULL的那一边 否则就继续处理
if(left!=NULL && right!=NULL) return root;
else if(left!=NULL && right==NULL) return left;
else if(left==NULL && right!=NULL) return right;
else return NULL;
}
};
124.二叉树的最大路径和
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int max_sum = INT_MIN;
int maxGain(TreeNode* node) {
if (node == nullptr) return 0;
// 1. 递归计算左右子节点的最大贡献
// 如果贡献为负，我们宁愿不选（即取 0）
int leftGain = max(maxGain(node->left), 0);
int rightGain = max(maxGain(node->right), 0);
// 2. 当前节点作为“拐点”时的路径和
int priceNewPath = node->val + leftGain + rightGain;
// 3. 更新全局最大值
max_sum = max(max_sum, priceNewPath);
// 4. 返回节点的最大贡献值（只能选左右一侧，再加上节点自身）
return node->val + max(leftGain, rightGain);
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return max_sum;
}
};
3454.分割正方形||
class Solution {
public:
// 辅助函数：计算一组区间在 X 轴上的覆盖总长度（处理重叠）
double getUnionWidth(vector<pair<int, int>>& intervals) {
if (intervals.empty()) return 0;
// 按左端点排序
sort(intervals.begin(), intervals.end());
double totalWidth = 0;
int start = intervals[0].first;
int end = intervals[0].second;
for (size_t i = 1; i < intervals.size(); ++i) {
if (intervals[i].first < end) {
// 有重叠，更新右边界
end = max(end, intervals[i].second);
} else {
// 没有重叠，结算上一段区间
totalWidth += (double)(end - start);
start = intervals[i].first;
end = intervals[i].second;
}
}
// 结算最后一段
totalWidth += (double)(end - start);
return totalWidth;
}
double separateSquares(vector<vector<int>>& squares) {
// 1. 收集所有可能的 Y 边界 (离散化)
vector<int> heights;
for (auto& s : squares) {
heights.push_back(s[1]); // y
heights.push_back(s[1] + s[2]); // y + l
}
sort(heights.begin(), heights.end());
heights.erase(unique(heights.begin(), heights.end()), heights.end());
// 2. 计算整个图形的并集总面积
double totalArea = 0;
// 为了避免重复计算，我们可以先存储每一层的"有效宽度"
// 这里的 map 或者 vector 对应 heights 的下标 -> 该层的宽度
// 考虑到 heights 可能不大，我们可以直接在第二次遍历时重算，或者存下来。
// 为了代码清晰，我演示两次遍历（一次算总面积，一次找分割线）。
// 实际上可以在一次遍历中完成，但逻辑会稍微复杂一点。
// 这里我们先算总面积。
// 注意：这种写法复杂度是 O(N^2)，如果 N 很大需要线段树，但通常题目 N<1000 这种写法能过。
// 实际上，为了效率，我们可以在一步里做：
// 我们需要先知道总面积才能找一半。所以必须先算总面积。
// 让我们优化一下：先计算每一层的宽度存起来
int n = heights.size();
vector<double> layerWidths(n - 1, 0.0);
for (int i = 0; i < n - 1; ++i) {
int h_bottom = heights[i];
int h_top = heights[i+1];
// 找出覆盖这一层的正方形的 X 区间
vector<pair<int, int>> intervals;
for (auto& s : squares) {
int s_y = s[1];
int s_h = s[2];
// 如果正方形覆盖了这个高度区间
if (s_y <= h_bottom && (s_y + s_h) >= h_top) {
intervals.push_back({s[0], s[0] + s[2]});
}
}
layerWidths[i] = getUnionWidth(intervals);
totalArea += layerWidths[i] * (double)(h_top - h_bottom);
}
// 3. 寻找分割线
double targetArea = totalArea / 2.0;
double currentArea = 0;
for (int i = 0; i < n - 1; ++i) {
int h_bottom = heights[i];
int h_top = heights[i+1];
double layerH = (double)(h_top - h_bottom);
double layerW = layerWidths[i];
double thisLayerArea = layerW * layerH;
if (currentArea + thisLayerArea >= targetArea) {
// 分割线就在这一层里面
// 剩余需要的面积
double needed = targetArea - currentArea;
// needed = width * delta_y => delta_y = needed / width
return (double)h_bottom + needed / layerW;
}
currentArea += thisLayerArea;
}
return heights.back();
}
};
160.相交链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
/*
题意理解：如何判定两个链表相交？高效的判定呢？以及如何在O（m+n）的时间复杂度内完成这项工作，怎样来做呢？我知道可以使用双指针来进行遍历，但是在相交点之前，他们各自都有几个节点才到橡胶节点呢？
难道先计算出两个链表各自的长度 然后来进行一起遍历吗 这样的话应可以
还有一种方法就是 假设链表A的长度为A 链表B的长度为B 公共部分为L 那么他们各自的部分为A-L B-L 而如果cur_A将链表A遍历完成之后，再去遍历B-L cur_B 也是一样 那么最后他们走的就都是A+B-L 这样如果有交点那么就能铁定碰见
*/
if (!headA || !headB) return nullptr;
ListNode* curA = headA;
ListNode* curB = headB;
while (curA != curB) {
// 如果 curA 走到末尾，就跳到 headB
curA = curA ? curA->next : headB;
// 如果 curB 走到末尾，就跳到 headA
curB = curB ? curB->next : headA;
}
// 要么相遇于交点，要么相遇于 nullptr（不相交）
return curA;
}
};
206.反转链表
class Solution {
public:
ListNode* reverseList(ListNode* head) {
// pre 充当反转后链表的头部，初始为空
ListNode* pre = nullptr;
ListNode* cur = head;
while(cur) {
// 1. 暂存 cur 后面的节点，防止断链
ListNode* temp = cur->next;
// 2. 核心反转：将当前节点的 next 指向前一个节点 (pre)
// 形象理解：把 cur 这个节点“摘”下来，“头插”到 pre 的前面
cur->next = pre;
// 3. 更新指针：pre 向前走一步，成为新的头
pre = cur;
// 4. 处理下一个节点
cur = temp;
}
// 这里的 pre 此时指向原链表的最后一个非空节点，也就是新链表的头
return pre;
}
};
234.回文链表
//方法1
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head){
ListNode* pre=nullptr;
ListNode* curr=head;
while(curr!=nullptr){
ListNode* next=curr->next;
curr->next=pre;
pre=curr;
curr=next;
}
return pre;
}
bool isPalindrome(ListNode* head) {
/*
题意理解：需要使用O（n）的时间复杂度以及O（1）的时间复杂度
应该怎样来解题？----->当然最笨的办法就是将这些节点的数据全部收集起来串成一个字符串 然后进行经典的字符串的回文判断
使用快慢指针找中点，然后在将后半部分链表进行反转 然后在进行比较
*/
if(!head || !head->next) return true;
//使用快慢指针找打中点
ListNode* slow=head;
ListNode* fast=head;
while(fast->next && fast->next->next){
slow=slow->next;
fast=fast->next->next;
}
//找到中点然后进行反转链表
ListNode* second_half = reverseList(slow->next);
//比较前半部分和反转后的后半部分
ListNode* first_half=head;
ListNode* second_half_temp=second_half;
bool rel=true;
while(second_half_temp!=nullptr){
if(first_half->val!=second_half_temp->val){
rel=false;
break;
}
first_half=first_half->next;
second_half_temp=second_half_temp->next;
}
return rel;
}
};
//方法2：哈希法
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
// 如果是空链表或只有一个节点，直接视为回文
if (!head || !head->next) return true;
// 使用 unsigned long long 可以在溢出时自动取模 (相当于对 2^64 取模)
// 也可以手动指定一个大质数 MOD，这里为了代码简洁利用了自然溢出
// 选取一个质数作为基底 (Base)，类似我们把字符串看成 131 进制数
const int BASE = 131;
unsigned long long hash_fwd = 0; // 正向哈希值
unsigned long long hash_rev = 0; // 反向哈希值
unsigned long long base_pow = 1; // 记录当前位的权重 (BASE^k)
ListNode* curr = head;
while (curr != nullptr) {
// 1. 正向计算：每遇到一个新节点，旧的哈希值整体左移一位，加上新值
// 公式：Hash = Hash * BASE + val
hash_fwd = hash_fwd * BASE + curr->val;
// 2. 反向计算：新节点放在当前的高位上
// 公式：Hash = Hash + val * BASE^k
hash_rev = hash_rev + curr->val * base_pow;
// 3. 更新权重，准备下一轮
base_pow *= BASE;
curr = curr->next;
}
// 如果是对称的，正反计算出的“特征值”应该相等
return hash_fwd == hash_rev;
}
};
class Solution {
private:
ListNode* frontPointer; // 用于正向遍历的指针
// 递归辅助函数
bool recursivelyCheck(ListNode* currentPointer) {
// base case: 递归到了链表尾部的 nullptr，此时认为无需比较，返回 true
if (currentPointer == nullptr) {
return true;
}
// Step 1: 先递归深入到下一个节点 (一直钻到底)
// 如果子问题返回 false，说明后面已经匹配失败了，直接一路 false 返回去
if (!recursivelyCheck(currentPointer->next)) {
return false;
}
// Step 2: 这里的代码是在递归“归来”时执行的
// 此时 currentPointer 是倒序移动的 (从尾部向头部)
// 而 frontPointer 我们让它手动正序移动
if (currentPointer->val != frontPointer->val) {
return false;
}
// Step 3: 移动正向指针，为下一次比较做准备
frontPointer = frontPointer->next;
return true;
}
public:
bool isPalindrome(ListNode* head) {
frontPointer = head; // 初始化正向指针指向头
return recursivelyCheck(head);
}
};
2975.移除栅栏得到的正方形田地的最大面积
class Solution {
public:
int maximizeSquareArea(int m, int n, vector<int>& hFences, vector<int>& vFences) {
/*
这里我们其实是可以求一个最大的正方形田地，我这个正方形田地 他的最长宽度一定是由我们的m*n这个矩形田地中
较小边来决定的 因此我认为应该是首先去判定较小边 然后我们绕着较小边 看是否能够通过移除栅栏 来构成一个适配于
最短边的正方形矩形
不过单纯这样想的话 比较片面我觉得 那如果外围就是不能够移开呢？而我们的里层反而可以通过移开一些然后来达到这个
正方形矩形目的----->此时我们应该怎么办？
首先，明确最大的正方形边长就是我们m n中较小的那条边
我在想的是 我能否方向来计算呢？就是我统计可以形成正方形的所有可能 也就是从0开始开始构造我们的最后的拥有栅栏的
矩形田地
但是这样的话还是有问题 就是不一定栅栏的顺序就是可以按照顺序来移除的啊
那我是不是就只有这样的思路了 先得到较小的边 这个是我们可以得到的最大的正方形面积的边长
然后依次的去判断是否可能
但是我们在转换一下视角 一个正方形他一定是由上下两个水平栅栏 然后竖直两根栅栏来形成的
如果我们能够找到两个水平栅栏围成的高以及两根竖直栅栏围成的宽 两者想等 我们就视为一种正方形可能
*/
//预处理 先将边界加入
hFences.push_back(1);hFences.push_back(m);sort(hFences.begin(),hFences.end());
vFences.push_back(1);vFences.push_back(n);sort(vFences.begin(),vFences.end());
//收集水平的所有可能间距
unordered_set<int> HGaps;
for(int i=0;i<hFences.size();i++){
for(int j=i+1;j<hFences.size();j++){
HGaps.insert(hFences[j]-hFences[i]);
}
}
long long ans=-1;
//遍历所有可能的竖直方向的距离可能
for(int i=0;i<vFences.size();i++){
for(int j=i+1;j<vFences.size();j++){
int WGps=vFences[j]-vFences[i];
//检查是否在HGps中出现过 如果出现过 就更新ans
if(HGaps.count(WGps)){
ans=max(ans,(long long)WGps);
}
}
}
if(ans==-1) return -1;
long long mod=1e9+7;
return (ans*ans)%mod;
}
};
142.环形链表||
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
/*
解这个题需要做两件事 第一件事，判定首先是不是环形链表
第二件事，在说找到入口点的事情
怎样判定是不是环形链表
使用双指针来先判定是不是有环---如果有环那么迟早能相遇
但是如何来判定环形链表的入口呢？
这里会用到Floyd判圈法
*/
ListNode* fast=head;
ListNode* slow=head;
while(fast!=NULL && fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
//步骤1.判定是否有环
if(fast==slow){
// 相遇了，说明有环！
// 步骤二：寻找入口点
// 此时 slow (或者 fast) 停在相遇点
// 我们新开一个指针 index1 从头开始
ListNode* index1=head;
ListNode* index2=slow;
while(index1!=index2){
index1=index1->next;
index2=index2->next;
}
return index1;
}
}
return NULL;
}
};
21.合并两个有序链表
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
/*
题意理解：注意解题细节即可，这个直接进行判断 直接将list2上的数据挂到list1
*/
ListNode dummy(0);
ListNode* tail=&dummy;
ListNode* cur1=list1;
ListNode* cur2=list2;
while(cur1!=nullptr && cur2!=nullptr ){
if(cur2->val >= cur1->val){
//先暂存cur1->next
tail->next=cur1;
cur1=cur1->next;
}
else{
tail->next=cur2;
cur2=cur2->next;
}
tail=tail->next;
}
tail->next=cur1?cur1:cur2;
return dummy.next;
}
};
2.两数相加
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
/*
两数相加：这个链表是逆序存储的 一个很自然的方法当然是将两个链表里的数字先存储在数组里
然后进行两数相加的逻辑 然后在将其存入到链表中
但是这样的话 空间复杂度就很高了 时间复杂度因为多次遍历那么也至少是三次O(n)
那么我可以先将链表反转 然后在将其按照两数相加的方式来进行相加可以吗
*/
//然后来进行相加 将其加入到l1表
ListNode dummy(0);
ListNode* tail=&dummy;
int up_num=0;
while(l1!=nullptr || l2!=nullptr || up_num!=0){
int n1=(l1!=nullptr)?l1->val:0;
int n2=(l2!=nullptr)?l2->val:0;
int sum=n1+n2+up_num;
//更新进位于当前位
up_num=sum/10;
tail->next=new ListNode(sum%10);
tail=tail->next;
//移动指针
if(l1) l1=l1->next;
if(l2) l2=l2->next;
}
return dummy.next;
}
};
19.删除链表的倒数第N个节点
//解法1
class Solution {
public:
ListNode* reverse(ListNode* head){
ListNode* pre=nullptr;
ListNode* cur=head;
while(cur){
ListNode* tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
//删除链表的倒数第N的节点 即整数的第N个节点
//先反转
ListNode dummy(0);
ListNode* cur=&dummy;
cur->next=reverse(head);
//我们要删除第N个节点 那么就遍历到第n-1个节点就行
for(int i=0;i<n-1;i++){
cur=cur->next;
}
ListNode* tmp=cur->next;
cur->next=cur->next->next;
delete tmp;
return reverse(dummy.next);
}
};
//解法2
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
dummy.next = head;
ListNode* fast = &dummy;
ListNode* slow = &dummy;
// 1. 快指针先走 n + 1 步
for (int i = 0; i <= n; i++) {
fast = fast->next;
}
// 2. 快慢指针同时移动，直到快指针到底
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
// 3. 此时 slow 就在倒数第 N 个节点的前面
ListNode* tmp = slow->next;
slow->next = slow->next->next;
delete tmp;
return dummy.next;
}
};
3047.求交集区域的最大矩形面积※
class Solution {
public:
long long largestSquareArea(vector<vector<int>>& bottomLeft, vector<vector<int>>& topRight) {
/*
求交集区域内的最大正方形面积
题意理解：两个数组其实的每一个下标所代表的其实是围成了一个矩形
我们选择可以放入两个矩形交集的最大矩形面积，其实就是求我们能够获得的最大交集区域的矩形中的正方形面积
那么我们从源头出发，想一想交集区域是怎样形成的-----还有这里我们必须记住是每一个下标两个数组是绑定的 不能随便的排序
两个交集怎样形成-----
1.后一个矩形的右下角在本矩形右上角的左下方
仔细考虑 我们的矩形相交一共有大概七种情况，如果一一判断的话我感觉太过冗余了 我们还是应该考虑一种比较高效的方式
我们是否可以直接将两个数组合并 然后相当于对矩形来排序 然后这样我们就不需要考虑那种不是连续的那种重合情况了是不是 直接就进行
连续处理
*/
long long max_side=0;
int n=bottomLeft.size();
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
//利用投影思想
int x_left=max(bottomLeft[i][0],bottomLeft[j][0]);
int x_right=min(topRight[i][0],topRight[j][0]);
int x_bottom=max(bottomLeft[i][1],bottomLeft[j][1]);
int x_top=min(topRight[i][1],topRight[j][1]);
//然后看看是否有重叠
if(x_right > x_left && x_top > x_bottom){
//计算差值
int w=x_right-x_left;
int h=x_top-x_bottom;
//然后计算当前的最大值
int cur_side=min(h,w);
if(cur_side>max_side){
max_side=cur_side;
}
}
}
}
return max_side*max_side;
}
};
24.两两交换链表中的节点【手动模拟一下即知】
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
/*
两两进行交换---->就像之前提及到的一个K节点交换一个道理
*/
ListNode dummyhead(0);
ListNode* cur=&dummyhead;
cur->next=head;
if(cur->next==NULL || cur->next->next==NULL){
return head;
}
while(cur->next!=NULL && cur->next->next!=NULL){
//先暂存第一个节点
ListNode* temp=cur->next;
//然后让cur->next指向原本的第二个节点 让其变为第一个节点
cur->next=temp->next;
//第三步，让原本第二个节点的后一个节点指向原本的第一个节点的next
temp->next=cur->next->next;
//然后让原本的第二节点的next指向第一个节点
cur->next->next=temp;
//最后，让cur移项下一个需要交换的两个节点的前一个节点
cur=temp;
}
return dummyhead.next;
}
};
25.K个一组的翻转链表
class Solution {
public:
// 这里的翻转逻辑稍微改一下，让它单纯只负责翻转一个区间的链表
// 能够将 head -> ... -> tail 翻转为 tail -> ... -> head
void reverse(ListNode* start, ListNode* end) {
ListNode* prev = nullptr;
ListNode* curr = start;
ListNode* stop = end->next; // 记住我们要反转到哪儿停下
while (curr != stop) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
}
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head || k <= 1) return head;
ListNode dummy(0);
dummy.next = head;
// slow 对应你思路中的“指向K个节点前面”的指针
ListNode* slow = &dummy;
// fast 对应你思路中的“快指针”，用来探路
ListNode* fast = &dummy;
while (true) {
// 1. Fast 指针先走 K 步
for (int i = 0; i < k; i++) {
fast = fast->next;
// 如果中途 fast 没了，说明剩下的节点不足 k 个，直接结束，保留原样
if (!fast) return dummy.next;
}
// 此时：
// slow 指向本组的前驱节点 (pre)
// fast 指向本组的最后一个节点 (tail)
// 记录下一组的开头，防止断链
ListNode* next_group_head = fast->next;
// 记录本组的开头（翻转后它会变成尾部）
ListNode* start = slow->next;
// 2. 执行翻转
// 为了方便翻转，我们可以先暂时切断 fast 后面的连接，或者修改 reverse 函数逻辑
// 这里我们采用不切断，直接传参给 reverse 函数控制边界的方式（见上方 reverse 修改）
reverse(start, fast);
// 3. 重新连接
// slow (pre) 的 next 应该指向翻转后的新头 (也就是原来的 fast)
slow->next = fast;
// start (原来的头，现在的尾) 的 next 应该指向下一组的头
start->next = next_group_head;
// 4. 指针复位，准备下一轮
// 现在的 start 已经是这一组的尾部了，它就是下一组的 "slow" (前驱)
slow = start;
fast = start; // fast 也回到这就位，准备下一次探路
}
return dummy.next;
}
};
1292.元素和小于等于阈值的正方形的最大边长
class Solution {
public:
bool check(int side_len,int m,int n,const vector<vector<int>>& P,int threshold){
if(side_len==0) return true;
for(int i=side_len;i<=m;i++){
for(int j=side_len;j<=n;j++){
//然后来检查是否有满足的
int current_sum=P[i][j]-P[i-side_len][j]-P[i][j-side_len]+P[i-side_len][j-side_len];
if(current_sum<=threshold){
return true;
}
}
}
return false;
}
int maxSideLength(vector<vector<int>>& mat, int threshold) {
/*
取一个正方形区域 其区域内的元素的和需要小于阈值
先进行暴力解决：先将暴力解决的思路给出，然后在进一步的优化：
其实我们是需要找最大的正方形 那么我们从每个节点出发 最开始就是这个节点 那么边长变为2的时候 就需要右边 下边 右下加起来四个数据了 然后依次类推
直到不满足阈值条件的时候----继续下一个位置 这样我们一共需要遍历O(n*m*(n-i)*(m-j))---这样下来大概是O(n^2 m^2)的时间复杂度
时间复杂度太高 但是我们又改怎样的来降低时间复杂度呢?
*/
int m=mat.size(),n=mat[0].size();
//构建一个m+1 n+1的前缀和数组
vector<vector<int>> P(m+1,vector<int>(n+1,0));
//然后因为我们是需要从上方 左方 以及左上方来进行遍历
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
P[i][j]=P[i-1][j]+P[i][j-1]-P[i-1][j-1]+mat[i-1][j-1];//上方+左方-左上方+当前位置
}
}
//然后我们来进行二分查找
int l=0,r=min(n,m);
int ans=0;
while(l<=r){
int mid=l+(r-l)/2;
if(check(mid,m,n,P,threshold)){
l=mid+1;
//更新ans
ans=max(ans,mid);
}else{
r=mid-1;
}
}
return ans;
}
};
3314.构造位运算最小的数组|
1877.数组中最大数对和的最小值
class Solution {
public:
int minPairSum(vector<int>& nums) {
/*
这个题的方案也就是让我们来划分数对，然后我们采用的方法
一定是所有划分数对的方案中，其最大数对和最小的
那么我们可以怎么样来做？
最笨的办法是什么？每一个nums[i]都可以与其他的元素有关系 那么这样加起来一共有n-1个方案
但是这样的话时间复杂度肯定是很高的 那么我们如何来进一步的降低这个时间复杂度呢？
*/
sort(nums.begin(),nums.end());
int min_num=INT_MIN;
int left=0,right=nums.size()-1;
while(left<=right){
if(nums[left]+nums[right]>min_num){
min_num=nums[left]+nums[right];
}
left++;right--;
}
return min_num;
}
};
1984.学生分数的最小差值
class Solution {
public:
int minimumDifference(vector<int>& nums, int k) {
//排序选择中间最小的
sort(nums.begin(),nums.end());
int sub=INT_MAX;
for(int i=0;i<nums.size()-k+1;i++){
if(nums[i+k-1]-nums[i]<=sub){
sub=nums[i+k-1]-nums[i];
}
}
return sub;
}
};
146.LRU缓存
class LRUCache {
public:
/*
题目理解：我们应该怎样来设计这个数据结构 首先分析一下这个类的要求
LRUCache(int capacity)：要求必须是正整数，那么是0或者负数 先报错吗 然后来重新resize这个数据结构的大小
get(int key):通过key来查询值的话，那么我们就需要建立比如map这样的容器
put(int key, int value)：这里我们需要完成三类操作，如果key已经存在 那么更新;如果不存在，那么就直接插入，但是再插入之前还需要检查当前的
容器里面元素的数量是不是超过capacity 如果超出那么就需要主厨最长时间未使用的的关键字
那么我们这里其实重点是如何来逐出这个最长时间的关键字 而我们的get put又要去O(1）的操作 那么肯定就需要如map这样的容器 并且这里put这个最久未使用的关键字
这个关键字肯定是处于队头或者队尾的 这样才能O(1)的操作
*/
//定义放在链表中的结构
struct node{
int key;
int value;
};
std::list<node> my_list;
std::unordered_map<int,std::list<node>::iterator> maps;
int cap=0;//缓存的最大容量
LRUCache(int capacity) {
if(capacity > 0) cap=capacity;
}
int get(int key) {
//1.先看看是不是在缓存中
if(maps.find(key)==maps.end()){
return -1;
}
//2.如果key存在 说明被访问了 先将其提拔到队列头部
//使用splice函数 将my_list中maps[key]指向的节点剪切并移动到my_list的头部
//splice是O(1)的操作，只修改指针，不涉及内存拷贝
my_list.splice(my_list.begin(),my_list,maps[key]);
//3.返回该节点的值
return maps[key]->value;
}
void put(int key, int value) {
//1.情况1 key已经存在
if(maps.find(key)!=maps.end()){
//那么就更新 先将其提拔到队列头部
maps[key]->value=value;
my_list.splice(my_list.begin(),my_list,maps[key]);
return;
}
//2.节点不存在 需要插入新节点
//先检查容量
if(my_list.size()==cap){
//这里注意的是，我们需要先删map里的记录 然后再来删list的节点
//因为我们需要通过list.back()来查看我们需要删谁
int key_to_remove=my_list.back().key;
maps.erase(key_to_remove);
my_list.pop_back();
}
//然后在将节点插入到链表头部
my_list.push_front({key,value});
maps[key]=my_list.begin();
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
128.最长连续序列
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
//这里他要我时间复杂度为O(n)的算法我可以这样不 建立一个数组 然后从nums里面钠元素
//然后不断的往里面填 最后来统计最大的连续长度
//但是这样肯定会超时，内存空间肯定会爆炸
unordered_set<int> st(nums.begin(),nums.end());//把nums转成哈希集合
int ans=0;
for(int x:st){
//1.先看是不是有x-1
if(st.contains(x-1)){
continue;
}
//x是序列起点
int y=x+1;
//然后再看能不能连起来
while(st.contains(y)){//不断查找下一个数是否在哈希集合中
++y;
}
//循环结束后 更新
ans=max(ans,y-x);
}
return ans;
}
};
2007.从双倍数组中还原数组
class Solution {
public:
vector<int> findOriginalArray(vector<int>& changed) {
//这里我们可以遇见的是这里我们的changed数组应该是2*n的长度
//那么original肯定就是N的长度 然后我们可以怎样
//将changed数组转为set数组 然后遍历其中的每一个元素 看其除以2是否在set中有 如果有就输出
int N_2=changed.size();
if(N_2%2!=0) return {};
//1.排序
sort(changed.begin(),changed.end());
//2.计数
unordered_map<int,int> count;
for(int x:changed){
count[x]++;
}
//然后来处理
vector<int> original;
for(int x:changed){
if(count[x]==0) continue;
count[x]--;
//看看有没有他的2倍
if(count[2*x]>0){
count[2*x]--;
original.push_back(x);
}else{
//找不到对应的双倍数
return {};
}
}
return original.size()==N_2/2?original:vector<int>{};
}
};
54.螺旋矩阵
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return {};
int m=matrix.size(),n=matrix[0].size();
vector<int> ans;
vector<vector<bool>> visited(m,vector<bool>(n,false));
//2.定义方向:右(0,1) 下(1,0) 左（0,-1） 上 (-1,0)
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int r=0,c=0,cur_d=0;
for(int i=0;i<n*m;i++){
ans.push_back(matrix[r][c]);
visited[r][c]=true;
//尝试走下一步
int next_r=r+dx[cur_d];
int next_c = c + dy[cur_d];
// 3. 判断是否需要转向
if (next_r < 0 || next_r >= m || next_c < 0 || next_c >= n || visited[next_r][next_c]) {
cur_d = (cur_d + 1) % 4; // 顺时针转向
next_r = r + dx[cur_d];
next_c = c + dy[cur_d];
}
r = next_r;
c = next_c;
}
return ans;
}
};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty()) return {};
// 定义四个边界
int upper = 0;
int lower = matrix.size() - 1;
int left = 0;
int right = matrix[0].size() - 1;
vector<int> ans;
while (true) {
// 1. 从左向右走 (遍历 upper 行)
for (int j = left; j <= right; ++j) ans.push_back(matrix[upper][j]);
if (++upper > lower) break; // 上边界下移，若越过下边界则结束
// 2. 从上向下走 (遍历 right 列)
for (int i = upper; i <= lower; ++i) ans.push_back(matrix[i][right]);
if (--right < left) break; // 右边界左移
// 3. 从右向左走 (遍历 lower 行)
for (int j = right; j >= left; --j) ans.push_back(matrix[lower][j]);
if (--lower < upper) break; // 下边界上移
// 4. 从下向上走 (遍历 left 列)
for (int i = lower; i >= upper; --i) ans.push_back(matrix[i][left]);
if (++left > right) break; // 左边界右移
}
return ans;
}
};
53.最大子树组合
//解法1：动态规划，如果前面的加起来的和 还没自己大 那么就不继续加 就以自己为新的起点开始子数组求和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<int> dp(nums.size(),0);
int max_result=nums[0];
dp[0]=nums[0];
for(int i=1;i<nums.size();i++){
dp[i] = max(dp[i-1] + nums[i], nums[i]); // 核心 DP 转移
max_result = max(max_result, dp[i]);
}
return max_result;
}
};
76.最小覆盖子串
class Solution {
public:
bool is_covered(const int cnt_s[],const int cnt_t[]){
for(int i='A';i<='Z';i++){
if(cnt_s[i]< cnt_t[i]){
return false;
}
}
for(int i='a';i<='z';i++){
if(cnt_s[i]<cnt_t[i]){
return false;
}
}
return true;
}
string minWindow(string s, string t) {
int cnt_s[128]{};//s子串字母出现的次数
int cnt_t[128]{};//t中字母出现的次数
for(char c:t){
cnt_t[c]++;
}
int m=s.size();
int ans_left=-1,ans_right=m;
int left=0;
for(int rihgt=0;rihgt<m;rihgt++){
//移动子串的右端点
cnt_s[s[rihgt]]++;
//然后来检查左端点
while(is_covered(cnt_s,cnt_t)){
//如果还是满足就不断的更新
if(rihgt-left < ans_right -ans_left){
ans_left=left;
ans_right=rihgt;
}
cnt_s[s[left]]--;
left++;
}
}
return ans_left<0?"":s.substr(ans_left,ans_right-ans_left+1);
}
};
56.合并区间
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
//先将数组按照第一个位置进行排序 然后如果第一个数组的右端点大于别人的左端点 那么就合并
//不过关键是万一是一连串的重叠怎么办 我觉得我们应该是这样维护左边界与右边界 直到不需要更新的时候 在放进结果数组里 并进行下一次的处理
sort(intervals.begin(),intervals.end());
//然后新建一个结果数组
vector<vector<int>> ans;
int left=intervals[0][0],right=intervals[0][1];
for(int i=1;i<intervals.size();i++){
//如果right大于当前结果的左边界 就将最右边界
if(right>=intervals[i][0]) right = max(right, intervals[i][1]);
else{
//不大于在加入到数组
ans.push_back({left,right});
left=intervals[i][0];
right=intervals[i][1];
}
}
//最后还需要加入最后一次的left right
ans.push_back({left,right});
return ans;
}
};
229.多数元素||
```
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
//这里我们需要求次数超过1/3的元素 我们最多可以出现两个不同的数
//这里 然后这里我们可以来确定的是如果这个数组的长度小于3 那么直接返回
//如果大于3 那么这个多数元素的距离最多不超过2 即 1 2 3 1 这样的样式
int candidate_1=0,candidate_2=0;
int count_1=0,count_2=0;
vector<int> ans;
//第一阶段配对抵消
for(int n:nums){
if(n==candidate_1){
count_1++;
}else if(n==candidate_2){
count_2++;
}else if(count_1==0){
candidate_1=n;
count_1=1;
}else if(count_2==0){
candidate_2=n;
count_2++;
}else{
count_1--;
count_2--;
}
}
//然后来检查是不是我们选出的最后两个决胜者能够满足1/3的条件
count_1=0;count_2=0;
for(int n:nums){
if(n==candidate_1) count_1++;
else if(n==candidate_2) count_2++;
}
//最后来检查
if(count_1 > nums.size()/3) ans.push_back(candidate_1);
if(count_2 > nums.size()/3) ans.push_back(candidate_2);
return ans;
}
};
```