LeetCode 做题笔记

Medium

189. Rotate Array

link

Solution#1: using extra space to store some elements which will be covered when rotating. 𝒪(n) Space and time complexity.

Solution #2: reverse three times on original array and only cost 𝒪(1) space.

CleanShot_2022-01-30_at_16.38.18.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    void rev(int l,int r,vector<int> &n) {
        while(l < r) {
            swap(n[l],n[r]);
            l++;
            r--;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        rev(0,nums.size()-1,nums);
        rev(0,k-1,nums);
        rev(k,nums.size()-1,nums);
    }
};

Best Time to Buy and Sell Stock

  • Best Time to Buy and Sell Stock II (no limit on how many times you can buy&sell)
  • Best Time to Buy and Sell Stock with Cooldown
  • Best Time to Buy and Sell Stock with transaction fee

122. Best Time to Buy and Sell Stock II

IMG_0251.jpeg

309. Best Time to Buy and Sell Stock with Cooldown

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// with cool-down
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> pf(2,vector<int>(3,0));
        pf[0][1] = 0-prices[0];
        for(int i=1;i< prices.size();i++) {
            pf[1][0] = max(pf[0][0],pf[0][2]);
            pf[1][1] = max(pf[0][1],pf[0][0] - prices[i]);
            pf[1][2] = pf[0][1] + prices[i];
            
            pf[0] = pf[1];
        }
        return max(max(pf[0][0],pf[0][1]),pf[0][2]);
    }
};

Jump Game II

DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size(),INT32_MAX);
        dp[0] = 0;
        int farthest = 0;
        for(int i=0;i<nums.size();i++) {
            if(i+nums[i] <= farthest) continue;
            farthest = i+nums[i];
            for(int j=i+1;j<=i+nums[i];j++) {
                if(j >= nums.size()) break;
                dp[j] = min(dp[j],dp[i]+1);
            }
        }
        return dp[nums.size()-1];
    }
};

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int jump(vector<int>& nums) {
        int steps = 0;
        int farthest = 0,thres=0;
        for(int i=0;i<nums.size()-1;i++) {
            farthest = max(farthest,i+nums[i]);
            
            if(i == thres) {
                steps++;
                thres = farthest;
                if(farthest >= nums.size()-1) break;
            }
            
        }
        
        return steps;
    }
};

Group Anagrams

using hashmap with several optimizations

main idea: hashmap which maps the sorted string to grouped anagrams.

  1. Line 5: using unordered_map because the sequence doesn’t matters.
  2. Line 11: reserve() to avoid reallocate
  3. Line 13: using std::move to avoid copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string,vector<string>> m;
        for(string &s:strs) {
            string cpy = s;
            std::sort(s.begin(), s.end());
            m[s].push_back(cpy);
        }
        ans.reserve(m.size());
for(pair<const string,vector<string>> &p:m) {
            ans.push_back(std::move(p.second));
        }
        return ans;
    }
};

tricks

since the string only includes lower-case alphabets, using this sort function is faster.

1
2
3
4
5
6
7
8
9
10
11
12
// Code from: https://leetcode.com/problems/group-anagrams/discuss/19200/C%2B%2B-unordered_map-and-counting-sort
string strSort(string s) {
    int counter[26] = {0};
    for (char c : s) {
        counter[c - 'a']++;
    }
    string t;
    for (int c = 0; c < 26; c++) {
        t += string(counter[c], c + 'a');
    }
    return t;
}

intuition

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    inline bool cmp(map<char,int> &l,map<char,int> &r) {
        for(pair<const char,int>& pr:l) {
            if(r.find(pr.first) == r.end() || pr.second != r[pr.first]) return false;
        }  return true;
    }

    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        vector<int > idx;
        if(strs.size() == 0) return ans;
        std::sort(strs.begin(), strs.end(),[](string &l,string &r) {
            return l.length() < r.length();
        });
        vector<map<char,int>> v;
        for(string & str : strs) {
            map<char,int> m;
            for(char &ch:str) {
                m[ch]++;
            }
            v.push_back(m);
        }

        ans.push_back({strs[0]});
        idx.push_back(0);
        bool flag;
        for(int i=1;i<strs.size();++i) {
            flag = false;
            for(int j=ans.size()-1;j>=0;j--) {
                if(ans[j][0].length() == strs[i].length()) {
                    if(cmp(v[idx[j]], v[i])) {
                        ans[j].push_back(strs[i]);
                        flag = true;
                        break;
                    }
                }
            }
            if(!flag) {
                ans.push_back({strs[i]});
                idx.push_back(i);
            }

        }
        return ans;
    }
};

424. Longest Repeating Character Replacement

Sliding window

In line 10, using if is enough because the sliding window only violates the restriction by one character.

Ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> v(26,0);
        int l=0,r=0;
        int maxl=0;
        int maxc = 0;
        for(;r<s.length();r++) {
            maxc = max(maxc, ++v[s[r]-'A']);
            if(r-l+1- maxc > k) {
                --v[s[l]-'A'];
                l++;
            }
            maxl=max(maxl,r-l+1);
        }
        return maxl;
    }
};

435. Non-overlapping Intervals

https://leetcode.com/problems/non-overlapping-intervals/discuss/91713/Java:-Least-is-Most/730443

105. Construct Binary Tree from Preorder and Inorder Traversal

//TBD

300. Longest Increasing Subsequence

DP solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        
        for(int i=0;i<nums.size();i++) {
            for(int j=0;j<i;j++) {
                if(nums[i] > nums[j]) {
                    dp[i] = max(dp[i],dp[j] + 1);
                }
            }
        }
        
        return *max_element(dp.begin(),dp.end());
    }
};

Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> ans;
        int n=nums.size();
        vector<int>::iterator it;
        for(int i=0;i<n;i++) {
            it = lower_bound(begin(ans),end(ans),nums[i]);
            if(it == end(ans)) {
                ans.push_back(nums[i]);
            } else {
                *it = nums[i];
            }
        }
        return ans.size();
    }
};

REF:

[C++/Python] DP, Binary Search, BIT Solutions - Picture explain - O(NlogN) - LeetCode Discuss

LongestIncreasingSubsequence.pdf

209. Minimum Size Subarray Sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = INT_MAX;
        vector<int> sum(n+1,0);
        
        for(int i=1;i<=n;++i) {
            sum[i] = nums[i-1] + sum[i-1];
        }
        
        for(int i=n;i>0 && sum[i] >= target; i--) {
            int j = upper_bound(begin(sum),end(sum), sum[i] - target) - begin(sum);
            ans = min(ans, i-j+1);
            
        }
        return ans == INT_MAX ? 0 : ans;        
    }
};

satisfy that:

Solution (sliding window)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
		    let mut ans = 200000;
		    
		    for lb in 0..nums.len() {
	        let mut sum = 0;
	        for rb in lb..nums.len() {
	            sum += nums[rb];
	            if sum >= target {
	                ans = std::cmp::min(ans,rb-lb+1);
	                break;
	            }
	        }
		    }
		    if ans == 200000 {
			        0 
        } else {
            ans as i32
        }
    }
}

378. Kth Smallest Element in a Sorted Matrix

Solution #1: min heap

[C++/Java/Python] MaxHeap, MinHeap, Binary Search - Picture Explain - Clean & Concise - LeetCode Discuss

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef pair<int,pair<int,int>> pr;
class Solution {
public:
    int n;
    
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        n = matrix.size();
        auto cmp = [](pr &l, pr &r){
            return l.first > r.first; 
        };
        priority_queue<pr,vector<pr>,decltype(cmp)> pq(cmp);
        for(int i=0;i<n;i++) {
            pq.push({ matrix[i][0], { i,0 }  });
        }
        
        for(int i=0;i<k-1;i++) {
            pair<int,int> ax = pq.top().second;
            pq.pop();
            if(ax.second + 1 < n)   pq.push( {matrix[ax.first][ax.second+1], {ax.first,ax.second+1}}  
            
        }
        return pq.top().first;
        
    }
};

Untitled

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef pair<int,pair<int,int>> pr;
class Solution {
public:
    int n;
    int ans=0;
    
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        n = matrix.size();
        int l = matrix[0][0];
        int r = matrix[n-1][n-1];
        int mid;
        int tmp;
        while(l <= r) {
            mid = (l+r)/2;
            tmp = num(mid,matrix);
            if(tmp >= k) {
                ans = mid;
                r = mid-1;    
            } else {
                l = mid+1;
            }
        }
                
        return ans;
    }
    
    int num(int thres,vector<vector<int>>& m) {
        int count = 0;
        int col = n-1;
        for(int i=0;i<n;i++) {
            while(col >= 0 && m[i][col] > thres) col--;
            count += (col+1);
        }
        return count;
    }
    
};

Subset

力扣

DFS

每一位数字可以选或者不选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> ans;
    int len;

    void dfs(int pos, vector<int>& path, vector<int>& nums) {
        if(pos == len) {
            ans.push_back(path);
            return;
        }
        dfs(pos+1,path,nums);
        path.push_back(nums[pos]);
        dfs(pos+1,path,nums);
        path.pop_back();
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        sort(begin(nums),end(nums));
        len = nums.size();
        vector<int> path(0);
        dfs(0,path,nums);
        return ans;
    }
};

状压

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<vector<int>> ans;
    int len;

    vector<vector<int>> subsets(vector<int>& nums) {
        len = nums.size();
        int lim = (1<<len);
        vector<int> v;
        v.reserve(20);
        for(int i=0;i<lim;i++) {
            for(int j=0;j<len;j++) {
                if( (i & (1 << j) )) v.push_back(nums[j]);
            }
            ans.push_back(v);
            v.clear();
        }
        return ans;
    }
};

525. Contiguous Array

find the maximum length of contiguous subarray with an equal number of 0 and 1.

Prefix Sum + HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int len = nums.size();
        vector<int> prefix(len+1,0);
        unordered_map<int,int> um={{0,0}};// {i,j} rep -> 
        int ans = 0;
        for(int i=1;i<=len;i++) {
            if(nums[i-1]) prefix[i] = prefix[i-1] + 1;
            else prefix[i] = prefix[i-1] - 1;
            if(um.find(prefix[i]) != um.end()) {
                ans = max(ans,i-um[prefix[i]]);
            } else {
                um[prefix[i]] = i;
            }
        }
        return ans;
    }
};

560. Subarray Sum Equals K

find the number of subarrays whose sum equals to k

Prefix Sum

加到目前的前缀和是pre。

用hashmap寻找前缀和是pre-k的数目，两个前缀之间的subarray就是和为k的subarray

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int pre = 0;
        unordered_map<int,int> um={{0,1}};
        int ans = 0;
        for(int i = 0; i<len ; i++) {
            pre += nums[i];
            if(um.find(pre-k) != um.end()) {
                ans += um[pre-k];
            }
            um[pre]++;
        }
        return ans;
    }
};

148. 排序链表

D&C + Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 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* mergeSort(ListNode* head,ListNode* tail=nullptr) {
        if(head->next == tail) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* l1=mergeSort(head,slow);
        ListNode* l2=mergeSort(slow,tail);
        head = nullptr;
        ListNode* cursor;
        while(l1 != slow && l2 != tail) {
            if(l1->val < l2->val) {
                if(head == nullptr) {
                    head = l1;
                    cursor = head;
                }
                else {
                    cursor->next = l1;
                    cursor = cursor->next;
                }
                l1=l1->next;
            } else {
                if(head == nullptr) {
                    head = l2;
                    cursor = head;
                } else {
                    cursor->next = l2;
                    cursor = cursor->next;
                }
                l2=l2->next;
            }
        }
        while(l1 != slow) {
            cursor ->next = l1;
            cursor = cursor->next;
            l1 = l1->next;
        }
        while(l2 != tail) {
            cursor ->next = l2;
            cursor = cursor->next;
            l2 = l2->next;
        }
        cursor->next = tail; // half an hour's debug.....
        return head;
    }

    ListNode* sortList(ListNode* head) {
        if(head == nullptr) return nullptr;
        return mergeSort(head);
    }
};

Faster Version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * 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* mergeSort(ListNode* head,ListNode* tail=nullptr) {
        if(head->next == tail) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != tail && fast->next != tail) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* l1=mergeSort(head,slow);
        ListNode* l2=mergeSort(slow,tail);
        head = nullptr;
        if(l1->val < l2->val) {
            head = l1;
            l1=l1->next;
        } else {
            head = l2;
            l2=l2->next;
        }
        ListNode* cursor=head;
        while(l1 != slow && l2 != tail) {
            if(l1->val < l2->val) {
                cursor->next = l1;
                cursor = cursor->next;
                l1=l1->next;
            } else {
                cursor->next = l2;
                cursor = cursor->next;
                l2=l2->next;
            }
        }
        if(l1 != slow) {
            cursor->next = l1;
            while(cursor->next != slow) cursor=cursor->next;
        } else if(l2 != tail){
            cursor->next = l2;
            while(cursor->next != tail) cursor=cursor->next;
        }
        cursor->next = tail; // half an hour's debug.....
        return head;
    }

    ListNode* sortList(ListNode* head) {
        if(head == nullptr) return nullptr;
        return mergeSort(head);
    }
};

1868. Product of Two Run-Length Encoded Arrays

  • two pointers

坑点：

  • 如果当前两个数的乘积和之前一样的话，直接把 frequency 累加到前面而不是 push_back 一个新的 element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        int p1 = 0;
        int s1 = encoded1.size();
        int p2 = 0;
        int s2 = encoded2.size();
        int prod,freq;
        vector<vector<int>> ans;
        while(p1 < s1 && p2 < s2) {
            prod = encoded1[p1][0] * encoded2[p2][0];
            freq = min(encoded1[p1][1],encoded2[p2][1]);
            if(!ans.empty() && prod == ans.back()[0]) {
                ans.back()[1] += freq;
            } else {
                ans.push_back({prod,freq});
            }
            if(encoded1[p1][1] == freq) {
                p1++;
            } else {
                encoded1[p1][1] -= freq;
            }
            if(encoded2[p2][1] == freq) {
                p2++;
            } else {
                encoded2[p2][1] -= freq;
            }
        }
        return ans;
    }
};

146. LRU Cache

Implement the LRUCache

  1. LRUCache(int capacity) initialize the Cache with positive size.
  2. int get(int key) return the value of key.
  3. void put(int key,int value) update the value at key. If the number of keys exceeds the capacity, evict the least recently used key.

get and put should run in O(1) time complexity.

How to?

  1. When an item is accessed, it should be “marked” as most recent used item. Doubly linked list can remove and insert in constant time. Each time the item is accessed, it is moved to the front of the linked list.
  2. Query? We use a hashmap to store <key, pointer> pair. The pointer points to the node of linked list.

Note that:

  1. When a node is removed, its key in the hashtable should also be removed.
  2. Dummy nodes can be used to reduce the complexity of insert and remove operation.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class LRUCache {
public:
    class Node{
    public:
        Node* prev,* next;
        pair<int,int> kv;
        Node(Node* p1= nullptr,Node* p2= nullptr):prev(p1),next(p2){}
        Node(int k,int v,Node* p1= nullptr,Node* p2= nullptr):kv({k,v}),prev(p1),next(p2){}
    };
    int capacity;
    int count;
    Node* dummy_head;
    Node* dummy_tail;
    unordered_map<int,Node*> um;
    int remove_head() {
        Node* node_delete = dummy_head->next;
        int key = node_delete->kv.first;
        Node* next = dummy_head->next->next;
        dummy_head->next = next;
        next->prev = dummy_head;
        delete node_delete;
        return key;
    }

    Node* insert(int key,int val) {
        Node* prev = dummy_tail->prev;
        Node* new_node = new Node(key,val,prev,dummy_tail);
        prev->next = new_node;
        dummy_tail->prev = new_node;
        return new_node;
    }

    void move_to_front(Node* node) {
        Node* prev = node->prev;
        Node* next = node->next;
        prev->next = next;
        next->prev = prev;
        // insert
        prev = dummy_tail->prev;
        prev->next = node;
        dummy_tail->prev = node;
        node->prev = prev;
        node->next = dummy_tail;
    }

    LRUCache(int capacity) {
        this->capacity = capacity;
        this->count = 0;
        dummy_head = new Node(nullptr,new Node());
        dummy_tail = dummy_head->next;
        dummy_tail->prev = dummy_head;
    }

    int get(int key) {
        if(um.find(key) == um.end()) return -1;
        move_to_front(um[key]);
        return um[key]->kv.second;
    }

    void put(int key, int value) {
        if(um.find(key) != um.end()) {
            um[key]->kv.second = value;
            move_to_front(um[key]);
        } else { // key not exists.
            if(count == capacity) {
                int removed_key = remove_head();
                um.erase(removed_key);
                count--;
            }
            Node* new_node = insert(key,value);
            um[key] = new_node;
            count++;
        }
    }
};