LeetCode81-90

81、搜索旋转排序数组 II

二分搜索，注意第 34 行的 L = L + 1 的条件判断，在最坏情况下，会使得该二分搜索退化为 O(N) 的时间复杂度。

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.size()==0)
            return false;
        int L = 0, R = nums.size()-1, mid;
        while(L <= R){
            cout << "L: " << L << ",  R: " << R << endl;
            mid = (L + R) >> 1;
            if(nums[mid]>nums[L]){
                if(target==nums[mid])
                    return true;
                else if(target>nums[mid])
                    L = mid + 1;
                else if(target>=nums[L])
                    R = mid - 1;
                else
                    L = mid + 1;
            }
            else if(nums[mid]<nums[L]){
                if(target==nums[mid])
                    return true;
                else if(target<nums[mid])
                    R = mid - 1;
                else if(target<=nums[R])
                    L = mid + 1;
                else
                    R = mid - 1;
            }
            else{ // nums[mid] == nums[L]
                if(target==nums[mid])
                    return true;
                else
                    L = L + 1;
            }
        }
        return false;
    }
};

82、删除排序链表中的重复元素 II

模拟题

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head)
            return NULL;
        ListNode *new_head = new ListNode(0);
        ListNode *new_p = new_head, *ptr=head;
        long long int num = 1e10;
        while(ptr!=NULL){
            if(ptr->next!=NULL && ptr->val==ptr->next->val){
                num = ptr->val;
                ptr = ptr->next;
            }
            else if((long long int)(ptr->val)==num){
                ptr = ptr->next;
            }
            else{
                new_p->next = ptr;
                ptr = ptr->next;
                new_p = new_p->next;
                new_p->next = NULL;
            }
        }
        return new_head->next;
    }
};

83、删除排序链表中的重复元素

模拟题，线上代码铁定不能这么写，内存泄露有木有！

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode *new_head = head, *p = head;
        while(p!=NULL){
            if(p->next!=NULL && p->val==p->next->val){
                p->next = p->next->next;
                continue;
            }
            p = p->next;
        }
        return new_head;
    }
};

84、柱状图中最大的矩形

一个很自然的想法是，以当前柱子为高，向两边遍历，时间复杂度为 $O(n^2)$。降低复杂度的关键是，如何快速找到以当前柱子为高的左右边界left_index 和 right_index，维护一个单调的递增栈 >=，即可快速找到 left_index 和 right_index。具体如代码第 14 行所示，整体时间复杂度为 $O(n)$ 。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.size()==0)
            return 0;
        stack<int> index;
        index.push(-1);
        int max_area = 0, N = heights.size(), h;
        for(int i=0; i<N; i++){
            if(index.size()>1 && heights[i]<heights[index.top()]){
                while(index.size()>1 && heights[i]<heights[index.top()]){
                    h = heights[index.top()];
                    index.pop();
                    max_area = max(max_area, h*(i-index.top()-1));
                }
            }
            index.push(i);
        }
        while(index.size()>1){
            h = heights[index.top()];
            index.pop();
            max_area = max(max_area, h*(N-index.top()-1));
        }
        return max_area;
    }
};

85、

86、分隔链表

使用两个指针即可。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode *big_head = new ListNode(0), *small_head = new ListNode(0);
        ListNode *big_p = big_head, *small_p = small_head, *p = head;
        while(p){
            if(p->val < x){
                small_p->next = p;
                p = p->next;
                small_p = small_p->next;
                small_p->next = NULL;
            }
            else{
                big_p->next = p;
                p = p->next;
                big_p = big_p->next;
                big_p->next = NULL;
            }
        }
        small_p->next = big_head->next;
        return small_head->next;
    }
};

88、合并两个有序数组

一个小的 trick 是从后往前遍历，时间复杂度 $O(n+m)$, 空间复杂度 $O(1)$ 。

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m-1, p2 = n-1, index = m+n-1;
        while(p1>=0 && p2>=0)
            nums1[index--] = nums1[p1]>=nums2[p2]? nums1[p1--] : nums2[p2--];
        while(p1+p2>=-1)
            nums1[index--] = p1>=0? nums1[p1--] : nums2[p2--];
    }
};