Leetcode hot 100

双指针

283.移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cnt = 0;
        for(vector<int>::iterator it = nums.begin(); it != nums.end(); ){
            if(*it == 0) it = nums.erase(it),cnt++;
            else it++;
        }
        while(cnt--){
            nums.push_back(0);
        }
    }
};

11.盛水最多的容器

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

53. 最大子数组和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return  maxx(nums, 0, nums.size() - 1);
    }
    int maxx(vector<int>& nums, int l, int r) {
        if (l > r) return 0;
        if (l == r) {
            return nums[l];
        }
        int mid = (l + r) / 2;
        int ret = maxx(nums, l, mid);
        if(mid + 1 <= r)ret = max(ret, maxx(nums, mid + 1, r));
        int i = mid-1, j = mid+1;
        int tmp = nums[mid], maxone = tmp;
        while ( i >= l ) {
            tmp += nums[i];
            if (tmp >= maxone)
                maxone = max(maxone, tmp);
            i--;
        }
        tmp = maxone;
        while ( j <= r ) {
            tmp += nums[j];
            if ( tmp >= maxone)
                 maxone = max(maxone, tmp);
            j++;
        }
        return max(ret, maxone);
    }
 
};

56. 合并区间

class Solution {
public:
    static bool cmp(vector<int> a, vector<int> b){
        if(a[0] !=  b[0]) return a[0] < b[0];
        if(a[1] !=  b[1]) return a[1] < b[1];
        return false; 
    }
    vector<vector<int>> merge(vector< vector > intervals) {
        vector<vector<int>> ret ;
        // vector<int> tmp; 
        sort(intervals.begin(), intervals.end(), cmp);
        int l = intervals[0][0], r = intervals[0][1];
        for(int i = 1; i< intervals.size(); i++){
            // cout<<intervals[i][0]<<' '<<intervals[i][1]<<endl;
            if(intervals[i][0] <= r) r = max(intervals[i][1], r);
            else {
                ret.push_back({l, r});
                l = intervals[i][0];
                r = intervals[i][1];
            }
        }
        ret.push_back({l, r});
        return ret;
    }
    
};

160. 相交链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* p = headA, *q = NULL;
        int len1 = 0,len2 = 0;
        while(p){
            len1++;
            p = p->next;
        }
        p = headB;
        while(p){
            len2 ++;
            p = p->next;
        }
        p = headA;
        q = headB;
        if(len1 > len2) {
            int n = len1 - len2;
            while(n--) p = p->next;
        }
        else{
            int n = len2 - len1;
            while(n--) q = q->next;
        }
        while(p != q){
            p = p->next;
            q = q->next;
        }
        return p;
    }
};

141. 环形链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        set<ListNode *> st;
        ListNode *p = head;
        while(p != NULL){
            if(st.find(p) == st.end()) st.insert(p);
            else return true;
            p = p->next;
        }
        return false;
    }
};

142. 环形链表 II

/**
 * 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) {
        map<ListNode *, int> mp;
        ListNode * ret = head;
        int idx = 0;
        while(ret != NULL){
            cout<<ret<<' ';
            if(mp.find(ret) != mp.end())
                return ret;
            else 
               mp[ret] = idx++ ;
            ret = ret->next;
        }
        return NULL;
    }
};

2. 两数相加

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* p, *q, *tmp, *tmp2;
        p = l1;
        q = l2;
        int c = 0;
        tmp2 = p;
        while(p != NULL && q!=NULL){
            tmp = p;
            p->val = p->val + q->val + c;
            c = p->val / 10;
            p->val %= 10;
            p = p->next;
            q = q->next;
        }
        while(p != NULL){
            tmp = p;
            p->val += c;
            c = p->val / 10;
            p->val %= 10;
            p = p->next;
        }
        if(q!=NULL){
            tmp->next = q;
        }
        while(q != NULL){
            tmp = q;
            q->val += c;
            c = q->val / 10;
            q->val %= 10;
            q = q->next;
        }
        if(c) {
            ListNode * x = new ListNode(c, NULL);
            tmp->next = x;
        }
        tmp = reverse(tmp2);
        tmp2 = reverse(tmp);
        return tmp2;
 
    }
     ListNode* reverse(ListNode* l1){
         ListNode* p, *q, *tmp;
         p = l1 ->next;
         q = l1;
         q->next = NULL;
         while(p != NULL){
             tmp = p->next;
             p->next = q;
             q = p;
             p = tmp;
         } 
         return q;
     }
};