3 Basic Strategy

Divide and Conquer

Deciding the term before the subproblem(e.g. half之间可比大小)

Case1: $T(n) = 2T(\frac n2) + O(n) \Rightarrow T(n) = O(nlogn)$
Case2: $T(n) = T(\frac n2) + O(1)/O(n) \Rightarrow T(n) = O(logn)$

Case1: Merge subproblem

Given a collection of n plugs of different widths, and n corresponding sockets. You are allowed to try plug and socket together, from which you can determine whether the socket is too large, too small, or an exac natch for the plug, but there is no way to compare two socket together, or two plugs together. You are asked to match each plug to its socket.

Solution: Select a plug p, and use it to separate the sockets into 3 sets, those smaller than p(S1), those bigger than p (S2), and the single socket s that matches p. Uses to do the same for the remaining plugs, separating them into those smaller than s (P1), and those bigger than s (P2). This takes a total of 2n - 1 comparisons (n for the sockets, and n - 1 for the prugs) Since the plugs in P1 match sockets in S1, and the plugs in P2 match the sockets in S2, it remains to apply the algorithm recursively to both P1 U S1, and P2 U S2

$T(n) = T(i) + T(n-1-i) + 2n-1 \Rightarrow T(n) = O(nlogn)$

Case2: Binary Search

在闭区间查找[begin,end],注意对找不到的处理

int binary_find(vector<int>& nums, int target){
    int l=0,r=nums.size()-1;//Notice1
    while(l<r){
        int mid=l+(r-l)/2;//Notice2
        if(nums[mid]==target)return mid;
        else if(nums[mid]>target)r=mid-1;
        else l=mid+1;
    }
    return nums[l]==target?l:-1;
}

Floating Point

double floating_find(double l, double r)
{
    while (r - l > eps)
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

Find the bound

在[begin,end)查找,故格外注意边界
先想最终目标>or>=,然后满足条件时右不变,不满足时左加一
注意变式如求上界(注释部分)

int upper_bound(vector<int>& nums, int target){
    int l=0,n=nums.size();//Notice1
    int r=n;
    while(l<r){
        int mid=l+(r-l)/2);//Notice2
        if(nums[mid]>target)r=mid;
        else l=mid+1;
    }
    if(r==n||nums[l]!=target)return -1;
    else return l;
    /*
    if(l==0||nums[l-1]!=target)return -1;
    else return l-1;    
    */
}
int lower_bound(vector<int>& nums, int target){
    int l=0,n=nums.size();//Notice1
    int r=n;
    while(l<r){
        int mid=l+(r-l)/2);//Notice2
        if(nums[mid]>=target)r=mid;
        else l=mid+1;
    }
    if(r==n||nums[l]!=target)return -1;
    else return l;
}

Two pointers

Merge Intervals

first pointer: merged interval right end

second pointer: the unmerged part

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(),intervals.end());
    int n = intervals.size();
    vector<vector<int>> ans;
    ans.push_back(intervals[0]);
    for(int i =1;i<n;++i){
        if(intervals[i][0]<=ans.back()[1]){
            ans.back()[1] = max(ans.back()[1],intervals[i][1]);
        }
        else{
            ans.push_back(intervals[i]);
        }
    }
    return ans;
}

Sliding Window

Leetcode76

Given two strings s and t of lengths m and n respectively, return the minimum window in s which will contain all the characters in t. If there is no such window in s that covers all characters in t, return the empty string ""

class Solution {
public:
    string minWindow(string s, string t) {
        fill(flag,flag+128,0);
        fill(each,each+128,0);
        int n=t.size();
        int m=s.size();
        int cap;
        int count=0,start=0,mini=m+1;//易错点1
        for(int i=0;i<n;++i)flag[t[i]]=1,each[t[i]]++;
        for(int i=0;i<m;++i){
            if(flag[s[i]]){
                if(--each[s[i]]>=0)count++;
                while(count==n){
                    if(i-start+1<mini){
                        mini=i-start+1;
                        cap=start;
                    }
                    if(flag[s[start]]&&++each[s[start]]>0)count--;
                    ++start;
                }
            }
        }
        return mini==m+1?"":s.substr(cap,mini);
    }
private:
    int flag[128];
    int each[128];
};

Leetcode3

Given a string s, find the length of the longest substring without repeating characters.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        fill(each,each+128,0);
        int n=s.size();
        int start=0,maxi=0;
        for(int i=0;i<n;++i){
            char p=s[i];
            if(++each[p]>1){
                while(start<i&&s[start]!=p){
                    --each[s[start]];
                    ++start;
                }
                if(start!=i){
                    --each[s[start]];
                    ++start;
                }
            }   
            maxi=max(maxi,i-start+1);
        }
        return maxi;
    }
private:
    int each[128];
};

Hash

思路

记录上一次位置(是否出现)

caution

用vector存,需要从-1开始
用unordered_map存,注意先判断count

Leetcode 3 Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

// unordered_map
int lengthOfLongestSubstring(string s) {
    unordered_map<char,int> record;
    int ans = 0;
    int n = s.size();
    int j = -1;
    for (int i =0;i<n;++i){
        if(record.count(s[i])&&record[s[i]]>j){
            j = record[s[i]];
        }
        record[s[i]] = i;
        ans = max(ans, i - j);
    }
    return ans;
}
// vector
int lengthOfLongestSubstring(string s) {
    vector<int> record(256,-1);
    int ans = 0;
    int n = s.size();
    int j = -1;
    for (int i =0;i<n;++i){
        j = max(j,record[s[i]]);
        record[s[i]] = i;
        ans = max(ans, i - j);
    }
    return ans;
}

记录出现次数(往往可以联系Two pointers)

Bit Manipulation

二进制中1的个数

题目链接

每位遍历O(n)

class Solution {
public:
     int  NumberOf1(int n) {
         unsigned int flag=1,sum=0;
         for(int i=0;i<32;++i){
             sum+=flag&n?1:0;
             flag<<=1;
         }
         return sum;
     }
};

只遍历1的个数O(m)

class Solution {
public:
     int  NumberOf1(int n) {
         unsigned int sum=0;
         while(n!=0){
             n=n&(n-1);
             sum++;
         }
         return sum;
     }
};

Set Mismatch

题目链接

a set of integers 1 to n but got repetition of one number and loss of another number,e.g. [1,2,2,4]

find the duplicate and the missing.

在后面添加1 to n，构建3个duplicate和1个missing,然后在数量上做文章

vector<int> findErrorNums(vector<int>& nums) {
    int sum=0,num1=0,num2=0;
    int n=nums.size();
    vector<int> result(2);
    for(int i=0;i<n;++i){
        sum^=nums[i];
        sum^=(i+1);
    }
    int low=sum&(-sum);
    for(int i=0;i<n;++i){
        if((nums[i]&low)==0)num1^=nums[i];
        else num2^=nums[i];
        if(((i+1)&low)==0)num1^=(i+1);
        else num2^=(i+1);
    }
    for(int i=0;i<n;++i){
        if(nums[i]==num1||nums[i]==num2){
            result[0]=nums[i];
            result[1]=nums[i]==num1?num2:num1;
            break;
        }
    }
    return result;
}

Sort

Brute Force

//Selection sort
//Finding the minimum element from the unsorted part,swapping it with the leftmost unsorted element
for(int i = 0; i< n-1; ++i){
    int min = i;
    for(int j = i+1; j<n; ++j)
        if(nums[j]<nums[min])min = j;
    swap(nums[i],nums[min]);
}
//Bubble sort
//Just like the movement of air bubbles in the water that rise up to the surface, each element of the array move to the end in each iteration
for(int i = 0; i< n-1; ++i){
    int flag = true;
    for(int j =0; j< n-1-i; ++j)
        if(nums[j+1]<nums[j]){
            swap(nums[j],nums[j+1]);
            flag = false;
        }
    if(flag == true)break;
}

Decrease & Conquer

//Insertion sort
//Compare the new card to each sorted card and find its position until the array is sorted
for(int i = 0; i < n; ++i){
    int v = nums[i];
    j = i - 1;
    while(j>= 0 && nums[j] > v){
        nums[j + 1] = nums[j];
        j--;
    }
    nums[j+1] = v;
}

Shell’s Sort:

compare items that are one stride length h apart. Do insertion sort.
Start with large stride, and decrease towards 1

Divide & Conquer

mergesort
quicksort

模板

void merge_sort(vector<int> &nums, int l, int r, vector<int> &temp) {
    if (r-l<=1) return; //Notice1
    // divide
    int mid = l + (r - l) / 2;
    merge_sort(nums, l, mid, temp); // Notice2, [l,mid), 如果是mid + 1有可能=r
    merge_sort(nums, mid, r, temp);
    // conquer
    int p = l, q = mid, k = l;
    while (p < mid && q < r)
        temp[k++] = nums[p]< nums[q]? nums[p++]:nums[q++];
    while(p < mid)temp[k++] = nums[p++];
    while(q < r) temp[k++] = nums[q++];
    for (k = l; k < r; ++k)
        nums[k] = temp[k];
}

// Leetcode 148 https://leetcode-cn.com/problems/sort-list/
ListNode* sortList(ListNode* head) {
    if(!head||!head->next)return head;
    //Find midium
    ListNode *slow = head,*fast = head;
    while(fast->next&&fast->next->next){
        slow = slow->next;
        fast = fast->next->next;
    }
    fast = slow->next;
    slow->next = NULL;
    slow = head;
    //divide
    slow=sortList(slow);fast=sortList(fast);
    //conquer
    ListNode * dummy = new ListNode(0);
    ListNode * node = dummy;
    while(slow&&fast){
        if(slow->val < fast->val){
            node->next = slow;
            slow = slow->next;
        }
        else{
            node->next = fast;
            fast = fast->next;
        }
        node = node->next;
    }
    node->next = slow?slow:fast;
    return dummy->next;
}

void quick_sort(int l,int r){//左闭右开
    if(r-l<=1)return;
    int first=l,last=r-1,key=nums[l];//保留pivot
    while(first<last){//先右再左，因为nums[first]可以被替换
        while(first<last&&nums[last]>=key)last--;
        nums[first]=nums[last];
        while(first<last&&nums[first]<=key)first++;
        nums[last]=nums[first];
    }
    nums[first]=key;
    quick_sort(l,first);
    quick_sort(first+1,r);
}

Transform & Conquer

Heap sort

sink: O(logn)
pop_heap: v[1] sink O(logn)
push_heap: v[n+1] up O(logn)
make_heap: bottom-up sink O(n)

heap sort: make_heap + sort_heap(O(nlog(n)))

//[f,l),[,Compare comp]
void pop_heap(iterator first, iterator last);
void push_heap(iterator first, iterator last);
void make_heap(iterator first, iterator last);
void sort_heap(iterator first, iterator last);

变式:vector只将a[i]用v[i-1]代替即可

void sink(int val, vector<int>& a){
    int n = a.size()-1;
    while(2*val<=n){//最终是2*val
        int i=2*val;
        if(i+1<=n&&a[i+1]>a[i])i++;//易错点2
        if(a[i]>a[val]){
            swap(a[i],a[val]);
            val=i;
        }
        else break;
    }
}
void up(int val, vector<int>& a){//最终是val/2
    while(val>1&&a[val>>1]<a[val]){// all but a[1]
        swap(a[val],a[val>>1]);
        val>>=1;
    }
}
int main(){
    for(int i=n>>1;i>=1;--i)sink(i);//construct heap
    // partition heap and sorted array
    while(--n){
        // get nums[1]
        nums[1] = nums.back();
        nums.pop_back();
        sink(1, nums);
    }
}

Leetcode215. Kth Largest Element in an Array

题目

法1:堆排序

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        // make heap
        for(int i=n/2;i>0;--i)sink(i,nums);
        // sort heap
        while(--k){
            nums[0] = nums.back();
            nums.pop_back();
            sink(1,nums);
        }
        return nums[0];
    }
private:
    void sink(int val, vector<int>& nums){
        int n = nums.size();
        while(val*2<=n){
            int i = val*2;
            if(i+1<=n&&nums[i]>nums[i-1]) ++i;
            if(nums[i-1]>nums[val-1]){
                swap(nums[i-1],nums[val-1]);
                val = i;
            }
            else break;
        }
    }
};

法2:快排

class Solution {
public:
    int findKthLargest(vector<int>& nums, int x) {
        k=x;
        n=nums.size();
        v=nums;
        quick_selection(0,n);
        return v[n-k];
    }
private:
    int k,n;
    vector<int> v;
    void quick_selection(int l,int r){
        if(r-l<=1)return;
        int first=l,last=r-1,p=v[l];
        while(first<last){
            while(first<last&&v[last]>=p)last--;
            v[first]=v[last];
            while(first<last&&v[first]<=p)first++;
            v[last]=v[first];
        }
        v[first]=p;
        if(first==n-k)return;
        else if(first<n-k)quick_selection(first+1,r);
        else quick_selection(l,first);
    }
};

3 Basic Strategy

Divide and Conquer​

Case1: Merge subproblem​

Case2: Binary Search​

Two pointers​

Merge Intervals​

Sliding Window​

Hash​

Bit Manipulation​

二进制中1的个数​

Set Mismatch​

Sort​

Brute Force​

Decrease & Conquer​

Divide & Conquer​

Transform & Conquer​

Heap sort​