Leetcode刷題學習筆記 – 解題技巧

Leetcode刷題學習筆記 -- 解題技巧

從後面往前統計

1010. Pairs of Songs With Total Durations Divisible by 60(Medium)

給你一個vector time，找出i < j 且 (time[i]+time[j]) % 60 == 0。

找出pair 且 i < j，說明了，==如果我找到j，則可以往前用已經統計過i的數值。==
所以只要O(N) 就可以，不需要全部找完後再回頭檢查那些pair符合。

int numPairsDivisibleBy60(vector<int>& time) {
    int rtn{0};
    vector<int> cnt(60, 0);
    for(auto& t : time) {
        int tt = t % 60;
        if(tt == 0) rtn += cnt[0];
        else rtn += cnt[60 - t % 60];
        cnt[tt]++;
    }
    return rtn;
}

從簡單的case開始延伸

例如題目給你一個input的長度，可以從length = 1開始推到n

22. Generate ParentheseMed

79. Word Search

探訪所有的可能(暴力破解/Burte force)

解題不外乎就是探訪所有的可能，從所有的可能中找出答案。雖然是一個時間複雜度很差的方法，但是通常可以從中得到靈感，繼續減少探訪的次數。

127. Word Ladder(Hard)

給你一個兩個string beginWord和endWord，還有一個string list，求出最少幾次變換，可以從beginWord變成endWord。

暴力破解，從beginWord開始，每個字母都從a-z試試看，看有沒有在word list裡面。
使用unordered_set 可以快速找出有沒有存在的string。

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> s(wordList.begin(), wordList.end());
    if(!s.count(endWord)) return 0;
    queue<string> q({beginWord});
    int rtn = 0;
    while(!q.empty()) {
        for(int k = q.size(); k > 0; --k) {
            string str = q.front(); q.pop();
            if(str == endWord) return rtn + 1;
            // 暴力搜尋，但是用set來快速檢查是不是在list裡面
            for(int i = 0; i < str.length(); ++i) {
                string newWord = str;
                for(char c = 'a'; c <= 'z'; ++c) {
                    newWord[i] = c;
                    if(s.count(newWord) && newWord != str) {
                        q.push(newWord);
                        s.erase(newWord);
                    }
                }
            }
        }
        rtn++;
    }
    return 0;
}

或是，有效率的列舉所有可能。怎麼列舉所有可能而不會錯過任何一種，也是一種藝術。

1675. Minimize Deviation in Array(Hard)

題目給你一個vector nums，其中奇數可以可以乘2，偶數可以除2得到一個新的數，求出數列的最小deviation(最大和最小的差)。

因為是要求最小deviation，所以會出現在數字都是最接近的情況。
set從每個數字都是最大的開始，一路往下尋找。(參考code的註解)

int minimumDeviation(vector<int>& nums) {
    set<int> s;
    for(auto& n : nums)
        s.insert(n & 1 ? n * 2 : n); // 所有最大的值集合(全部都是even)
    int ans = *s.rbegin() - *s.begin(); // deviation的定義最大和最小的差
    while((*s.rbegin() & 1) == 0) {     // 只有even才可以變小
        s.insert(*s.rbegin() / 2);      // 放回變小的值，等於insert其他可能
        s.erase(*s.rbegin());           // 因為s.rbegin()已經比過了，所以刪除
        ans = min(ans, *s.rbegin() - *s.begin());
    }
    return ans;
}

93. Restore IP Addresses

驗證給你的string中所有可能的ip address。

一開始想到用backtracking的方法來做，但是錯誤很多，沒辦法寫出一個好的答案。
其實這個問題也可以用暴力破解，就是四個欄位長度從1~3都有可能。
在從可能的答案中，刪除長度不符合的，或是檢查不過的，最後就可以得出正確答案。
暴力破解雖然time complexity不一定是最好的，但是code的錯誤機會比較小。

class Solution {
    bool check(string& s) {
        if(s.size() == 1) return true;
        else if(s.front() == '0') return false;
        else if(stoi(s) > 255) return false;
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> rtn;
        // 探訪所有可能的長度組合
        for(int a = 1; a <= 3; ++a)
        for(int b = 1; b <= 3; ++b)
        for(int c = 1; c <= 3; ++c)
        for(int d = 1; d <= 3; ++d) {
            // 四個欄位的長度和必需為s.size()
            if(a + b + c + d == s.size()) {
                string A = s.substr(0, a);
                string B = s.substr(a, b);
                string C = s.substr(a + b, c);
                string D = s.substr(a + b + c, d);
                // 四個欄位比須通過檢查
                if(!check(A) || !check(B) || !check(C) || !check(D)) continue;
                rtn.push_back(A + "." + B + "." + C + "." + D);
            }
        }
        return rtn;
    }
};

從答案的範圍中，假設答案，驗證答案的正確性。

可以反推從答案的範圍中，選一個值(通常使用binary search)，才可以降低搜尋的次數(O(logN), N為答案的範圍)。
Leetcode刷題學習筆記–Binary Search

int left = ANS_MIN, right = ANS_MAX;
while(left < right) {
    int mid = left + (right - left) / 2;
    // 計算由mid得到的答案是否正確
    
    // 由題目設計下一個left和right的位置               
}

從例外開始思考

可以從例外開始思考，看看有沒有想法。
例如 556. Next Greater Element III，從完全沒有答案的例子開始，什麼樣的情況是沒有答案?回推怎樣的情況才會開始有答案。

犧牲space換來答案的正確

答案正確比浪費的空間還重要。當沒有想法的時候不然浪費一點空間換來答案的正確性。

1089. Duplicate Zeros

在原本的vector上，如果遇到0，就在0的右邊補上一個0。
例如:[1,0,2,3,0,4,5,0] -> [1,0,0,2,3,0,0,4]

// 比起浪費的空間，答案正確比較重要
// 使用比較大的空間來儲存答案
// 可以套過pointer的方法來不使用到額外的空間
void duplicateZeros(vector<int>& arr) {
    int sz = arr.size();
    int i = sz - 1, j = i + count(arr.begin(), arr.end(), 0);
    for(;i >= 0; --i) {
        if(arr[i] == 0) {
            if(j < sz)
                arr[j] = arr[i];
            j--;
        }
        if(j < sz)
            arr[j] = arr[i];
        j--;
    }
}

方法簡單不會出錯即可

有時候我會拘泥於比較複雜的方法，導致不容易寫出正確的程式。仔細想想，就跟上面的心得一樣，有時候正確性會比酷炫的方法或是浪費space的方法還重要。甚至暴力破解也會比沒解法或是解法錯誤來的好。

143. Reorder List

重新排列list從原本的L0->L1->L2->L3 變成 L0->L3->L1->L2

一開始我想用recursive來做，但是過於複雜容易寫出錯的程式碼。
其實只要用stack把node全部存起來，就會有簡單的解法。

void reorderList(ListNode* head) {
    ListNode *p = head, *np;
    stack<ListNode *> st;
    while(p) {
        st.push(p);
        p = p->next;
    }
        
    p = head;
    for(int i = st.size() / 2; i > 0; --i) {
        np = p->next;
        p->next = st.top(); st.pop();
        p->next->next = np;
        p = np;
    }
    p->next = nullptr;
}

想想答案的反向

有時候很難想出一個好的解法，其實可以想想反向答案。

918. Maximum Sum Circular Subarray

找出最大的subarray(連續的元素)和。因為是circular所以可以接到前面，只要元素不重疊。

最大subarray和，且可以接到circular等於是找出最小的subarray和。
(max subarry sum) = total - (min subarray sum)

graphic solution

int maxSubarraySumCircular(vector<int>& nums) {
    int total, maxsum , curmax, minsum, curmin;
    total = maxsum = curmax = minsum = curmin = nums[0];
    for(int i = 1; i < nums.size(); ++i) {
        curmax = max(curmax + nums[i], nums[i]);
        maxsum = max(maxsum, curmax);
        curmin = min(curmin + nums[i], nums[i]);
        minsum = min(minsum, curmin);
        total += nums[i];
    }
    // 因為如果maxsum為負數，minsum會更負。導致total - minsum會更大
    return maxsum > 0 ? max(maxsum, total - minsum) : maxsum;
}

1658. Minimum Operations to Reduce X to Zero

一開始看到了minimum operrations，就使用了DP結果TLE。看了hints，因為只能從最左和最右刪除，所以最後只會剩下subarray，所以問題就可變成找出最長的subarray，則sz - subarray.size() 就會是minimal operations。

下面的解法是用prefix sum + hash table。
time complexity : $O(N)$
space complexity : $O(N)$

int minOperations(vector<int>& nums, int x) {
    int sz = nums.size();
    int total = accumulate(nums.begin(), nums.end(), 0);
    if(x > total) return -1;
    if(x == total) return sz;
    int target = total - x;
    unordered_map<int, int> m;
    m[0] = -1;
    int sum = 0, maxlen = 0;
    for(int i = 0; i < sz; ++i) {
        sum += nums[i];
        if(sum >= target && m.count(sum - target))
                maxlen = max(maxlen, i - m[sum - target]);
        m[sum] = i;
    }
    return maxlen > 0 ? sz - maxlen : -1;
}

以下是two points的解法，個人覺得應該比prefix sum還慢但是leetcode判斷出來是比較快。

int minOperations(vector<int>& nums, int x) {
    int sz = nums.size();
    int total = accumulate(nums.begin(), nums.end(), 0);
    if(x > total) return -1;
    if(x == total) return sz;
    int target = total - x, left = 0, sum = 0, maxlen = 0;
    for(int right = 0; right < sz; ++right) {
        sum += nums[right];
        while(sum > target)
            sum -= nums[left++];
        if(sum == target)
            maxlen = max(maxlen, right - left + 1);
    }
    return maxlen > 0 ? sz - maxlen : -1;
}

從沒有例外，推到題目的情況

665. Non-decreasing Array

給你一個vector，允許你修改一個數值，問這個vector是不是non-decreasing array(就是後面的數值只會大於等於前面的數值)。

先列出 non-decreasing array
判斷方法是nums[i] < nums[i - 1], 並且用一個cnt紀錄使否修改過。

int cnt = 0;
for(int i = 1; i < nums.size(); ++i) {
    if(nums[i] < nums[i - 1]) {
        if(cnt) return false;
        cnt++;
    }
}

有noise, 有一個點特別高或是特別低
特別低，就是移除nums[i]
特別高，就是移除nums[i - 1]，因為剛剛的判斷會在特別高的下一個點才發生。
從vector中移除element的成本很高，所以使用取代的
如果都是用nums[i] = nums[i - 1]來取代，會有一種special case，所以必須判斷nums[i - 2]是否小於等於nums[i]

bool checkPossibility(vector<int>& nums) {
    int cnt = 0;
    for(int i = 1; i < nums.size(); ++i) {
        if(nums[i] < nums[i - 1]) {
            if(cnt) return false;
            if(i == 1 || nums[i - 2] <= nums[i]) nums[i - 1] = nums[i];
            else nums[i] = nums[i - 1];
            cnt++;
        }
    }
    // time  : O(N)
    // space : O(1)
    return true;
}

拼湊題目要的答案

有時候題目要的答案不容易拼湊到，導致寫的程式碼過於奇怪，因為要一次就得到答案。其實只要有辦法拼湊回來，應該是先照程式方便寫的方向。

2096. Step-By-Step Directions From a Binary Tree Node to Another

先找出從root到startValue和destValue的path
移除從root到LCA的相同路徑
拼湊答案，start path轉換成連續的U，反轉dest path

bool find(TreeNode *root, int val, string& path) {
    if(!root) return false;
    if(root->val == val) return true;
    bool rtn = false;
    if(find(root->left, val, path)) {
        path.push_back('L');
        rtn = true;
    }
    if(find(root->right, val, path)) {
        path.push_back('R');
        rtn = true;
    }
    return rtn;
}
string getDirections(TreeNode* root, int startValue, int destValue) {
    string sp, dp;
    find(root, startValue, sp);
    find(root, destValue, dp);
    // remove the common part before LCA to root
    while(!sp.empty() && !dp.empty() && sp.back() == dp.back()) {
        sp.pop_back();
        dp.pop_back();
    }
    return string(sp.size(), 'U') + string(dp.rbegin(), dp.rend());
}

列出所有的case

當沒有頭緒的時候，可以列出所有可能的情況。幫助整理思緒。例如:838. Push Dominoes，列出所有可能的骨牌排列:

L...L 或是 R...R 兩邊都是一樣，則中間倒的方式一樣。
L...R 往兩邊倒，則中間不會改變。
R...L 往中間倒，根據中間點數長度，如果為偶數即為RRRLLL，如果為奇數，則為RRR.LLL。

所以程式碼如下:

string pushDominoes(string dominoes) {
    string rtn{""};
    string d = 'L' + dominoes + 'R';
    for(int i = 0, j = 1; j < d.size(); ++j) {
        if(d[j] == '.') continue;
        if(i > 0) rtn += d[i];
        int len = j - i - 1;
        // case 1
        if(d[i] == d[j]) rtn += string(len, d[i]);
        // case 2
        else if(d[i] == 'L' && d[j] == 'R') rtn += string(len, '.');
        // case 3
        else rtn += string(len / 2, 'R') + string(len % 2, '.') + string(len / 2, 'L');
        i = j;
    }
    return oss.str();
}