就是在旋转后的数组里用$O(logn)$的时间复杂度做，最坏时间复杂度其实是$O(n)$

class Solution {
public:
    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;
                else l = mid+1;
            }
            else {
                if(target>=nums[mid] && target<=nums[r]) l=mid+1;//这里的target大于还是大于等于似乎并不影响最终结果，仔细体会。
                else r= mid-1;
            }
        }
        return false;
    }
};

思路见代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() <= 2) return nums.size();
        int index = 2;
        for(int i = 2 ; i < nums.size();i++){
            if(nums[i] != nums[index-2])
                nums[index++] = nums[i];
        }
        return index;
    }
};

直接把最终结果放在了nums1中，从后往前遍历nums1也不用担心nums1被覆盖

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int last = m + n -1 ;
        while(n){
            if(m == 0 || nums1[m-1]<=nums2[n-1]){
                nums1[last--] = nums2[--n];
            }
            else{
                nums1[last--] = nums1[--m];
            }
        }
    }
};

思路

hash表存val值的个数t，如果 t能被 val+1 整除，sum加上t；如果不能被整除，加上(t/(val+1)+1)*(val+1)

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        map<int,int> mp;
        for(auto it : answers){
            mp[it] ++ ;
        }
        int sum = 0 ;
        for(auto it : mp){
            int val = it.first, t = it.second;
            sum+=((t-1)/(val+1)+1)*(val+1);
        }
        return sum;
    }
};

思路

dp[i][j] 表示 text1[i-1] 和text2[j-1] 的最长公共子序列，dp[0][0] = 0 ,初始化为0；如果text1[i-1] == text2[j-1],那么dp[i][j] = dp[i-1][j-1]+1 ; 如果不相等，那么dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

仔细体会

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int len1 = text1.length();
        int len2 = text2.length();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
        for(int i = 1 ; i< len1+1;i++){
            for(int j = 1;j<len2+1;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[len1][len2];
    }
};

方法一：按层遍历

class Solution {
public:
    int trap(vector<int>& height) {
        int Sum = accumulate(height.begin(),height.end(),0);
        int volume = 0;
        int layer = 1;
        int n = height.size();
        int left = 0 ;
        int right = n-1;        
        while(left <= right){
            while(left <= right && height[left] < layer) 
                left++;
            while(left <= right && height[right] < layer) 
                right--;
            volume += right-left+1;
            layer++;
        }
        return volume - Sum;
    }
};

方法二：正序遍历一次记录左边最大值，逆序遍历一次记录每个元素的右边最大值，每个位置的存水量就是min（left_max,right_max）- 该点的height；

要用到两个指针遍历，一个是cur遍历老链表，一个是p用来做结果链表不断往里添加。

/**
 * 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 || !head->next) return head;
        ListNode* dumpy = new ListNode(-1);
        ListNode* cur = head;
        dumpy->next = head;
        ListNode* p = dumpy;
        map<int,int> mp;
        while(cur){
            if(mp[cur->val] == 0){
                mp[cur->val] = 1;
                p->next = new ListNode(cur->val);//这里不能写成p->next = cur ;
                p = p->next;
            }
            cur = cur->next;
        }
        return dumpy->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* deleteDuplicates(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        map<int,int> visit;
        ListNode* cur = head;
        ListNode* dummy = new ListNode(-1);
        ListNode* res = dummy;
        while(cur){
            visit[cur->val]++;
            cur = cur->next;
        }
        cur = head;
        while(cur){
            if(visit[cur->val] == 1){
                res->next = new ListNode(cur->val);
                res = res->next;
            }
            cur =cur->next;
        }
        return dummy->next;
    }
};

思路：

1. two 记录 132 中的2
2. 单调栈维护当前比 2 大的 3，栈顶为3中的最小值
3. 从后往前遍历，如果当前值比栈顶值大，two更新为栈顶值（之前的two（2）存的是是比栈（3）里小的，更新相当于把two变大），顺便把栈里的小于更新完后的two 的 值全部出栈（栈里全是序列中当前two以后而且比two大的元素）
4. 如果当前值比栈顶值小，说明找到了1（two已被记录的情况下，这里如果只有三个元素123会怎么样，不会怎么样，这样的话two不会被更新，始终是INT_MIN，也就找不到比他小的1了。结果就是false）
5. 一句话总结，two越大，越好找比他小的1

class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if(n<3) return false;
        stack<int> s;
        int two = INT_MIN;
        for(int i = n-1 ; i >= 0 ; i--){
            if(nums[i]< two) return true;
            else{
                while(!s.empty() && nums[i] > s.top()){
                    two = s.top();
                    s.pop();
                }
                s.push(nums[i]);
            }
        }
        return false;
    }
};

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0 ;
        while(n){
            n&=n-1;
            cnt++;
        }
        return cnt;
    }
};

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int cnt = 0 ;
        while(n){
            cnt+= n %2;
            n>>=1;
        }
        return cnt;
    }
};