C++ For Hot100

数组：数组是存放在连续内存空间上的相同类型数据的集合。

1. 两数之和 - 力扣（LeetCode）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v;
        for(int i = 0;i<nums.size();i++)
        {
            for(int j = i+1;j<nums.size();j++)
            {
                if(target-nums[i]==nums[j]) 
                {
                    v.push_back(i);
                    v.push_back(j);
                    return v;
                }
            }
        }
        return v;
    }
};

1512. 好数对的数目 - 力扣（LeetCode）

class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int j, ans = 0;
        int hash[101];
        memset(hash,0,sizeof(hash));
        for(j=0;j<nums.size();++j)
        {
            ans += hash[nums[j]];
            ++hash[nums[j]];
        }
        return ans;
    }
};

注意：这里的ans是累加的形式，也就是当前时刻的nums[j]会去和之前的配对找到相应的组数，并且加上之前的组数，因此才是ans = ans + hash[nums[j]];

709. 转换成小写字母 - 力扣（LeetCode）

tolower()

这里需要注意的是用引用，因为需要修改字符串s里面元素的值；

class Solution {
public:
    string toLowerCase(string s) {
        for(char& ch:s) ch = tolower(ch);
        return s;
    }
        
};

258. 各位相加 - 力扣（LeetCode）

这道题指的注意的就是：int temp = num%10; sum+=num;num/=10;就可以得到num的各个位相加的数；

class Solution {
public:
    int addDigits(int num) {
        int sum;
        while(num>=10){
            sum=0;
            while(num)
            {
                int temp=num%10;
                sum+=temp;
                num/=10;
            }
            num = sum;
        }
        return num;
    }
};

1281. 整数的各位积和之差 - 力扣（LeetCode）

class Solution {
public:
    int subtractProductAndSum(int n) {
        int sum = 0;
        int pro = 1;
        int ans;
        int arr[] ={0};
        while(n>0)
        {
            int temp = n%10;
            sum += temp;
            pro *= temp;
            n /= 10;
        }
        ans = pro - sum;
        return ans;
    }
};

231. 2 的幂 - 力扣（LeetCode）

这道题有了二进制的按位与，因为如果是2的幂，减一之后两个数的按位与就是0；

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0 && (n&(n-1)) == 0;
    }
};

867. 转置矩阵 - 力扣（LeetCode）

矩阵转置，最好创建新的vector<int,vector<int>> result(col,vector<int> (row) 二维容器就是

vector<int,vector<int>> result(col//行数，vector<int> (row) //列数）；

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>> result(col, vector<int>(row));
        for(int i=0;i<row;i++){
            for(int j = 0;j<col;j++){
                result[j][i] = matrix[i][j]; // 转置操作
            }
        }
        return result;
    }
};

也就是说如果是创建二维的容器，vector<vector<int>> result(col, vector<int>(row)); 这里面的result的两个参数分别是

704. 二分查找 - 力扣（LeetCode）

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

27. 移除元素 - 力扣（LeetCode）

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowindex = 0;
        if(nums.size()==0) return 0;
        for(int i=0;i<nums.size();i++)
        {
            if(nums[i]!=val)
            {
                nums[slowindex] = nums[i];
                slowindex++;
            }

        }
        return slowindex;

    }
};

977. 有序数组的平方 - 力扣（LeetCode）

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for(int i =0;i<nums.size();i++)
        {
            nums[i] = nums[i]*nums[i];
        }
        std::sort(nums.begin(), nums.end());
        return nums;
    }
};

第一种方法就是利用了迭代器，sort(nums.begin(),nums.end());

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> ans(nums.size());;
        int k=nums.size()-1;
        int left = 0;
        int right = nums.size()-1;
        while(left <= right)
        {
            if(nums[left]*nums[left]<=nums[right]*nums[right]) 
            {
                ans[k] = (nums[right] * nums[right]);
                right-=1;
            }
            else 
            {
                ans[k] = nums[left] * nums[left];
                left+=1;
            }
            k--;
        }

        return ans;
    }
};

双指针法，就是right和left两个指针从begin和end开始找

209. 长度最小的子数组 - 力扣（LeetCode）

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int slowindex = 0;
        int min_len = INT_MAX;
        int sum = 0;
        for(int fast=0;fast<nums.size();fast++)
        {
            sum += nums[fast];
            while(sum>=target)
            {
                min_len = std::min(min_len, fast - slowindex + 1);
                sum -= nums[slowindex];
                slowindex+=1;
            }
        }
        return (min_len == INT_MAX) ? 0 : min_len;
    }
};

59. 螺旋矩阵 II - 力扣（LeetCode）

class Solution
{
public:
    vector<vector<int>> generateMatrix(int n)
    {
        vector<vector<int>> mat(n, vector<int>(n)); 
        int l=0, r=n-1, t=0, b=n-1;
        int num=1, tar=n*n;
        while(num<=tar){
        for(int i=l;i<=r;i++) mat[t][i] = num++;
        t++;
        for(int i=t;i<=b;i++) mat[i][r] = num++;
        r--;
        for(int i=r;i>=l;i--) mat[b][i] = num++;
        b--;
        for(int i=b;i>=t;i--) mat[i][l] = num++;
        l++; 
        }
        return mat;
    }
};

58. 区间和（第九期模拟笔试）

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n,a,b;
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    for(int i=0;i<n;i++){
        cin >> vec[i];
        presum += vec[i];
        p[i] = presum;
    }
    while(cin >> a >> b)
    {
        int sum;
        if(a==0) sum = p[b];
        else sum = p[b]-p[a-1];
        cout<<sum<<endl;
    }
}

区间和，利用前缀和操作，也就是对于p这个vector容器，里面的每一个元素都是该index之前的元素的累加和；

283. 移动零 - 力扣（LeetCode）

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slowindex = 0;
        for(int fast = 0;fast<nums.size();fast++)
        {
            if(nums[fast]!=0)
            {
                nums[slowindex] = nums[fast];
                slowindex++;
            }
        }
        for(int i=slowindex;i<nums.size();i++)
        {
            nums[i] = 0;
        }
        return;
    }
};

11. 盛最多水的容器 - 力扣（LeetCode）

class Solution {
public:
    int maxArea(vector<int>& height){
        int left =0, right = height.size()-1;
        int hei = 0, temp = 0;
        int area = INT32_MIN;
        while(left<=right)
        {
            if(height[left]<height[right]){
                hei = height[left]; 
                temp = (right-left) * hei;
                left += 1;
            }
            else{
                hei = height[right];
                temp = (right-left) * hei;
                right -= 1;
            }
            area = area > temp? area : temp;
        }
        return area;
    }
};

15. 三数之和 - 力扣（LeetCode）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int slow = 0, fast = nums.size()-1;
        std::sort(nums.begin(), nums.end());

        for(int i=0;i<nums.size();i++)
        {
            if (nums[i] > 0) {
                return ans;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            slow = i+1;
            fast = nums.size()-1;
            while(slow<fast)
            {
                if((nums[i]+nums[fast]+nums[slow])<0) slow+=1;
                else if((nums[i]+nums[fast]+nums[slow])>0) fast-=1;
                else
                {
                    ans.push_back({nums[i],nums[slow],nums[fast]});
                    while (fast > slow && nums[fast] == nums[fast - 1]) fast--;
                    while (fast > slow && nums[slow] == nums[slow + 1]) slow++;

                    // 找到答案时，双指针同时收缩
                    fast--;
                    slow++;
                }
            }
        }
        return ans;
    }
};

三数之和，首先就用sort(nums.begin(),nums,end())进行排序；然后剪枝，如果nums[i]一开始就大于0那不可能存在三元组，直接return；如果nums[i]==nums[i-1]说明之前已经有过相同的元素了，这次就跳过；后面才开始真正地找三元素；总结就是i作为循环因子，然后slow和fast作为双指针，在nums[i]元素的的后面进行寻找；

11.24已完成

42. 接雨水 - 力扣（LeetCode）

个人认为最快的方法就是，前后缀；

通过前缀找到每个坐标点左侧的最大高度，通过后缀找到右侧最大高度，两者取最小值再减去桶的高度，就能得到这个坐标点水的高度，又因为横坐标都是1，因此该点的面积就是高度值；

为什么能用前后缀，就比如图中画粉色的这个面积，左边木板的高度取决于左边的最大高度，右边木板的高度取决于右边的最大高度，否则水就会流出去，因此才有了前缀后缀；

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        vector<int> pre_max(n);
        pre_max[0] = height[0];
        for(int i =1;i<n;i++){
            pre_max[i] = std::max(pre_max[i-1],height[i]);
        }
        vector<int> suf_max(n);
        suf_max[n-1] = height[n-1];
        for(int i=n-2;i>=0;i--){
            suf_max[i] = std::max(suf_max[i+1],height[i]);
        }

        int ans = 0;
        for(int i=0;i<n;i++){
            ans += min(pre_max[i],suf_max[i]) - height[i];
        }
        return ans;
    }
};

class Solution {
public:
    int trap(vector<int>& height) {
        int left=0, right = height.size()-1;
        int n = height.size();
        int pre_max=0, suf_max=0;
        int ans = 0;
        while(left<right){
                pre_max = max(pre_max,height[left]);
                suf_max = max(suf_max,height[right]);
                if(pre_max<suf_max) 
                {
                    ans+= pre_max - height[left];
                    left+=1;
                }
                else
                {
                    ans += suf_max -height[right];
                    right -=1;
                }
            }
        return ans;
    }
};

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

不定长的滑动窗口，主要是先把p的字符都映射进int cnt[26]{}，用char c = p[i]-'a';

然后就是滑动窗口，right一直遍历，然后减去cnt对应位置的数，如果出现0，意味着当前遍历的s字符串中的字符可能不存在于p中或者已经重复出现导致减到小于0；

这个时候就需要重新加回来并且left++，知道这个元素对应的cnt位恢复大于等于0；

这样当fast-left+1长度等于p的长度时，就表明得到了一个异位词；

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int cnt[26]{};
        int slow = 0;
        for(char c:p) cnt[c-'a']++;
        vector<int> ans;
        for(int fast=0;fast<s.size();fast++){
            char c = s[fast];
            cnt[c-'a']--;
            while(cnt[c-'a']<0){
                cnt[s[slow]-'a']++;
                slow++;
            }
            if(p.length()==(fast-slow+1)) ans.push_back(slow);
        }
        return ans;
    }
};

3. 无重复字符的最长子串 - 力扣（LeetCode）

主要是对unordered_set<int>这个容器的使用；

unordered_set<char> window;

然后就是window.count(c)判断c在不在window

window.erase(c)删除指定元素

window.insert(c)插入指定元素；

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        unordered_set<char> window;
        int left =0;
        for(int right=0;right<s.size();right++)
        {
            char c = s[right];
            while(window.count(c)){
                window.erase(s[left++]);
            }
            window.insert(c);
            ans = max(ans, right-left+1);
        }
        return ans;
    }
};

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

这道题计算的点在于，子区间的数组个数，用的是r-l+1；

l r,既然l-r连乘小于目标值k，那l+1 -r ,l+2 - r。。。。r -r都满足，因此个数位l-r+1；

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if (k <= 1) return 0;
        int ans = 0;
        int pro = 1;
        int slow = 0;
        vector<vector<int>> arr;
        vector<int> arr1;
        for(int fast=0;fast<nums.size();fast++){
            pro*=nums[fast];
            while(pro>=k){
                pro = pro / nums[slow];
                slow++;
            }
            ans += fast-slow+1;
        }
        return ans;
    }
};

滑动窗口，双指针完成

203. 移除链表元素 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummynode = new ListNode(0);
        dummynode->next = head;
        auto current = dummynode; 
        while(current->next)
        {
            auto nxt = current->next;
            if(nxt->val == val)
            {current->next = current->next->next;
            delete nxt;}
            else{
                current = nxt;
            }
        }
        return dummynode->next;
    }
};

707. 设计链表 - 力扣（LeetCode）

class MyLinkedList {
public:
    // 定义链表节点结构体
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val), next(nullptr){}
    };
    MyLinkedList() {
        _dummyHead = new LinkedNode(0);
        _size = 0;
    }
    
    int get(int index) {
        if(index>(_size-1)||index < 0){
            return -1;
        }
        LinkedNode* cur = _dummyHead->next;
        while(index--){
            cur = cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* new_head = new LinkedNode(val);
        new_head->next = _dummyHead->next;
        _dummyHead->next = new_head;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(cur->next!=nullptr){
            cur = cur->next;
        }
        cur->next = newNode;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        if(index<0) index = 0;
        if(index>_size) return;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        _size++;
    }
    
    void deleteAtIndex(int index) {
        if(index >=_size || index <0){
            return;
        }
        LinkedNode* cur = _dummyHead;
        while(index--){
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        tmp=nullptr;
        _size--;}

// 打印链表
    void printLinkedList() {
        LinkedNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
private:
    int _size;
    LinkedNode* _dummyHead;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206. 反转链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            auto temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

92. 反转链表 II - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* dummy = new ListNode(0,head);
        auto p0 = dummy;
        for (int i = 0; i < left - 1; i++) {
            p0 = p0->next;
        }

        ListNode* pre = nullptr;
        ListNode* cur = p0->next;
        int n = right-left+1;
        for (int i = 0; i < right - left + 1; i++) {
            auto temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }

        p0->next->next = cur;
        p0->next = pre;
        
        return dummy->next; 
    }
};

24. 两两交换链表中的节点 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0,head);
        auto cur = dummy;
        while(cur->next!=nullptr && cur->next->next !=nullptr)
        {
            auto temp1 = cur->next;
            auto temp2 = cur->next->next->next;

            cur->next = cur->next->next;
            cur->next->next = temp1;
            cur->next->next->next = temp2;

            cur = cur->next->next;
        }
        ListNode* result = dummy;
        return dummy->next;
    }

};

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0,head);
        ListNode* slow = dummyHead;
        ListNode* fast = dummyHead;
        while(n-- && fast->next!=nullptr){
            fast = fast->next;
        }
        fast = fast->next;
        while(fast!=nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dummyHead->next;
    }
};

面试题 02.07. 链表相交 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        auto curA = headA;
        auto curB = headB;
        int lenA =0;
        int lenB =0;
        while(curA!=NULL){
            curA=curA->next;
            lenA+=1;
        }
        while(curB!=NULL){
            curB=curB->next;
            lenB+=1;
        }

        curA = headA;
        curB = headB;
        
        if(lenB>lenA){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        int gap = lenA - lenB;

        
        while(gap--){
            curA = curA->next;
        }
        while(curA!=NULL){
            if(curA==curB){
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

142. 环形链表 II - 力扣（LeetCode）

环也很简单，就是双指针，然后需要一些数学上的处理

先去判断会不会相遇，用快慢指针，快指针的速度是满指针的两倍；

有了相遇点之后，根据公式计算得到x = (n - 1) (y + z) + z，也就表明从相遇点开始和起点开始两者相遇点就是环的入口；

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast !=NULL && fast->next!=NULL)
        {
            slow = slow->next;
            fast = fast->next->next;
        
            if(slow == fast)
            {
                slow = head;
                
                while(fast!=slow){
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;
    }
}; // <-- Missing closing brace added here

234. 回文链表 - 力扣（LeetCode）

三部曲：算中间节点，反转链表，判断是否回文；

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head){
        ListNode* cur = head;
        ListNode* pre = nullptr;
        while(cur){
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
    ListNode* midNode(ListNode* head){
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast&&fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    bool isPalindrome(ListNode* head) {
        
        ListNode* mid = midNode(head);
        ListNode* head2 = reverseList(mid);
        while(head2)
        {
            if(head->val != head2->val)
            {
                return false;
            }
            else
            {
                head = head->next;
                head2 = head2->next;
            }
            
        }
        return true;
    }
};

21. 合并两个有序链表 - 力扣（LeetCode）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* cur1 = list1;
        ListNode* cur2 = list2;
        ListNode* dummy3 = new ListNode(0);
        ListNode* cur3 = dummy3;
        while(cur1 && cur2){
            if(cur1->val < cur2->val){
                cur3->next = cur1;
                cur1 = cur1->next;
            }
            else{
                cur3->next = cur2;
                cur2 = cur2->next;
            }
            cur3 = cur3->next;
        }
        if(cur1) {
            cur3->next = cur1;
        }
        if(cur2) {
            cur3->next = cur2;
        }
        return dummy3->next;
    }
};

2. 两数相加 - 力扣（LeetCode）

直接写的，太冗长；

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur3 = dummy;
        ListNode* curA = l1;
        ListNode* curB = l2;
        int lenA = 0, lenB = 0;
        while(curA){
            curA = curA->next;
            lenA++;
        }
        while(curB){
            curB = curB->next;
            lenb++;
        }
        
        curB = head;
        curA = head;
        if(lenA<lenB){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        int gap = lenA - lenB;
        int count = 0;
        int count1 = 0;
        while(curB){
            if(count==1) count1 = 1;
            else count1 = 0;            
            if(curA->val+curB->val+count1 > 9){
                int temp = (curA->val+curB->val) - 10;
                cur3->next = new ListNode(temp);
                curA = curA->next;
                curB = curB->next;
                count = 1;
            }
            else
            {
                cur3->next = new ListNode((curA->val+curB->val+count1));
                curA = curA->next;
                curB = curB->next;
                count = 0;
            }
            cur3 = cur3->next;
        }
        while(curA){

            cur3->next = curA;
            if(count=1) cur3->next->val+=1;
            if(cur3->next->val>9){
                int temp = (curA->val) - 10;
                cur3->next = new ListNode(temp);
                curA = curA->next;
                curB = curB->next;
                count = 1;
            }
            curA = curA->next;
        }



    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur3 = dummy;
        int carry = 0;
        while(l1 || l2 || carry){
            if(l1){
                carry += l1->val;
                l1 = l1->next;
            }
            if(l2){
                carry+=l2->val;
                l2 = l2->next;
            }
            cur = cur->next = new ListNode(carry%10);
            carry /= 10;
        }
        return dummy->next;
    }
};

简化，直接用carry作进位；秒不可言；

25. K 个一组翻转链表 - 力扣（LeetCode）

思路没错，先把链表长度算出来，然后根据外层循环每k次计算一下，里面就是把这k次的链表反转，之后p0还是要等于下一次链表区间的上一个节点ListNode* temp = p0->next;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        int n = 0;
        for(ListNode* cur=head;cur;cur =cur->next){
            n++;
        }
        ListNode* dummy = new ListNode(0,head);
        auto p0 = dummy;
        ListNode* pre = nullptr;
        ListNode* cur = head;

        for(;n>=k;n-=k){
            for(int i=0;i<k;i++){
                ListNode* temp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = temp;
            }
            ListNode* temp = p0->next;
            p0->next->next = cur;
            p0->next = pre;
            p0 = temp;
        }
        return dummy->next;
    }
};

138. 随机链表的复制 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr){
            return nullptr;
        }
        for(Node* cur=head;cur;cur=cur->next->next){
            cur->next = new Node(cur->val,cur->next,nullptr);
        }
        for(Node* cur=head;cur;cur=cur->next->next){
            if(cur->random){
                cur->next->random = cur->random->next;
            }
        }
        Node* new_head = head->next;
        Node* cur = head;
        for(;cur->next->next;cur=cur->next){
            Node* copy = cur->next;
            cur->next = cur->next->next;
            copy->next = copy->next->next;
        }
        cur->next = nullptr;
        return new_head;
    }
};

560. 和为 K 的子数组 - 力扣（LeetCode）

通过map去找，因为是找连续的子数组，

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n+1);
        for(int i=0;i<n;i++){
            s[i+1] = s[i] + nums[i];
        }

        int ans = 0;
        unordered_map<int,int> cnt;
        for(int sj:s){
            ans += cnt.contains(sj-k)? cnt[sj-k] : 0;
            cnt[sj]++;
        }
        return ans;

    }
};

242. 有效的字母异位词 - 力扣（LeetCode）

class Solution {
public:
    bool isAnagram(string s, string t) {
        int cnt[26];
        for(char c: s){
            cnt[c-'a']++;
        }
        for(char c:t){
            cnt[c-'a']--;
        }
        for(int i=0;i<size(cnt);i++){
            if(cnt[i]!=0) return false;
        }
        return true;
    }
};

349. 两个数组的交集 - 力扣（LeetCode）

使用哈希表，unordered_set，不包含重复的元素

unordered_set<int> result;

unordered_set<int> num(nums1.begin(),nums1.end());

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> nums(nums1.begin(),nums1.end());
        for(int num: nums2){
            if(nums.find(num)!=nums.end()){
                result.insert(num);
            }

        }
        return vector<int>(result.begin(),result.end());
    }
};

202. 快乐数 - 力扣（LeetCode）

主要是有一个死循环的可能，所以采用了unordered_set,将每次得到的sum加入到set中，如果判断不等于cnt.end()说明以前已经出现过，进入了死循环，因此return false;

class Solution {
public:
    int getsum(int n){
        int sum=0;
        while(n){
            sum += (n%10)*(n%10);
            n /= 10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> cnt;
        while(1){
            auto sum = getsum(n);
            if(sum==1) return true;
            if(cnt.find(sum)!=cnt.end()) return false;
            else cnt.insert(sum);
            n = sum;
        }
    }
};

1. 两数之和 - 力扣（LeetCode）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> idx;
        for(int j=0;;j++){
            if(idx.find(target-nums[j])!=idx.end()){
                return {idx.find(target-nums[j])->second, j};
            }
            idx[nums[j]] = j;
        }
    }
};

383. 赎金信 - 力扣（LeetCode）

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<int,int> map1;
        for(int i=0;i<magazine.size();i++){
            map1[magazine[i]]++;
        }
        for(char c: ransomNote){
            map1[c]--;
        }
        // 遍历map1，检查是否有字符的频次小于0
        for (auto pair : map1) {
            if (pair.second < 0) {
                return false;  // 如果某个字符的频次小于0，说明无法构成ransomNote
            }
        }
        
        // 如果所有字符的频次都不小于0，说明可以构造ransomNote
        return true;

    }
};

18. 四数之和 - 力扣（LeetCode）

三数之和再套一层，注意剪枝和去重；

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
            	break; // 这里使用break，统一通过最后的return返回
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.size(); i++) {
                // 2级剪枝处理
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }

                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.size() - 1;
                while (right > left) {
                    // nums[k] + nums[i] + nums[left] + nums[right] > target 会溢出
                    if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
                        right--;
                    // nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出
                    } else if ((long) nums[k] + nums[i] + nums[left] + nums[right]  < target) {
                        left++;
                    } else {
                        result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        right--;
                        left++;
                    }
                }

            }
        }
        return result;
    }
};

49. 字母异位词分组 - 力扣（LeetCode）

思路，通过unordered_map<string, vector<string>> map1;

然后对strs里面的元素进行遍历，并排序；

map1[sorted_s].push_back(s);

之后再对map1进行遍历

ans.push_back(value)；

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map1;
        for(auto& s: strs){
            string sorted_s = s;
            ranges::sort(sorted_s);
            map1[sorted_s].push_back(s);
        }
        vector<vector<string>> ans;
        ans.reserve(map1.size());
        for(auto& [_,value]:map1){
            ans.push_back(value);
        }
        return ans;

    }
};

128. 最长连续序列 - 力扣（LeetCode）

很巧妙，先用unordered_map将每个元素都输入，然后再次遍历，第一步就是去重，确保每次的元素都是序列的最开始，所以才有了if(m[t-1]) continue;

然后通过while(m[++t]) len++不断去找到下一个是否存在，最后记录长度；

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int> m;
        for(auto n : nums){
            m[n]++;
        }
        int ans = 0;
        for(auto t:nums){
            if(m[t-1]) continue;
            int len =1;
            while(m[++t]) len++;
            ans = max(ans,len);
        }
        return ans;
    }

};

344. 反转字符串 - 力扣（LeetCode）

class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i=0,j=s.size()-1;i<s.size()/2;i++,j--){
            swap(s[i],s[j]);
        }
    }
};

541. 反转字符串 II - 力扣（LeetCode）

i+=2*k;

min(i+k,n) 最后不满足k则翻转剩余全部子串；

class Solution {
public:
    string reverseStr(string s, int k) {
        int n = s.size();
        for(int i=0;i<n;i+=2*k){
            reverse(s.begin()+i,s.begin()+min(i+k,n));
        }
        return s;
    }
};

54. 替换数字（第八期模拟笔试）

思路：先算数字个数，再resize(),然后两个指针，一个指向旧元素一个指向新元素地址；

#include<iostream>
#include<string>

using namespace std;

int main(){
    string s;
    cin >> s;
    int count = 0;
    int n = s.size();
    for(int i=0;i<s.size();i++){
        if(s[i]>='0' && s[i]<='9'){
            count++;
        }
    }
    int sOldIndex = s.size() - 1;
    s.resize(n + 5*count);
    int sNewIndex = s.size() - 1;
    while(sOldIndex>=0){
        if(s[sOldIndex]>='0' && s[sOldIndex]<='9'){
            s[sNewIndex--] = 'r';
            s[sNewIndex--] = 'e';
            s[sNewIndex--] = 'b';
            s[sNewIndex--] = 'm';
            s[sNewIndex--] = 'u';
            s[sNewIndex--] = 'n';
        }
        else
        {s[sNewIndex--] = s[sOldIndex];
            
        }
        sOldIndex--;
    }
    cout << s << endl;
}

151. 反转字符串中的单词 - 力扣（LeetCode）

翻转+取空格+大转加小转

class Solution {
public:
    void reverse(string& s,int start, int end){
        for(int i=start,j=end;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    void removespace(string& s){
        int slow=0;
        for(int i=0;i<s.size();i++){
            if(s[i]!=' '){
                if(slow!=0) s[slow++] = ' ';
                while(s[i]!=' ' && i<s.size()){
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);
    }
    string reverseWords(string s) {
        removespace(s);
        reverse(s,0,s.size()-1);
        int start = 0;
        for(int i=0;i<=s.size();i++){
            if(s[i]==' '|| i==s.size()){
                reverse(s,start,i-1);
                start = i+1;
            }
        }
        return s;
    }
};

KMP

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

关键就是把公共相等前后缀表计算出来。有了这个表碰到不匹配的时候就不需要重头开始查找，而是跳转到后缀表前一个位上去

class Solution {
public:
    void getNext(int* next, const string& s){
        int j=0;
        next[0]=0;
        for(int i=1;i<s.size();i++){
            while(j>0 && s[i]!=s[j]){
                j=next[j-1];
            }
            if(s[i]==s[j]) j++;
            next[i]=j;
        }

    }
    int strStr(string haystack, string needle) {
        if(needle.size()==0){
            return 0;
        }
        vector<int> next(needle.size());
        getNext(&next[0],needle);
        int j =0;
        for(int i=0;i<haystack.size();i++){
            while(j>0 && haystack[i]!=needle[j]){
                j = next[j-1];
            }
            if(haystack[i]==needle[j]){
                j++;
            }
            if(j==needle.size()){
                return (i-needle.size()+1);
            }
        }
        return -1;
    }
};

459. 重复的子字符串 - 力扣（LeetCode）

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // r
        return false;
    }
};

76. 最小覆盖子串 - 力扣（LeetCode）

先写一个判断是否覆盖的函数，之后就利用快慢指针来找最小的；

class Solution {
public:
    bool is_covered(int cnt_s[], int cnt_t[]){
        for(int i = 'A';i<='Z';i++){
            if(cnt_s[i]<cnt_t[i]){
                return false;
            }
        }
        for(int i = 'a';i<='z';i++){
            if(cnt_s[i]<cnt_t[i]){
                return false;
            }
        }
        return true;
    }
    string minWindow(string s, string t) {
        int m = s.size();
        int ans_left = -1, ans_right = m;
        int cnt_s[128]{};
        int cnt_t[128]{};
        for(char c: t){
            cnt_t[c]++;
        }

        int left = 0;
        for(int right=0;right<m;right++){
            cnt_s[s[right]]++;
            while(is_covered(cnt_s,cnt_t)){
                if(right-left < ans_right - ans_left){
                    ans_left = left;
                    ans_right = right;
                }
                cnt_s[s[left]]--;
                left++;
            }
        }
        return ans_left < 0? "":s.substr(ans_left,ans_right-ans_left+1);
    }
};

232. 用栈实现队列 - 力扣（LeetCode）

栈实现队列，比较简单，就是两个栈，出栈和入栈 stack; 进的时候push就行了，出的时候要判断stou这个栈是不是为空，如果是，就从stin里面把数据放到stou里面；

class MyQueue {
public:
    stack<int> stIn;
    stack<int> stOu;
    MyQueue() {
    
    }
    
    void push(int x) {
        stIn.push(x);
    }
    
    int pop() {
        if(stOu.empty()){
            while(!stIn.empty()){
                stOu.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOu.top();
        stOu.pop();
        return result;
    }
    
    int peek() {
        if(stOu.empty()){
            while(!stIn.empty()){
                stOu.push(stIn.top());
                stIn.pop();
            }
        }
        int result = stOu.top();
        return result;
    }
    
    bool empty() {
        return stIn.empty() && stOu.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */