# 80 - 删除排序数组中的重复元素

一个记录当前判断元素的下标，一个记录当前待插入元素的下标

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i=0,virtualI=0,rgCnt=0,dicti=0;
        for(i=0;i<nums.size();++i){
            if(i==0){
                virtualI=0;
                rgCnt=1;
                dicti=1;
            }else if(i>0){
                if(nums[i]==nums[virtualI]){
                    if(rgCnt==2)continue;
                    virtualI=i;
                    rgCnt++;
                    nums[dicti++] = nums[i]; 
                }else{
                    rgCnt=1;
                    nums[dicti++]=nums[i];
                    virtualI=i;
                }
            }
        }
        for(i=nums.size();i>dicti;--i){
            nums.pop_back();
        }
        return dicti;
    }
};

# 81

class Solution {
    public:
    //C++最简洁的二分法分类讨论
    //每次二分，左半部分和右半部分至少有一边是有序的，以此为条件可以分成两种情况：
    //1、左半边是有序的
    //(1) target落在左半边
    //(2) otherwise
    //2、右半边是有序的
    //(1) target落在右半边
    //(2) otherwise
    //综上所述，一共两种可能性，这两种情况各自又有两种可能性，代码如下：
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l<=r){
            //处理重复数字
            while(l<r&&nums[l]==nums[l+1]) ++l;
            while(l<r&&nums[r]==nums[r-1]) --r;
            int mid = l+(r-l)/2;
            if(nums[mid]==target) return true;
            //左半部分有序
            if(nums[mid]>=nums[l]){
                if(target<nums[mid]&&target>=nums[l]) r = mid-1;//target落在左半边
                else l = mid+1;
            }
            else{//右半部分有序
                if(target>nums[mid]&&target<=nums[r]) l = mid+1;//target落在右半边
                else r = mid-1;
            }
        }
        return false;
    }
};

# 82 删除链表中重复元素②

人傻了，线性思维傻了

想 O (N) 解决，双重判重，不断更新吧

/**
 * 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* deleteDuplicates(ListNode* head) {
        if(head==NULL  head->next==NULL) return head;
        ListNode* next=head->next,*ph=head,*cur,*start;
        cur=new ListNode();
        start=cur;
        while(next){
            while(next && next->val==ph->val){
                while(next && next->val==ph->val){
                    next=next->next;
                    if(!next  next->val!=ph->val)break;
                }
                ph = next;
                if(next)next=next->next;
                if(next==NULL  next->val!=ph->val) break;
            }
            cur->next = ph;
            cur=cur->next;
            ph=next;
            if(next!=NULL)next=next->next;
        }
        if(start->next!=NULL)
            return start->next;
        else return NULL;
    }
};

# 86 分割链表

我的方法报莫名其妙的错误。我的方法：设定一个头部空节点。一旦遇到一个比 x 小的，直接插入到小的链表中，遇到大的，直接过去，不管它，全部在原链表上操作通过的办法，将链表的记录分割成两个，因为他注定按照 x 分割到两边，所以完全可以用两个链表拉进行插入，最后直接合并

/**
 * 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* partition(ListNode* head, int x) {

        struct ListNode headLess,headGreater;
        struct ListNode *curLess,*curGreater;

        headLess.next = headGreater.next = NULL;
        curLess = &headLess; curGreater = &headGreater;

        while(head){
            if(head -> val < x){
                curLess->next = head;
                curLess = curLess->next;
            }else{
                curGreater->next=head;
                curGreater=curGreater->next;
            }
            head=head->next;
        }
        curGreater->next = NULL;
        curLess->next = headGreater.next;
        return headLess.next;

        /*
        ListNode cur;
        cur.next=head;
        ListNode* cur1 = head,*cur2=&cur,*cur3=&cur,*pre=&cur;
        while(cur1->next){
            if(cur1->val >= x){
                cur1=cur1->next;
            }else{
                cur3 = cur1;
                cur1=cur1->next;
                pre->next = cur3->next;
                cur3->next = cur2->next;
                cur2->next=cur3;
                cur2=cur2->next;
            }
            pre = cur1;
        }
        return cur.next;
        */
    }
};

# 89 格雷编码

背公式提 (√)
$G\_{i}=i \\oplus (i/2)$

class Solution {
public:
    vector<int> grayCode(int n) {
        //格雷编码的生成过程G(i)==i^(i/2)
        vector<int> ret(1<<n);
        for(int i=0;i<1<<n;i++)
            ret[i]=i^i>>1;
        return ret;
    }
};

# 102 层序遍历

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    void dfs(TreeNode* cur,int depth){
        if(cur==nullptr) return;
        if(ans.size()<depth){
            vector<int> vec;
            ans.push_back(vec);
        }
        ans[depth-1].push_back(cur->val);

        dfs(cur->left,depth+1);
        dfs(cur->right,depth+1);
    }

    vector<vector<int>> levelOrder(TreeNode* root) {
        dfs(root,1);
        return ans;
    }
};

# 103. 螺旋层序遍历

# reverse 函数

最简单的方法，调用 reverse 函数，但其实可以直接 bfs, 记录层，一个是 push_front, 一个是 push_back

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> ans;
    void dfs(TreeNode* cur,int depth){
        if(cur==nullptr) return;
        if(ans.size()<depth){
            vector<int> vec;
            ans.push_back(vec);
        }
        ans[depth-1].push_back(cur->val);

        dfs(cur->left,depth+1);
        dfs(cur->right,depth+1);
    }

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        dfs(root,1);
        for(int i=0;i<ans.size();++i){
            if(i&1){
                reverse(ans[i].begin(),ans[i].end());
            }
        }
        return ans;
    }

};

# 354. 俄罗斯套娃

LIS, 先按宽度排序，后根据高度 LIS

class Solution {
public:
    static bool cmp(const vector<int> &x,const vector<int> &y){
        return x[0]<y[0];
    }
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end(),cmp);
        vector<int> dp(envelopes.size(),1);
        if(envelopes.size()==0)return 0;

        for(int i=1;i<envelopes.size();++i){
            for(int j=0;j<i;++j){
                if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }

        int res=0;
        for(int i=0;i<envelopes.size();++i){
            res = max(res,dp[i]);
        }
        return res;
    }
};

# 90: 子集

思路：一开始想 DFS，但是忽略了一些情况，问题蛮大的

# 一般子集扩充思路

即使用一个 set 记录当前的每个子集，然后每次扩充在当前子集基础上扩充，扩充完毕以后再直接赋值给 set 这道题思路:
先记录每个数的频率
然后用一个 set 只记录当前的所有数字
保证不重复的方法就是按当前数字的数量扩充子集，这样就不需要判重了

class Solution {
public:

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        map<int,int> iL;
        set<int> nums2;
        vector<vector<int>> ans;
        vector<vector<int>> tmp;
        vector<int> empty;
        ans.push_back(empty);
        tmp=ans;
        for(int i=0;i<nums.size();++i){
            iL[nums[i]]++;
            nums2.insert(nums[i]);
        }

        for(auto it=nums2.begin();it!=nums2.end();it++){
            int num = *it;
            int cnt = iL[num];
            for(int k=0;k<tmp.size();++k){
                vector<int> now = tmp[k];
                for(int j=0;j<cnt;++j){
                    now.push_back(num);
                    ans.push_back(now);
                }
            }
            tmp=ans;
        }

        return ans;
    }
};

# 91: 解码方法

很久前好像见过类似的

dp [i][0] 代表当前位置单独解码时解码方案个数
dp [i][0] 代表当前位置配合前面的位置解码的方案个数

如果 1 成立: dp [i][0] = dp [i-1][0]+dp [i-1][1]
如果 2 成立: dp [i][1] = dp [i-1][0] 注意要特殊处理 s [i]'0’的情况

class Solution {
public:

    int numDecodings(string s) {
        if(s[0]=='0')return 0;
        int dp[s.length()+1][2];
        dp[0][0]=1;
        dp[0][1]=0;
        for(int i=1;i<s.length();++i){
            if(s[i]!='0'){
                dp[i][0]=dp[i-1][0]+dp[i-1][1];
                if((s[i-1]=='1'&&s[i]>='1'&&s[i]<='9')  (s[i-1]=='2'&&s[i]>='1'&&s[i]<='6')){
                    dp[i][1] = dp[i-1][0];
                }else dp[i][1] = 0;
            }else{
                dp[i][0]=0;
                if(s[i-1]=='1'  s[i-1]=='2'){
                    dp[i][1] = dp[i-1][0];
                }else return 0;
            }
        }
        return dp[s.length()-1][0]+dp[s.length()-1][1];
    }
};

# 92: 反转链表

设置 dummy 节点，头插法解决很简单

/**
 * 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) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        ListNode *next;
        for (int i = 0; i < right - left; i++) {
            next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummyNode->next;
    }
};

# 93: 复原 IP 地址

最暴力的方式：三层 for 循环

直接判断结果是否满足即可

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res=new LinkedList<>();
        int n1,n2,n3,n4;
        for (int i1=1;i1<=3;i1++){
            for (int i2=1;i2<=3;i2++){
                for (int i3=1;i3<=3;i3++){
                    if (i1+i2+i3<s.length()){
                        n1=Integer.parseInt(s.substring(0,i1));
                        n2=Integer.parseInt(s.substring(i1, i1+i2));
                        n3=Integer.parseInt(s.substring(i1+i2, i1+i2+i3));
                        if (s.length()-i1-i2-i3>3)
                            continue;
                        n4=Integer.parseInt(s.substring(i1+i2+i3));
                        if (n1<=255&&n1>=0 && n2<=255&&n2>=0 && n3<=255&&n3>=0 && n4<=255&&n4>=0){
                            String str=(n1+"."+n2+"."+n3+"."+n4);
                            if (str.length()==s.length()+3)
                                res.add(str);
                        }
                    }
                }
            }
        }
        return res;
    }
}

# 209 长度最小的子数组

先说思路

二分:
1. 先计算前缀和 2. 遍历 ans 3. 在 ans 前面找第一个满足条件的下标 4. 纪录最小的其中遇到的一个问题是: lower_bound 找到的是大于等于 target 的第一个目标
那么就会出现一个问题，当 ans [target] 大于 t 的时候，目标的 target 应该是前一个，否则就是当前的

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(nums.size()==0)return 0;
        if(nums[0]>=target) return 1;
        vector<int> ans;
        int _min = 0x3f3f3f3f;
        ans.push_back(nums[0]);
        for(int i=1;i<nums.size();++i){
            if(nums[i]>=target) return 1;
            ans.push_back(ans[i-1]+nums[i]);
            if(ans[i]>=target){
                int t = ans[i]-target;
                int upper = i;
                int lower = lower_bound(ans.begin(), ans.begin()+i-1,t)-ans.begin();
                if(ans[lower]>t){
                    _min = min(_min,i-lower+1);
                }else{
                    _min = min(_min,i-lower);
                }
            }
        }

        return _min==0x3f3f3f3f?0:_min;
    }
};

# 滑动窗口法

一个 s, 如果 s 大于等于 target 的话，就往里缩窗口，直到不满足为止

(目的是尽量只遍历满足条件的区间)

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(nums.size()==0)return 0;
        if(nums[0]>=target) return 1;
        int _min = 0x3f3f3f3f;
        int s = nums[0];
        int left= 0;
        for(int i=1;i<nums.size();++i){
            s+=nums[i];
            while(s>=target){
                _min = min(_min, i-left+1);
                s-=nums[left++];
            }
        }
        return _min==0x3f3f3f3f?0:_min;
    }
};

# 477. 汉明距离总和

题目说的是一个数组里任意两个数的汉明距离的总和。

汉明距离就是两个数字之间有多少不同位。暴力解法就是先异或，然后判断结果中 1 的个数 (不同为 1) 但是暴力二轮循环复杂度过大 10⁴2*30 看的是题解，优化方法是：直接针对每个位进行计算，统计每个位上 1 的个数结果就是 (c*(size-c)) 的和

class Solution {
public:

    int totalHammingDistance(vector<int>& nums) {
        long long ans = 0;
        for(int i=0;i<=30;++i){
            int p=0;
            for(int j=0;j<nums.size();++j){
                if((nums[j] & (1<<i))!=0){
                    p++;
                }
            }
            ans+=(p*(nums.size()-p));
        }
        return ans;
    }
};

# 1074

class Solution {
public:

    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int pre[matrix.size()+2][matrix[0].size()+2];
        int m = matrix.size(),n = matrix[0].size();
        for(int i=0;i<=m;++i) pre[i][0]=0;
        for(int j=0;j<=n;++j) pre[0][j]=0;
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                pre[i][j] = pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1] + matrix[i-1][j-1];
            }
        }

        int cnt=0;

        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                for(int t=1;t<=i;++t){
                    for(int k=1;k<=j;++k){
                        if((pre[i][j]-pre[t-1][j]-pre[i][k-1]+pre[t-1][k-1])==target){
                            cnt++;
                        }
                    }
                }
            }
        }
        return cnt;
    }
};

# 米哈游系列：只有 25 题…

# 53: 最大子序和

分三种情况，1. 和前面相加小于 0, 那等于自己就行了 2. 和前面相加大于 0, 但是本身就比这个数值大，等于自己就行 3. 和前面相加大于 0, 且大于自身，等于该值遍历取最大

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int dp[nums.size()+1];
        dp[0]=nums[0];
        for(int i=1;i<nums.size();++i){
            if(dp[i-1]+nums[i]<0)dp[i]=nums[i];
            else dp[i]=max(dp[i-1]+nums[i],nums[i]);
        }
        int mx = -0x3f3f3f3f;
        for(int i=0;i<nums.size();++i){
            mx = max(mx,dp[i]);
        }
        return mx;
    }
};

# 215 数组中的第 K 大元素

手撸快排

class Solution {
public:

    int part(vector<int>& nums,int start,int end){
        //以第一个为基准
        int X=nums[start];
        int i= start,j=end;
        bool isNormal=false;
        while(i<j){
            while(!isNormal && i<j){
                if(nums[j]>X){
                    nums[i]=nums[j];
                    isNormal=true;
                    break;
                }
                j--;
            }
            while(isNormal && i<j){
                if(nums[i]<X){
                    nums[j]=nums[i];
                    isNormal=false;
                    break;
                }
                i++;
            }
        }
        nums[i]=X;
        return i;
    }

    void ExcutePart(vector<int>& nums,int start,int end,int k){
        if(start>=end) return;
        int order = part(nums,start,end);
        if(order==k-1) return;
        ExcutePart(nums,start,order-1,k);
        ExcutePart(nums,order+1,end,k);
    }

    int findKthLargest(vector<int>& nums, int k) {
        ExcutePart(nums,0,nums.size()-1,k);
        return nums[k-1];
    }
};

# 1035 不相交的线

就是最长公共子序列

这里在重新学一下，老忘 dp [i][j] 代表 A [0_{i-1] 和 B [0}j-1] 的最长公共子序列长度
如果 A [i-1] B [j-1], 则 dp [i][j]=dp [i-1][j-1]+1;
否则 dp [i][j] = max (dp [i][j-1],dp [i-1][j]);

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        //最长公共子序列
        int m = A.size();
        int n= B.size();
        if(m<=0  n<=0){
            return 0;
        }
        int **d = new int*[m+1];
        for(int i=0;i<m+1;++i){
            d[i] = new int[n+1];
            memset(d[i],0,sizeof(int)*(n+1));
        }
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(A[i-1] == B[j-1]){
                    d[i][j] = d[i-1][j-1] +1;
                }else{
                    d[i][j] = max(d[i][j-1],d[i-1][j]);
                }
            }
        }
        return d[m][n];
    }
};

LeetCode