4. Median of Two Sorted Arrays

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m > n) return findMedianSortedArrays(nums2, nums1);
        nums1.insert(nums1.begin(), INT_MIN);
        nums2.insert(nums2.begin(), INT_MIN);
        nums1.push_back(INT_MAX);
        nums2.push_back(INT_MAX);
        m = nums1.size();
        n = nums2.size();
        int il = 0, ih = m-1;
        int i, j;
        while(il<=ih) {
            i = (il + ih)/2;           
            j = (m+n+1)/2 - i;           
            if(nums1[i-1]>nums2[j]) {
                ih = i-1;
            }
            else if(nums2[j-1]>nums1[i]) {
                il = i+1;
            }
            else break;
        }
        if((m+n)%2==0) return (max(nums1[i-1],nums2[j-1]) + min(nums1[i],nums2[j]))/2.;
        return max(nums1[i-1], nums2[j-1]);
    }

443. String Compression

int compress(vector<char>& chars) {
        if(chars.size() == 0) return 0;
        chars.push_back(1);
        char c_prev = 1;
        int cnt = 0, k = 0;
        for(int j=0; j<chars.size(); j++) {
            if(chars[j] == c_prev) cnt++;
            else {
                if(cnt != 0) {
                    chars[k++] = c_prev;
                    if(cnt != 1) {
                        string s = to_string(cnt);
                        for(char cs: s) {
                            chars[k++] = cs;
                        }
                    }
                }
                c_prev = chars[j];
                cnt = 1;
            }
        }
        chars.pop_back();
        return k;
    }

539. Minimum Time Difference

https://leetcode.com/problems/minimum-time-difference/description/
    int findMinDifference(vector<string>& timePoints) {
        sort(timePoints.begin(), timePoints.end());
        int h0 = stoi(timePoints.back().substr(0,2));
        int m0 = stoi(timePoints.back().substr(3));
        int h1, m1, dif, res = 12*60;
        for(auto &s : timePoints) {
            h1 = stoi(s.substr(0,2));
            m1 = stoi(s.substr(3));
            dif = abs(h1*60+m1 - (h0*60+m0));  
            if(dif>12*60) dif = 24*60 - dif;
            if(dif<res) res = dif;
            h0 = h1;
            m0 = m1;
        }
        return res;
    }

696. Count Binary Substrings

    int countBinarySubstrings(string s) {
        if(s.size()<2) return 0;
        s += "*";
        int x = 0, y = 0, res = 0;
        char cx = 0, cy = 0, pre = 0;
        for(char &c : s) {
            if(c!='0' && c!='1') {
                res+=min(x,y);
                x=0, y=0;
                pre = 0;
                continue;
            }
            if(c!=pre) {
                res+=min(x,y);
                x=y, y=1;
                pre = c;
            }
            else{
                y++;
            }
        }
        return res;
    }

413. Arithmetic Slices

https://leetcode.com/problems/arithmetic-slices/description/
    int numberOfArithmeticSlices(vector<int>& A) {
        if(A.size()<3) return 0;
        int N = A.size();
        A.push_back(A.back() + A[N-1] - A[N-2] -1);
        int k=2, d=A[1]-A[0];
        int res = 0;
        for(int i=2; i<A.size(); i++) {
            if(d == A[i] - A[i-1]) k++;
            else {
                if(k>=3) res += (k-1)*(k-2)/2;
                k=2;
                d = A[i] - A[i-1];
            }
        }
        return res;
    }

665. Non-decreasing Array

https://leetcode.com/problems/non-decreasing-array/description/
    bool checkPossibility(vector<int>& nums) {
        nums.insert(nums.begin(), INT_MIN);
        nums.push_back(INT_MAX);
        int dec = 0, idx = -1;
        for(int i=1; i<nums.size(); i++) {
            if(nums[i-1]>nums[i]) {
                dec++;
                if(dec == 1) idx = i;
            }
            if(dec>1) return false;
        }
        if(dec == 1)
                return (idx>1 && nums[idx]>=nums[idx-2])
                    || (idx+1<nums.size() && nums[idx+1]>=nums[idx-1]);
        return true;
    }

581. Shortest Unsorted Continuous Subarray

https://leetcode.com/problems/shortest-unsorted-continuous-subarray/description/
    int findUnsortedSubarray(vector<int>& nums) {
        nums.insert(nums.begin(), INT_MIN);
        nums.push_back(INT_MAX);
        int l = 0, h = nums.size() - 1;
        for(int i=1; i<nums.size()-1; i++ ) {
            if(nums[i]<nums[l]) {
                while(nums[i]<nums[l]) l--;
            }
            else if(l == i-1) l++;
        }
        for(int i=nums.size()-2; i>=0; i-- ) {
            if(nums[i]>nums[h]) {
                while(nums[i]>nums[h]) h++;
            }
            else if(h == i+1) h--;
        }
        return max(h-l-1, 0);
    }

21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/description/
Solution 0. Use a dummy node as the head. (9 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(INT_MIN);
        ListNode* tail = &head;
        while(l1 && l2) {
            if(l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            }
            else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        tail->next = l1? l1:l2;
        return head.next;
    }
Solution 1.0 Recursion. Slow but simple. (19 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val > l2->val) return mergeTwoLists(l2, l1);
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    }
Solution 1.1  (12 ms)
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val > l2->val) return mergeTwoLists(l2, l1);
        ListNode* head = l1;
        ListNode* p;
        while(true) {
            while(l1->next && l1->next->val <= l2->val) l1 = l1->next;
            p = l1;
            l1 = l1->next;
            p->next = l2;
            if(!l1) return head;
            while(l2->next && l2->next->val <= l1->val) l2 = l2->next;
            p = l2;
            l2 = l2->next;
            p->next = l1;
            if(!l2) return head;
        }
    }