3.26更新

2月把hot100过了一遍。2月底-3月中旬根据hot100,codetop,面经，整理了一套自己的题单和笔记，刷了一遍。唉反复刷反复忘。先开始背八股了，八股背完看看再刷一遍就投。

hot100 45道

⭐️：codetop上高频，前60道，100次以上

🔥：朋友帖子,40道常考手撕

合集：28道，并集：72道

⭐️1. 两数之和✅

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i++){
            auto it=mp.find(target-nums[i]);
            if(it!=mp.end()) return {it->second,i};
            mp.insert(pair(nums[i],i));
        }
        return {};
    }

遍历数组，用哈希表记录已经访问过的数字及其下标。

在哈希表中查找是否存在“互补数”，找到了，返回互补数的下标和当前下标。2. 没找到，将当前数值和下标存入哈希表。

Key 存储数字的值，Value 存储该数字在数组中的下标。使用 find 而不是 mp[target - nums[i]] 的好处是：find 不会因为没找到而往 map 里插入多余的默认值，效率更高。

O(n)/O(n)

为什么用 unordered_map 而不是 map**？**

unordered_map 基于哈希表，平均查找 O(1)；map 基于红黑树，查找是 O(log n)。在不需要有序的情况下，哈希表更快。

使用 it**：避免二次查找。** mp.find() 已经定位到了该元素在哈希表中的位置。直接通过 it->second 取值，时间复杂度是 O(1)。使用了 find 返回的迭代器，这样在确认元素存在后，可以直接从迭代器取值，避免了重复哈希计算带来的性能开销。

ACM处理1

#include <iostream>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < (int)nums.size(); i++) {
        auto it = mp.find(target - nums[i]);
        if (it != mp.end()) return {it->second, i};
        mp[nums[i]] = i;
    }
    return {};
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, target;
    while (cin >> n >> target) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
 
        vector<int> res = twoSum(nums, target);
 
        if (!res.empty()) {
            cout << res[0] << " " << res[1] << "\n";
        } else {
            cout << "No Solution\n";
        }
    }
    return 0;
}

⭐️2. 两数相加✅

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry=0;
        ListNode dummy(0);
        ListNode* tail=&dummy;
        while(l1||l2||carry){
            int sum=(l1?l1->val:0)+(l2?l2->val:0)+carry;
            tail->next=new ListNode(sum%10);
            tail=tail->next;
            carry=sum/10;
            if(l1) l1=l1->next;
            if(l2) l2=l2->next;
        }
        return dummy.next;
    }

模拟竖式加法。同时遍历两个**链表**，逐位相加，处理进位，用虚拟头节点简化边界处理，直到两个链表都遍历完且没有进位为止。

循环条件分析：while(l1 || l2 || carry)

l1 未遍历完：还有数字要加
l2 未遍历完：还有数字要加
carry != 0：还有进位要处理（如 9+9=18 的情况）

边界情况：

链表长度不同：短链表用 0 补齐 ✓
最后有进位：循环条件包含 carry，会额外创建节点 ✓
空链表：相当于加 0，算法仍然正确 ✓
大数相加：链表表示天然支持大数，不会溢出 ✓

复杂度：

时间复杂度：O(max(m, n))
- m, n 分别是两个链表的长度
- 需要遍历较长的链表
空间复杂度：O(max(m, n))
- 结果链表长度最多为 max(m, n) + 1（有进位时）
- 不包括输入链表，只计算额外空间

ACM处理2

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* buildList(const vector<int>& nums) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int x : nums) {
        cur->next = new ListNode(x);
        cur = cur->next;
    }
    return dummy.next;
}
 
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}
 
// --- 核心代码分离 ---
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int carry = 0;
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 || l2 || carry) {
        int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
        tail->next = new ListNode(sum % 10);
        tail = tail->next;
        carry = sum / 10;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    return dummy.next;
}
 
// --- main 处理输入输出 ---
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n1, n2;
    while (cin >> n1 >> n2) {
        vector<int> v1(n1), v2(n2);
        for (int i = 0; i < n1; i++) cin >> v1[i];
        for (int i = 0; i < n2; i++) cin >> v2[i];
 
        ListNode* l1 = buildList(v1);
        ListNode* l2 = buildList(v2);
 
        ListNode* res = addTwoNumbers(l1, l2);
 
        printList(res);
    }
    return 0;
}

🔥⭐️3. 无重复字符的最长子串✅

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> cnt;
        int left=0,ans=0;
        for(int i=0;i<s.size();i++){
            cnt[s[i]]++;
            while(cnt[s[i]]>1){
                cnt[s[left]]--;
                left++;
            }
            ans=max(ans,i-left+1);
        }
        return ans;
    }

维护一个不含重复字符的滑动窗口，用哈希表记录窗口内字符的出现次数，当窗口右侧加入新字符导致重复时，移动窗口左侧直到重复消除，过程中记录窗口的最大长度。

ACM处理3

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s;
    while (cin>>s) {              // EOF，多组字符串
        cout<<lengthOfLongestSubstring(s)<<'\n';
    }
    return 0;
}

⭐️4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size()>nums2.size()) return findMedianSortedArrays(nums2,nums1);
        int m=nums1.size(),n=nums2.size();
        int left=0,right=m;
        while(left<=right){
            int i=(left+right)/2;
            int j=(m+n+1)/2-i;
            int s1_left=(i==0)?INT_MIN:nums1[i-1];
            int s1_right=(i==m)?INT_MAX:nums1[i];
            int s2_left=(j==0)?INT_MIN:nums2[j-1];
            int s2_right=(j==n)?INT_MAX:nums2[j];
            if(s1_left<=s2_right&&s2_left<=s1_right){
                if((m+n)%2==1) return max(s1_left,s2_left);
                else return (max(s1_left,s2_left)+min(s1_right,s2_right))/2.0;
            }else if(s1_left>s2_right) right=i-1;
            else left=i+1;
        }
        return 0.0;
    }

思路：在短数组上二分一个切分点 i，同时在另一个数组确定 j，让左右两边元素个数相等或左边多一个。当左右最大最小满足顺序时，中位数就在边界。

将两个数组分别划分为左右两部分，使得左半部分的所有元素都小于右半部分，且左右数量平衡。

确保 nums1 是较短的数组，在短数组上进行二分查找，可以保证时间复杂度最小，同时确保在计算长数组切割位置 j 时，它永远不会是负数。

左边总元素个数 = (m + n + 1) / 2

nums1 左边取 i 个，nums2 左边就必须取 j

+1的作用，统一奇偶情况，奇数时：左边比右边多 1，中位数就在左边

left 和 right 是对短数组 nums1 进行二分查找的边界。

关键公式：i + j = (m + n + 1) / 2。这保证了左半部分的总数等于右半部分（或多 1 个，针对总数为奇数的情况）。

如果分割点在数组最左边（i=0），左侧没有元素，设为负无穷 INT_MIN。

如果分割点在最右边（i=m），右侧没有元素，设为正无穷 INT_MAX。

if(s1_left<=s2_right && s2_left<=s1_right)

条件成立：说明左边两部分的最大值都小于右边两部分的最小值，即找到了完美的切分。

奇数情况

左边比右边多 1
中位数 = 左半部分最大值

偶数情况

左右一样多
中位数 = 左最大 + 右最小 / 2

i=0：nums1 左边一个都不取，i=m：nums1 全部放左边

ACM处理4

#include <bits/stdc++.h>
using namespace std;
 
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size()) return findMedianSortedArrays(nums2, nums1);
    int m = nums1.size(), n = nums2.size();
    int left = 0, right = m;
    while (left <= right) {
        int i = (left + right) / 2;
        int j = (m + n + 1) / 2 - i;
        int s1_left = (i == 0) ? INT_MIN : nums1[i - 1];
        int s1_right = (i == m) ? INT_MAX : nums1[i];
        int s2_left = (j == 0) ? INT_MIN : nums2[j - 1];
        int s2_right = (j == n) ? INT_MAX : nums2[j];
        if (s1_left <= s2_right && s2_left <= s1_right) {
            if ((m + n) % 2 == 1) return max(s1_left, s2_left);
            else return (max(s1_left, s2_left) + min(s1_right, s2_right)) / 2.0;
        } else if (s1_left > s2_right) right = i - 1;
        else left = i + 1;
    }
    return 0.0;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m, n;
    while (cin >> m >> n) {
        vector<int> nums1(m), nums2(n);
        for (int i = 0; i < m; i++) cin >> nums1[i];
        for (int i = 0; i < n; i++) cin >> nums2[i];
 
        double res = findMedianSortedArrays(nums1, nums2);
 
        cout << fixed << setprecision(1) << res << "\n";
    }
    return 0;
}

🔥⭐️5. 最长回文子串✅

给你一个字符串 s，找到 s 中最长的回文子串。

string longestPalindrome(string s) {
        string ans="";
        for(int i=0;i<s.size();i++){
            int l=i-1,r=i+1;
            while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;
            if(ans.size()<r-l-1) ans=s.substr(l+1,r-l-1);
            l=i,r=i+1;
            while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++;
            if(ans.size()<r-l-1) ans=s.substr(l+1,r-l-1);
        }
        return ans;
    }

遍历字符串的每个位置（包括字符和字符之间的间隙），以每个位置为中心向两边扩展，找到以该位置为中心的最长回文子串，并记录全局最长的那个。

中心扩展法：每一个字符（或每两个字符之间）都可以作为回文的中心。

奇数长度：中心是一个字符（如 aba ）；偶数长度：中心是两个字符之间的缝隙（如 abba）

在“中心扩展法”求最长回文子串时，计算长度使用 r - l - 1 是因为当 while 循环停止时，l 和 r 已经指向了不满足回文条件的边界。

时间 $O(n^2$

ACM处理5

#include <bits/stdc++.h>
using namespace std;
 
string longestPalindrome(string s) {
    string ans = "";
    for (int i = 0; i < s.size(); i++) {
        int l = i - 1, r = i + 1;
        while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
        if (ans.size() < r - l - 1) ans = s.substr(l + 1, r - l - 1);
 
        l = i, r = i + 1;
        while (l >= 0 && r < s.size() && s[l] == s[r]) l--, r++;
        if (ans.size() < r - l - 1) ans = s.substr(l + 1, r - l - 1);
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s;
    while (cin >> s) {
        cout << longestPalindrome(s) << "\n";
    }
    return 0;
}

🔥11. 盛最多水的容器✅

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。

int maxArea(vector<int>& height) {
        int l=0,r=height.size()-1,ans=0;
        while(l<r){
            ans=max(ans,min(height[l],height[r])*(r-l));
            if(height[l]<height[r]) l++;
            else r--;
        }
        return ans;
    }

利用双指针从数组两端向中间收缩，每次计算面积并更新最大值，同时依据贪心策略总是移动高度较短的那一侧指针（因为受限于短板，移动长板面积只会因宽度减小而变小），直到指针相遇。

每次移动高度较小的那一侧指针。

ACM处理11

#include <bits/stdc++.h>
using namespace std;
 
int maxArea(vector<int>& height) {
    int n = height.size();
    int right = n - 1, left = 0, ans = 0;
    while (left < right) {
        int l = right - left;
        ans = max(ans, l * min(height[right], height[left]));
        if (height[right] >= height[left]) left++;
        else right--;
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> height(n);
        for (int i = 0; i < n; i++) cin >> height[i];
        cout << maxArea(height) << "\n";
    }
    return 0;
}

🔥⭐️15. 三数之和✅

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。

vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n=nums.size();
        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            if(nums[i]>0) break;
            if(i>0&&nums[i]==nums[i-1]) continue;
            int j=i+1,k=n-1;
            while(j<k){
                int sum=nums[i]+nums[j]+nums[k];
                if(sum==0){
                    ans.push_back({nums[i],nums[j],nums[k]});
                    int left=nums[j],right=nums[k];
                    while(j<k&&nums[j]==left) j++;
                    while(j<k&&nums[k]==right) k--;
                }else if(sum<0) j++;
                else k--;
            }
        }
        return ans;
    }

先对数组排序，然后固定一个数，用双指针在剩余部分寻找两个数，使得三数之和为0，过程中通过跳过重复元素来避免结果重复。

提前终止：如果固定数 nums[i] > 0，由于数组已升序排序，后面所有数都≥0，三数和不可能为0
去重：如果当前数和前一个数相同，直接跳过，避免重复解

双指针移动逻辑：

sum == 0：记录解，并同时移动左右指针并跳过重复值
sum < 0：和太小，左指针右移（值增大）
sum > 0：和太大，右指针左移（值减小）

复杂度：

时间复杂度：O(n²)
- 排序：O(n log n)
- 双指针遍历：O(n²)，外层循环 O(n)，内层双指针 O(n)
空间复杂度：O(1)（不考虑结果存储），排序可能是 O(log n) 的栈空间

ACM处理15

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        vector<vector<int>> res = threeSum(nums);
 
        for (auto& v : res) {
            cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n';
        }
    }
    return 0;
}

⭐️19. 删除链表的倒数第 N 个结点✅

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next=head;
        ListNode* fast=&dummy;
        ListNode* slow=&dummy;
        while(n--) fast=fast->next;
        while(fast->next){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummy.next;
    }

快指针 fast 先向前移动 n 步，然后快慢指针同步移动，直到快指针到达链表末尾。此时慢指针指向要删除节点的前一个节点，删除。

ACM处理19

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* buildList(const vector<int>& nums) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int x : nums) {
        cur->next = new ListNode(x);
        cur = cur->next;
    }
    return dummy.next;
}
 
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}
 
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* fast = dummy;
    ListNode* slow = dummy;
    while (n--) fast = fast->next;
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    slow->next = slow->next->next;
    return dummy->next;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int count, n;
    while (cin >> count >> n) {
        vector<int> nums(count);
        for (int i = 0; i < count; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        ListNode* res = removeNthFromEnd(head, n);
 
        printList(res);
    }
    return 0;
}

⭐️20. 有效的括号✅

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

bool isValid(string s) {
        if(s.size()%2!=0) return false;
        stack<char> st;
        for(char ch:s){
            if(ch=='(') st.push(')');
            else if(ch=='{') st.push('}');
            else if(ch=='[') st.push(']');
            else{
                if(st.empty()||st.top()!=ch) return false;
                st.pop();
            }
        }
        return st.empty();
    }

利用栈处理嵌套结构，遍历时遇到左括号便将对应的右括号压入栈中，遇到右括号时检查是否与栈顶一致并弹出，最终通过栈是否为空判断所有括号是否正确闭合。

剪枝优化：如果字符串长度是奇数，肯定无法成对匹配，

遇到左括号时，直接把对应的右括号压入栈中。这样后续遇到右括号时，只需要判断是否等于 st.top() 即可。

处理右括号的情况(else), 如果此时栈已经空了（说明右括号多了），或者栈顶元素不是当前正期待的括号（顺序错了，比如 "([)]"）

return st.empty(); 的作用：

如果栈为空：说明每一个入栈的左括号都被对应的右括号抵消掉了。

如果栈不为空：说明还有左括号在等它的右括号，但字符串已经结束了。

ACM处理20

#include <bits/stdc++.h>
using namespace std;
 
bool isValid(string s) {
    if (s.size() % 2 != 0) return false;
    stack<char> st;
    for (char ch : s) {
        if (ch == '(') st.push(')');
        else if (ch == '{') st.push('}');
        else if (ch == '[') st.push(']');
        else {
            if (st.empty() || st.top() != ch) return false;
            st.pop();
        }
    }
    return st.empty();
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s;
    while (cin >> s) {
        if (isValid(s)) cout << "true" << "\n";
        else cout << "false" << "\n";
    }
    return 0;
}

🔥⭐️21. 合并两个有序链表✅

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy(0);
        ListNode* cur=&dummy;
        while(list1&&list2){
            if(list1->val<list2->val){
                cur->next=list1;
                list1=list1->next;
            }else{
                cur->next=list2;
                list2=list2->next;
            }
            cur=cur->next;
        }
        cur->next=list1?list1:list2;
        return dummy.next;
    }

利用虚拟头节点 (Dummy Head) 简化结果链表的构建，通过循环比较两个有序链表的当前节点值，将较小者依次拼接到新链表末尾，并在循环结束后直接挂接剩余的非空链表段。

ACM处理21

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* buildList(const vector<int>& nums) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int x : nums) {
        cur->next = new ListNode(x);
        cur = cur->next;
    }
    return dummy.next;
}
 
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}
 
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    while (list1 && list2) {
        if (list1->val < list2->val) {
            cur->next = list1;
            list1 = list1->next;
        } else {
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next;
    }
    cur->next = list1 ? list1 : list2;
    return dummy->next;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n1, n2;
    while (cin >> n1 >> n2) {
        vector<int> v1(n1), v2(n2);
        for (int i = 0; i < n1; i++) cin >> v1[i];
        for (int i = 0; i < n2; i++) cin >> v2[i];
 
        ListNode* l1 = buildList(v1);
        ListNode* l2 = buildList(v2);
 
        ListNode* res = mergeTwoLists(l1, l2);
 
        printList(res);
    }
    return 0;
}
#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
 
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
 
    cur->next = l1 ? l1 : l2;
 
    return dummy.next;
}
 
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
 
int main() {
    // 写死测试用例
    // l1 = 1->2->4
    ListNode* a1 = new ListNode(1);
    ListNode* a2 = new ListNode(2);
    ListNode* a3 = new ListNode(4);
    a1->next = a2;
    a2->next = a3;
 
    // l2 = 1->3->4
    ListNode* b1 = new ListNode(1);
    ListNode* b2 = new ListNode(3);
    ListNode* b3 = new ListNode(4);
    b1->next = b2;
    b2->next = b3;
 
    ListNode* result = mergeTwoLists(a1, b1);
    printList(result);
 
    return 0;
}

🔥⭐️22. 括号生成✅

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

class Solution {
public:
    string path="";
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        backtrack(n,n);
        return res;
    }
    void backtrack(int left,int right){
        if(right<left||left<0||right<0) return;
        if(left==0&&right==0){
            res.push_back(path);
            return;
        }
        path.push_back('(');
        backtrack(left-1,right);
        path.pop_back();
        path.push_back(')');
        backtrack(left,right-1);
        path.pop_back();
    }
};

利用回溯算法（DFS）逐位构建字符串，维护剩余左右括号的计数，并通过“剩余右括号数不能少于剩余左括号数”这一约束条件提前剪枝非法路径，从而生成所有有效的括号组合。

left 和 right 分别代表剩余可用的左括号和右括号的数量。

初始状态：left = n, right = n。

终止状态：left == 0 && right == 0（所有的括号都用完了）。

right < left：这是合法括号组合的铁律。在生成过程中，剩余的右括号数量必须大于等于左括号数量。

尝试放入左括号：path.push_back('(') 递归 path.pop_back()。

时间：卡特兰数，空间：O(n)

ACM处理22

#include <bits/stdc++.h>
using namespace std;
 
string path;
vector<string> res;
 
void backtrack(int left, int right) {
    if (right < left || left < 0 || right < 0) return;
    if (left == 0 && right == 0) {
        res.push_back(path);
        return;
    }
    path.push_back('(');
    backtrack(left - 1, right);
    path.pop_back();
 
    path.push_back(')');
    backtrack(left, right - 1);
    path.pop_back();
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        path.clear();
        res.clear();
 
        backtrack(n, n);
 
        for (auto &s : res) {
            cout << s << '\n';
        }
    }
    return 0;
}

🔥⭐️23. 合并 K 个升序链表✅

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

struct Cmp{
    bool operator()(ListNode* a,ListNode* b)const{
        return a->val>b->val;
    }
};
 
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*,vector<ListNode*>,Cmp> pq;
        for(auto head:lists){
            if(head) pq.push(head);
        }
        ListNode dummy(0);
        ListNode* tail=&dummy;
        while(!pq.empty()){
            ListNode* cur=pq.top();pq.pop();
            tail->next=cur;
            tail=tail->next;
            if(cur->next) pq.push(cur->next);
        }
        return dummy.next;
    }

用一个小根堆维护 k 个链表的当前头结点，每次取出最小的节点接到结果链表中，再把该节点的 next 放回堆，时间复杂度是 O(N log k)。

Cmp 是一个比较器，它告诉 priority_queue： 如果 a 的值比 b 大，那么 a 的优先级更低，应该排在后面

bool operator(): 重载括号运算符，使 Cmp 的实例可以像函数一样被调用。

STL 容器可能以 const 方式持有比较器，因此 operator() 需要是 const。

a->val > b->val:在 C++ 优先队列中，比较函数返回 true 表示第一个参数的优先级低于第二个参数。

priority_queue 的规则：Compare(a, b) == true ⇒ a 的优先级低于 b

priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;

定义一个小根堆 pq，堆中存的是 ListNode*，底层用 vector 存储，比较规则由 Cmp 决定。

pq存储了 K 个链表的当前头节点

小根堆：a->val > b->val → a 排后面，val 小的排前面，堆顶是最小值

遍历 lists 数组（即 K 个链表的头）。

if (head): 必须检查，防止将 nullptr 推入堆，否则后续访问 val 会崩溃。

pq.push(head): 堆会自动根据 val 进行调整，此时堆顶就是 K 个链表中最小的那个节点。

取出全场最小值，将其从堆中弹出，把这个最小节点接到结果链表后面，移动尾指针到最新的节点上，如果被弹出的节点后面还有兄弟节点，把兄弟节点送进堆去参加下一轮“海选”

pq.top() 返回的是当前堆中所有节点里 val 最小的那个节点的指针。

pq.pop() 把这个指针从堆里删掉。堆里存的是 ListNode*（指针/内存地址）

pq.pop() 弹出的是地址信息，而不是销毁**内存**。只是把一个**指针**从队列的数据结构里移除了。

cur：是当前 k 个链表头中最小节点的“接力棒”。

pop：是为了腾出位置，好让被取出的节点的下一个节点有机会进入堆进行下一轮竞争。

从堆顶取出当前所有链表中最小的节点,将该节点的指针从堆中弹出

$O(N \log K$ ,O(K). 堆操作logk

ACM处理23

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* buildList(const vector<int>& nums) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int x : nums) {
        cur->next = new ListNode(x);
        cur = cur->next;
    }
    return dummy.next;
}
 
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}
 
struct Cmp {
    bool operator()(ListNode* a, ListNode* b) const {
        return a->val > b->val;
    }
};
 
ListNode* mergeKLists(vector<ListNode*>& lists) {
    priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
    for (ListNode* head : lists) {
        if (head) pq.push(head);
    }
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (!pq.empty()) {
        ListNode* cur = pq.top();
        pq.pop();
        tail->next = cur;
        tail = tail->next;
        if (cur->next) {
            pq.push(cur->next);
        }
    }
    return dummy.next;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int k;
    while (cin >> k) {
        vector<ListNode*> lists;
        for (int i = 0; i < k; i++) {
            int n;
            cin >> n;
            vector<int> nums(n);
            for (int j = 0; j < n; j++) cin >> nums[j];
            lists.push_back(buildList(nums));
        }
 
        ListNode* res = mergeKLists(lists);
        printList(res);
    }
    return 0;
}

⭐️31. 下一个排列✅

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。
必须** 原地 **修改，只允许使用额外常数空间。

void nextPermutation(vector<int>& nums) {
        int i=nums.size()-1;
        while(i>0&&nums[i]<=nums[i-1]) i--;
        if(i==0) reverse(nums.begin(),nums.end());
        else{
            int j=nums.size()-1;
            while(nums[j]<=nums[i-1]) j--;
            swap(nums[i-1],nums[j]);
            reverse(nums.begin()+i,nums.end());
        }
    }

从后向前寻找第一个相邻升序对以锁定需变动的“小数”，将其与后缀中略大于它的数交换，最后反转后缀使其变为升序（最小化），从而构造出紧邻的下一个字典序排列。

找一个尽量靠右的数字（低位）来增大，这样增量最小。增大之后，要保证后面的数字尽可能小（升序排列）。

while 循环里使用的是 nums[i] <= nums[i-1]（带有等号）。为了处理重复元素

从后往前找第一个比它大的数。这个数是能让排列变大的最小变动量。交换后，i 往后的序列依然是降序的。为了让字典序“最小”，我们需要把它变成升序。降序序列反转后就是升序。

ACM处理31

#include <bits/stdc++.h>
using namespace std;
 
void nextPermutation(vector<int>& nums) {
    int i = nums.size() - 1;
    while (i > 0 && nums[i] <= nums[i - 1]) i--;
    if (i == 0) reverse(nums.begin(), nums.end());
    else {
        int j = nums.size() - 1;
        while (nums[j] <= nums[i - 1]) j--;
        swap(nums[i - 1], nums[j]);
        reverse(nums.begin() + i, nums.end());
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        nextPermutation(nums);
 
        for (int i = 0; i < n; i++) {
            cout << nums[i] << (i == n - 1 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

⭐️32. 最长有效括号✅

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
左右括号匹配，即每个左括号都有对应的右括号将其闭合的字符串是格式正确的，比如 "(()())"。

int longestValidParentheses(string s) {
        stack<int> st;
        st.push(-1);
        int ans=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='(') st.push(i);
            else{
                st.pop();
                if(st.empty()) st.push(i);
                else ans=max(ans,i-st.top());
            }
        }
        return ans;
    }

利用栈存储下标并预置 -1 作为参照底座，遇到右括号弹出栈顶后，若栈非空则通过下标差更新最大长度，若栈空则将当前位置作为新的分割点重新入栈。

-1 是一个虚拟的起始边界（参照点）便于处理从索引 0 开始的合法序列。

栈顶元素始终代表：“最后一个未匹配的右括号的下标” 或者 “当前匹配序列的前一个字符下标”。

当计算长度时，公式是：当前下标 i - 栈顶下标。
如果第一个字符就是 (，下标为 0，匹配成功后长度应为 0 - (-1) = 1（逻辑上），等到匹配完 )，长度就是 1 - (-1) = 2。

遇到 ( 时：

直接把当前下标 i 压入栈。不确定它能不能被匹配，先存着。

遇到 ) 时：

先 st.pop()：尝试匹配掉栈顶的 (。
判断 st.empty()：
1. 如果栈空了：说明刚才 pop 掉的是最后一个参照点（可能是 -1，也可能是上一个断掉的右括号）。这表示当前的 ) 是多余的，无法被匹配。
2. 动作：我们把这个新的“断点”下标 i 压入栈，作为新的参照点。
3. 如果栈不空：说明刚才 pop 掉的是一个 (，匹配成功！
4. 计算长度：ans = max(ans, i - st.top())。注意这里是用 i 减去减完之后的栈顶（参照点），因为现在的栈顶才是这段合法序列的“左边界的前一个位置”。

当 ( 剩在栈里： 说明左边太长了，匹配不完，不影响已有的 ans。

当 ) 导致栈空： 说明右边太长了，当前的合法序列彻底断掉。我们必须把这个 ) 的下标作为新的“地基”（哨兵），重新开始计算后面可能出现的合法序列。

ACM处理32

#include <bits/stdc++.h>
using namespace std;
 
int longestValidParentheses(string s) {
    stack<int> st;
    st.push(-1);
    int ans = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (st.empty()) {
                st.push(i);
            } else {
                ans = max(ans, i - st.top());
            }
        }
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s;
    while (cin >> s) {
        cout << longestValidParentheses(s) << "\n";
    }
    return 0;
}

⭐️33. 搜索旋转排序数组✅

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 下标 3 上向左旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(target==nums[mid]) return mid;
            if(nums[mid]>=nums[left]){
                if(target>=nums[left]&&target<nums[mid]) right=mid-1;
                else left=mid+1;
            }else{
                if(target<=nums[right]&&target>nums[mid]) left=mid+1;
                else right=mid-1;
            }
        }
        return -1;
    }

利用二分查找，在每轮迭代中判断哪一半区间是有序的（单调递增），通过检查 target 是否落在这个有序区间内，若在有序半区，则在这边搜，否则去另一边。

数组被旋转了，如果从中间切一刀，左右两部分中至少有一半是一定有序的。

左端点小于等于中间点，左半部分 [left, mid] 是有序的。如果 target 恰好落在左侧有序区间的范围内，二分。

如果 nums[mid] >= nums[left]，说明从 left 到 mid 是一直递增的，没有发生旋转。

在二分查找中，mid 是向下取整的。当区间剩下两个元素时，mid 必然等于 left。

O(log N)

直接找某个目标值（Target） 的题目，使用 while (left <= right) 最简单

ACM处理33

#include <bits/stdc++.h>
using namespace std;
 
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (target == nums[mid]) return mid;
 
        if (nums[mid] >= nums[left]) {
            if (target >= nums[left] && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else {
            if (target <= nums[right] && target > nums[mid]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, target;
    while (cin >> n >> target) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
        cout << search(nums, target) << "\n";
    }
    return 0;
}

🔥39. 组合总和✅

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtrack(vector<int>& candidates, int target, int sum, int start){
        if(sum==target) {
            res.push_back(path);
            return;
        }
        for(int i=start;i<candidates.size()&&sum+candidates[i]<=target;i++){
            sum+=candidates[i];
            path.push_back(candidates[i]);
            backtrack(candidates,target,sum,i);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        backtrack(candidates,target,0,0);
        return res;
    }
};

先对数组排序以便提前终止循环（剪枝），利用回溯算法搜索组合，通过在递归时传入当前下标 i（而非 i+1）来实现元素的无限重复选取。

去重机制（start 指针）：为了避免搜到重复的组合（例如 [2, 2, 3] 和 [3, 2, 2] 是同一个组合），使用 start 确保每一层递归只搜索当前及之后的元素。

候选列表（candidates）：可以使用的数字。

选择限制（target）：路径中数字之和必须等于目标值。

递归参数是i而不是i+1。这代表“数字可以无限制重复被选取”，即下一层递归依然可以从当前的 candidates[i] 开始。

ACM处理39

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, target;
    while (cin >> n >> target) {
        vector<int> candidates(n);
        for (int i = 0; i < n; i++) cin >> candidates[i];
 
        Solution sol;
        auto res = sol.combinationSum(candidates, target);
 
        for (auto& vec : res) {
            for (int i = 0; i < vec.size(); i++) {
                if (i) cout << ' ';
                cout << vec[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

🔥⭐️42. 接雨水✅

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

int trap(vector<int>& height) {
        int l=0,r=height.size()-1;
        int lmax=0, rmax=0, ans=0;
        while(l<r){
            lmax=max(lmax,height[l]);
            rmax=max(rmax,height[r]);
            if(lmax<rmax){
                ans+=lmax-height[l];
                l++;
            }else{
                ans+=rmax-height[r];
                r--;
            }
        }
        return ans;
    }

利用双指针从两端向中间收缩，实时维护左（lmax）右（rmax）两侧的最高挡板，依据“短板效应”（较矮的一侧决定水位）直接计算当前位置的积水量并移动较矮侧的指针。

每次算一格。

ACM处理42

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> height(n);
        for (int i = 0; i < n; i++) cin >> height[i];
        cout << trap(height) << '\n';
    }
    return 0;
}

🔥⭐️46. 全排列✅

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtrack(vector<int>& nums,vector<bool>& used){
        if(path.size()==used.size()){
            res.push_back(path);
            return;
        }
        for(int i=0;i<nums.size();i++){
            if(used[i]) continue;
            used[i]=true;
            path.push_back(nums[i]);
            backtrack(nums,used);
            used[i]=false;
            path.pop_back();
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        res.clear();
        path.clear();
        vector<bool> used(nums.size(),false);
        backtrack(nums,used);
        return res;
    }
};

利用回溯算法按位填充，借助 used 数组标记当前路径中已使用的元素以避免重复选择，通过“做出选择-递归进入-撤销选择”的流程穷举所有排列。

标记数组。used 数组记录 nums 中哪些位置的数字已经被放进 path 了

每一层递归都会尝试从头遍历 nums。如果 nums[i] 已经被用过了，跳过，尝试下一个数字。做选择：将当前数字标记为已使用，并压入路径。递归：进入下一层决策树，去选下一个数字。递归返回后，必须将当前状态恢复原样，以便 for 循环尝试下一个 i

if (used[i]) continue;：如果数字 i 用过了，跳过，看下一个。

used[i] = true;：选定这个数，打上标签。

used[i] = false;：回溯的核心，从递归回来后，把标签撕掉，让这个数在其他位置还能被使用。

$O(n \times n!$ ，O(n)

ACM处理46

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while(cin >> n){
        vector<int> nums(n);
        for(int i = 0; i < n; i++){
            cin >> nums[i];
        }
 
        vector<bool> used(n, false);
        backtrack(nums, used);
 
        for(auto& v : res){
            for(int i = 0; i < v.size(); i++){
                if(i) cout << ' ';
                cout << v[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

🔥⭐️53. 最大子数组和✅

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

int maxSubArray(vector<int>& nums) {
        int ans=nums[0],pre=0;
        for(int x:nums){
            pre=max(x+pre,x);
            ans=max(ans,pre);
        }
        return ans;
    }

运用 Kadane 算法（动态规划的一种空间优化），遍历数组时计算以当前元素结尾的最大和，通过比较“当前元素”与“前缀和 + 当前元素”的大小来决定是延续之前的子数组还是重新开始，并实时更新全局最大值。

pre ：以当前数字 x 结尾的最大子数组和。

ans ：到目前为止，我们遇到的所有子数组和里的最大值。

ACM处理53

#include <bits/stdc++.h>
using namespace std;
 
int maxSubArray(vector<int>& nums) {
    if (nums.empty()) return 0;
    int ans = nums[0], pre = 0;
    for (int x : nums) {
        pre = max(x + pre, x);
        ans = max(ans, pre);
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
        cout << maxSubArray(nums) << "\n";
    }
    return 0;
}

🔥⭐️56. 合并区间✅

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start(i), end(i)] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(),intervals.end());
        int start=intervals[0][0],end=intervals[0][1];
        for(int i=1;i<intervals.size();i++){
            if(intervals[i][0]>end){
                ans.push_back({start,end});
                start=intervals[i][0];
                end=intervals[i][1];
            }else{
                end=max(end,intervals[i][1]);
            }
        }
        ans.push_back({start,end});
        return ans;
    }

首先按起始位置排序，随后遍历数组，维护一个动态的合并区间，若当前区间与该区间重叠则通过取最大终点值扩展右边界，否则说明断开，将旧区间存入结果并开启新区间。

为什么要排序？ 当我们按照区间的左端点（start）排序后，我们只需要考虑当前的区间是否与上一个合并后的区间有交集。

合并规则： 假设当前合并区间的范围是 [start, end]，我们要处理下一个区间 [intervals[i][0], intervals[i][1]]：

无法合并（intervals[i][0] > end）说明当前区间和上一个区间完全断开了。此时我们要把旧的 [start, end] 存入答案，然后开启一个新的合并区间。
可以合并（intervals[i][0] <= end）说明有重叠。我们只需要更新右边界 end，取两者的最大值即可：end = max(end, intervals[i][1])。

循环内每次push的是上一组答案。ans.push_back({start, end}); /补上最后一组

$O(n \log n$ ,O(nlog n)

ACM处理56

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<vector<int>> intervals(n, vector<int>(2));
        for (int i = 0; i < n; i++) {
            cin >> intervals[i][0] >> intervals[i][1];
        }
 
        auto res = merge(intervals);
 
        for (auto& v : res) {
            cout << v[0] << ' ' << v[1] << '\n';
        }
    }
    return 0;
}

🔥⭐️70. 爬楼梯✅

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

int climbStairs(int n) {
        if(n<=2) return n;
        int prev1=1,prev2=2,res=0;
        for(int i=3;i<=n;i++){
            res=prev1+prev2;
            prev1=prev2;
            prev2=res;
        }
        return res;
    }

当前阶数的方案数等于前两阶方案数之和，通过不断更新两个变量（滚动数组思想）原地完成累加。

到达第 $$$$ 级台阶的方案数，等于到达第 $n-$ 级和第 $n-$ 级台阶方案数的总和。

状态压缩：prev1 代表 f(i-2)，初始为 f(1) = 1，prev2 代表 f(i-1)，初始为 f(2) = 2

ACM处理70

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        cout << climbStairs(n) << '\n';
    }
    return 0;
}

🔥⭐️72. 编辑距离✅

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符

int minDistance(string word1, string word2) {
        int m=word1.size(),n=word2.size();
        vector dp(m+1,vector<int>(n+1));
        for(int i=0;i<=m;i++) dp[i][0]=i;
        for(int j=0;j<=n;j++) dp[0][j]=j;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1];
                else dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
            }
        }
        return dp[m][n];
    }

利用二维动态规划，定义 dp[i][j] 为两个字符串前缀间的最小编辑距离，根据当前字符是否相等，从插入、删除、替换（分别对应左、上、左上三个邻格状态）三种操作中择优递推，从而求得将 word1 转换为 word2 的最少操作数。

dp[i][j]：将 word1 的前 i个字符转换成 word2 的前 j 个字符所需要的最少操作步数。

dp[0][0] 表示两个空串之间的距离。

偏移量：由于要处理空字符串的情况，dp 数组的大小是 (m+1) x (n+1)。

dp[i][0] = i：要把一个长度为 i 的单词变成空串，只能删除 i 次。

dp[0][j] = j：要把一个空串变成长度为 j 的单词，只能插入 j 次。

字符相等 (**word1[i-1] == word2[j-1]**)：

不需要任何操作，代价直接继承自左上方：dp[i][j] = dp[i-1][j-1]。

字符不等：

三种方式转化为字符相等的情况，取最小值并 +1（代表执行了一次操作）：

左边 (**dp[i][j-1]**)：代表插入一个字符。插入后两个单词最后一个字符相同。
上边 (**dp[i-1][j]**)：代表删除一个字符。
左上 (**dp[i-1][j-1]**)：代表替换一个字符。

当 word1[i-1] != word2[j-1] 时，我们要从三种操作中选步数最少的：

dp[i][j-1] + 1 (插入)：代表在 word1 的末尾插入一个和 word2[j-1] 一样的字符。操作后，我们要看 word1 前 i 个字符变到 word2 前 j-1 个字符需要多少步。
dp[i-1][j] + 1 (删除)：代表把 word1 的第 i 个字符删掉。操作后，我们要看 word1 前 i-1 个字符变到 word2 前 j 个字符需要多少步。
dp[i-1][j-1] + 1 (替换)：代表把 word1[i-1] 直接改成 word2[j-1]。操作后，问题转化为 word1 前 i-1 变到 word2 前 j-1。

删除操作 (dp[i-1][j] + 1)

已知：已经把 word1 的前 i-1 个字符变成了 word2 的前 j 个字符（这步数就是 dp[i-1][j]）。
现状：现在 word1 多出了第 i 个字符。
动作：把第 i个字符删掉。
代价：步数就是在 dp[i-1][j] 的基础上 +1。

例子：word1 = "abce", word2 = "abc"。
我们已经知道把 "abc" 变成 "abc" 需要 0 步（即 dp[3][3] = 0）。
那么要把 "abce" 变成 "abc"，只需把多余的 'e' 删掉，步数就是 dp[3][3] + 1 = 1。

插入操作 (dp[i][j-1] + 1)

已知：word1 的前 i 个已经匹配好了 word2 的前 j-1 个（步数是 dp[i][j-1]）。
现状：word2 还多出一个第 j 个字符没搞定。
动作：在 word1 的末尾插入一个和 word2[j-1] 一模一样的字符。
代价：步数就是 dp[i][j-1] + 1。

复杂度： $O(m \times n$ / $O(m \times n$

ACM处理72

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string word1, word2;
    while (cin >> word1 >> word2) {
        cout << minDistance(word1, word2) << '\n';
    }
    return 0;
}

⭐️76. 最小覆盖子串✅

给定两个字符串 s 和 t，长度分别是 m 和 n，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""。
测试用例保证答案唯一。

string minWindow(string s, string t) {
        int cnt[128]={0};
        for(char c:t) cnt[c]++;
        int need=t.length();
        int left=0,right=0;
        int minLen=INT_MAX,start=0;
        while(right<s.length()){
            if(cnt[s[right]]-- >0) need--;
            while(need==0){
                if(right-left+1<minLen){
                    minLen=right-left+1;
                    start=left;
                }
                if(cnt[s[left]]++ ==0) need++;
                left++;
            }
            right++;
        }
        return minLen==INT_MAX?"":s.substr(start,minLen);
    }

双指针维护一个动态窗口，右指针扩张寻找“可行解”、左指针收缩寻找“最优解”，用哈希计数器（或数组）配合 need 变量。

一旦窗口内包含了 t 的所有字符（即 need == 0），就开始尝试移动 left 指针来缩小窗口，以去除冗余字符并更新最优解。

need 表示当前窗口还欠缺多少个字符才能覆盖 t。

cnt[s[right]]-- > 0：这一行同时完成了“判断是否为目标字符”和“更新窗口状态”两件事。正数代表该字符是 t 缺少的，减为负数则代表窗口内该字符已溢出。

cnt[s[left]]++ == 0：这是收缩窗口的触发点。当一个字符的计数回到 1 时，说明它是“必须存在”且“恰好用完”的，此时 need++ 打破循环，继续寻找下一个右边界。

如果 s[right] 是 t 里的字符（cnt[c] > 0），need 减少。无论是不是 t 里的字符，cnt[s[right]] 都会自减。t 以外的字符计数会变成负数。

right - left + 1：是当前窗口的长度。

O(N)

ACM处理76

#include <bits/stdc++.h>
using namespace std;
 
string minWindow(string s, string t) {
    int cnt[128] = {0};
    for (char c : t) cnt[c]++;
    int need = t.length();
    int left = 0, right = 0;
    int minLen = INT_MAX, start = 0;
    while (right < (int)s.length()) {
        if (cnt[(int)s[right]]-- > 0) need--;
        while (need == 0) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            if (cnt[(int)s[left]]++ == 0) need++;
            left++;
        }
        right++;
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s, t;
    while (cin >> s >> t) {
        cout << minWindow(s, t) << "\n";
    }
    return 0;
}

⭐️78. 子集✅

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集不能包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
public:
    void backtrack(vector<int>& nums, int start,
                   vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path);
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return res;
    }
};

回溯（DFS）遍历决策树，在进入递归函数的每一个节点时都直接记录当前路径（即收集所有树节点而非仅叶子节点），并通过传入 start 索引控制遍历顺序以避免生成重复子集。

start去重。

res.push_back(path) 放在了递归函数的最开始，而且没有终止条件。子集问题不要求长度。空集 [] 是子集，单个元素 [1] 是子集，全选 [1,2,3] 也是子集。每进入一级递归，当前的 path 状态就是一个合法的子集，直接存入结果。

$O(n \cdot 2^n$

ACM处理78

#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    void backtrack(vector<int>& nums, int start,
                   vector<int>& path,
                   vector<vector<int>>& res) {
 
        res.push_back(path);
 
        for (int i = start; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtrack(nums, i + 1, path, res);
            path.pop_back();
        }
    }
 
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> path;
        backtrack(nums, 0, path, res);
        return res;
    }
};
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
 
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
 
        Solution sol;
        auto res = sol.subsets(nums);
 
        for (auto& vec : res) {
            for (int i = 0; i < vec.size(); i++) {
                if (i) cout << ' ';
                cout << vec[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

🔥79. 单词搜索✅

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m=board.size(),n=board[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0)) return true;
            }
        }
        return false;
    }
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int p){
        if(p==word.size()) return true;
        int m=board.size(),n=board[0].size();
        if(i<0||j<0||i>=m||j>=n) return false;
        if(board[i][j]!=word[p]) return false;
        char ch=board[i][j];
        board[i][j]='.';
        bool ans=dfs(board,word,i+1,j,p+1)||
                dfs(board,word,i-1,j,p+1)||
                dfs(board,word,i,j+1,p+1)||
                dfs(board,word,i,j-1,p+1);
        board[i][j]=ch;
        return ans;
    }
};

以网格中每个位置为起点发起深度优先搜索 (**DFS**)，递归地向四周邻居试探匹配字符，并通过临时修改当前格内容（如改为 .）来标记已访问以防止路径回头，最终在递归返回时回溯（还原字符）。

标记为已访问（暂存当前字符并修改为特殊符号）,进行四个方向的 DFS,还原状态。

指针 p 到达单词末尾，说明全部匹配成功。

标记当前格，防止 DFS 走回头路,向四个方向扩散,只要有一个方向成功，就向上返回 true.

$O(M \cdot N \cdot 3^L$

ACM处理79

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m, n;
    while (cin >> m >> n) {
        vector<vector<char>> board(m, vector<char>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> board[i][j];
            }
        }
 
        string word;
        cin >> word;
 
        cout << (exist(board, word) ? "true" : "false") << '\n';
    }
    return 0;
}

🔥⭐️94. 二叉树的中序遍历✅

给定一个二叉树的根节点 root ，返回它的中序遍历。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        traversal(root,res);
        return res;
    }
 
    void traversal(TreeNode* root, vector<int> &res){
        if(!root) return;
        traversal(root->left,res);
        res.push_back(root->val);
        traversal(root->right,res);
    }
};

递归（DFS）方式，严格遵循“左根右”的访问顺序，优先深入左侧直至叶子节点，记录数值后再转向右侧，从而得到中序遍历序列。

ACM处理94

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
void traversal(TreeNode* root, vector<int> &res) {
    if (!root) return;
    traversal(root->left, res);
    res.push_back(root->val);
    traversal(root->right, res);
}
 
vector<int> inorderTraversal(TreeNode* root) {
    if (!root) return {};
    vector<int> res;
    traversal(root, res);
    return res;
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < nums.size()) {
        TreeNode* curr = q.front();
        q.pop();
        if (i < nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            q.push(curr->left);
        }
        i++;
        if (i < nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        auto res = inorderTraversal(root);
 
        for (int i = 0; i < (int)res.size(); i++) {
            if (i) cout << ' ';
            cout << res[i];
        }
        cout << '\n';
    }
    return 0;
}

🔥101. 对称二叉树✅

给你一个二叉树的根节点 root ，检查它是否轴对称。

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return compare(root->left,root->right);
    }
 
    bool compare(TreeNode* p, TreeNode* q){
        if(!p&&!q) return true;
        if(!p||!q) return false;
        return p->val==q->val&&compare(p->left,q->right)&&compare(p->right,q->left);
    }
};

利用递归同时遍历左右子树，通过同步比较对称位置的节点——即“左子树的左孩子 vs 右子树的右孩子”（外侧）与“左子树的右孩子 vs 右子树的左孩子”（内侧）——是否相等，从而判断二叉树是否呈镜像对称。

ACM处理101

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
bool compare(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p->val == q->val && compare(p->left, q->right) && compare(p->right, q->left);
}
 
bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return compare(root->left, root->right);
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < nums.size()) {
        TreeNode* curr = q.front();
        q.pop();
        if (i < nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            q.push(curr->left);
        }
        i++;
        if (i < nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        if (isSymmetric(root)) cout << "true" << endl;
        else cout << "false" << endl;
    }
    return 0;
}

🔥⭐️102. 二叉树的层序遍历✅

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if(root) que.push(root);
        while(!que.empty()){
            int size=que.size();
            vector<int> ans;
            while(size--){
                TreeNode* node=que.front();
                que.pop();
                ans.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            res.push_back(ans);
        }
        return res;
    }

利用队列实现广度优先搜索 (**BFS**)，在每轮迭代开始时记录当前队列长度以锁定当前层级的节点数量，从而批量处理该层所有节点并将下一层的子节点加入队列尾部。

ACM处理102

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
vector<vector<int>> levelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    vector<vector<int>> res;
    if (root) que.push(root);
    while (!que.empty()) {
        int size = que.size();
        vector<int> ans;
        while (size--) {
            TreeNode* node = que.front();
            que.pop();
            ans.push_back(node->val);
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        res.push_back(ans);
    }
    return res;
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < (int)nums.size()) {
        TreeNode* curr = q.front();
        q.pop();
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            q.push(curr->left);
        }
        i++;
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        auto res_levels = levelOrder(root);
 
        for (auto& level : res_levels) {
            for (int i = 0; i < (int)level.size(); i++) {
                if (i) cout << ' ';
                cout << level[i];
            }
            cout << '\n';
        }
    }
    return 0;
}

🔥⭐️105. 从前序与中序遍历序列构造二叉树✅

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

class Solution {
public:
    unordered_map<int,int> pos;
    int preIdx=0;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i=0;i<inorder.size();i++) pos[inorder[i]]=i;
        return dfs(preorder,0,inorder.size()-1);
    }
    TreeNode* dfs(vector<int>& preorder,int l,int r){
        if(l>r) return nullptr;
        int rootVal=preorder[preIdx++];
        TreeNode* root=new TreeNode(rootVal);
        int mid=pos[rootVal];
        root->left=dfs(preorder,l,mid-1);
        root->right=dfs(preorder,mid+1,r);
        return root;
    }
};

利用前序遍历确定根节点，用哈希表在中序遍历中定位根的位置，递归构建左右子树，通过索引区间避免数组拷贝。

建立中序遍历**的索引表, 从整个中序区间** [0, n-1] 开始构建整棵树。

前序遍历**的第一个元素一定是根，**

rootVal是从 preorder 中取出当前指针指向的值，作为 当前子树的根。

preIdx++：当前处理到前序遍历的第几个元素

pos 哈希表：键是节点值，值是该节点在 中序遍历 中的下标。

mid找根节点在中序遍历中的位置

l 和 r 表示当前子树在中序遍历中的区间，根节点在中序中的位置是 mid，因此左子树区间是 [l, mid-1]，右子树区间是 [mid+1, r]。

O(n)

ACM处理105

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
unordered_map<int, int> pos;
int preIndex = 0;
 
TreeNode* build(vector<int>& preorder, int l, int r) {
    if (l > r) return nullptr;
    int rootVal = preorder[preIndex++];
    TreeNode* root = new TreeNode(rootVal);
    int mid = pos[rootVal];
    root->left  = build(preorder, l, mid - 1);
    root->right = build(preorder, mid + 1, r);
    return root;
}
 
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    pos.clear();
    preIndex = 0;
    for (int i = 0; i < (int)inorder.size(); i++) pos[inorder[i]] = i;
    return build(preorder, 0, (int)inorder.size() - 1);
}
 
void inorderCheck(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorderCheck(root->left, res);
    res.push_back(root->val);
    inorderCheck(root->right, res);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> preorder(n), inorder(n);
        for (int i = 0; i < n; i++) cin >> preorder[i];
        for (int i = 0; i < n; i++) cin >> inorder[i];
 
        TreeNode* root = buildTree(preorder, inorder);
 
        vector<int> res;
        inorderCheck(root, res);
 
        for (int i = 0; i < (int)res.size(); i++) {
            if (i) cout << ' ';
            cout << res[i];
        }
        cout << '\n';
    }
    return 0;
}

🔥⭐️121. 买卖股票的最佳时机✅

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=max(-prices[i],dp[i-1][0]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }

动态规划。分别维护“持有股票”（dp[i][0]，本质上是在记录历史最低买入成本的负值）和“不持有股票”（dp[i][1]，即当前最大利润）两个状态，通过在每一天决策是延续旧状态还是进行买卖操作，求解单次交易的最大收益。

dp[i][j] 表示在第 i 天结束时，我们所能获得的最大利润。

j = 0：表示第 i 天结束时，手里持有股票的状态。
j = 1：表示第 i 天结束时，手里不持有股票的状态。

dp[0][0] = -prices[0]; 买入股票，利润为负

dp[0][1] = 0; 不买，利润为 0

dp[i][0]=max(-prices[i],dp[i-1][0]);尽量减小买入成本（让利润这个负数尽量大）

dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);尽量增加卖出后的**净利润**。今天把昨天的**持仓**卖了

ACM处理121

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> prices(n);
        for (int i = 0; i < n; i++) cin >> prices[i];
 
        int res = maxProfit(prices);
 
        cout << res << '\n';
    }
    return 0;
}

🔥128. 最长连续序列✅

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(),nums.end());
        int res=0;
        for(int n:st){
            if(st.find(n-1)!=st.end()) continue;
            int curNum=n;
            int curLen=1;
            while(st.find(curNum+1)!=st.end()){
                curLen++;
                curNum++;
            }
            res=max(res,curLen);
        }
        return res;
    }

利用 哈希集合 (**HashSet**) 去重并实现 O(1) 查找，遍历时仅对没有前驱（即 n-1 不存在）的数字发起连续序列长度统计，跳过非起点元素，从而确保每个数字仅被处理一次，实现 O(N) 时间复杂度。

if(st.find(n-1) != st.end()) continue;

只有当一个数 n 的前一个数 n-1 不存在于集合中时，我们才认为 n 是一个连续序列的起点。每个数字最多只会被访问两次（一次在for循环里，一次在某个while循环里），从而保证了线性时间。

核心剪枝：检查 n 是不是序列的开头。如果 n-1 存在，说明 n 只是序列中间的一个数，直接跳过。

接下来，说明 n 必定是一个序列的起点。向后不断寻找连续的数字

$O(n$ ,O(n)

ACM处理128

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
        }
        cout << longestConsecutive(nums) << '\n';
    }
    return 0;
}

🔥139. 单词拆分✅

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> st(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        for(int i=1;i<=s.size();i++){
            for(int j=0;j<i;j++){
                if(dp[j]){
                    string word=s.substr(j,i-j);
                    if(st.count(word)){
                        dp[i]=true;
                        break;
                    }
                }
            }
        }
        return dp[s.size()];
    }

dp[i] 表示字符串 s 的前 i个字符是否可以被拆分成字典中的单词。

将字典转为哈希集合，降低单词查找的时间复杂度

动态规划，枚举分割点 j，检查“前缀 dp[j] 是否合法”以及“剩余后缀子串是否在字典中”。

寻找切分点。字符串 s 的前 j 个字符可以被拆分，且剩下的部分 s[j...i] 恰好在字典里，那么前 i个字符就可以被拆分。

break:只需要知道是否存在至少一种有效的分割方式，只要找到一个j。

dp[0] = true：初始状态，空字符串可以被拆分

外层循环 i：当前要处理的“目标前缀”长度。内层循环 j：在这个前缀中寻找“切分点”。

检查 s.substr(j, i-j)：如果前 j个合法，那么剩下的这一段（从 j 开始，长度为 i-j 的子串）在不在字典里？

$O(n^2 \cdot k$ 。其中 $$$$ 是字符串长度，k 是子串截取和哈希比较的开销。

ACM处理139

#include <bits/stdc++.h>
using namespace std;
 
bool wordBreak(string s, vector<string>& wordDict) {
    unordered_set<string> st(wordDict.begin(), wordDict.end());
    vector<bool> dp(s.size() + 1, false);
    dp[0] = true;
    for (int i = 1; i <= (int)s.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j]) {
                string word = s.substr(j, i - j);
                if (st.count(word)) {
                    dp[i] = true;
                    break;
                }
            }
        }
    }
    return dp[s.size()];
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s;
    int n;
    while (cin >> s >> n) {
        vector<string> wordDict(n);
        for (int i = 0; i < n; i++) cin >> wordDict[i];
 
        if (wordBreak(s, wordDict)) cout << "true" << '\n';
        else cout << "false" << '\n';
    }
    return 0;
}

🔥⭐️141. 环形链表✅

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：**pos** 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。否则，返回 false 。

bool hasCycle(ListNode *head) {
        if(!head||!head->next) return false;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow) return true;
        }
        return false;
    }

如果链表**有环，**快指针一定会在环中 追上慢指针。

如果**无环，**快指针会先到 nullptr。

成环，写死测试用例。

ACM处理141

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
bool hasCycle(ListNode *head) {
    if (!head || !head->next) return false;
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) return true;
    }
    return false;
}
 
ListNode* buildCycleList(const vector<int>& nums, int pos) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    ListNode* cycleNode = nullptr;
    if (pos == 0) cycleNode = head;
 
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
        if (i == pos) cycleNode = cur;
    }
    if (pos != -1) cur->next = cycleNode;
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, pos;
    while (cin >> n >> pos) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildCycleList(nums, pos);
        if (hasCycle(head)) cout << "true" << '\n';
        else cout << "false" << '\n';
    }
    return 0;
}

🔥⭐️142. 环形链表 II✅

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null**。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：**pos** 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
            if(fast==slow){
                while(head!=slow){
                    head=head->next;
                    slow=slow->next;
                }
                return head;
            }
        }
        return nullptr;
    }

先用快慢指针在环内相遇，再将其中一个指针放回起点，两人以相同速度前进，再次相遇点即为环的入口。

ACM处理142

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
// Floyd 判环 + 入环点
ListNode* detectCycle(ListNode* head) {
    if (!head) return nullptr;
 
    ListNode* slow = head;
    ListNode* fast = head;
 
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
 
        if (slow == fast) {
            ListNode* p = head;
            while (p != slow) {
                p = p->next;
                slow = slow->next;
            }
            return p;
        }
    }
    return nullptr;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, pos;
    cin >> n >> pos;
 
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
 
    // 构建链表
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    ListNode* entry = nullptr;   // 记录入环点
 
    for (int i = 0; i < n; i++) {
        ListNode* node = new ListNode(nums[i]);
        if (!head) head = node;
        else tail->next = node;
        tail = node;
 
        if (i == pos) entry = node;
    }
 
    // 制造环
    if (pos != -1 && tail) {
        tail->next = entry;
    }
 
    // 判环
    ListNode* res = detectCycle(head);
 
    if (res)
        cout << res->val << "\n";
    else
        cout << -1 << "\n";
 
    return 0;
}

写死测试用例

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
// Floyd 判环，返回入环节点
ListNode* detectCycle(ListNode* head) {
    if (!head) return nullptr;
 
    ListNode* fast = head;
    ListNode* slow = head;
 
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
 
        if (fast == slow) {           // 相遇
            ListNode* p = head;       // ⚠️ ACM里不直接复用 head 更清晰
            while (p != slow) {
                p = p->next;
                slow = slow->next;
            }
            return p;                 // 入环点
        }
    }
    return nullptr;
}
 
int main() {
    // 构造节点
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    ListNode* n5 = new ListNode(5);
 
    // 连成链表
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = n3;   // 🔴 制造环（入环点是 3）
 
    ListNode* entry = detectCycle(n1);
 
    if (entry)
        cout << "Cycle entry value: " << entry->val << endl;
    else
        cout << "No cycle" << endl;
 
    return 0;
}

⭐️146. LRU 缓存✅

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

class LRUCache {
    int cap;
    list<int> l;
    unordered_map<int,pair<int,list<int>::iterator>> mp;
public:
    LRUCache(int capacity):cap(capacity) {}
 
    int get(int key) {
        if(!mp.count(key)) return -1;
        touch(key);
        return mp[key].first;
    }
 
    void put(int key, int value) {
        if(mp.count(key)){
            l.erase(mp[key].second);
        }else if(cap==l.size()){
            mp.erase(l.front());
            l.pop_front();
        }
        l.push_back(key);
        mp[key]={value,prev(l.end())};
    }
 
    void touch(int key){
        l.erase(mp[key].second);
        l.push_back(key);
        mp[key].second=prev(l.end());
    }
};

结合 哈希表 和 双向链表，利用哈希表存储 key 到 {value, list_iterator} 的映射以实现 O(1) 的快速查找，同时利用链表维护操作的时间顺序。每次访问或更新数据时，将对应的 Key 移动到链表尾部（表示最近使用），而在容量不足时，直接移除链表头部（表示最近最少使用）的元素。

存储了指向 list 节点的迭代器 (list<int>::iterator)

list<int> l 只是存 key，不存 value；value 存在 cache[key].first。

unordered_map<int, pair<int, list<int>::iterator>> mp;

map 的每一项存了三个信息：

Key (键)：数据的 ID（比如 1）。
Value (值)：mp[key].first，这是你真正要存的数据（比如 100）。
Iterator (**迭代器**/指针)：mp[key].second指向了该数据在双向链表 l 中的位置。

链表“头部”（front()）是最久未使用（LRU），“尾部”（push_back / prev(l.end())）是最近使用（MRU）。

prev(l.end()) 获取指向最后一个元素的迭代器（因为 end() 指向的是末尾后的空位）。

时间复杂度：get 与 put 都是 O(1)，空间复杂度 O(capacity)。

list<int> l (**双向链表**)：负责记录访问的时间顺序。

末尾 (back)：存储最近使用的元素。
头部 (front)：存储最久未使用的元素。

unordered_map<int, pair<int, list<int>::iterator>> mp (**哈希表**)：负责O(1)时间定位。

键（Key）对应一个 pair：包含 value 本身和它在链表中对应的迭代器**（指针）**。

为什么要存迭代器（Iterator）？

在 LRU 中，每当我们 get 或 put 一个已存在的 key 时，都需要把这个 key 移动到链表的末尾

: cap(capacity)：这就是初始化列表。它的意思是：把输入参数 capacity 的值赋给类成员变量 cap。

它等同于在花括号里写 this->cap = capacity;，但性能更好（直接初始化而不是先创建再赋值）。

{ }：函数体是空的。因为初始化成员变量的工作已经在冒号后面做完了，这里不需要再写其他逻辑。

mp 是覆盖更新，而 l 必须移动位置。

容量满时需要 mp.erase，这里要删除的是一个完全不同的 key（最久未使用的）。要腾出空间给新 key，如果不显式 mp.erase，哈希表里就会永远残留那个已经失效的旧数据。

注释版本：

class LRUCache {
    int cap;
    list<int> l; // key 顺序：头旧，尾新
    unordered_map<int, pair<int, list<int>::iterator>> mp;
// cache: key -> (value, 指向链表中该 key 节点的迭代器)
 
public:
    LRUCache(int capacity) : cap(capacity) {}
 
    int get(int key) {
        if (!mp.count(key)) return -1;
        touch(key);    // key 存在：把它标记为“最近使用”
        return mp[key].first;
    }
 
    void put(int key, int value) {
        if (mp.count(key)) {
            l.erase(mp[key].second);  // 如果 key 已存在，先把旧节点从链表中删除（准备放到尾部）
        } else if (l.size() == cap) {
            mp.erase(l.front());  // 从哈希表中移除对应项
            l.pop_front();  // 从链表中移除头结点
        }
        l.push_back(key);  // 在链表尾部插入（表示最近使用），并在哈希表中更新value与迭代器
        mp[key] = {value, prev(l.end())};  //指向新插入的尾节点
    }
 
    void touch(int key) {
        l.erase(mp[key].second);
        l.push_back(key);
        mp[key].second = prev(l.end());
    }
};

ACM处理146

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int capacity;
    if (!(cin >> capacity)) return 0;
    LRUCache cache(capacity);
 
    string op;
    while (cin >> op) {
        if (op == "put") {
            int key, value;
            cin >> key >> value;
            cache.put(key, value);
        } else if (op == "get") {
            int key;
            cin >> key;
            cout << cache.get(key) << "\n";
        }
    }
    return 0;
}

🔥198. 打家劫舍✅

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

int rob(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        vector<int> dp(nums.size());
        dp[0]=nums[0];
        dp[1]=max(dp[0],nums[1]);
        for(int i=2;i<nums.size();i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.size()-1];
    }

动态规划。对于每一间房屋，要么偷窃当前房屋（此时只能加上 i-2 位置的累积金额），要么跳过当前房屋（直接继承 i-1 位置的累积金额），通过始终取两者的最大值来递推全局最优解。

dp[i]：表示偷到第 i 间房时，能够获得的最大金额。

面对第 i 间房，只有两种选择：

偷第 i 间房：由于不能触发警报，他前一天（i-1）必须没偷。那么他的收益就是：前天（i-2）的最大收益 + 今天的钱 (**nums[i]**)。
不偷第 i 间房：那么他的收益就直接等于：昨天（i-1）的最大收益。

ACM处理198

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
        cout << rob(nums) << '\n';
    }
    return 0;
}

⭐️200. 岛屿数量✅

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size(),n=grid[0].size();
        int ans=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    ans++;
                    dfs(grid,i,j);
                }
            }
        }
        return ans;
    }
    void dfs(vector<vector<char>>& grid, int i, int j) {
        int m=grid.size(),n=grid[0].size();
        if(i<0||i>=m||j<0||j>=n||grid[i][j]=='0') return;
        grid[i][j]='0';
        dfs(grid,i+1,j);
        dfs(grid,i,j+1);
        dfs(grid,i-1,j);
        dfs(grid,i,j-1);
    }
};

dfs: 把当前陆地及其上下左右所有连通的陆地，全部访问一遍

遍历网格，遇到 '1' 计数一次，并用 DFS/BFS 把整座岛淹掉，最终统计岛屿数量。

ACM处理200

#include <bits/stdc++.h>
using namespace std;
 
void dfs(vector<vector<char>>& grid, int i, int j) {
    int m = grid.size(), n = grid[0].size();
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') return;
    grid[i][j] = '0';
    dfs(grid, i + 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i - 1, j);
    dfs(grid, i, j - 1);
}
 
int numIslands(vector<vector<char>>& grid) {
    if (grid.empty()) return 0;
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                ans++;
                dfs(grid, i, j);
            }
        }
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m, n;
    while (cin >> m >> n) {
        vector<vector<char>> grid(m, vector<char>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> grid[i][j];
            }
        }
        cout << numIslands(grid) << '\n';
    }
    return 0;
}

🔥⭐️206. 反转链表✅

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

ListNode* reverseList(ListNode* head) {
        ListNode* pre=nullptr;
        ListNode* nxt=nullptr;
        ListNode* cur=head;
        while(cur){
            nxt=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }

采用迭代法（双指针），在遍历过程中维护 pre、cur和 nxt三个指针。核心逻辑在于先暂存后继节点以防断链，随后将当前节点的 next 指针反向指回 pre，最后整体向后移动指针，直到遍历结束。

循环结束时，cur 指向 null，pre 正好指向原链表的最后一个节点，即新链表的头

虚拟头节点：反转不需要

头节点可能会变：比如删除节点、插入节点。

需要统一逻辑：当“处理头节点”的操作和“处理中间节点”的操作不一致时，用虚拟头节点把头节点变成“中间节点”。

ACM处理206

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* nxt = nullptr;
    ListNode* cur = head;
    while (cur) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}
 
ListNode* buildList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        ListNode* res = reverseList(head);
 
        vector<int> out;
        while (res) {
            out.push_back(res->val);
            res = res->next;
        }
 
        for (int i = 0; i < (int)out.size(); i++) {
            if (i) cout << ' ';
            cout << out[i];
        }
        cout << '\n';
    }
    return 0;
}

🔥⭐️215. 数组中的第K个最大元素✅

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n=nums.size();
        return solve(nums,0,n-1,n-k);
    }
    int solve(vector<int>& nums, int l, int r, int target){
        int randomId=l+rand()%(r-l+1);
        swap(nums[l],nums[randomId]);
        int pivot=nums[l];
        int i=l,j=r;
        while(i<j){
            while(i<j&&nums[j]>=pivot) j--;
            nums[i]=nums[j];
            while(i<j&&nums[i]<=pivot) i++;
            nums[j]=nums[i];
        }
        nums[i]=pivot;
        if(i==target) return nums[i];
        else if(i<target) return solve(nums,i+1,r,target);
        else return solve(nums,l,i-1,target);
    }
};

数组中“第k大”的元素，在从小到大排序的数组中，其下标是 n - k。

将当前区间的第一个数作为 pivot。算法的目标是：把比它小的放左边，比它大的放右边。

每次 partition 后，pivot 会到达它排序后的最终位置。

如果 pivot 的下标等于 n-k，直接返回；否则只在包含目标下标的一侧继续递归，

O(n)

在挖坑法中，pivot 先被取出，数组中始终只有一个坑。i 和 j 分别从左右向中间移动，每次用对侧找到的数填坑，

当 i 和 j 相遇时，坑的位置正好是 pivot 的最终排序位置。

从右往左找第一个小于 pivot 的数，把这个小数填到左边的坑位里。从左往右找第一个大于 pivot 的数，把这个大数填到右边的坑位里。最后 i 和 j 重合，把 pivot 填回中点

ACM处理215

#include <bits/stdc++.h>
using namespace std;
 
int quickSelect(vector<int>& nums, int l, int r, int k) {
    int p = l + rand() % (r - l + 1);
    swap(nums[l], nums[p]);
 
    int pivot = nums[l];
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        nums[i] = nums[j];
        while (i < j && nums[i] <= pivot) i++;
        nums[j] = nums[i];
    }
    nums[i] = pivot;
 
    if (i == k) return nums[i];
    else if (i < k) return quickSelect(nums, i + 1, r, k);
    else return quickSelect(nums, l, i - 1, k);
}
 
int findKthLargest(vector<int>& nums, int k) {
    int n = nums.size();
    return quickSelect(nums, 0, n - 1, n - k);
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    srand(time(nullptr));
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        int k;
        cin >> k;
 
        cout << findKthLargest(nums, k) << '\n';
    }
    return 0;
}

🔥234. 回文链表✅

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

class Solution {
public:
    ListNode* findMiddle(ListNode* head){
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    ListNode* reverse(ListNode* head){
        ListNode* pre=nullptr;
        ListNode* nxt=nullptr;
        ListNode* cur=head;
        while(cur){
            nxt=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
 
    bool isPalindrome(ListNode* head) {
        ListNode* dummy1=new ListNode(0);
        ListNode* dummy2=new ListNode(0);
        ListNode* list1=findMiddle(head);
        ListNode* list2=reverse(list1);
        dummy2->next=list2;
        dummy1->next=head;
        while(dummy1->next&&dummy2->next){
            if(dummy1->next->val==dummy2->next->val){
                dummy1=dummy1->next;
                dummy2=dummy2->next;
            }else return false;
        }
        return true;
    }
};

结合 快慢指针 和链表**反转** 技巧，首先利用快慢指针定位链表的中点，随后将**后半部分**链表进行原地反转，最后通过双指针同步比较前半段与反转后的后半段是否一致

奇数个节点时，中间节点被归入了后半部分进行比较，逻辑依然成立。

ACM处理234

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* findMiddle(ListNode* head) {
    ListNode* fast = head;
    ListNode* slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
 
ListNode* reverse(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* nxt = nullptr;
    ListNode* cur = head;
    while (cur) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}
 
bool isPalindrome(ListNode* head) {
    if (!head || !head->next) return true;
 
    ListNode* mid = findMiddle(head);
    ListNode* list2 = reverse(mid);
    ListNode* p1 = head;
    ListNode* p2 = list2;
 
    while (p2) {
        if (p1->val != p2->val) return false;
        p1 = p1->next;
        p2 = p2->next;
    }
    return true;
}
 
ListNode* buildList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        if (isPalindrome(head)) cout << "true" << '\n';
        else cout << "false" << '\n';
    }
    return 0;
}

🔥⭐️236. 二叉树的最近公共祖先✅

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return nullptr;
        if(root==q||root==p) return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left&&right) return root;
        else if(!left&&right) return right;
        else if(left&&!right) return left;
        else return nullptr;
    }

利用递归（DFS）进行后序遍历。当遇到节点 p 或 q 时直接返回该节点；若在当前节点的左、右子树中分别找到了这两个节点（即 left 和 right 均非空），则说明当前节点即为最近公共祖先；若仅有一侧找到了节点，则向上返回该侧的结果（代表目标节点或已找到的公共祖先）。

后序遍历：先深入子树探路。

一旦撞见其中一个，立刻撤回是效率最高的选择。

如果 p 是 q的祖先，程序只会找到 p 就会停止向下探索。

整个 p 以下的子树（包含 q）都会被剪枝。

ACM处理236

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
 
    TreeNode* left = lowestCommonAncestor(root->left, p, q);
    TreeNode* right = lowestCommonAncestor(root->right, p, q);
 
    if (left && right) return root;
    return left ? left : right;
}
 
TreeNode* findNode(TreeNode* root, int val) {
    if (!root || root->val == val) return root;
    TreeNode* left = findNode(root->left, val);
    if (left) return left;
    return findNode(root->right, val);
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> qu;
    qu.push(root);
    int i = 1;
    while (!qu.empty() && i < (int)nums.size()) {
        TreeNode* curr = qu.front();
        qu.pop();
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            qu.push(curr->left);
        }
        i++;
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            qu.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, p_val, q_val;
    while (cin >> n >> p_val >> q_val) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        TreeNode* p = findNode(root, p_val);
        TreeNode* q = findNode(root, q_val);
 
        TreeNode* res = lowestCommonAncestor(root, p, q);
 
        if (res) cout << res->val << '\n';
        else cout << "null" << '\n';
    }
    return 0;
}

🔥⭐️239. 滑动窗口最大值✅

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            if(!dq.empty()&&dq.front()<i-k+1) dq.pop_front();
            while(!dq.empty()&&nums[i]>=nums[dq.back()]) dq.pop_back();
            dq.push_back(i);
            if(i-k+1>=0) res.push_back(nums[dq.front()]);
        }
        return res;
    }

用单调递减队列。队列里存的是下标，并且保证从队首到队尾对应的值是递减的。每次右指针右移时： 1️⃣ 先判断队首下标是否已经滑出窗口，如果是就弹出； 2️⃣ 再从队尾把所有比当前值小的元素弹出，因为它们不可能成为最大值； 3️⃣ 把当前下标加入队尾；当窗口大小达到 k（也就是 i-k+1 >=0）时，队首元素就是当前窗口的最大值。整个过程每个元素最多进出队一次，时间复杂度是 O(n)。

deque<int> 维护了一个下标队列，其对应数值严格单调递减。

队头 (**front**)：永远是当前窗口的最大值的下标。

队尾 (**back**)：新进来的元素会踢掉前面所有比它小的元素。

检查队头是否过期，如果队头下标不在 [i-k+1, i] 这个范围内，说明它已经滑出窗口了。

当前窗口 合法下标范围 是：[i - k + 1 , i]

如果新来的 nums[i] 比队尾大，说明队尾元素永远没机会当老大，踢掉它。将当前下标入队。当 i >= k-1 时，说明第一个窗口已经形成了，队头就是最大值

priority_queue（大顶堆）可以拿到最大值，但它不支持删除“已过期”的任意元素。且堆的操作是 O(log k)，会导致总复杂度变成 O(n log k)。

ACM处理239

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    while (cin >> n >> k) {         // 多组输入
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        vector<int> ans = maxSlidingWindow(nums, k);
        for (int i = 0; i < ans.size(); i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

🔥⭐️300. 最长递增子序列✅

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

int lengthOfLIS(vector<int>& nums) {
        int n=nums.size(),ans=1;
        if(n==1) return 1;
        vector<int> dp(n,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]) dp[i]=max(dp[j]+1,dp[i]);
                ans=max(ans,dp[i]);
            }
        }
        return ans;
    }

dp[i] 为以第 i 个元素结尾的最长上升子序列长度。

通过双重循环遍历，对于每个元素 nums[i]，回头检查所有之前的元素 nums[j]，若满足递增关系（nums[i] > nums[j]），则尝试将当前元素拼接到 j 的序列后以更新最大长度，最终取所有位置的峰值。

外层循环, 遍历每一个位置 i，计算以 i 结尾的最长长度。内层循环：检查 i 之前的所有位置 j

用 max。因为对于同一个 i，可能存在多个满足条件的 j。

$O(n^2$ ，O(n)

ACM处理300

#include <bits/stdc++.h>
using namespace std;
 
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    int ans = 1;
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
        ans = max(ans, dp[i]);
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        cout << lengthOfLIS(nums) << '\n';
    }
    return 0;
}

🔥⭐️322. 零钱兑换✅

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的**硬币**个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount+1,amount+1);
        dp[0]=0;
        for(int i=0;i<coins.size();i++){
            for(int j=coins[i];j<=amount;j++){
                dp[j]=min(dp[j],dp[j-coins[i]]+1);
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }

dp[j] 为凑成金额 j 所需的最少**硬币**数量。

外层遍历硬币类型、内层正向遍历金额（从小到大，意味着允许重复使用同一面额），在每次迭代中尝试加入当前硬币，并取“当前已知最优解”与“加入新硬币后的解”的最小值来更新状态。

状态转移：凑成金额 j 所需的最少**硬币**数量 = min(不选当前硬币, 选了当前硬币后的剩余金额 j-coin 的最少硬币数 + 1)

“当我考虑面值为 coins[i] 的硬币时，如果我用掉一枚，剩下的金额就是 j - coins[i]。所以我只需要看凑齐那个剩余金额需要多少枚，再加上这枚新的即可。”

遍历顺序：

正向遍历意味着当你计算 dp[j] 时，dp[j - coin] 已经在当前这轮循环中被更新过了。

这意味着：你可以在凑齐金额 j 时，重复使用同一枚硬币。

完全背包：先物品，后背包。

对比：为什么 0-1 背包要“逆向”遍历？

如果题目要求每种**硬币**只能用一次（0-1 背包），内层循环必须是 for(int j=amount; j >= coin; j--)。

逻辑：逆向遍历保证了当你计算dp[j] 时，dp[j-coin] 还是上一轮循环（即还没考虑当前硬币时）留下的旧值。
结果：这样就保证了每一枚硬币在凑成金额 j 的过程中只被贡献了一次。

ACM处理322

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, amount;
    while (cin >> n >> amount) {  // 多组输入
        vector<int> coins(n);
        for (int i = 0; i < n; i++) cin >> coins[i];
 
        cout << coinChange(coins, amount) << '\n';
    }
    return 0;
}

🔥337. 打家劫舍 III✅

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> ans=dfs(root);
        return max(ans[0],ans[1]);
    }
    vector<int> dfs(TreeNode* root){
        if(!root) return {0,0};
        vector<int> left=dfs(root->left);
        vector<int> right=dfs(root->right);
        int val0=max(left[0],left[1])+max(right[0],right[1]);
        int val1=root->val+left[0]+right[0];
        return {val0,val1};
    }
};

利用树形动态规划结合后序遍历。对于每个节点，递归地计算并返回两个状态值：

偷当前节点（val1）：此时必须跳过左右子节点，收益为“当前节点值 + 左子不偷 + 右子不偷”。
不偷当前节点（val0）：此时左右子节点可偷可不偷，取各自状态下的最大值之和。

通过自底向上的推导，最终在根节点处比较这两种选择的最大值。

下标 [0] (val0)：表示不偷当前节点时，其子树能得到的最大收益。

下标 [1] (val1)：表示偷当前节点时，其子树能得到的最大收益。

ACM处理337

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
vector<int> robtree(TreeNode* cur) {
    if (!cur) return {0, 0};
    vector<int> left = robtree(cur->left);
    vector<int> right = robtree(cur->right);
    int val0 = max(left[0], left[1]) + max(right[0], right[1]);
    int val1 = cur->val + left[0] + right[0];
 
    return {val0, val1};
}
 
int rob(TreeNode* root) {
    vector<int> result = robtree(root);
    return max(result[0], result[1]);
}
 
// --- 辅助：层序构建二叉树 ---
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> qu;
    qu.push(root);
    int i = 1;
    while (!qu.empty() && i < (int)nums.size()) {
        TreeNode* curr = qu.front();
        qu.pop();
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            qu.push(curr->left);
        }
        i++;
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            qu.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        cout << rob(root) << '\n';
    }
    return 0;
}

🔥437. 路径总和 III✅

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

class Solution {
public:
    int target=0,ans=0;
    unordered_map<long long, int> prefix;
    void dfs(TreeNode* node, long long curSum){
        if(!node) return;
        curSum+=node->val;
        if(prefix.count(curSum-target)) ans+=prefix[curSum-target];
        prefix[curSum]++;
        dfs(node->left,curSum);
        dfs(node->right,curSum);
        prefix[curSum]--;
    }
    int pathSum(TreeNode* root, int targetSum) {
        target=targetSum;
        prefix[0]=1;
        dfs(root,0);
        return ans;
    }
};

DFS 遍历二叉树，把从根到当前节点的路径和当作前缀和，用哈希表统计历史前缀和出现次数，当前前缀和减去 target 的次数就是以当前节点结尾的合法路径数。

prefix[0] = 1 表示：在任何节点之前，存在一条“和为 0 的空路径”。

在 DFS 开始之前，前缀和为 0 的路径，出现过 1 次。这个「路径」就是：空路径（什么节点都不选）

要想把任意路径和都表示成两个前缀和的差，必须添加一个 0，否则当路径是前缀时（从根节点开始的路径），没法减去一个数。

从根到当前节点的前缀和为 curSum。如果在之前的路径中，存在一个位置的前缀和等于 curSum - target，那么这两个位置之间的路径和就正好是 target。

ACM处理437

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
int target = 0, ans = 0;
unordered_map<long long, int> prefix;
 
void dfs(TreeNode* node, long long curSum) {
    if (!node) return;
    curSum += node->val;
    if (prefix.count(curSum - target)) {
        ans += prefix[curSum - target];
    }
 
    prefix[curSum]++;
    dfs(node->left, curSum);
    dfs(node->right, curSum);
    prefix[curSum]--;
}
 
int pathSum(TreeNode* root, int targetSum) {
    ans = 0;
    target = targetSum;
    prefix.clear();
    prefix[0] = 1; // 初始化：前缀和为0的情况出现1次
    dfs(root, 0);
    return ans;
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> qu;
    qu.push(root);
    int i = 1;
    while (!qu.empty() && i < (int)nums.size()) {
        TreeNode* curr = qu.front();
        qu.pop();
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            qu.push(curr->left);
        }
        i++;
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            qu.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, targetSum;
    while (cin >> n >> targetSum) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        cout << pathSum(root, targetSum) << '\n';
    }
    return 0;
}

🔥560. 和为 K 的子数组✅

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

int subarraySum(vector<int>& nums, int k) {
        int pre=0,cnt=0;
        unordered_map<int,int> mp;
        mp[0]=1;
        for(auto s:nums){
            pre+=s;
            if(mp.count(pre-k)) cnt+=mp[pre-k];
            mp[pre]++;
        }
        return cnt;
    }

利用 前缀和 结合 哈希表 优化。转化为“在当前位置之前，寻找前缀和等于 pre - k 的出现次数”。

核心逻辑

前缀和转换：定义 pre[i] 为数组前 i 个元素的和。那么子数组 [j, i] 的和可以表示为 pre[i] - pre[j-1]。
等式变形：要找的是满足 pre[i] - pre[j-1] = k 的区间，等价于在遍历到 i 时，寻找之前有多少个 j 满足 pre[j-1] = pre[i] - k。
哈希表**计数**：利用 unordered_map 存储每个前缀和出现的**频次**。
1. 初始化 mp[0] = 1：为了处理 从下标 0 开始的子数组。假设在数组开始前有一个前缀和是 0，
2. 实时累加：在一次遍历中，计算当前前缀和 pre，在哈希表中查找 pre - k，将其出现的次数累加进结果 cnt，然后更新哈希表中 pre 的频次。

数学上相当于：sum(-1) = 0

这样就能统一处理：[0 ... i] 这种子数组

O(N)

ACM处理560

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    while (cin >> n >> k) {  // 多组输入
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        cout << subarraySum(nums, k) << '\n';
    }
    return 0;
}

非hot100 26道

归并排序：先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并。

快速排序是先将一个元素排好序，然后再将剩下的元素排好序。

快速排序的核心无疑是 partition 函数，partition 函数的作用是在 nums[lo..hi] 中寻找一个切分点 p，通过交换元素使得 nums[lo..p-1] 都小于等于 nums[p]，且 nums[p+1..hi] 都大于 nums[p]：

快速排序的过程是一个构造二叉搜索树的过程。

⭐️8. 字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。
函数 myAtoi(string s) 的算法如下：
**空格：**读入字符串并丢弃无用的前导空格（" "）
**符号：**检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
**转换：**通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
**舍入：**如果整数数超过 32 位有符号整数范围 [−2(31), 2(31 )− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2(31) 的整数应该被舍入为 −2(31) ，大于 2(31 )− 1 的整数应该被舍入为 2(31 )− 1 。
返回整数作为最终结果。

int myAtoi(string s) {
        int n=s.size(),i=0;
        while(i<n&&s[i]==' ') i++;
        if(i==n) return 0;
        int sign=1;
        if(s[i]=='-'||s[i]=='+'){
            sign=(s[i]=='-')?-1:1;
            i++;
        }
        long long res=0;
        while(i<n&&isdigit(s[i])){
            res=res*10+(s[i]-'0');
            if(sign*res>=INT_MAX) return INT_MAX;
            else if(sign*res<=INT_MIN) return INT_MIN;
            i++;
        }
        return res*sign;
    }

去掉前导空格,判断符号,转数字,溢出判断

res \* 10 + (s[i] - '0')：这是字符转数字的标准公式。

ACM处理8

#include <bits/stdc++.h>
using namespace std;
 
int myAtoi(string s) {
    int n = s.size(), i = 0;
    while (i < n && s[i] == ' ') i++;
    if (i == n) return 0;
 
    int sign = 1;
    if (s[i] == '-' || s[i] == '+') {
        sign = (s[i] == '-') ? -1 : 1;
        i++;
    }
 
    long long res = 0;
    while (i < n && isdigit(s[i])) {
        res = res * 10 + (s[i] - '0');
        if (sign == 1 && res >= INT_MAX) return INT_MAX;
        if (sign == -1 && -res <= INT_MIN) return INT_MIN;
        i++;
    }
    return (int)(res * sign);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string line;
    while (getline(cin, line)) {
        if (line.empty()) continue;
        cout << myAtoi(line) << '\n';
    }
    return 0;
}

🔥⭐️25. K 个一组翻转链表✅

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0);
        dummy.next=head;
        ListNode* pre=&dummy;
        while(true){
            ListNode* cur=pre;
            for(int i=0;i<k&&cur;i++) cur=cur->next;
            if(!cur) break;
            ListNode* start=pre->next;
            ListNode* nxt=start->next;
            for(int i=1;i<k;i++){
                start->next=nxt->next;
                nxt->next=pre->next;
                pre->next=nxt;
                nxt=start->next;
            }
            pre=start;
        }
        return dummy.next;
    }

找到一段长度为 k 的区间，原地翻转它，然后更新指针处理下一段。整体 O(n) / O(1)。

区间内原地翻转 (头插法), 不是把整个区间切下来翻转，而是逐个将后面的节点移到区间的最前面。

pre: 永远指向“已翻转好的部分”的最后一个节点。

start: 翻转后的尾节点（原本的头）。

next: 当前待移动到前面的节点。

cur：探测剩余长度是否足够 k 个。

ACM处理25

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* pre = &dummy;
    while (true) {
        ListNode* cur = pre;
        for (int i = 0; i < k && cur; i++) cur = cur->next;
        if (!cur) break;
        ListNode* start = pre->next;
        ListNode* nxt = start->next;
        for (int i = 1; i < k; i++) {
            start->next = nxt->next;
            nxt->next = pre->next;
            pre->next = nxt;
            nxt = start->next;
        }
        pre = start;
    }
    return dummy.next;
}
 
ListNode* buildList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    while (cin >> n >> k) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        ListNode* res = reverseKGroup(head, k);
 
        vector<int> out;
        while (res) {
            out.push_back(res->val);
            res = res->next;
        }
 
        for (int i = 0; i < (int)out.size(); i++) {
            if (i) cout << ' ';
            cout << out[i];
        }
        cout << '\n';
    }
    return 0;
}

⭐️41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

int firstMissingPositive(vector<int>& nums) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            while(nums[i]>=1&&nums[i]<=n&&nums[i]!=nums[nums[i]-1]){
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i]!=i+1) return i+1;
        }
        return n+1;
    }

如果数字 $$$$ 在 $1 \sim$ 范围内，就通过交换把它送回下标为 $x-$ 的座位上。

nums[i] != nums[nums[i]-1] 如果要交换的目标位置已经坐了一个正确的数，就没必要换了（处理了重复元素）。

使用 while 的原因：当你把 nums[i] 换到它该去的地方时，从那边换回来的新数字可能也是一个属于 [1, n]范围内的数。你需要连续不断地把换回来的数送走，直到当前 i 位置坐了一个不属于这里的数，或者是一个已经归位的数。

ACM处理41

#include <bits/stdc++.h>
using namespace std;
 
int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        cout << firstMissingPositive(nums) << '\n';
    }
    return 0;
}

⭐️43. 字符串相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
**注意：**不能使用任何内置的 BigInteger 库或直接将输入转换为整数。

string multiply(string num1, string num2) {
        if(num1=="0"||num2=="0") return "0";
        int m=num1.size(),n=num2.size();
        vector<int> res(m+n,0);
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                int mul=(num1[i]-'0')*(num2[j]-'0');
                int sum=mul+res[i+j+1];
                res[i+j+1]=sum%10;
                res[i+j]+=sum/10;
            }
        }
        string ans;
        for(int i=0;i<res.size();i++){
            if(ans.empty()&&res[i]==0) continue;
            ans+=to_string(res[i]);
        }
        return ans;
    }

模拟十进制竖式乘法。 m 位数乘 n 位数，结果最多是 m + n 位，因此用一个长度为 m + n 的数组 res 存放结果。

从两个字符串的末尾（低位）开始遍历，这与我们手算时从个位开始计算一致。对于 num1[i] 和 num2[j] 的乘积 mul：

个位落在结果数组的 i + j + 1
十位（进位） 落在结果数组的 i + j

由于同一结果位可能被多次命中（多个乘积都会加到同一列），所以在计算时需要把该位置之前已经累积的值一起算上：

res[i+j+1] 永远保存当前这一位的个位
res[i+j] 永远保存所有可能打到这里的进位之和

具体含义是：

sum = mul + res[i+j+1] 👉 合并“当前乘积 + 之前在同一列累积的值”，模拟竖式中同一列的加法
res[i+j+1] = sum % 10 👉 当前列只保留个位
res[i+j] += sum / 10 👉 将进位累加到前一列（注意是累加，不是覆盖）

所有进位在累加过程中自然被处理，不需要额外再写一轮统一进位逻辑。

最后从高位到低位遍历结果数组，跳过前导 0：

如果 ans 为空且当前位为 0，则跳过。一旦 ans 非空，后面的 0 必须保留

时间O(mn)/空间O(m + n)

ACM处理43

#include <bits/stdc++.h>
using namespace std;
 
string multiply(string num1, string num2) {
    if (num1 == "0" || num2 == "0") return "0";
    int m = num1.size(), n = num2.size();
    vector<int> res(m + n, 0);
    for (int i = m - 1; i >= 0; i--) {
        for (int j = n - 1; j >= 0; j--) {
            int mul = (num1[i] - '0') * (num2[j] - '0');
            int sum = mul + res[i + j + 1];
            res[i + j + 1] = sum % 10;
            res[i + j] += sum / 10;
        }
    }
    string ans;
    for (int i = 0; i < (int)res.size(); i++) {
        if (ans.empty() && res[i] == 0) continue;
        ans += to_string(res[i]);
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string num1, num2;
    while (cin >> num1 >> num2) {
        cout << multiply(num1, num2) << '\n';
    }
    return 0;
}

🔥⭐️54. 螺旋矩阵✅

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m=matrix.size(),n=matrix[0].size();
        vector<int> ans;
        int up=0,down=m-1,left=0,right=n-1;
        while(true){
            for(int i=left;i<=right;i++) ans.push_back(matrix[up][i]);
            if(++up>down) break;
            for(int i=up;i<=down;i++) ans.push_back(matrix[i][right]);
            if(--right<left) break;
            for(int i=right;i>=left;i--) ans.push_back(matrix[down][i]);
            if(--down<up) break;
            for(int i=down;i>=up;i--) ans.push_back(matrix[i][left]);
            if(++left>right) break;
        }
        return ans;
    }

“四指针边界收缩法”。O(mxn)，空间复杂度为 O(1)。

将矩阵想象成由多个“圈”。定义四个边界：当前未处理的最外侧的行/列。每走完一条边，就将对应的边界向内收缩。如果收缩后边界交错（例如 upper > lower），说明所有元素已遍历完成。

ACM处理54

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m, n;
    while (cin >> m >> n) {  // 多组输入
        vector<vector<int>> matrix(m, vector<int>(n));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                cin >> matrix[i][j];
 
        vector<int> ans = spiralOrder(matrix);
        for (int i = 0; i < ans.size(); i++) {
            if (i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

⭐️69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去。
**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

二分查找。

int mySqrt(int x) {
        int left=0,right=x,i=0;
        while(left<=right){
            int mid=left+(right-left)/2;
            if((long long)mid*mid<=x){
                i=mid;
                left=mid+1;
            }else right=mid-1;
        }
        return i;
    }

时间复杂度 O(**log*_ n)，空间 O(1) 用 long long 防止 mid _ mid 溢出。

在 [0, x] 上二分，判断 mid*mid 与 x 的关系。若 mid^2 ≤ x，说明答案至少是 mid，继续向右；否则向左。最终保存的 ans 即为向下取整结果。

优化方法：牛顿迭代。

ACM处理69

#include <bits/stdc++.h>
using namespace std;
 
int mySqrt(int x) {
    int left = 0, right = x, i = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if ((long long)mid * mid <= x) {
            i = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return i;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int x;
    while (cin >> x) {
        cout << mySqrt(x) << '\n';
    }
    return 0;
}

⭐️82. 删除排序链表中的重复元素 II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(0);
        dummy.next=head;
        ListNode* cur=&dummy;
        while(cur->next&&cur->next->next){
            if(cur->next->val==cur->next->next->val){
                int x=cur->next->val;
                while(cur->next&&cur->next->val==x) cur->next=cur->next->next;
            }else cur=cur->next;
        }
        return dummy.next;
    }

O(n)，O(1)

用指针 cur 从 dummy 开始，如果 cur->next 和 cur->next->next 值相同，记录这个重复值，一直跳过所有等于该值的节点。否则正常向前移动

ACM处理82

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* deleteDuplicates(ListNode* head) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* cur = &dummy;
    while (cur->next && cur->next->next) {
        if (cur->next->val == cur->next->next->val) {
            int x = cur->next->val;
            while (cur->next && cur->next->val == x) {
                cur->next = cur->next->next;
            }
        } else {
            cur = cur->next;
        }
    }
    return dummy.next;
}
 
ListNode* buildList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        ListNode* res = deleteDuplicates(head);
 
        vector<int> out;
        while (res) {
            out.push_back(res->val);
            res = res->next;
        }
 
        for (int i = 0; i < (int)out.size(); i++) {
            if (i) cout << ' ';
            cout << out[i];
        }
        cout << '\n';
    }
    return 0;
}

⭐️88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1,j=n-1,k=m+n-1;
        while(j>=0){
            if(i>=0&&nums1[i]>nums2[j]) nums1[k--]=nums1[i--];
            else nums1[k--]=nums2[j--];
        }
    }

从后往前合并（**双指针**）利用 nums1 末尾的空位，避免额外空间。

i = m - 1 指向 nums1 有效末尾;j = n - 1 指向 nums2 末尾;k = m + n - 1 指向 nums1 最后位置

每次把较大的元素放到 nums1[k]，指针左移. O(m+n)/O(1)

因为最终目标是把 nums2 全部合进 nums1。当 nums2 用完时，nums1 剩余部分已经在正确位置；所以循环条件只需要 j >= 0。

ACM处理88

#include <bits/stdc++.h>
using namespace std;
 
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int m, n;
    while (cin >> m >> n) {
        vector<int> nums1(m + n);
        vector<int> nums2(n);
        for (int i = 0; i < m; i++) cin >> nums1[i];
        for (int i = 0; i < n; i++) cin >> nums2[i];
 
        merge(nums1, m, nums2, n);
 
        for (int i = 0; i < (int)nums1.size(); i++) {
            if (i) cout << ' ';
            cout << nums1[i];
        }
        cout << '\n';
    }
    return 0;
}

⭐️92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode dummy(0);
        dummy.next=head;
        ListNode* pre=&dummy;
        for(int i=0;i<left-1;i++) pre=pre->next;
        ListNode* cur=pre->next;
        for(int i=0;i<right-left;i++){
            ListNode* nxt=cur->next;
            cur->next=nxt->next;
            nxt->next=pre->next;
            pre->next=nxt;
        }
        return dummy.next;
    }

pre 到达 left 位置的前一个节点。

cur 指针：指向反转区域的第一个节点

要让 k 个节点完成反转，我们只需要把 cur 后面的 k-1 个节点依次“插”到前面去。

移动的是“间隙”，假设反转从第 left 到第 right 个节点，这一共有 k = right - left + 1 个节点。

在 C++ 的 for 循环中，for(int i = 0; i < k; i++) 会精确执行 k 次。

ACM处理92

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* reverseBetween(ListNode* head, int left, int right) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* pre = &dummy;
    for (int i = 0; i < left - 1; i++) {
        pre = pre->next;
    }
    ListNode* cur = pre->next;
    for (int i = 0; i < right - left; i++) {
        ListNode* nxt = cur->next;
        cur->next = nxt->next;
        nxt->next = pre->next;
        pre->next = nxt;
    }
    return dummy.next;
}
 
ListNode* buildList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, left, right;
    while (cin >> n >> left >> right) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        ListNode* res = reverseBetween(head, left, right);
 
        vector<int> out;
        while (res) {
            out.push_back(res->val);
            res = res->next;
        }
 
        for (int i = 0; i < (int)out.size(); i++) {
            if (i) cout << ' ';
            cout << out[i];
        }
        cout << '\n';
    }
    return 0;
}

⭐️93. 复原 IP 地址

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。

ACM处理93

⭐️103. 二叉树的锯齿形层序遍历✅

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if(root) que.push(root);
        while(!que.empty()){
            int size=que.size();
            vector<int> ans;
            while(size--){
                TreeNode* node=que.front();
                que.pop();
                ans.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
            if(res.size()%2==1) reverse(ans.begin(),ans.end());
            res.push_back(ans);
        }
        return res;
    }

第 0 层 (res 为空)：0 % 2 == 0，不翻转（左右）。

第 1 层 (res 已有 1 个元素)：1 % 2 == 1，执行 reverse（右左）。

ACM处理103

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    queue<TreeNode*> que;
    vector<vector<int>> res;
    if (root) que.push(root);
    while (!que.empty()) {
        int size = que.size();
        vector<int> ans;
        while (size--) {
            TreeNode* node = que.front();
            que.pop();
            ans.push_back(node->val);
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
        if (res.size() % 2 == 1) reverse(ans.begin(), ans.end());
        res.push_back(ans);
    }
    return res;
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> qu;
    qu.push(root);
    int i = 1;
    while (!qu.empty() && i < (int)nums.size()) {
        TreeNode* curr = qu.front();
        qu.pop();
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            qu.push(curr->left);
        }
        i++;
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            qu.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        vector<vector<int>> res = zigzagLevelOrder(root);
 
        for (const auto& level : res) {
            for (int i = 0; i < (int)level.size(); i++) {
                cout << level[i] << (i == (int)level.size() - 1 ? "" : " ");
            }
            cout << '\n';
        }
    }
    return 0;
}

🔥122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。然而，你可以在 同一天 多次买卖该股票，但要确保你持有的股票不超过一股。
返回 你能获得的 最大利润。

    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<vector<int>> dp(n,vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }
        return dp[n-1][1];
    }

ACM处理122

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> prices(n);
        for (int i = 0; i < n; i++) cin >> prices[i];
 
        cout << maxProfit(prices) << '\n';
    }
    return 0;
}

⭐️124. 二叉树中的最大路径和✅

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

class Solution {
public:
    int ans=INT_MIN;
    int maxPathSum(TreeNode* root) {
        findSum(root);
        return ans;
    }
    int findSum(TreeNode* cur){
        if(!cur) return 0;
        int left=max(findSum(cur->left),0);
        int right=max(findSum(cur->right),0);
        int val=cur->val+left+right;
        ans=max(val,ans);
        return cur->val+max(left,right);
    }
};

路径可以经过根节点并连接左右子树，但不能在同一个子树中往返

内部最大路径 val = cur->val + left + right;

表示以当前节点为“转折点”，连接左、右两边形成的一条完整路径。

对外贡献值 return cur->val + max(left, right);

表示如果父节点想要包含当前节点，它只能从左或者右选一条路走下去，不能两边都占

如果某条子路径的和是负数，不要它（即贡献为 0）。

return的值返回给父节点，只能单侧，才能让这一枝（提供最大贡献度）与父节点形成可能的最大路径。

如果给双侧，无法形成一条路径（同一子树往返）。

ACM处理124

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
int ans = INT_MIN;
 
int findSum(TreeNode* cur) {
    if (!cur) return 0;
    int left = max(findSum(cur->left), 0);
    int right = max(findSum(cur->right), 0);
    int val = cur->val + left + right;
    ans = max(val, ans);
    return cur->val + max(left, right);
}
 
int maxPathSum(TreeNode* root) {
    ans = INT_MIN;
    findSum(root);
    return ans;
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> qu;
    qu.push(root);
    int i = 1;
    while (!qu.empty() && i < (int)nums.size()) {
        TreeNode* curr = qu.front();
        qu.pop();
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            qu.push(curr->left);
        }
        i++;
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            qu.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        TreeNode* root = buildTree(nums);
        cout << maxPathSum(root) << '\n';
    }
    return 0;
}

🔥131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

ACM处理131

⭐️143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L(0) → L(1) → … → L(n - 1) → L(n)
请将其重新排列后变为：
L(0) → L(n) → L(1) → L(n - 1) → L(2) → L(n - 2) → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* mid= getMiddle(head);
        ListNode* ans= reverseList(mid->next);
        mid->next=nullptr;
        merge(head,ans);
    }
    void merge(ListNode* l1, ListNode* l2){
        while(l1&&l2){
            ListNode* n1=l1->next,* n2=l2->next;
            l1->next=l2;
            l2->next=n1;
            l1=n1,l2=n2;
        }
    }
    ListNode* getMiddle(ListNode* head){
        ListNode* fast=head,* slow=head;
        while(fast->next&&fast->next->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        return slow;
    }
    ListNode* reverseList(ListNode* head){
        ListNode* pre=nullptr, *cur=head;
        while(cur){
            ListNode* nxt=cur->next;
            cur->next=pre;
            pre=cur;
            cur=nxt;
        }
        return pre;
    }
};

ACM处理143

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* getMiddle(ListNode* head) {
    ListNode *fast = head, *slow = head;
    while (fast->next && fast->next->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
 
ListNode* reverseList(ListNode* head) {
    ListNode *pre = nullptr, *cur = head;
    while (cur) {
        ListNode* nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre;
}
 
void merge(ListNode* l1, ListNode* l2) {
    while (l1 && l2) {
        ListNode *n1 = l1->next, *n2 = l2->next;
        l1->next = l2;
        l2->next = n1;
        l1 = n1;
        l2 = n2;
    }
}
 
void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode* mid = getMiddle(head);
    ListNode* l2 = reverseList(mid->next);
    mid->next = nullptr;
    merge(head, l2);
}
 
ListNode* buildList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        reorderList(head);
 
        while (head) {
            cout << head->val << (head->next ? " " : "");
            head = head->next;
        }
        cout << '\n';
    }
    return 0;
}

⭐️148. 排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode* fast=head->next;
        ListNode* slow=head;
        while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* mid=slow->next;
        slow->next=nullptr;
        ListNode* left=sortList(head);
        ListNode* right=sortList(mid);
        return merge(left,right);
    }
 
    ListNode* merge(ListNode* l1,ListNode* l2){
        ListNode* dummy=new ListNode(0);
        ListNode* cur=dummy;
        while(l1&&l2){
            if(l1->val<l2->val){
                cur->next=l1;
                l1=l1->next;
            }else{
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        cur->next=l1?l1:l2;
        return dummy->next;
    }
};

归并排序在链表上表现得最为出色。主要原因有两个：链表不支持随机访问（排除了快排的高效分区），但链表合并操作只需要修改指针。

寻找中点，断开**链表*_：ListNode_ mid = slow->next; slow->next = nullptr;。这一步至关重要，它将一个长链表物理截断为两个独立的子链表，否则递归将无法终止。

不断将链表对半切开，直到每个子链表只剩一个节点（即 !head || !head->next）。一个节点的链表天生就是有序的。

初始化 fast = head->next 确保了在只有两个节点时，slow 指向第一个节点，从而能正确地将链表平分为 1 和 1。

时间复杂度：O(n log n) 这达到了排序算法的理论下限。递归树的高度是 log n，每一层合并的总工作量是 n。

空间复杂度：O(log n)。虽然合并本身是 O(1) 空间的，但递归调用栈需要占据 log n 的深度。

ACM处理148

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* merge(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    cur->next = l1 ? l1 : l2;
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}
 
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
 
    ListNode* fast = head->next;
    ListNode* slow = head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
 
    ListNode* mid = slow->next;
    slow->next = nullptr;
 
    ListNode* left = sortList(head);
    ListNode* right = sortList(mid);
 
    return merge(left, right);
}
 
ListNode* buildList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode* head = new ListNode(nums[0]);
    ListNode* cur = head;
    for (int i = 1; i < (int)nums.size(); i++) {
        cur->next = new ListNode(nums[i]);
        cur = cur->next;
    }
    return head;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        ListNode* head = buildList(nums);
        ListNode* res = sortList(head);
 
        while (res) {
            cout << res->val << (res->next ? " " : "");
            res = res->next;
        }
        cout << '\n';
    }
    return 0;
}

⭐️151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

string reverseWords(string s) {
        int n=s.size(),slow=0;
        for(int fast=0;fast<n;fast++){
            if(s[fast]!=' '){
                if(slow!=0) s[slow++]=' ';
                while(fast<n&&s[fast]!=' ') s[slow++]=s[fast++];
            }
        }
        s.resize(slow);
        reverse(s.begin(),s.end());
        int start=0;
        for(int i=0;i<=s.size();i++){
            if(i==s.size()||s[i]==' '){
                reverse(s.begin()+start,s.begin()+i);
                start=i+1;
            }
        }
        return s;
    }

**去除多余空格，**前导空格，尾随空格，单词之间只保留一个空格
整体反转字符串；3.逐个单词反转

fast 负责寻找单词，slow 负责“写入”有效字符。

遇到单词字符,如果不是第一个单词，单词前加个空格,将整个单词搬运到前面

if (slow != 0) 确保只有在单词之间才添加空格，避免了首位空格。

遇到空格或者到达字符串末尾，说明找完了一个单词

i <= s.size()最后一个单词后面没有空格，只能靠 i == size 触发反转

ACM处理151

#include <bits/stdc++.h>
using namespace std;
 
string reverseWords(string s) {
    int n = s.size(), slow = 0;
    for (int fast = 0; fast < n; fast++) {
        if (s[fast] != ' ') {
            if (slow != 0) s[slow++] = ' ';
            while (fast < n && s[fast] != ' ') s[slow++] = s[fast++];
        }
    }
    s.resize(slow);
 
    reverse(s.begin(), s.end());
 
    int start = 0;
    for (int i = 0; i <= (int)s.size(); i++) {
        if (i == (int)s.size() || s[i] == ' ') {
            reverse(s.begin() + start, s.begin() + i);
            start = i + 1;
        }
    }
    return s;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string line;
    while (getline(cin, line)) {
        if (line.empty()) continue;
        cout << "\"" << reverseWords(line) << "\"" << '\n';
    }
    return 0;
}

⭐️160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交**：**

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cur1=headA;
        ListNode* cur2=headB;
        if(!cur1||!cur2) return nullptr;
        while(cur1!=cur2){
            cur1=cur1==nullptr?headB:cur1->next;
            cur2=cur2==nullptr?headA:cur2->next;
        }
        return cur1;
    }

指针 cur1 遍历完链表 A 后，跳转到链表 B 的头部继续走。

指针 cur2 遍历完链表 B 后，跳转到链表 A 的头部继续走。

如果链表相交，它们会在交点处相等，跳出循环。

如果不相交， 它们会各自走完 A+B 的全程，最后同时变成 nullptr。因为 nullptr == nullptr，循环依然会终止，并返回 nullptr

$O(m + n$ / O(1)

ACM处理160

⭐️165. 比较版本号

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。
比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。
返回规则如下：
如果 version1 < version2 返回 -1，
如果 version1 > version2 返回 1，
除此之外返回 0。

int compareVersion(string version1, string version2) {
        int m=version1.size(),n=version2.size();
        int i=0,j=0;
        while(i<m||j<n){
            int a=0,b=0;
            while(i<m&&version1[i]!='.') a=a*10+(version1[i++]-'0');
            i++;
            while(j<n&&version2[j]!='.') b=b*10+(version2[j++]-'0');
            j++;
            if(a!=b) return a>b?1:-1;
        }
        return 0;
    }

字符串转整数的核心算法a * 10 + (char - '0')

注意：它会自动忽略前导零（例如 "001" 会变成 1）。

O(m+n) / O(1)

ACM处理165

#include <bits/stdc++.h>
using namespace std;
 
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
 
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode* cur1 = headA;
    ListNode* cur2 = headB;
    if (!cur1 || !cur2) return nullptr;
    while (cur1 != cur2) {
        cur1 = (cur1 == nullptr) ? headB : cur1->next;
        cur2 = (cur2 == nullptr) ? headA : cur2->next;
    }
    return cur1;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int intersectVal, nA, nB, skipA, skipB;
    while (cin >> intersectVal >> nA >> nB >> skipA >> skipB) {
        vector<int> valsA(nA), valsB(nB);
        for (int i = 0; i < nA; i++) cin >> valsA[i];
        for (int i = 0; i < nB; i++) cin >> valsB[i];
 
        ListNode *headA = new ListNode(0), *headB = new ListNode(0);
        ListNode *currA = headA, *currB = headB, *interNode = nullptr;
 
        for (int i = 0; i < nA; i++) {
            currA->next = new ListNode(valsA[i]);
            currA = currA->next;
            if (i == skipA) interNode = currA;
        }
        for (int i = 0; i < nB; i++) {
            if (i == skipB) {
                currB->next = interNode;
                break;
            }
            currB->next = new ListNode(valsB[i]);
            currB = currB->next;
        }
 
        ListNode *res = getIntersectionNode(headA->next, headB->next);
        if (res) cout << "Intersected at '" << res->val << "'\n";
        else cout << "No intersection\n";
    }
    return 0;
}

⭐️199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> ans;
        if(root) que.push(root);
        while(!que.empty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode* node=que.front();
                que.pop();
                if(i==size-1) ans.push_back(node->val);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return ans;
    }

ACM处理199

#include <bits/stdc++.h>
using namespace std;
 
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
vector<int> rightSideView(TreeNode* root) {
    queue<TreeNode*> que;
    vector<int> ans;
    if (root) que.push(root);
    while (!que.empty()) {
        int size = que.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = que.front();
            que.pop();
            if (i == size - 1) ans.push_back(node->val);
            if (node->left) que.push(node->left);
            if (node->right) que.push(node->right);
        }
    }
    return ans;
}
 
TreeNode* buildTree(const vector<int>& nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> qu;
    qu.push(root);
    int i = 1;
    while (!qu.empty() && i < (int)nums.size()) {
        TreeNode* curr = qu.front();
        qu.pop();
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            qu.push(curr->left);
        }
        i++;
        if (i < (int)nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            qu.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
        TreeNode* root = buildTree(nums);
        vector<int> res = rightSideView(root);
        for (int i = 0; i < (int)res.size(); i++) {
            cout << res[i] << (i == (int)res.size() - 1 ? "" : " ");
        }
        cout << '\n';
    }
    return 0;
}

⭐️232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

ACM处理232

🔥⭐️347. 前 K 个高频元素✅

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> cnt;
        int max_cnt=0;
        for(int n:nums){
            cnt[n]++;
            max_cnt=max(max_cnt,cnt[n]);
        }
        vector<vector<int>> buckets(max_cnt+1);
        for(auto& [x,c]:cnt){
            buckets[c].push_back(x);
        }
        vector<int> ans;
        for(int i=max_cnt;i>=0&&ans.size()<k;i--){
            ans.insert(ans.end(),buckets[i].begin(),buckets[i].end());
        }
        return ans;
    }

频率作为下标,统计频率,装桶,逆序收集

buckets 的长度是 max_cnt + 1，这意味着即便某个元素出现了 N次，我们也总能找到对应的桶。

创建足够的桶,把数字 x 放到频率为 c 的桶里

在 ans 的末尾，把 buckets[i] 桶里从头到尾的所有元素都塞进去。

ans.end() (插入位置) 这是一个迭代器，指向 ans 最后一个元素之后的位置。新元素将以 追加（Append） 的方式加入。

buckets[i].begin() (源起始位置);buckets[i].end()(源结束位置)

$O(N$

ACM处理347

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k;
    while (cin >> n >> k) {  // 多组输入
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        vector<int> ans = topKFrequent(nums, k);
        for(int i = 0; i < ans.size(); i++){
            if(i) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

⭐️415. 字符串相加

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

string addStrings(string num1, string num2) {
        int i=num1.size()-1,j=num2.size()-1,carry=0;
        string ans;
        while(i>=0||j>=0||carry){
            int x=(i>=0)?(num1[i--]-'0'):0;
            int y=(j>=0)?(num2[j--]-'0'):0;
            int sum=x+y+carry;
            ans.push_back(sum%10+'0');
            carry=sum/10;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }

核心循环：只要还有数字没加完，或者还有进位没处理，就继续

取出当前位的数字。如果指针已经越界（小于0），说明该数已处理完，补0

当前位的总和 = num1当前位 + num2当前位 + 上一次的进位

ACM处理415

#include <bits/stdc++.h>
using namespace std;
 
string addStrings(string num1, string num2) {
    int i = num1.size() - 1, j = num2.size() - 1, carry = 0;
    string ans;
    while (i >= 0 || j >= 0 || carry) {
        int x = (i >= 0) ? (num1[i--] - '0') : 0;
        int y = (j >= 0) ? (num2[j--] - '0') : 0;
        int sum = x + y + carry;
        ans.push_back(sum % 10 + '0');
        carry = sum / 10;
    }
    reverse(ans.begin(), ans.end());
    return ans;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string n1, n2;
    while (cin >> n1 >> n2) {
        cout << addStrings(n1, n2) << '\n';
    }
    return 0;
}

⭐️704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。
你必须编写一个具有 O(log n) 时间复杂度的算法。

int search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target) right=mid-1;
            else if(nums[mid]<target) left=mid+1;
            else return mid;
        }
        return -1;
    }

ACM处理704

#include <bits/stdc++.h>
using namespace std;
 
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, target;
    while (cin >> n >> target) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
        cout << search(nums, target) << '\n';
    }
    return 0;
}

⭐️912. 排序数组（快排）✅

给你一个整数数组 nums，请你将该数组升序排列。
你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

class Solution {
public:
    void quickSort(vector<int>& nums,int l,int r){
        if(l>=r) return;
        int p=l+rand()%(r-l+1);
        swap(nums[l],nums[p]);
        int pivot=nums[l],i=l,j=r;
        while(i<j){
            while(i<j&&nums[j]>=pivot) j--;
            nums[i]=nums[j];
            while(i<j&&nums[i]<=pivot) i++;
            nums[j]=nums[i];
        }
        nums[i]=pivot;
        quickSort(nums,l,i-1);
        quickSort(nums,i+1,r);
    }
    vector<int> sortArray(vector<int>& nums) {
        srand(time(0));
        quickSort(nums,0,nums.size()-1);
        return nums;
    }
};

随机化,左右横跳填坑,右找小,左找大,基准归位,递归分治.

递归**出口**。区间只有一个数或为空时，无需再排。

pivotIdx:随机化。防止在“近乎有序”的数组上退化到 O(n^2)。将随机选中的数换到最左侧作为基准。

pivot:暂存基准。nums[l] 的位置相当于一个可以被覆盖的“坑”。

双指针**填坑**。j 从右往左找小的，i 从左往右找大的。

归位。指针重合，将基准值填入最终位置（此时左侧全小于等于它，右侧全大于等于它）

分治。递归处理左右两半，注意不包含已归位的 i。

边界条件：while 内部必须带 i < j，防止越界。

随机种子：srand(time(0)) 只需在入口调用一次。

基准判断：nums[j] >= pivot 的等号不能漏，否则遇到重复值会死循环。

pivotIdx = l + rand() % (r - l + 1) 是什么意思？

是一个标准的生成闭区间[l, r]内随机整数的公式：

r-l+1：计算当前处理区间的长度。
rand()%(长度)：产生一个偏移量。保证随机索引落在 [l, r] 范围内。

srand(time(0))：以当前系统时间作为种子。确定随机规则。

全局打乱 (**Shuffle**)：时间复杂度 O(n)。如果你在每一层递归都打乱，总开销太大。

ACM处理912

#include <bits/stdc++.h>
using namespace std;
 
void quickSort(vector<int>& nums, int l, int r) {
    if (l >= r) return;
    swap(nums[l], nums[l + rand() % (r - l + 1)]);
    int pivot = nums[l], i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        nums[i] = nums[j];
        while (i < j && nums[i] <= pivot) i++;
        nums[j] = nums[i];
    }
    nums[i] = pivot;
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    srand(time(0));
 
    int n;
    while (cin >> n) {
        vector<int> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
 
        quickSort(nums, 0, n - 1);
 
        for (int i = 0; i < n; i++) {
            if (i) cout << ' ';
            cout << nums[i];
        }
        cout << '\n';
    }
    return 0;
}

🔥⭐️1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

    int longestCommonSubsequence(string text1, string text2) {
        int m=text1.size(),n=text2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(text1[i-1]==text2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m][n];
    }

dp[i][j]：表示 text1 前 i 个字符 和 text2 前 j 个字符 的最长公共子序列长度。

维度为 m+1 和 n+1：多出的一行和一列是为了处理空字符串的情况（即 dp[0][j] 和 dp[i][0]）。

text1 = "abcde", text2 = "ace"

else的情况例如j=3时，取abc与ac和ab与ace的dp最大值。

ACM处理1143

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    string s1, s2;
    while (cin >> s1 >> s2) {  // 多组输入
        cout << longestCommonSubsequence(s1, s2) << '\n';
    }
    return 0;
}

ACM 模式代码模板

#include <iostream>
using namespace std;
 
class Solution {
public:
    int add(int a, int b) {
        return a + b;
    }
};
 
int main() {
    int a, b;
    // 读取到 EOF
    while (cin >> a >> b) {
        int result = Solution().add(a, b);
        cout << result << endl;
    }
    return 0;
}

链表ACM模板

#include <iostream>
#include <vector>
#include <sstream>
 
using namespace std;
 
// 1. 定义结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
// 2. 核心逻辑函数 (以合并/反转为例)
ListNode* solution(ListNode* head) {
    // Your Code Here
    return head;
}
 
// 3. 【工具函数】构造链表
ListNode* createList(const vector<int>& nums) {
    if (nums.empty()) return nullptr;
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int x : nums) {
        cur->next = new ListNode(x);
        cur = cur->next;
    }
    return dummy.next;
}
 
// 4. 【工具函数】打印链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}
 
int main() {
    // 优化 I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    while (cin >> n) { // 假设先输入长度
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) cin >> nums[i];
 
        ListNode* head = createList(nums);
        head = solution(head);
        printList(head);
    }
    return 0;
}
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
ListNode* buildList(const vector<int>& nums) {
    ListNode dummy(0);
    ListNode* cur = &dummy;
    for (int x : nums) {
        cur->next = new ListNode(x);
        cur = cur->next;
    }
    return dummy.next;
}
 
void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << " -> ";
        head = head->next;
    }
    cout << endl;
}
 
ListNode* solve(ListNode* head) {
    // 核心逻辑
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];
 
    ListNode* head = buildList(nums);
    head = solve(head);
}

二叉树ACM模板

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <sstream>
 
using namespace std;
 
// 1. 定义结构体
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
// 2. 【工具函数】层序构造二叉树 (核心)
// 输入示例：{"1", "2", "3", "null", "4"}
TreeNode* createTree(const vector<string>& nodes) {
    if (nodes.empty() || nodes[0] == "null") return nullptr;
 
    TreeNode* root = new TreeNode(stoi(nodes[0]));
    queue<TreeNode*> q;
    q.push(root);
 
    int i = 1;
    while (!q.empty() && i < nodes.size()) {
        TreeNode* curr = q.front();
        q.pop();
 
        // 处理左节点
        if (i < nodes.size() && nodes[i] != "null") {
            curr->left = new TreeNode(stoi(nodes[i]));
            q.push(curr->left);
        }
        i++;
 
        // 处理右节点
        if (i < nodes.size() && nodes[i] != "null") {
            curr->right = new TreeNode(stoi(nodes[i]));
            q.push(curr->right);
        }
        i++;
    }
    return root;
}
 
// 3. 核心逻辑函数
void solve(TreeNode* root) {
    // Your Code Here (如先序遍历)
}
 
int main() {
    string line;
    while (getline(cin, line)) { // 读入整行
        stringstream ss(line);
        string item;
        vector<string> nodes;
        while (ss >> item) nodes.push_back(item);
 
        TreeNode* root = createTree(nodes);
        solve(root);
    }
    return 0;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
// 1. 定义结构
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
 
// 2. 核心算法 (例如：求树的最大深度)
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
 
// 3. 快速构造辅助函数 (层序构造，用 -1 代表 null)
TreeNode* createTree(vector<int> nums) {
    if (nums.empty() || nums[0] == -1) return nullptr;
    TreeNode* root = new TreeNode(nums[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < nums.size()) {
        TreeNode* curr = q.front(); q.pop();
        if (i < nums.size() && nums[i] != -1) {
            curr->left = new TreeNode(nums[i]);
            q.push(curr->left);
        }
        i++;
        if (i < nums.size() && nums[i] != -1) {
            curr->right = new TreeNode(nums[i]);
            q.push(curr->right);
        }
        i++;
    }
    return root;
}
 
int main() {
    // 写死测试用例 (LeetCode 风格)
    // 结构：  1
    //       / \
    //      2   3
    //       \
    //        4
    vector<int> testData = {1, 2, 3, -1, 4};
    TreeNode* root = createTree(testData);
 
    cout << "Max Depth: " << maxDepth(root) << endl;
 
    return 0;
}
 
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->right = new TreeNode(4);
#include <bits/stdc++.h>
 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <climits>
 
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while(cin>>n){
        vector<int> nums(n);
        for(int i=0;i<n;i++) cin>>nums[i];
        // 核心代码
        for(int i=0;i<n;i++) {
            if(i) cout<<' ';
            cout<<nums[i];
        }
        cout<<'\n';
    }
    return 0;
}

sync_with_stdio(false)：取消 C++ 标准流（cin/cout）与 C 标准流（scanf/printf）的同步，显著提高读取速度。

cin.tie(nullptr)：解除 cin 和 cout 的绑定，避免每次读取前都自动刷新缓冲区。

if(i) cout << ' '; 这是一个很优雅的技巧：当 i 不为 0 时（即不是第一个元素时），先输出一个空格。这样可以确保两个数字之间有空格，但最后一个数字后面没有多余空格（这是很多判题系统的严格要求）。

ios::sync_with_stdio(false);

含义：取消 C++ 的 cin/cout 与 C 语言的 scanf/printf 之间的同步。
原理：默认情况下，为了让你在代码里混用 printf 和 cout 而不导致输出顺序错乱，C++ 会加一把“同步锁”。这把锁非常耗时。
后果：
- 利：cin/cout 的速度提升 5-10 倍，基本持平甚至超越 scanf/printf。
- 弊：禁忌混用。一旦写了这一句，代码里绝对不能再出现 printf, scanf, getchar 等 C 风格 IO，否则输出顺序会随机乱跳。
cin.tie(nullptr);
含义：解除 cin 与 cout 的绑定。
原理：默认情况下，cin 和 cout 是捆绑的。每当你执行 cin >> 读取数据前，系统会强行刷新（flush）一次 cout 的缓冲区，确保你在输入前能看到之前的提示文字。
后果：
- 利：在大规模读写交替时（比如读一个数、输一个数），减少了大量无意义的刷新操作，极大地提高效率。
- 弊：如果在交互式题目（根据输入立刻给输出）中，可能导致你的提示信息没及时显示出来。但 LeetCode 和普通 OJ 都是离线评测，完全没影响。

头文件模板

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <cmath>
#include <limits>
#include <cstdlib>
#include <ctime>
 
using namespace std;

LC Core