Algorithms & Data Structures : Array Problems

Problems

LeetCode 56. Merge Intervals

LeetCode 2016. Maximum Difference Between Increasing Elements

LeetCode 2013. Detect Squares

LeetCode 2018. Check if Word Can Be Placed In Crossword

LeetCode 1182. Shortest Distance to Target Color
[Array]

LeetCode 251. Flatten 2D Vector
[Array]

LeetCode : 2268. Minimum Number of Keypresses
[Array]

LeetCode : 2257. Count Unguarded Cells in the Grid
[Array]

LeetCode : 1424. Diagonal Traverse II
[Array][sorting]

LeetCode : 2087. Minimum Cost Homecoming of a Robot in a Grid
[Array][Greedy]

LeetCode : 2201. Count Artifacts That Can Be Extracted
[Array][hash table]

LeetCode : 2274. Maximum Consecutive Floors Without Special Floors
[array][sorting]

LeetCode : 1855. Maximum Distance Between a Pair of Values
[array][two-pointers]

LeetCode : 2105. Watering Plants II
[array][two-pointers]

LeetCode : 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit
[array][ordered set][monotonic queue]

LeetCode : 2012. Sum of Beauty in the Array
[array][dynamic programming]

LeetCode : 2261. K Divisible Elements Subarrays
[array][trie]

LeetCode : 2365. Task Scheduler II
[Array][Simulation][Hash Table]

LeetCode : 848. Shifting Letters
[Array][String]

LeetCode : 822. Card Flipping Game
[Array]

LeetCode : 2391. Minimum Amount of Time to Collect Garbage
[Array]

LeetCode : 1868. Product of Two Run-Length Encoded Arrays
[Array][Two Pointers]

LeetCode : 1060. Missing Element in Sorted Array
[Array][Binary Search]

LeetCode : 2061. Number of Spaces Cleaning Robot Cleaned
[Array][Simulation][Matrix]

LeetCode : 2405. Optimal Partition of String
[Array]

LeetCode : 2270. Number of Ways to Split Array
[Array][Prefix Sum]

LeetCode : 2090. K Radius Subarray Averages
[Array][Sliding Window]

LeetCode : 218. The Skyline Problem
[Hard][Array][Line Sweep][Divide and Conquer]
[Binary Indexed Tree][Segment Tree][Heap ( Priority Queue )]
[Ordered Set]

LeetCode : 2424. Longest Uploaded Prefix
[Array][Binary Search][Union Find][Design]
[Binary Indexed Tree][Segment Tree]
[Heap (Priority Queue)][Ordered Set]

LeetCode : 16. 3Sum Closest
[Array][Two Pointers][Sorting]

LeetCode : 334. Increasing Triplet Subsequence
[Array][Greedy]

LeetCode : 1995. Count Special Quadruplets
[Array]

LeetCode : 2462. Total Cost to Hire K Workers
[Array][Two Pointers][Heap (Priority Queue)][Ordered Map]

LeetCode : 2078. Two Furthest Houses With Different Colors
[Array][Greedy]

LeetCode : 2210. Count Hills and Valleys in an Array
[Array]

LeetCode : 2229. Check if an Array Is Consecutive
[Array]

LeetCode : 2482. Difference Between Ones and Zeros in Row and Column
[Array]

LeetCode : 2350. Shortest Impossible Sequence of Rolls
[Array][Greedy][Hash Table][Hard]

LeetCode : 2502. Design Memory Allocator
[Array]

LeetCode : 2511. Maximum Enemy Forts That Can Be Captured
[Easy][Array]

LeetCode : 2555. Maximize Win From Two Segments
[Medium][Array][Queue][Sliding Window][Binary Search]

LeetCode 56. Merge Intervals

假如有重疊，就記下左邊界與右邊界
假如不重疊，就將紀錄的左邊界與右邊界丟到 vector裡

class Solution {
public:    
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        vector<vector<int>> sorted = intervals;
        sort(sorted.begin(), sorted.end());
        
        int minVal = INT_MAX;
        int maxVal = INT_MIN;
        for(int i = 0;i < sorted.size();i++) {
            if(minVal == INT_MAX) {
                minVal = sorted[i][0];
                maxVal = sorted[i][1];
            } else {
                if(maxVal >= sorted[i][0]) {
                    // overlap
                    minVal = min(minVal, sorted[i][0]);
                    maxVal = max(maxVal, sorted[i][1]);
                } else {
                    res.push_back({minVal, maxVal});
                    minVal = sorted[i][0];
                    maxVal = sorted[i][1];
                }
            }
        }
        
        if(res.size() == 0 || res.back()[0] != minVal) {
            res.push_back({minVal, maxVal});
        }
        
        return res;
    }
};

LeetCode 2016. Maximum Difference Between Increasing Elements

由右往左，一邊紀錄當前最大值，一邊求解。

class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int res = -1;
        int maxVal = INT_MIN;
        for(int i = nums.size() - 1;i >= 0;i--) {
            if(maxVal != INT_MIN && maxVal != nums[i]) {
                res = max(res, maxVal - nums[i]);
            }
            maxVal = max(maxVal, nums[i]);
        } 
        return res;
    }
};

LeetCode 2013. Detect Squares

無腦暴力解… 所以效能很差。
TODO : 優化看看，或是看其他人怎麼解

class DetectSquares {
private:
    vector<vector<int>> panel;
public:
    
    DetectSquares() {
        panel = vector<vector<int>>(1001, vector<int>(1001, 0));
    }
    
    void add(vector<int> point) {
        panel[point[0]][point[1]]++;
    }
    
    int count(vector<int> point) {
        int ans = 0;
        for(int i = 0;i < panel.size();i++) {
            if(i == point[0]) {
                continue;
            }
            
            if(panel[i][point[1]] > 0) {
                int len = i - point[0];                
                // Upper
                if(point[1] + abs(len) <= 1000 && 
                   panel[i][point[1] + abs(len)] > 0 &&
                   panel[point[0]][point[1] + abs(len)] > 0) {
                    int tmp = 1;
                    tmp *= panel[i][point[1]];
                    tmp *= panel[i][point[1] + abs(len)];
                    tmp *= panel[point[0]][point[1] + abs(len)];
                    ans += tmp;
                }
                
                // Lower
                if(point[1] - abs(len) >= 0 &&
                   panel[i][point[1] - abs(len)] > 0 &&
                   panel[point[0]][point[1] - abs(len)] > 0) {
                    int tmp = 1;
                    tmp *= panel[i][point[1]];
                    tmp *= panel[i][point[1] - abs(len)];
                    tmp *= panel[point[0]][point[1] - abs(len)];
                    ans += tmp;
                }
            }
        }
        return ans;
    }
};
/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares* obj = new DetectSquares();
 * obj->add(point);
 * int param_2 = obj->count(point);
 */

LeetCode 2018. Check if Word Can Be Placed In Crossword

簡而言之就是暴力解。

TODO : 在複雜度上理應會 TLE，看有沒有辦法壓低複雜度，或是參考別人的寫法。

// 只有最端點的格子需要進行字串的比對
// 1. 遍尋所有格子，找出每一個端點，以及字串可進行比對的方向 
// 2. 就每個可比對的格子，以及其方向進行比對
typedef enum {
    UP,
    DOWN,
    LEFT,
    RIGHT
} DIRECTION;
class Solution {
private:
    // 
    int X[4] = {-1, 1, 0, 0};
    int Y[4] = {0, 0, -1, 1};
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        for(int i = 0;i < board.size();i++) {
            for(int j = 0;j < board[0].size();j++) {
                if('#' != board[i][j]) {
                    for(int q = 0;q < 4;q++) {
                        int newx = i + X[q];
                        int newy = j + Y[q];
                        int tmpx = i;
                        int tmpy = j;
                        if(newx >= board.size() || newx < 0 ||
                           newy >= board[0].size() || newy < 0 ||
                           '#' == board[newx][newy]) {
                            
                            int num = 0;
                            while(tmpx >= 0 && tmpx < board.size() &&
                                tmpy >= 0 && tmpy < board[0].size() &&
                                '#' != board[tmpx][tmpy]) {
                                
                                if(num == word.size()) {
                                    // 空格超出字串長度
                                    // 故意把 num 用錯
                                    num = -1;
                                    break;
                                }
                                
                                if(' ' == board[tmpx][tmpy] ||
                                   word[num] == board[tmpx][tmpy]) {
                                    num++;
                                } else {
                                    num = -1;
                                    break;
                                }
                                
                                if(UP == q) {
                                    // 字串要往 DOWN 的方向進行比對
                                    tmpx += X[DOWN];
                                    tmpy += Y[DOWN];
                                } else if(DOWN == q) {
                                    // 字串要往 UP 的方向進行比對
                                    tmpx += X[UP];
                                    tmpy += Y[UP];
                                } else if(LEFT == q) {
                                    // 字串要往 RIGHT 的方向進行比對
                                    tmpx += X[RIGHT];
                                    tmpy += Y[RIGHT];
                                } else if(RIGHT == q) {
                                    // 字串要往 LEFT 的方向進行比對
                                    tmpx += X[LEFT];
                                    tmpy += Y[LEFT];
                                }       
                            }
                            
                            if(num == word.size()) {
                                return true;
                            }
                        }
                        
                    }
                }
            }
        }
        
        return false;
    }
};

LeetCode 1182. Shortest Distance to Target Color

由左往右處理一次，再由右往左處理一次。

class Solution {
public:
    vector<int> shortestDistanceColor(vector<int>& colors, vector<vector<int>>& queries) {
        vector<int> v;
        vector<vector<int>> rec = vector<vector<int>>(colors.size(), vector<int>(3, -1));
        vector<int> tmp = vector<int>(3, -1);
        
        
        for(int i = 0;i < colors.size();i++) {
            for(int j = 0;j < tmp.size();j++) {
                if(-1 == tmp[j]) {
                    
                } else {
                    tmp[j]++;
                }
                if(colors[i % colors.size()] - 1 == j) {
                    tmp[j] = 0;
                }
            }
            
            for(int j = 0;j < tmp.size();j++) {
                if(-1 != tmp[j]) {
                    if(-1 == rec[i][j]) {
                        rec[i][j] = tmp[j];
                    } else {
                        rec[i][j] = min(rec[i][j], tmp[j]); 
                    }
                }
            }
            
        }
        
        for(int i = colors.size() - 1;i >= 0;i--) {
            for(int j = 0;j < tmp.size();j++) {
                if(-1 == tmp[j]) {
                    
                } else {
                    tmp[j]++;
                }
                if(colors[i] - 1 == j) {
                    tmp[j] = 0;
                }
            }
            
            for(int j = 0;j < tmp.size();j++) {
                if(-1 != tmp[j]) {
                    if(-1 == rec[i][j]) {
                        rec[i][j] = tmp[j];
                    } else {
                        rec[i][j] = min(rec[i][j], tmp[j]); 
                    }
                }
            }
        }
        
        for(int i = 0;i < queries.size();i++) {
            v.push_back(rec[queries[i][0]][queries[i][1] - 1]);
        }
        
        return v;
    }
};

LeetCode 251. Flatten 2D Vector

其實不太確定我的實作有沒有符合題目要求 XD。

// TODO 使用 C++ 的 iterator 來解這一題
class Vector2D {
private:    
    vector<int> v;
    int index = 0;
public:
    Vector2D(vector<vector<int>>& vec) {
        for(int i = 0;i < vec.size();i++) {
            for(int j = 0;j < vec[i].size();j++) {
                v.push_back(vec[i][j]);
            }
        }
    }
    
    int next() {
        return v[index++];
    }
    
    bool hasNext() {
        return index != v.size();
    }
};
/**
 * Your Vector2D object will be instantiated and called as such:
 * Vector2D* obj = new Vector2D(vec);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

LeetCode : 2268. Minimum Number of Keypresses

typedef struct Node Node;
struct Node {
    char c;
    int n;
};
class Solution {
public:
    // 把頻率最高的字元放在第一個，最多能有 9 個字元在第一個位置
    // 於是照著頻率排序後，每九個字元就把 val += 1
    int minimumKeypresses(string s) {
        vector<Node> v = vector<Node>(26, { 0 });
        
        for(int i = 0;i < s.size();i++) {
            v[s[i] - 'a'].c = s[i];
            v[s[i] - 'a'].n++;
        }
        
        sort(v.begin(), v.end(), [](Node &a, Node &b) {
            return a.n > b.n;
        });
        
        int num = 0;
        int val = 1;
        int ans = 0;
        for(int i = 0;i < v.size();i++) {
            if(v[i].n > 0) {
                ans += val * v[i].n;
                num++;
                if(9 == num) {
                    val++;
                    num = 0;
                }
            }
        }
        
        return ans;
    }
};

LeetCode : 2257. Count Unguarded Cells in the Grid

// 整個 grid 遍尋三次
class Solution {
public:
    int countUnguarded(int m, int n, vector<vector<int>>& guards, vector<vector<int>>& walls) {
        // G ==> 'G'
        // W ==> 'W'
        // 0 ==> not visited
        // 1 ==> visited
        vector<vector<int>> grid = vector<vector<int>> (m, vector<int> (n, 0));
        
        for(int i = 0;i < guards.size();i++) {
            grid[guards[i][0]][guards[i][1]] = 'G';
        }
        
        for(int i = 0;i < walls.size();i++) {
            grid[walls[i][0]][walls[i][1]] = 'W';
        }
        
        for(int i = 0;i < grid.size();i++) {
            bool f = false;
            for(int j = 0;j < grid[0].size();j++) {
                if('G' == grid[i][j]) {
                    f = true;
                } else if('W' == grid[i][j]) {
                    f = false;
                } else {
                    if(f) {
                        grid[i][j] = 1;
                    }
                }
            }
            
            f = false;
            for(int j = grid[0].size() - 1;j >= 0;j--) {
                if('G' == grid[i][j]) {
                    f = true;
                } else if('W' == grid[i][j]) {
                    f = false;
                } else {
                    if(f) {
                        grid[i][j] = 1;
                    }
                }
            }
        }
        
        for(int i = 0;i < grid[0].size();i++) {
            bool f = false;
            for(int j = 0;j < grid.size();j++) {
                if('G' == grid[j][i]) {
                    f = true;
                } else if('W' == grid[j][i]) {
                    f = false;
                } else {
                    if(f) {
                        grid[j][i] = 1;
                    }
                }
            }
            
            f = false;
            for(int j = grid.size() - 1;j >= 0;j--) {
                if('G' == grid[j][i]) {
                    f = true;
                } else if('W' == grid[j][i]) {
                    f = false;
                } else {
                    if(f) {
                        grid[j][i] = 1;
                    }
                }
            }
        }
        
        int ans = 0;
        for(int i = 0;i < grid.size();i++) {
            for(int j = 0;j < grid[0].size();j++) {
                if(0 == grid[i][j]) {
                    ans++;
                }
            }
        }
        
        return ans;
    }
};

LeetCode : 1424. Diagonal Traverse II

// TODO : 效能太差，耗用的記憶體太多
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& nums) {
        vector<int> ans;
        vector<vector<int>> tmp = vector<vector<int>>(200005);
        
        int base = 0;
        for(int i = 0;i < nums.size();i++) {
            for(int j = 0;j < nums[i].size();j++) {
                tmp[base + j].push_back(nums[i][j]);
            }
            base++;
        }
        
        for(int i = 0;i < tmp.size();i++) {
            for(int j = tmp[i].size() - 1;j >= 0;j--) {
                ans.push_back(tmp[i][j]);
            }
        }
        
        return ans;
    }
};

LeetCode : 2087. Minimum Cost Homecoming of a Robot in a Grid

class Solution {
public:
    int minCost(vector<int>& startPos, vector<int>& homePos, vector<int>& rowCosts, vector<int>& colCosts) {
        int ans = 0;
        
        int stx = startPos[0]; // startPos : x
        int sty = startPos[1];
        if(stx > homePos[0]) {
            while(stx != homePos[0]) {
                stx--;
                ans += rowCosts[stx];
            }
        } else {
            while(stx != homePos[0]) {
                stx++;
                ans += rowCosts[stx];
            }
        }
        
        if(sty > homePos[1]) {
            while(sty != homePos[1]) {
                sty--;
                ans += colCosts[sty];
            }
        } else {
            while(sty != homePos[1]) {
                sty++;
                ans += colCosts[sty];
            }
        }
        
        return ans;
    }
};

LeetCode : 2201. Count Artifacts That Can Be Extracted

// TODO : 學習下 hash table 的解法
class Solution {
public:
    int digArtifacts(int n, vector<vector<int>>& artifacts, vector<vector<int>>& dig) {
        int ans = 0;
        vector<vector<int>> grid = vector<vector<int>>(n, vector<int>(n, -1));
        // 某個 artifact 所佔面積
        vector<int> alla = vector<int>(artifacts.size(), 0);
               
        // 因為 artifacts 間不會 overlap，所以
        // 這邊最多也就是 1000000 ， 應該是不會 TLE
        for(int i = 0;i < artifacts.size();i++) {
            for(int j = artifacts[i][0];j <= artifacts[i][2];j++) {
                for(int q = artifacts[i][1];q <= artifacts[i][3];q++) {
                    grid[j][q] = i;
                    alla[i]++;
                }
            }
        }
        
        for(int i = 0;i < dig.size();i++) {
            if(-1 != grid[dig[i][0]][dig[i][1]]) {
                alla[grid[dig[i][0]][dig[i][1]]]--;    
            }
        }
        
        for(int i = 0;i < alla.size();i++) {
            if(0 == alla[i]) {
                ans++;
            }
        }
        
        return ans;
    }
    
};

LeetCode : 2274. Maximum Consecutive Floors Without Special Floors

class Solution {
public:
    int maxConsecutive(int bottom, int top, vector<int>& special) {
        int bot = bottom - 1;
        int t   = top + 1;
        
        vector<int> sp = special;
        special.push_back(bot);
        special.push_back(t);
        
        sort(special.begin(), special.end());
        
        int maxVal = INT_MIN;
        for(int i = 1;i < special.size();i++) {
            int tmp = special[i] - special[i - 1] - 1;
            maxVal = max(maxVal, tmp);
        }
        
        return maxVal;
    }
};

LeetCode : 1855. Maximum Distance Between a Pair of Values

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        
        int i = 0;
        int j = 0;
        int maxVal = 0;
        while(i < nums1.size() && j < nums2.size()) {
            if(i > j) {
                j++;
            } else if(nums1[i] <= nums2[j]) {
                maxVal = max(maxVal, j - i);
                j++;
            } else {
                i++;
            }
        }
        return maxVal;
    }
};

LeetCode : 2105. Watering Plants II

class Solution {
public:
    
    bool water(int plant, int capacity, int *capa) {
        bool result = false;
        if(*capa >= plant) {
            result = false;
        } else {
            *capa = capacity;
            result = true;
        }
        
        *capa -= plant;
        
        return result;
    }
    
    int minimumRefill(vector<int>& plants, int capacityA, int capacityB) {
        int ali = 0;
        int bob = plants.size() - 1;
        int ans = 0;
        
        int capaA = capacityA;
        int capaB = capacityB;
        
        while(ali <= bob) {
            if(ali != bob) {
                if(water(plants[ali], capacityA, &capaA)) {
                    ans++;
                } 
                
                if(water(plants[bob], capacityB, &capaB)) {
                    ans++;
                }
                
                ali++;
                bob--;
            } else {
                if(capaA >= capaB) {
                    if(water(plants[ali], capacityA, &capaA)) {
                        ans++;
                    }    
                } else {
                    if(water(plants[bob], capacityB, &capaB)) {
                        ans++;
                    }
                }
                break;
            }
        }
        
        return ans;
    }
};

LeetCode : 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

// TODO : 試試 Monotonic Queue 的解法
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        
        map<int, int> m;
        int left = 0;
        int right = 0;
        m[nums[0]] = true;
        
        int maxVal = 1;
        
        while(left <= right && right < nums.size()) {
            auto it_small = m.begin();
            auto it_big = m.rbegin();
            
            int small = it_small->first;
            int big = it_big->first;
            
            if(big - small <= limit) {
                maxVal = max(maxVal, right - left + 1);
                
                right++;
                if(right < nums.size()) {
                    m[nums[right]]++;
                }
            } else {
                m[nums[left]]--;
                if(0 == m[nums[left]]) {
                    m.erase(nums[left]);
                }
                left++;
            }
            
        }
        
        return maxVal;
    }
};

LeetCode : 2012. Sum of Beauty in the Array

// TODO : 效能太差
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        
        vector<pair<int, int>> l2r = vector<pair<int, int>> (nums.size());
        vector<pair<int, int>> r2l = vector<pair<int, int>> (nums.size());
        
        int maxVal = INT_MIN;
        for(int i = 0;i < nums.size();i++) {
            if(nums[i] > maxVal) {
                l2r[i] = {nums[i], i};
                maxVal = nums[i];
            }
        }
        
        int minVal = INT_MAX;
        for(int i = nums.size() - 1;i >= 0;i--) {
            if(nums[i] < minVal) {
                r2l[i] = {nums[i], i};
                minVal = nums[i];
            }
        }
        
        int ans = 0;
        for(int i = 1;i < nums.size() - 1;i++) {
            if(nums[i] == nums[i - 1] ||
               nums[i] == nums[i + 1]) {                
                
            } else if (nums[i] == l2r[i].first &&
                       i == l2r[i].second &&
                       nums[i] == r2l[i].first &&
                       i == r2l[i].second) {
                ans += 2;
            } else if(nums[i] > nums[i - 1] &&
                      nums[i] < nums[i + 1]) {
                ans += 1;
            }
        }
        
        return ans;
    }
};

LeetCode : 2261. K Divisible Elements Subarrays

// TODO : 效能真的太差了
// TODO : 我猜 trie 有機會 ?
class Solution {
public:
    int countDistinct(vector<int>& nums, int k, int p) {
        
        map<vector<int>, bool> m;
        vector<bool> rec = vector<bool>(nums.size(), false);
        for(int i = 0;i < nums.size();i++) {
            if(0 == nums[i] % p) {
                rec[i] = true;
            }
        }
        
        for(int i = 0;i < nums.size();i++) {
            vector<int> tmp;
            int nown = 0;
            for(int j = i;j < nums.size();j++) {
                if(rec[j]) {
                    nown++;
                }
                if(nown > k) {
                    break;
                }
                tmp.push_back(nums[j]);
                m[tmp] = true;
            }
        }
        
        return m.size();
    }
};

LeetCode : 2365. Task Scheduler II

#define LL long long
class Solution {
public:
    long long taskSchedulerII(vector<int>& tasks, int space) {
        
        unordered_map<LL, LL> um;
        LL nowd = 0;
        
        
        for(int i = 0;i < tasks.size();i++) {
            if(um.find(tasks[i]) == um.end()) {
                nowd++;
                um[tasks[i]] = nowd;
            } else {
                LL lastday = um[tasks[i]];
                if(lastday + space >= nowd) {
                    nowd = lastday + space + 1;
                } else {
                    nowd++;
                }
                um[tasks[i]] = nowd;
            }
        }
        
        return nowd;
    }
};

LeetCode : 848. Shifting Letters

#define LL long long
class Solution {
public:
    string shiftingLetters(string s, vector<int>& shifts) {
        string ans;
        vector<LL> tmp = vector<LL>(s.size(), 0);
        
        vector<LL> shifSum = vector<LL>(s.size(), 0);
        shifSum[shifSum.size() - 1] = shifts.back();
        for(int i = shifts.size() - 2;i >= 0;i--) {
            shifSum[i] = shifSum[i + 1] + shifts[i];
        }
        
        for(int i = 0;i < s.size();i++) {
            tmp[i] = s[i] - 'a';
            tmp[i] += shifSum[i];
            tmp[i] %= 26;
            ans.push_back('a' + tmp[i]);
        }
        
        return ans;
    }
};

LeetCode : 822. Card Flipping Game

// 題目有點難懂
// 簡單來說，某個 int 是 good，代表他會在 facing down 出現，但不會在 facing up 出現。
// 因為數字總數只有 2000，所以遍尋每一個數字即可
class Solution {
public:
    int flipgame(vector<int>& fronts, vector<int>& backs) {
        
        vector<bool> rec = vector<bool>(2001, false);
        
        for(int i = 0;i < fronts.size();i++) {
            rec[fronts[i]] = true;
            rec[backs[i]] = true;
        }
        
        for(int i = 0;i < fronts.size();i++) {    
            if(fronts[i] == backs[i]) {
                rec[fronts[i]] = false;
            }
        }
        
        for(int i = 1;i <= 2000;i++) {
            if(rec[i]) {
                return i;
            }
        }
        
        return 0;
    }
};

LeetCode : 2391. Minimum Amount of Time to Collect Garbage

class Solution {
public:
    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
        
        int mfinal = -1;
        int pfinal = -1;
        int gfinal = -1;
        for(int i = 0;i < garbage.size();i++) {
            for(int j = 0;j < garbage[i].size();j++) {
                switch(garbage[i][j]) {
                    case 'M':
                        mfinal = i;
                        break;
                    case 'P':
                        pfinal = i;
                        
                        break;
                    case 'G':
                        gfinal = i;
                        break;
                }
            }
        }
        
        int ans = 0;
        for(int i = 0;i < garbage.size();i++) {
            if(i < garbage.size() - 1) {
                if(i + 1 <= mfinal) {
                    ans += travel[i];
                }
                if(i + 1 <= pfinal) {
                    ans += travel[i];
                }
                if(i + 1 <= gfinal) {
                    ans += travel[i];
                }
            }
            
            ans += garbage[i].size();
        }
        
        return ans;
    }
};

LeetCode : 1868. Product of Two Run-Length Encoded Arrays

class Solution {
public:
    vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
        vector<vector<int>> ans;
        vector<vector<int>> tmp;
        int i1 = 0;
        int i2 = 0;
    
        while(i1 < encoded1.size() && i2 < encoded2.size()) {
            int tmpv = encoded1[i1][0] * encoded2[i2][0];
            if(encoded1[i1][1] == encoded2[i2][1]) {
                tmp.push_back({tmpv, encoded2[i2][1]});
                i1++;
                i2++;
            } else if(encoded1[i1][1] > encoded2[i2][1]) {
                tmp.push_back({tmpv, encoded2[i2][1]});
                encoded1[i1][1] -= encoded2[i2][1];
                i2++;
            } else if(encoded1[i1][1] < encoded2[i2][1]) {
                tmp.push_back({tmpv, encoded1[i1][1]});
                encoded2[i2][1] -= encoded1[i1][1];
                i1++;
            }
        }
        
        while(i1 < encoded1.size()) {
            tmp.push_back(encoded1[i1]);
            i1++;
        }
        
        while(i2 < encoded2.size()) {
            tmp.push_back(encoded2[i2]);
            i2++;
        }
        
        int nowv = tmp[0][0];
        int nown = tmp[0][1];
        for(int i = 1;i < tmp.size();i++) {
            if(tmp[i][0] == nowv) {
                nown += tmp[i][1];
            } else {
                ans.push_back({nowv, nown});
                nowv = tmp[i][0];
                nown = tmp[i][1];
            }
        }
        ans.push_back({nowv, nown});
        
        return ans;
    }
};

LeetCode : 1060. Missing Element in Sorted Array

// medium
// TODO : Follow Up
class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int tmpk = k;
        nums.push_back(200000000);
        for(int i = 0;i < nums.size() - 1;i++) {
            if(nums[i + 1] > nums[i] + 1) {
                int diff = nums[i + 1] - nums[i];
                if(diff - 1 < tmpk) {
                    tmpk -= (diff - 1);
                } else {
                    return nums[i] + tmpk;
                }
            }
        }
        return 0;
    }
};

LeetCode : 2061. Number of Spaces Cleaning Robot Cleaned

// TODO : 效能太差了
// 猜是 medium
// 每到一個格子時，除了記錄到過這個格子，也要記錄到這個格子時面向的方向
// 假如到某個格子且這個方向也相同，就表示可以停下來了
class Solution {
public:
    
    int X[4] = {0, 1, 0, -1};
    int Y[4] = {1, 0, -1, 0};
    
    int numberOfCleanRooms(vector<vector<int>>& room) {
       vector<vector<vector<bool>>> visited =  vector<vector<vector<bool>>> (room.size(), vector<vector<bool>>(room[0].size(), vector<bool>(4, false)));
        
        vector<vector<bool>> v2 = vector<vector<bool>>(room.size(), vector<bool>(room[0].size(), false));
        
        int x = 0;
        int y = 0;
        // direction
        int d = 0;
        int ans = 0;
        
        while(1) {
            visited[x][y][d] = true;
            
            if(!v2[x][y]) {
                v2[x][y] = true;
                ans++;
            }
            
            bool flag = false;
            for(int i = 0;i < 4;i++) {
                int newd = (d + i) % 4;
                int newx = x + X[newd];
                int newy = y + Y[newd];
                
                if (newx >= 0 && newx < room.size() &&
                    newy >= 0 && newy < room[0].size() && 
                    1 != room[newx][newy]) {
                    flag = true;
                    
                    x = newx;
                    y = newy;
                    d = newd;
                    
                    break;
                }
            }
            
            if(visited[x][y][d]) {
                break;
            }
            
            if (!flag) {
                break;
            }
        }
        
        return ans;
    }
};

LeetCode : 2405. Optimal Partition of String

// TODO : 應該還是太慢了
class Solution {
public:
    int partitionString(string s) {
        int ans = 0;
        vector<int> rec = vector<int>(26, 0);
        int left = 0;
        rec[s[0] - 'a']++;
        for(int i = 1;i < s.size();i++) {
            rec[s[i] - 'a']++;
            bool f = false;
            for(int j = 0;j < 26;j++) {
                if(rec[j] > 1) {
                    f = true;
                    break;
                }
            }
            if(f) {
                ans++;
                while(left < i) {
                    rec[s[left] - 'a']--;
                    left++;
                }
            }
        }
        
        return ans + 1;
    }
};

LeetCode : 2270. Number of Ways to Split Array

#define LL long long
class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        LL sum = 0;
        for(int i = 0;i < nums.size();i++) {
            sum += nums[i];
        }
        LL nows = 0;
        int ans = 0;
        for(int i = 0;i < nums.size() - 1;i++) {
            nows += nums[i];
            if(nows >= (sum - nows)) {
                ans++;
            }
        }
        
        return ans;
    }
};

LeetCode : 2090. K Radius Subarray Averages

#define LL long long
class Solution {
public:
    vector<int> getAverages(vector<int>& nums, int k) {
        vector<int> ans = vector<int>(nums.size(), 0);
        
        for(int i = 0;i < k && i < nums.size();i++) {
            ans[i] = -1;
            ans[ans.size() - i - 1] = -1;
        }
        
        if(k * 2 + 1 > nums.size()) {
            return ans;
        }
        
        int end = k * 2;
        int len = k * 2 + 1;
        LL nows = 0;
        queue<int> q;
        
        for(int i = 0;i <= end;i++) {
            nows += nums[i];
            q.push(nums[i]);
        }
        ans[k] = nows / len;
        
        for(int i = k + 1;i < nums.size() - k;i++) {
            nows -= nums[i - k - 1];
            nows += nums[i + k];
            q.push(nums[i + k]);
            
            ans[i] = nows / len;
        }
        
        return ans;
    }
};

LeetCode : 218. The Skyline Problem

// TODO : 效能太差，程式碼太醜
bool myCompare_r2l(vector<int> &a, vector<int> &b) {
    if(a[1] == b[1]) {
        return a[2] < b[2];
    }
    return a[1] < b[1];
}
bool myCompare_l2r(vector<int> &a, vector<int> &b) {
    if(a[0] == b[0]) {
        return a[2] < b[2];
    }
    return a[0] < b[0];
}
 
class Solution {
public:
    vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
        vector<vector<int>> ans;
        
        if(buildings.size() == 0) {
            return ans;
        }
        
        unordered_map<int, int> r2b;
        unordered_map<int, int> l2b;
        unordered_map<int, int> b2h;
        
        for(int i = 0;i < buildings.size();i++) {
            // 這裡沒考慮到 index
            r2b[buildings[i][1]] = i;
            l2b[buildings[i][0]] = i;
            b2h[i] = buildings[i][2];
        }
        
        vector<vector<int>> building_sorted;
        vector<vector<int>> building_rsorted;// = buildings;
        
        for(int i = 0;i < buildings.size();i++) {
            building_sorted.push_back({buildings[i][0], buildings[i][1], buildings[i][2], i});
            building_rsorted.push_back({buildings[i][0], buildings[i][1], buildings[i][2], i});
        }
sort(building_sorted.begin(), building_sorted.end(), myCompare_l2r);
        sort(building_rsorted.begin(), building_rsorted.end(), myCompare_r2l);
        
        vector<vector<int>> events;
        
        int lsortedI = 0; //left sorted index
        int rsortedI = 0; //right sorted index
        
        while(lsortedI < building_sorted.size() && rsortedI < building_rsorted.size()) {
            if(building_sorted[lsortedI][0] < building_rsorted[rsortedI][1]) {
                events.push_back({0, building_sorted[lsortedI][3], building_sorted[lsortedI][0]});
                lsortedI++;
            } else {
                events.push_back({1, building_rsorted[rsortedI][3], building_rsorted[rsortedI][1]});
                rsortedI++;
            }
        }
        
        while(lsortedI != buildings.size()) {
            events.push_back({0, building_sorted[lsortedI][3], building_sorted[lsortedI][0]});
            lsortedI++;
        }
        
        while(rsortedI != building_rsorted.size()) {
            events.push_back({1, building_rsorted[rsortedI][3], building_rsorted[rsortedI][1]});
            rsortedI++;
        }
        
        // events {left or right, 建築的 index, 現在的 x 值}
        // 反正我們已經照著 x 走了，應該不需要紀錄現在的 x 了吧? --> 要得 QQ ， 解答需要
        
        map<int, int> nowHs;
        int lastHighest = -1;
        int nowHigh = -1;
        int lastx = -1;
        
        for(int i = 0;i < events.size();i++) {
            
            if(i == 0) {
            } else {
                if(events[i][2] != lastx) {
                    // one step
                    if(ans.size() == 0) {
                        ans.push_back({lastx, nowHigh});
                    } else {
                        if(ans.back()[1] != nowHigh) {
                            ans.push_back({lastx, nowHigh});
                        }
                    }
                }
            }
            
            int height = b2h[events[i][1]];
            if(events[i][0] == 0) {
                nowHs[height]++;
            } else {
                nowHs[height]--;
                if(nowHs[height] == 0) {
                    nowHs.erase(height);
                }
            }
            
            if(i == 0) {
                lastx = events[i][2];
                if(nowHs.size() == 0) {
                    nowHigh = 0;
                } else {
                    nowHigh = nowHs.rbegin()->first;
                }
            } else {
                if(events[i][2] != lastx) {
                    // one step
                    lastx = events[i][2];    
                    if(nowHs.size() == 0) {
                        nowHigh = 0;
                    } else {
                        nowHigh = nowHs.rbegin()->first;
                    }
                } else {
                    if(nowHs.size() == 0) {
                        nowHigh = 0;
                    } else {
                        nowHigh = nowHs.rbegin()->first;
                    }
                }
            }
            
        }
        
        ans.push_back({events.back()[2], 0});
        
        return ans;
    }
};

LeetCode : 2424. Longest Uploaded Prefix

// TODO : 效能太差
class LUPrefix {
public:
    vector<bool> v;
    int i = 1;
    LUPrefix(int n) {
        v = vector<bool>(n + 1, false); 
    }
    
    void upload(int video) {
        v[video] = true;
    }
    
    int longest() {
        while(v[i]) {
            i++;
        }
        return i - 1;
    }
};
/**
 * Your LUPrefix object will be instantiated and called as such:
 * LUPrefix* obj = new LUPrefix(n);
 * obj->upload(video);
 * int param_2 = obj->longest();
 */

LeetCode : 16. 3Sum Closest

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = 0;
        int offset = 1e9;
        
        sort(nums.begin(), nums.end());
        
        for(int i = 0;i < nums.size()-2;i++){
            int left = i+1;
            int right = nums.size()-1;
            
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                
                if(sum == target){
                    return target;
                } else if(sum < target){
                    if((target - sum) < offset){
                        ans = sum;
                        offset = target-sum;
                    }
                    
                    left++;
                } else {
                    if((sum - target) < offset){
                        ans = sum;
                        offset = sum - target;
                    }
                    
                    right--;
                }
            }
        }
        
        return ans;
        
    }
};

LeetCode : 334. Increasing Triplet Subsequence

// TODO : 效能太差，沒有做出 follow up
class Solution {
public:
    
    // https://leetcode.com/problems/increasing-triplet-subsequence/discuss/78993/Clean-and-short-with-comments-C%2B%2B
    // 簡單易懂，但我完完全全沒想過...好強
    
    bool increasingTriplet(vector<int>& nums) {
        map<int, int> r2l;
        map<int, int> l2r;
        
        for(int i = nums.size() - 1;i >= 0;i--) {
            r2l[nums[i]]++;
        }
        
        for(int i = 0;i < nums.size();i++) {
            r2l[nums[i]]--;
            if(r2l[nums[i]] == 0) {
                r2l.erase(nums[i]);
            }
            
            if(i != 0 &&
               i != nums.size() - 1) {
                auto left = l2r.begin()->first;
                auto right = r2l.rbegin()->first;
            
                if(left < nums[i] &&
                   right > nums[i]) {
                    return true;
                }
            }
            
            l2r[nums[i]]++;
        }
        
        return false;
    }
};

LeetCode : 1995. Count Special Quadruplets

// TODO : 效能太差
class Solution {
public:
    int countQuadruplets(vector<int>& nums) {
        unordered_map<int, bool> um;
        int ans = 0;
        for(int i = 0;i < nums.size();i++) {
            um[nums[i]] = true;
        }
        
        for(int i = 0;i < nums.size();i++) {
            for(int j = i + 1;j < nums.size();j++) {
                for(int q = j + 1;q < nums.size();q++) {
                    for(int p = q + 1;p < nums.size();p++) {
                        if (nums[i] + nums[j] + nums[q] == nums[p]) {
                            ans++;
                        }
                    }
                }
            }
        }
        
        return ans;
    }
};

LeetCode : 2462. Total Cost to Hire K Workers

// TODO : 效能太差
#define LL long long
class Solution {
public:
    long long totalCost(vector<int>& costs, int k, int candidates) {
        map<LL, int> left;
        map<LL, int> right;
        LL ans = 0;

        if (costs.size() >= 2 * candidates) {
            int lefti = candidates;
            int righti = costs.size() - 1 - candidates;
            for(int i = 0;i < candidates;i++) {
                left[costs[i]]++;
                right[costs[costs.size() - 1 - i]]++;
            }
            
            for(int i = 0;i < k;i++) {
                int minvl = INT_MAX;
                int minvr = INT_MAX;    

                if(left.size() > 0) {   
                    minvl = left.begin()->first;
                }
                if(right.size() > 0) {
                    minvr = right.begin()->first;
                }

                if(minvl <= minvr) {
                    left[minvl]--;
                    if(left[minvl] == 0) {
                        left.erase(minvl);
                    }

                    ans += minvl;
                    if (lefti <= righti) {
                        left[costs[lefti]]++;
                        lefti++;
                    }
                } else {
                    right[minvr]--;
                    if(right[minvr] == 0) {
                        right.erase(minvr);
                    }

                    ans += minvr;
                    if (lefti <= righti) {
                        right[costs[righti]]++;
                        righti--;
                    }
                }
            }

        } else {
            for(int i = 0;i < costs.size();i++) {
                left[costs[i]]++;
            }

            for(int i = 0;i < k;i++) {
                int minv = left.begin()->first;
                left[minv]--;
                if(left[minv] == 0) {
                    left.erase(minv);
                }
                ans += minv;
            }
        }
        
        return ans;
    }
};

LeetCode : 2078. Two Furthest Houses With Different Colors

// TODO : 效能太差，有辦法再降複雜度嗎?
class Solution {
public:
    int maxDistance(vector<int>& colors) {
        int maxVal = INT_MIN;
        for(int i = 0;i < colors.size();i++) {
            for(int j = i + 1;j < colors.size();j++) {
                if(colors[i] != colors[j]) {
                    maxVal = max(maxVal, abs(i - j));
                }
            }
        }
        return maxVal;
    }
};

LeetCode : 2210. Count Hills and Valleys in an Array

// TODO : 應該有效能更好的做法
class Solution {
public:
    int countHillValley(vector<int>& nums) {
        int ans = 0;
        vector<int> newnums;
        int last = -1;
        for(int i = 0;i < nums.size();i++) {
            if (nums[i] != last) {
                newnums.push_back(nums[i]);
                last = nums[i];
            }
        }
        for(int i = 1;i < newnums.size() - 1;i++) {
            if((newnums[i - 1] > newnums[i] &&
                newnums[i + 1] > newnums[i]) ||
               (newnums[i - 1] < newnums[i] &&
                newnums[i + 1] < newnums[i])) {
                ans++;
            } 
        }
        return ans;
    }
};

LeetCode : 2229. Check if an Array Is Consecutive

// TODO : 效能太差了
class Solution {
public:
    bool isConsecutive(vector<int>& nums) {
        unordered_map<int, bool> um;
        int minVal = INT_MAX;
        int maxVal = INT_MIN;
        for(int i = 0;i < nums.size();i++) {
            minVal = min(minVal, nums[i]);
            maxVal = max(maxVal, nums[i]);
            um[nums[i]] = true;
        }
        if((maxVal - minVal + 1) != nums.size()) {
            return false;
        }
        for(int i = minVal;i <= maxVal;i++) {
            if(!um[i]) {
                return false;
            }
        }
        return true; 
    }
};

LeetCode : 2482. Difference Between Ones and Zeros in Row and Column

class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        vector<int> onesRow = vector<int>(grid.size());
        vector<int> onesCol = vector<int>(grid[0].size());
        vector<int> zerosRow = vector<int>(grid.size());
        vector<int> zerosCol = vector<int>(grid[0].size());
        vector<vector<int>> ans = vector<vector<int>>(grid.size(), vector<int>(grid[0].size(), 0));

        for(int i = 0;i < grid.size();i++) {
            int oneNum = 0;
            int zeroNum = 0;
            for(int j = 0;j < grid[0].size();j++) {
                if(grid[i][j] == 1) {
                    oneNum++;
                } else {
                    zeroNum++;
                }
            }
            onesRow[i] = oneNum;
            zerosRow[i] = zeroNum;
        }
        for(int i = 0;i < grid[0].size();i++) {
            int oneNum = 0;
            int zeroNum = 0;
            for(int j = 0;j < grid.size();j++) {
                if(grid[j][i] == 1) {
                    oneNum++;
                } else {
                    zeroNum++;
                }
            }
            onesCol[i] = oneNum;
            zerosCol[i] = zeroNum;
        }

        for(int i = 0;i < grid.size();i++) {
            for(int j = 0;j < grid[0].size();j++) {
                ans[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
            }
        }

        return ans;
    }
};

LeetCode : 2350. Shortest Impossible Sequence of Rolls

// TODO : 找找看有沒有辦法不要每輪都重新 vector<bool>(k + 1, false) ??
/*
一：
暴力解，從長度為 1 的陣列開始試每一種排列組合
每生成一種組合，就使用字串搜尋去找

二：
二分搜加上暴力解：
長度使用二分搜，使用該長度去生成每一種排列組合

p.s.
sequence 也包含重複
--> 很關鍵的性質 XDD，幸好有想到這個點，是解題的關鍵
e.g. 
k = 2
--> 1, 1
    1, 2
    2, 1
    2, 2

三：
概念： 
dp[x] ， 當 index 為 x 時，k 的值
現在從最簡單的開始思考，從 k = 1 開始湊
每當我們集齊 k 種數字，此時該 index 就會變成 dp[x] = 1
從這個 index 開始，再集齊 k 種數字，該 index 就能變成 dp[x] = 2
-->
從對右邊開始往左掃
每集齊 k 種數字，就將計數器 + 1 ，並重新開始蒐集 k 種數字
 */

class Solution {
public:
    int shortestSequence(vector<int>& rolls, int k) {
        vector<bool> rec = vector<bool>(k + 1, false);
        int ans = 0;
        int nowk = k;
        for(int i = rolls.size() - 1;i >= 0;i--) {
            if(!rec[rolls[i]]) {
                nowk--;
                rec[rolls[i]] = true;

                if(nowk == 0) {
                    ans++;
                    nowk = k;
                    rec = vector<bool>(k + 1, false);
                }
            }
        }
        return ans + 1;
    }
};

LeetCode : 2502. Design Memory Allocator

// TODO : 效能太差了
class Allocator {
private:
    vector<int> m;
public:
    Allocator(int n) {
        m = vector<int>(n, 0);
    }
    
    int allocate(int size, int mID) {
        vector<int> tmp = vector<int>(m.size(), 0);
        for(int i = m.size() - 1;i >= 0;i--) {
            if(m[i] == 0) {
                if(i == m.size() - 1) {
                    tmp[i] = 1;
                } else {
                    tmp[i] = tmp[i + 1] + 1;
                }
            } else {
                tmp[i] = 0;
            }
        }

        /*
        printf("tmp : ");
        for(int i = 0;i < tmp.size();i++) {
            printf("%d ", tmp[i]);
        }
        printf("\n");*/
        int starti = -1;
        for(int i = 0;i < tmp.size();i++) {
            if(tmp[i] >= size) {
                starti = i;
                break;
            }
        }
        if(starti == -1) {
            return -1;
        }
        for(int i = 0;i < size;i++) {
            m[starti + i] = mID;
        }
        return starti;
    }
    
    int free(int mID) {
        int ans = 0;
        for(int i = 0;i < m.size();i++) {
            if(m[i] == mID) {
                ans++;
                m[i] = 0;
            }
        }
        return ans;
    }
};

/**
 * Your Allocator object will be instantiated and called as such:
 * Allocator* obj = new Allocator(n);
 * int param_1 = obj->allocate(size,mID);
 * int param_2 = obj->free(mID);
 */

LeetCode : 2511. Maximum Enemy Forts That Can Be Captured

// TODO : 效能應該可以再優化
class Solution {
public:
    int captureForts(vector<int>& forts) {
        int maxval = 0;
        for (int i = 0; i < forts.size(); i++) {
            if (forts[i] != 1) {
                continue;
            }
            int tmpi = i;
            int tmp = 0;
            bool found = false;
            tmpi--;
            while(tmpi >= 0) {
                if(forts[tmpi] == 0) {
                    tmp++;
                } else if (forts[tmpi] == -1) {
                    found = true;
                    break;
                } else {
                    break;
                }
                tmpi--;
            }
            if (found) {
                maxval = max(maxval, tmp);
            }

            tmpi = i;
            tmp = 0;
            found = false;
            tmpi++;

            while(tmpi < forts.size()) {
                if (forts[tmpi] == 0) {
                    tmp++;
                } else if (forts[tmpi] == -1) {
                    found = true;
                    break;
                } else {
                    break;
                }
                tmpi++;
            }
            if (found) {
                maxval = max(maxval, tmp);
            }
        }
        
        return maxval;
    }
};

LeetCode : 2555. Maximize Win From Two Segments

// 想法 1. segment tree
// 想法 2. priority queue
// 想法 3. queue
// 想法 4. 建表與查表
// --> 先看每個 x 會拿到多少值
// --> 再查表看 x + k + 1 以後，最多能拿到多少值

// 注意到這題不是求 1 segment，而是求 2 segment。
// TODO : 用錯了，這邊應該是要用 queue 才對!
// TODO : 效能還有很大的改善空間
// NOTE : 有趣的一題! 花了很多時間 (也可能是我太廢 QQ)
class Solution {
public:
    int maximizeWin(vector<int>& prizePositions, int k) {
        if(prizePositions.size() == 0) {
            return 0;
        }

        unordered_map<int, bool> re;
        vector<int> dis;
        for(int i = 0; i < prizePositions.size(); i++) {
            if(re.find(prizePositions[i]) == re.end()) {
                re[prizePositions[i]] = true;
                dis.push_back(prizePositions[i]);
            }
        }

        // 找出 dis[x] + k 的 index
        // dis_jump[x] == -1，代表沒辦法往下跳了
        vector<int> dis_jump = vector<int>(dis.size(), -1);
        int left = 0;
        for(int i = 0;i < dis.size();i++) {
            if(dis[i] > dis[left] + k) {
                dis_jump[left] = i;
                left++;
            }
        }

        // tbl_val[x] 代表當我們選擇 dis[x] 作為出發點時，可以拿到什麼值
        vector<int> tbl_val = vector<int>(dis.size(), 0);
        queue<int> q;
        int righti = 0;

        for(int i = 0;i < dis.size();i++) {
            if (i > 0) {
                while(!q.empty() && dis[i] > q.front()) {
                    q.pop();
                }
            }
            while(righti < prizePositions.size() &&
                  prizePositions[righti] == dis[i]) {
                q.push(prizePositions[righti]);
                righti++;
            }
            while(righti < prizePositions.size() &&
                  prizePositions[righti] - q.front() <= k) {
                q.push(prizePositions[righti]);
                righti++;
            }
            tbl_val[i] = q.size();
        }

        // tbl_max[x] 代表 dis >= dis[x] 時，所能取得的最大值
        vector<int> tbl_max = vector<int>(dis.size(), 0);
        int tmp_max = INT_MIN;
        for(int i = tbl_val.size() - 1;i >= 0;i--) {
            tmp_max = max(tbl_val[i], tmp_max);
            tbl_max[i] = tmp_max;
        }

        // 遍尋 tbl_val, tbl_max 這兩張表來求解
        int ans = INT_MIN;
        for(int i = 0;i < tbl_val.size();i++) {
            int ans2 = 0;
            if (dis_jump[i] != -1) {
                ans2 = tbl_max[dis_jump[i]];
            }
            ans = max(ans, tbl_val[i] + ans2);
        }

        return ans;
    }
};