LeetCode 解題筆記

2551. Put Marbles in Bags =>Difficulty: Hard, Rating: 2042

Solution

創一個n-1的Table，用以記錄說要分割的位置在哪，並且會多出多少的Marbles保存下來後，先用Sort將其排序後，再由最末端往前，最前端往後互相扣除，及為所求。
其中因為Head, Tail均包含在min, max中，所以可以不用特別再去算。

















class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        vector<long long> res;
        int n = weights.size();
        long long ans = 0;

        for(int i = 1; i < n; i++)
            res.push_back(weights[i] + weights[i-1]);
        sort(res.begin(), res.end());

        for(int i = 0; i < k-1; i++)
            ans +=  res[n-i-2] - res[i];
        
        return ans;
    }
};

Time Complexity : O(N*logN), Space Complexity : O(N)

Solution 2

延續Solution 1，sorting的部分可以更快，所以可以用C++的library中nth_element、accumulate等函式，nth_element是排序第k個數字，使其前k-1個都比k小，後k+1個都比k大，就像是Quick sort中的partition，至於accumulate則是累加。


















class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        vector<long long> res;
        int n = weights.size();
        long long ans = 0;

        for(int i = 1; i < n; i++)
            res.push_back(weights[i] + weights[i-1]);
        
        nth_element(res.begin(), res.begin()+(k-1), res.end());
        ans -= accumulate(res.begin(), res.begin()+(k-1), 0LL);
        nth_element(res.begin(), res.end()-(k-1), res.end());
        ans += accumulate(res.end()-(k-1), res.end(), 0LL);
        
        return ans;
    }
};

Time Complexity : O(N), Space Complexity : O(N)

Solution 3

根據所給的提示可以改用Priority_Queue來儲存，一個存max、另一個存min，最後依次pop出來相減。























class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        if(k == 1)
            return 0;
        int n = weights.size();
        long long ans = 0;

        priority_queue<int> pq1; // Descending Order
        priority_queue<int, vector<int>, greater<int>> pq2; // Ascending Order

        for(int i = 0; i < n-1; i++){
            pq1.push(weights[i]+weights[i+1]);
            pq2.push(weights[i]+weights[i+1]);
        }

        for(int i = 0; i < k-1; i++){
            ans += pq1.top(), pq1.pop();
            ans -= pq2.top(), pq2.pop();
        }
        return ans;
    }   
};

Time Complexity : O(N*logK), Space Complexity : O(N)

Solution 4

Sorting的部分可以優化成Radix Sort，使其達到O(N)，空間只用了Constant time，再加上weight不需另外用一個矩陣來存，僅迭代後更新，砍掉最後一個多餘的，空間複雜度也會Down到O(1)，最後其餘與上述想法相同。









































class Solution {
public:

    const int BUCKET_SIZE = 256;
    const int MASK = 255;

    void Radix_Sort(vector<int> &nums){
        int n = nums.size();
        vector<int> buckets(BUCKET_SIZE);
        vector<int> temp(n);

        for(int i = 0; i < 32; i += 8){
            for(auto& it : nums)
                buckets[(it >> i) & MASK]++;
            for(int k = 0; k < BUCKET_SIZE-1; k++)
                buckets[k+1] += buckets[k];
            for(int k = n-1; k >= 0; k--)
                temp[--buckets[(nums[k] >> i) & MASK]] = nums[k];
            fill(buckets.begin(), buckets.end(), 0);
            nums.swap(temp);
        }
    }

    long long putMarbles(vector<int>& weights, int k) {
        if(k == 1)
            return 0;
        int n = weights.size();
        long long ans = 0;

        for(int i = 0; i < n-1; i++)
            weights[i] += weights[i+1];
        weights.pop_back();

        Radix_Sort(weights);

        for(int i = 0; i < k-1; i++)
            ans += weights[n-2-i] - weights[i];

        return ans;
    }   
};

Time Complexity : O(N), Space Complexity : O(1)

2873. Maximum Value of an Ordered Triplet I =>Difficulty: Easy, Rating: 1270

Solution 1

Hint給的方式，直接用暴力法找到i, j, k，並判斷是否為最大，但時間複雜度會較大。
















class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        long long Max = 0, t;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                for(int k = j+1; k < n; k++){
                    t = (long long)(nums[i]-nums[j])*nums[k];
                    Max = max(Max, t);
                }
            }
        }
        return Max;
    }
};

Time Complexity : O(N^3), Space Complexity : O(1)

Solution 2

這題有O(N)的解法，可以觀察到我們想要的是i < j < k，其中i, k越大越小，j則是越小越好，所以可以遍歷一次找到最大的max紀錄後鎖定，再繼續找到j使其nums[i]-nums[j]為最小同時也用max_diff紀錄，最後找到ｋ使其Value為最大。

















class Solution {
public:
    long long maximumTripletValue(vector<int>& nums) {
        int n = nums.size();
        long long max = 0, max_diff = 0, ans = 0;

        for(int i = 0; i < n; i++){
            if(max_diff*nums[i] > ans)
                ans = max_diff*nums[i];
            if(nums[i] > max)
                max = nums[i];
            else if(max-nums[i] > max_diff)
                max_diff = max-nums[i];
        }
        return ans;
    }
};

Time Complexity : O(N), Space Complexity : O(1)

2874. Maximum Value of an Ordered Triplet II =>Difficulty: Medium, Rating: 1583

Soultion 1

可使用上題2873的Solution 2可解，不過也可根據所給的Hints做出prefix, suffix max來紀錄目前走到可得最大的value，並且用for loop將所有可能計算過後便可得到最大值。
















class Solution{
    public:
        long long maximumTripletValue(vector<int>& nums){
            int n = nums.size();
            vector<int> prefix_max(n, 0), suffix_max(n, 0);
            prefix_max[0] = nums[0], suffix_max[0] = nums[n-1];
            for(int i = 1; i < n-1; i++){
                prefix_max[i] = max(prefix_max[i-1], nums[i]);
                suffix_max[i] = max(suffix_max[i-1], nums[n-i-1]);
            }
            long long ans = 0;
            for(int i = 1; i < n-1; i++)
                ans = max(ans, (long long)(prefix_max[i-1]-nums[i])*suffix_max[n-i-2]);
            return ans;
        }
};

Time Complexity : O(N), Space Complexity : O(N)

3272. Find the Count of Good Integers => Difficulty: Hard, Rating: 2382

Solution

要找N個位數中的隨意數字排列後剛好滿足該數字是迴文且可整除K e.g 10301(Yes), 1051(No)，2112重排可獲得1221，使其均滿足以上兩性質。
首先可以先鎖定位數的值域範圍內去尋找，像是N=6可以從100000~999999中找，不過這樣稍慢一點，可以利用palindromic的性質，可省下找非palindromic的時間，分割成兩段，另一段則是取reverse後再相加(注意奇偶不同)；同時也可用Hash Table(unordered_set)的方式來建立，避免了相同的數字不同的排列重複問題，最後用高中數學的排列組合計算出Permutation之個數後加入至答案中。












































class Solution {
public:
    long long countGoodIntegers(int n, int k) {
        long long ans = 0;
        vector<long long> factorial(n+1, 1);
        unordered_set<string> visited;

        for(int i = 1; i <= n; i++)
            factorial[i] = factorial[i-1]*i;

        int base = pow(10, (n-1)/2);
        string s, reverse_s, temp;

        for(int i = base; i < base*10; i++){
            s = to_string(i);
            reverse_s = s;
            reverse(reverse_s.begin(), reverse_s.end());
            s += reverse_s.substr(n % 2); 
            // if (odd) discard first, (even) get all, e.g. 106 => 10601, 1060 => 1060 + 0601.

            if(stoll(s) % k)
                continue;

            temp = s;
            sort(temp.begin(), temp.end());
            if(visited.count(temp)) // the number permutation has been calculated.
                continue;
            else{
                visited.insert(temp);
                vector<int> cnt(10, 0);
                for(auto c : temp)
                    cnt[c-'0']++;
                long long res = (n-cnt[0])*factorial[n-1];
                // because 0 can't be prefix, so that select first digits nonzero and Arrange the remaining.
                // => so (number of nonzero) * arrange remaining number. 
                // if digits not have 0, that will be face[n].
                for(auto i : cnt)
                    res /= factorial[i];
                ans += res;
            }
        }
        return ans;
    }
};

Time Complexity: O(10^m*n*lon(n)), Space Complexity: O(10^m*n), 其中m = floor((n-1)/2)

2537. Count the Number of Good Subarrays => Difficulty: Medium, Rating:1891

Solution

題意為給定一個Array,找出其中滿足K個Pairs的Subarray有多少個?
Subarray可以先聯想到Slide Windowns下手去判斷，首先可用Hash Table來儲存資料(unordered_map)，並可以發現Pairs的個數會是Combination當下X的個數取2種pair，不過同時也等於對於N個數的pairs有0+1+2+3+4+5…+n-1個數，由此可以將目前Windowns中所含的Pairs記錄下來(Line 10)，且注意是先加入後再++；若假設其中有一段Subarray已滿足題目需求，則此時可以知若能夠再往右擴張，即可增加N-Right個滿足條件的Subarray，此時將其加入到Ans當中(Line 13)，且將left也向右移動更新，計算更新少了nums[left]後的目前pairs數(Line 14、15)。
如此一來便能夠判斷所有可能的Value。
e.g.
Gievn: [3,1,4,3,3,3,2,2,4], k = 2
第一次找到為(3,1,4,3,3)，Pairs = 3，且後面加上四位數後也均符合條件 => ans+5
同時找到後移動left，查看left移動後的可能，此時Windowns = [1,4,3,3]，不滿足pairs >= k
於是繼續移動right，直到找到pairs滿足後，Pairs = 3，發現Windowns = [1,4,3,3,3]，加上後面三位也符合條件 => ans+4
且移動left，發現此時Pairs >= k，可以繼續移動left找到合法的子序列，將1的pairs減少，不過因為為0，所以pairs不受影響，並且Windowns = [4,3,3,3]，可將值將入其中，最後重複以上動作。























class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        unordered_map<int, int> counter;
        int n = nums.size();
        int left = 0, right = 0;
        long long pairs = 0LL, ans = 0LL;

        while(right < n){
            pairs += counter[nums[right]]++;

            while(pairs >= k){
                ans += (n-right);
                counter[nums[left]]--;
                pairs -= counter[nums[left]];
                left++;
            }
            right++;
        }

        return ans;
    }
};

Time Complexity: O(N), Space Complexity: O(N)

3439. Reschedule Meetings for Maximum Free Time I => Difficulty: Medium, Rating: 1728

Solution

可能第一時間看到題目會想不到是slide Window, 不過觀察到想要一個區間塊中最大休息時間，並可挪動左右的meeting時間，就聯想到把各個可休息的時間拉出來當作一個陣列，並從中找到Subarray使其休息時間最大，因為挪動一個meeting time會使兩端左右均有空隙休息，所以需要找到K+1的連續Subarray來使其得到最大值。
較簡單的做法當然是把空隙時間（gap）儲存一個陣列後再找出K+1=>length長的Max value Subarray，不過缺點是要花費O(N)空間去儲存。
當初是有想過能不能用O(1)的空間，僅用left, right pointer去維護，不過left會是小麻煩，如何找到left所在的位置？因為可能會有meeting time緊連接一起，使其沒有空隙時間，則該段區間不能當作left，須找到下一段有空隙時間的區段當作left；但或許是有方法，可將空間複雜度壓縮到O(1)。


























class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        int n = startTime.size(), ans = 0;
        vector<int> gap;

        if(startTime[0])
            gap.push_back(startTime[0]);

        for(int i = 1; i < n; i++)
            gap.push_back(startTime[i]-endTime[i-1]);
        if(eventTime - endTime[n-1])
            gap.push_back(eventTime - endTime[n-1]);
        
        int left = 0, temp = 0;
        for(int i = 0; i < gap.size(); i++){
            temp += gap[i];
            if(k >= 0)
                k--;
            else
                temp -= gap[left++];
            ans = max(ans, temp);
        }
        return ans;
    }
};

Time Complexity: O(N),Space Complexity: O(N), 其中Ｎ為startTime的個數，也就是meeting之個數，而非eventTime。

2444. Count Subarrays With Fixed Bounds => Difficulty:Hard, Rating: 2092

Solution

4/25的Medium甚至比今日(4/26)的Hard還難…
要求滿足最小與最大值區間的Subarray的個數，首先可以先用For Loop來找到Min、Max，同時友也維護一個InValid的變數，讓他為目前所概括範圍內，最靠右且不符合的數之位置，如此一來若是invalid的位置位在[Min, Max]or[Max, Min]之間的話，會目前計算的數不加入Ans之中(為負數)，但是一旦落在範圍之外則會計算到。
寫法的話是依照For Loop，一直向右擴張，同時保持紀錄Min、Max的位置，min(last_min, last_max)的原因是無法得知目前最可接受的數為Min or Max，但是要取得哪個位置之後，均是合法的範圍，至於InValid的位置若是超過min(last_min, last_max)則會使其變成負數，意為目前所概括的範圍內已有不合法的數字了(InValid)，如此遍歷一次矩陣，即可得到所求解。



















class Solution {
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        long long ans = 0;
        int last_min= -1, last_max = -1, invalid = -1;

        for(int i = 0; i < nums.size(); i++){
            if(nums[i] < minK || nums[i] > maxK)
                invalid = i;
            if(nums[i] == minK)
                last_min = i;
            if(nums[i] == maxK)
                last_max = i;
            
            ans += max(0, min(last_min, last_max) - invalid);
        }
        return ans;
    }
};

Time Complexity: O(N), Space Complexity: O(1)

649. Dota2 Senate => Difficulty: Medium, Rating: N/A

Solution

這題還蠻酷的，題意主要是有兩個黨派的人，在互相爭奪投票權，每個參議院的人每個回合都可選兩種操作擇一，一個是永久褫奪他黨其中一人的投票權，另一個則是在沒有他黨任何人仍具有投票權的情況下宣布勝利。

看到這題時，剛開始比較沒有想法，不過當時我是有考慮到用Queue來不斷地push下一輪仍會有投票權的人，不過這個方法可能不太行？會有當前與往後的關係要考慮；且還有褫奪投票權一定會盡量離當下最接近、接續自己之後敵對陣營的人，因為若褫奪前方已行使過權利的人會對己方不利、多給敵方一次行使權利的機會。

同時仔細想想後可以發覺，因為會有順序優先的問題，所以其實可以給每個人一個優先順序的號碼牌，號碼牌越小者優先度越高，若該回合沒有被褫奪投票權的話則可進階到下一輪，並且重新領號碼牌，反之被淘汰者就直接被刪除。

首先因為有兩個陣容，所以一定是要與當前敵對陣營來做比較，所以可以先建立2個Queue，並依順序給予號碼，同時每次都拿Queue中的前兩者來做比對，誰的號碼牌小，則會被重新Push到自己陣營的下一輪，且號碼牌大者被淘汰，如此一直循環，直到有一方陣營落敗(Queue is empty)，則代表已有贏家陣營。

















class Solution {
public:
    string predictPartyVictory(string senate) {
        queue<int> Radi, Dire;

        for(int i = 0; i < senate.size(); i++)
            senate[i] == 'R' ? Radi.push(i) : Dire.push(i);
        
        int k = senate.size();
        while(!Radi.empty() && !Dire.empty()){
            Radi.front() < Dire.front() ? Radi.push(k++) : Dire.push(k++);
            Radi.pop(), Dire.pop();
        }

        return Radi.empty() ? "Dire" : "Radiant";
    }
};

1466. Reorder Routes to Make All Paths Lead to the City Zero => Difficulty: Medium, Rating: 1633

Solution

題目為找改變幾條Edge後才可以使所有的Node均有Path到0節點。
首先可以創一個adjacency list，因為node之間必只有一個方向，所以可以對每個Edge標記（可想成當作無向圖處理，並同時利用±號來標記是否要反轉），若是0節點往別的node則該edge會為正數（因為需要被改變方向），若是負數則代表他有path到0節點，不斷如此遞迴下去，並加總其需要被改變的Edge。

總結的話就是，先視為無向圖，並且先標記邊是否需反轉(正數負數)，然後一邊DFS traversal一邊紀錄我需要有幾個需要被反轉的邊才能到達所有的點。























class Solution {
public:
    int DFS(vector<vector<int>>& gr, vector<bool>& visited, int from){
        int change = 0;
        visited[from] = true;
        for(auto& it : gr[from]){
            if(!visited[abs(it)])
                change += DFS(gr, visited, abs(it)) + (it >= 0);
        }
        return change;
    }
    int minReorder(int n, vector<vector<int>>& connections) {
        vector<bool> visited(n, false);
        vector<vector<int>> gr(n);

        for(auto &it : connections){
            gr[it[0]].push_back(it[1]);
            gr[it[1]].push_back(-it[0]);
        }

        return DFS(gr, visited, 0);
    }
};

Time Complexity: O(N), Space Complexity: O(N)

2858. Minimum Edge Reversals So Every Node Is Reachable => Difficulty: Hard, Rating: 2294

Solution

跟上題蠻像的，差別只在於對每個點都要求出需要反轉的邊數，暴力法每個node都去測的話是沒辦法過的，觀察一下可知其實每個Node與其相臨的Node的個數最多相差一而已（本題關鍵），因為若是知道對於上一個點，我總共需要多少次反轉邊後，對於相鄰的邊節點，必然只有一個的邊不同，並且不是多一個需反向的邊，否則就是少一個需反轉的邊。
由於知道了相鄰的節點，個數必為+1 or -1後，問題就簡單了，可以像上題先求出0節點需要反轉的個數後，再求所有與0節點有邊相鄰的點，並看連接的邊是需要+1還是-1，並記錄下來，並且遞迴下去，如此DFS一次所有的邊檢查後，即可求得解。









































class Solution {
public:
    int DFS(vector<vector<int>>& g, vector<bool>& visited, int from){
        int cnt = 0;
        visited[from] = true;
        for(auto & it : g[from]){
            if(!visited[abs(it)])
                cnt += DFS(g, visited, abs(it)) + (it <= 0);
        }
        return cnt;
    };

    void find(vector<vector<int>>& g, vector<bool>& visited, vector<int>& ans, int from){
        visited[from] = true;
        for(auto & it : g[from]){
            if(!visited[abs(it)]){
                int temp = it > 0 ? 1 : -1;
                ans[abs(it)] = ans[from] + temp;
                find(g, visited, ans, abs(it));
            }
        }
    };

    vector<int> minEdgeReversals(int n, vector<vector<int>>& edges) {
        vector<vector<int>> g(n);
        vector<bool> visited(n, false);
        vector<int> ans(n, 0);

        for(auto & it : edges){
            g[it[0]].emplace_back(it[1]);
            g[it[1]].emplace_back(-it[0]);
        }
        ans[0] = DFS(g, visited, 0);

        fill(visited.begin(), visited.end(), false);
        find(g, visited, ans, 0);


        return ans;
    }
};

Time Complexity: O(N), Space Complexity: O(N)

3343. Count Number of Balanced Permutations => Difficulty: Hard, Rating: 2614

Solution

DP加上組合數學的題目。
先部分解釋一下各部分的意義，首先是先將階層以及反階層先計算好儲存在Table之中，如同註解中的內容，inverse是為了計算inverse_factorial，而inverse_factorial則是為了組合數學中，為了要扣除重覆計算部分時要除的階層數，其中若是單純使用除法效能會比較很低；在模數中可以使用乘法反元素來去加快(Line:17-23, 53)，如下例子:

$\frac{x}{y} \mod m \equiv x \cdot y^{- 1} \mod m$

$10 \cdot 2^{- 1} \equiv \frac{10}{2} \mod 13, 2^{- 1} \equiv 7 \mod 13$

回到主題部分，因為題目所求為給定數字排列後，奇數位置與偶數位置總和相等之排列個數，所以可知若這個條件要成立，總和必能是偶數，否則排列後不可能可以分成兩部分(Line:30-33)。
要重複利用已經算過的資訊，可以用DP來避免掉重複的運算，其中利用Bottom-Up的方式就可以確保每個每個字母都只會被計算過一次，並每次更新組合數為目前已有的組合數，加上長度減一且總和減掉目前的Digits的紀錄，最後能夠得知要在長度為固定及總和固定的組合數中取得答案。
不要忘記因為可能會有重複問題，所以要除以重複數字的階層，且除法因為在模數中，所以可以用乘法反元素去替代除法來做更有效率的運算。
$d p [i] [j] = 從給定數字中選出 j 個，使得總和為 i 的組合數。 0 \leq i \leq h a l f S u m, 0 \leq j \leq h a l f L e n$

























































class Solution {
public:
    static const int MOD = 1e9+7;
    vector<long long> factorial, inverse, inverse_factorial;

    /*
    factorial[i] : Stores i! mod
    inverse[i] : stores the modular inverse of i
    inverse_factorial[i] : stores (i !)−1 mod
    */

    void precomputing(int n){
        factorial.assign(n+1, 1);
        for(int i = 2; i <= n; i++)
            factorial[i] = (factorial[i-1]*i) % MOD;

        inverse.assign(n+1, 1);
        for(int i = 2; i <= n; i++)
            inverse[i] = MOD - (MOD / i) * inverse[MOD%i] % MOD;

        inverse_factorial.assign(n+1, 1);
        for(int i = 1; i <= n; i++)
            inverse_factorial[i] = inverse_factorial[i-1] * inverse[i] % MOD;
    }

    int countBalancedPermutations(string num) {
        int sum = 0, n = num.size();

        precomputing(n);
        for(auto & c : num)
            sum += c - '0';
        if(sum & 1)
            return 0;

        int half_sum = sum / 2, half_length = n/2;
        vector<vector<int>> dp(half_sum+1, vector<int>(half_length+1));

        vector<int> digits(10, 0);
        dp[0][0] = 1;
        
        for(auto & c : num){
            int d = c - '0';
            ++digits[d];
            for(int i = half_sum; i >= d; i--){
                for(int j = half_length; j > 0; j--)
                    dp[i][j] = (dp[i][j] + dp[i-d][j-1]) % MOD;
            }
        }
        long long res = dp[half_sum][half_length];
        res = res * factorial[half_length] % MOD * factorial[n-half_length] % MOD;

        for(auto & it : digits)
            res = res * inverse_factorial[it] % MOD;
        
        return res;
    }
};

Time Complexity: O(S * n²)，其中 S 為數字總和的一半，n 為字串長度
Space Complexity: O(S * n)（DP 表） + O(n)（階乘表）

1931. Painting a Grid With Three Different Colors => Difficulty: Hard, Rating: 2170

Solution

本題題意上蠻簡單的，就是給你MxN的girds，要填入三種Red, Green, Blue不同顏色，且每個Block上都不會有相同顏色相臨，等同於三著色問題的個數而已。
這題比較巧妙的地方是可以看到他的Constraints的M最多只有5而已，所以可以針對這部分去下手，大致整體的想法是可以先算出一整行可以填入的可能性，加上一行在限制上也最多5格而已，所以數字不會太大，像是程式碼Line:9基本上就是先確定給定M後一行最多的數目，這邊因為最多5而已，所以五個填入三種數字的可能性為
$3^{5} 種 = 243$ 。
Line:12~26的部分是狀態壓縮+儲存其可行的組合(Good)，RGB三種顏色的話可以用三進位來表示，像是
$P a t t e r n [i] [j], i r e p r e s e n t t o P o s s i b l e C o m b i n a t i o n s, j i s t h i s c o l o r s .$ ，若舉實際例子的話像是:

0 = Red, 1 = Green, 2 = Blue; m = 4
則代表總共會有3^4=81種可能，像是其中像是第4種可能的數字為=>0012(R,R,G,B)
第72種可能的數字為=>2200(B,B,R,R)…以此類推

壓縮過後會將每格的所代表顏色(數值0,1,2)填入pattern[i]中的第j個位置，也Line:16、17所做的事，其中還要去檢查相鄰的位置中是否有相同的顏色，若是將該列的可能性都檢查過後，發現是合法的行排列，則會將其放入到Good矩陣之中。
前面只有檢查過列的部分，後面Line:28~37的部分則是檢查對於任兩行是否可以擺再一起，用兩個For Loop去對每個元素都做檢查Pattern[第i個的排列下][第k個元素]是否也等於Pattern[第j個的排列下][第k個元素]，並用row_valid來記錄下任意i, j兩個行是否相容。
Line38~49則是用DP來記錄下目前第i種排列中有j行之可能個數，Line39、40只是初始化對於一開始第一種排列下僅會有一種方法，後面則是要由一行一行去推導增加，若上一列的 pattern 是 j，而當前列選擇 pattern i 是合法的，那麼從 j 延伸到 i 是一種合法的情況，我們要把這種情況的數量累加進來，過程中記得要取餘數，如此推導下去會得到最後第DP[第i種排列可能下][從1~j行]之可能的個數。
最後因為有Good.size()種可能，並全部做加總起來後即為所求。

Code
























































class Solution {
public:
    const int MOD = 1e9 + 7;
    int colorTheGrid(int m, int n) {
        // Since M in the constraint is small, we start counting from the rows.
        vector<int> pattern[243], good;
        int cols_total = 1; // for each columns possible count.
        for (int i = 0; i < m; ++i) 
            cols_total *= 3;


        bool valid;
        for(int i = 0; i < cols_total; i++){
            int val = i;
            valid = true;
            for(int j = 0; j < m; j++)
                pattern[i].push_back(val % 3), val /= 3;
            for(int j = 1; j < m; j++){
                if(pattern[i][j] == pattern[i][j-1]){
                    valid = false;
                    break;
                }
            }
            if(valid)
                good.push_back(i);
        }

        bool row_valid[243][243];
        for(int & i : good){
            for(int & j : good){
                row_valid[i][j] = true;
                for(int k = 0; k < m; k++){
                    if(pattern[i][k] == pattern[j][k])
                        row_valid[i][j] = false;
                }
            }
        }
        int dp[243][1001] = {0};
        for(int & i : good)
            dp[i][1] = 1;

        for(int cols = 2; cols <= n; cols++){
            for(int & i : good){
                for(int & j : good){
                    if(row_valid[i][j])
                        dp[i][cols] = (dp[i][cols] + dp[j][cols-1]) % MOD;
                }
            }
        }
        long long ans = 0;
        for(auto i : good)
            ans = (ans + dp[i][n]) % MOD;

        return ans;
    }
};

Time Complexity:

$O (N \cdot 3^{2 M})$ , Space Complexity:
$O ((n + m) \cdot 3^{m} + 9^{m})$

3551. Minimum Swaps to Sort by Digit Sum => Difficulty: Medium, Rating: N/A

Solution

這題是本週賽的Q2，題意基本上就是重新以每個數digits的總和為Sorting的依據，並在排序過程中求所需的最小次數。
一開始我的做法是聯想要Swap次數最小的話到可用Select Sorting來去模擬一下排序的過程，但後來提交的時候發現TLE了，我想可能時間複雜度至少要壓到
$O (N \cdot l o g N)$ 以下吧；後來才發現其實可以用Cycle decomposition，去判別Cycle的個數扣掉一之後即為Swap的個數，如此只需要用內建的Sorting去排列後，並記下原本位置的資訊再與其比對Cycle，即可得到所求。

Code
































class Solution {
public:
    int minSwaps(vector<int>& nums) {
        vector<pair<pair<int, int>, int>> v;
        for(int i = 0; i < nums.size(); i++){
            int temp = nums[i], sum = 0;
            while(temp)
                sum += temp % 10, temp /= 10;
            v.push_back({{sum, nums[i]}, i});
        }

        sort(v.begin(), v.end());
        vector<bool> visited(nums.size(), false);

        int ans = 0;
        for(int i = 0; i < nums.size(); i++){
            if(visited[i] || v[i].second == i)
                continue;
            int c = 0, j = i;
            while(!visited[j]){
                visited[j] = true;
                j = v[j].second;
                c++;
            }
            if(c > 1)
                ans += c-1;
        }
        
        return ans;
    }
};
// [8,12,92,57,3,111] shoudle be 4

Time Complexity:

$O (N \cdot \log N)$ , Space Complexity:
$O (N)$

3362. Zero Array Transformation III => Difficulty: Medium, Rating: 2423

Soltion

這題感覺也不像Medium，Rating有2423就感覺已經是Hard了，先說說核心想法，就是可以利用Greedy+Difference Array，另外因為要找出最多可以Remove的數，所以可以Soting後再用Priority Queue來做篩選。
廢話不多說，直接看程式碼，Sorting的目的是為了等等取出符合條件的queries是盡可能地最小，原先vector[0]的東西就會排列了，如果vector[0]的Value相等的話則會用Vector[1]的值再作排列，目的就是要先pop出剛好符合當下情況，並且可以利用最少的queries數，舉個例子:

若先考慮0的位置，當下nums[0] = 1，則有兩個queries分別為(0, 5), (0, 3), (0, 1)，若可以的話我們會選擇(0, 5)這個queries而捨棄掉(0, 3)和(0, 1)queries。

我們可以針對每個nums[i]的值來看，判斷是否有滿足到queries能夠使其為ZeroArray，首先sum就是所謂的prefix_sum，用來記下Difference Array的當下累積數；(Line:12)是用來判斷說，以當下的位置i，queries可以先走到哪個位置，先將其目前有累積到的Value加入到Priority Queue，並且Priority Queue會可以用來pop出目前最大的值(因為會待在PQ之中的都會是可被刪除的queries)，(Line:16)則是代表說目前符合條件的queries則會先被pop出去，同時也紀錄下當前的prefix_sum，同時也做Differnece Array的事情，至於那些可能不會被pop出去的queries則是代表它們目前的值已經超過nums[i]。
(Line:22)的則是不同意思，指若是當前queue為空但是又沒有足夠的queries能夠使nums[i]的值扣到0，則就是不可能有ZeroArray了，這邊可以自己實際舉個例子跑跑看，只能說程式碼我覺得寫得蠻妙的，像是若while迴圈跑完後發現現在剛好滿足sum == nums[i]，則他不會繼續跑第二個while loop也不會跑if loop，而是直接往下一個nums[i+1]去判斷，我當下寫也是寫不出這麼漂亮的架構。

Code



























class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        sort(queries.begin(), queries.end());
        priority_queue<int> pq;
        int n = nums.size();

        vector<int> diff(n + 1, 0);
        int sum = 0, j = 0;
        for (int i = 0; i < n; i++) {
            sum += diff[i];
            while(j < queries.size() && queries[j][0] <= i){
                pq.push(queries[j][1]);
                j++;
            }
            while(sum < nums[i] && !pq.empty() && pq.top() >= i){
                sum++;
                int end = pq.top();
                pq.pop();
                --diff[end+1];
            }
            if(sum < nums[i])
                return -1;
        }
        return pq.size();
    }
};

Time Complexity:

$O (N + M + M \cdot \log M)$ , Space Complexity:
$O (N + M)$ , N = nums.size(), M = queries.size()

3557. Find Maximum Number of Non Intersecting Substrings => Difficulty: Medium, Rating: N/A

Solution 1

老實講這題我一開始吃蠻多WA的，一開始直接用直接兩個for loop去找每個i最短的pair，結果就是TLE，然後又用把它想成activity selection problem，結果就是WA。
回到正題，這解法蠻酷的，我也是參照別人的解答，基本上能夠在One Pass做完整個運算，概念上就是Greedy，一邊選目前可行的pair，並且一邊判斷目前是否滿足，若滿足的話則清除之前紀錄過的alphabet，這樣選出來的能夠確保他是截至目前走到第i個位置最多的pair數。
並且alphabet[x] = k，其中x是目前紀錄的字元，k為目前該字元的上一個位置在哪，i - alphabet[x] + 1 >= 4則是確保其長度至少要為四。

Code





















class Solution {
public:
    int maxSubstrings(string word) {
        int n = word.size(), ans = 0;
        vector<int> alphabet(26, -1);

        for(int i = 0; i < n; i++){
            int x = word[i]-'a';
            if(alphabet[x] != -1 && i - alphabet[x] + 1 >= 4){
                ans++;
                fill(alphabet.begin(), alphabet.end(), -1);
            }
            else{
                if(alphabet[x] == -1)
                    alphabet[x] = i;
            }

        }
        return ans;
    }
};

Time Complexity:

$O (26 \cdot N)$ , Space Complexity:
$O (26)$

3568. Minimum Moves to Clean the Classroom => Difficulty:Medium, Rating: N/A

Solution

這題是Q3週賽題，不過我沒有解出來，只能說我超爛QAQ

題意為給予起點，L位置為垃圾(Litter)位置，X位置代表該位置不可通過，R位置為可以補充滿能量(Energy)，每走到另一個位置都會花費一個能量值，若是能量值歸零則無法再繼續往前，另外題目會給予能量值，所求為從起點開始，能量不歸零且能收集完所有垃圾最少需要之步數；另外對於一些走過的點可以重複再走，只要能量還夠。
基本上是可以想到用BFS去遍歷，不過因為他有很多限制，像是能量值，還有可以重複去走等等，所以要從中修改並記錄一些訊息。像是因為題目限制有說L的數量最多十種，所以我們可以先從這裡下手。
首先L最多只有10，所以BFS的queue之中也要儲存目前已經撿拾過垃圾的資訊，其中若是另外在用位置以及個數會有點太龐大，所以可以利用bitmask的技巧，因為其最多只有
$2^{10} = 1024$ 個，而且可以用第幾個bit是否為1來紀錄是否已經被撿拾過，所以(Line:11-20)主要是來紀錄他是第幾個Litter和位置，還有找尋起點
因為目的是要clean all Litter，所以如果全部都被清除的話則代表所有bit都是1，若是找到則回傳。
$D i s t [i] [j] [e] [m] a n d Q u e u e [i] [j] [e] [m]$ ，其中i, j為目前的row, and col，而e則是目前還有的Energy，m則是目前mask的狀態。
基本上剩下就是BFS基本操作了，檢查四個方向還有邊界條件、目前的cell的內容為何，做何更新而已，拾起垃圾的話只是把mask中該位置的index做or設定為1。更新新位置是否要放進Queue也是判斷是否沒有被遍歷過或是目前有更短的路徑可以達到再去做更新。














































































class Solution {
public:
    const int dir[5] = {0, 1, 0, -1, 0};
    int minMoves(vector<string>& classroom, int energy) {
        int rows = classroom.size(), cols = classroom[0].size();
        int start_r = -1, start_c = -1;

        vector<pair<int, int>> litter_coords;
        map<pair<int, int>, int> litter_coords_idx_map;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (classroom[i][j] == 'S') {
                    start_r = i, start_c = j;
                } else if (classroom[i][j] == 'L') {
                    litter_coords_idx_map[{i, j}] = litter_coords.size();
                    litter_coords.push_back({i, j});
                }
            }
        }

        int nums_litter = litter_coords.size();
        if (nums_litter == 0)
            return 0;

        int target_mask = (1 << nums_litter) - 1;

        vector<vector<vector<vector<int>>>> dist(
            rows, vector<vector<vector<int>>>(
                cols, vector<vector<int>>(
                    energy + 1, vector<int>(1 << nums_litter, -1))));

        queue<tuple<int, int, int, int>> q;

        dist[start_r][start_c][energy][0] = 0;
        q.push({start_r, start_c, energy, 0});

        while (!q.empty()) {
            auto [r, c, cur_energy, mask] = q.front();
            q.pop();

            int moves = dist[r][c][cur_energy][mask];

            if (mask == target_mask)
                return moves;

            for (int i = 0; i < 4; i++) {
                int now_r = r + dir[i];
                int now_c = c + dir[i + 1];

                if (now_r >= 0 && now_r < rows && now_c >= 0 && now_c < cols &&
                    classroom[now_r][now_c] != 'X' && cur_energy > 0) {
                    int new_energy = cur_energy - 1;
                    int next_moves = moves + 1;

                    int new_mask = mask;
                    char new_cell = classroom[now_r][now_c];

                    if (new_cell == 'L') {
                        int litter_idx = litter_coords_idx_map[{now_r, now_c}];
                        new_mask |= (1 << litter_idx);
                    }

                    if (new_cell == 'R')
                        new_energy = energy;

                    if (dist[now_r][now_c][new_energy][new_mask] == -1 ||
                        next_moves < dist[now_r][now_c][new_energy][new_mask]) {
                        dist[now_r][now_c][new_energy][new_mask] = next_moves;
                        q.push({now_r, now_c, new_energy, new_mask});
                    }
                }
            }
        }

        return -1;
    }
};

Time Complexity:

$O (R o w s \times C o l s \times E n e r g y \times 2^{n u m b e r o f L i t t e r})$
Space Complexity :
$O (R o w s \times C o l s \times E n e r g y \times 2^{n u m b e r o f L i t t e r})$

$w h e r e R o w s, C o l s \leq 20, E n e r g y \leq 50, n u m b e r o f L i t t e r \leq 10$

LeetCode 解題筆記

2551. Put Marbles in Bags =>Difficulty: Hard, Rating: 2042

Solution

Solution 2

Solution 3

Solution 4

2873. Maximum Value of an Ordered Triplet I =>Difficulty: Easy, Rating: 1270

Solution 1

Solution 2

2874. Maximum Value of an Ordered Triplet II =>Difficulty: Medium, Rating: 1583

Soultion 1

3272. Find the Count of Good Integers => Difficulty: Hard, Rating: 2382

Solution

2537. Count the Number of Good Subarrays => Difficulty: Medium, Rating:1891

Solution

3439. Reschedule Meetings for Maximum Free Time I => Difficulty: Medium, Rating: 1728

Solution

2444. Count Subarrays With Fixed Bounds => Difficulty:Hard, Rating: 2092

Solution

649. Dota2 Senate => Difficulty: Medium, Rating: N/A

Solution

1466. Reorder Routes to Make All Paths Lead to the City Zero => Difficulty: Medium, Rating: 1633

Solution

2858. Minimum Edge Reversals So Every Node Is Reachable => Difficulty: Hard, Rating: 2294

Solution

3343. Count Number of Balanced Permutations => Difficulty: Hard, Rating: 2614

Solution

1931. Painting a Grid With Three Different Colors => Difficulty: Hard, Rating: 2170

Solution

Code

3551. Minimum Swaps to Sort by Digit Sum => Difficulty: Medium, Rating: N/A

Solution

Code

3362. Zero Array Transformation III => Difficulty: Medium, Rating: 2423

Soltion

Code

3557. Find Maximum Number of Non Intersecting Substrings => Difficulty: Medium, Rating: N/A

Solution 1

Code

3568. Minimum Moves to Clean the Classroom => Difficulty:Medium, Rating: N/A

Solution

Read more

Department of Computer Science & Information Engineering

Algorithms 筆記

Operating System --Question&MyAnswer

SQLMAP學習