changed 2 years ago  
Published Linked with GitHub

Leetcode刷題學習筆記–Binary Search

Introduction

binary search的精隨就是在一個排序過的數列裡面，找出所要的值。因為每次都切半，所以可以時間複雜度達到O(logN)。相較於暴力破解法，例如答案在1~N之內，如果測試函數可以讓你知道數字是往更大或更小的方向，就可以用binary search。

  1. remove special case(答案不在可能的範圍內)
    因為繼續使用binary search，如果答案比範圍內的還大，會得到left = sz。(還可以判斷)
    如果答案比範圍內的還小，會得到left = 0。(無法判斷)
  2. 定義出答案可能出現的範圍left和right。
    因為計算mid的方法，right必須是範圍最大值+1。
  3. 決定中間點，mid = left + (righ - left) / 2;
    避免有overflow的問題。
  4. 判斷中間點是否超過要搜尋的值，例如278是用isBadVersion(), 668是看有多少數值超過目前的值。
  5. 更新left, right。通常right為錯誤的那一邊。所以判斷完中間點是錯的，需要把區間往下則right = mid，如果是對的，則區間往上，left = mid +1;
  6. 直到left < right不成立為止。
    最後left會等於right。
  7. 最後結果會在上一次的right上。所以要根據題目決定要取目前這一個(left)還是left - 1的結果。

Code Snippet















int left = 0;
int right = arr.size() - 1; // 或是 right = arr.size(); 端看最後一個值是不是已經確定了
while(left < right) {
    int mid = left + (right - left) / 2; // 避免overflow
                                         // 如果要拿mid來計算，
                                         // 值域會超過int(4)則改用long(8)
    int val = ...; // 使用mid計算出新的值。
                   // 如果計算結果會overflow則可改用long(8)
    if(val == target) // 依題目需求決定要步要用
    else if(val > target) // 或是使用 val >= target
        right = mid;
    else
        left = mid + 1;
}

Corner Case

當長度為1

left = mid = right，都會指向同一個element。

當長度為2

left = mid, right = mid + 1, 只有left和mid一樣。所以竟可能拿mid和right來判斷。

Special Case

當使用 while(left<right)的時候，最左邊和最右邊的答案不會檢查。所以當答案有可能在這兩個之外，必須在while之外做額外的檢查。

case 1 : 如果答案比index 0還小，則最後left/right會停在node 0而離開while loop，但是沒檢查node 0。

case 2 : 如果答案比index 5還大，則最後left/right會停在node 5而離開while loop，但是沒檢查node 5。

這種情況必須視題目而定。如果答案一定是在node0node5之間，那就直接return沒關係。如果除了node0node5之外還有額外的答案，那就必須檢查left/right使否正確。

從答案的範圍，用binary search 猜測是否正確。

另一種binary search的應用。只知道答案的範圍，使用binary search來逼近正確的答案。如下的code:

int left = ANS_MAX, right = ANS_MIN;
while(left < right) {
    int mid = left + (right - left) / 2;
    // 根據題目計算由mid得到的結果
    
    // 和題目給的條件去比較，並更新left, right
}

case 1 : 當搜尋範圍就是比較的範圍

例如 : 從已排列好的array中，找出4的數字。

題目:

case 2 : 當搜尋範圍和比較的範圍不一樣

case 2-1 : 比較範圍是遞增數列

case 2-2 : 比較範圍是遞減數列

搜尋的範圍和比較的範圍不一樣，且比較的範圍是遞減數列。

題目:

Search Range

針對binary search，首先一定要有一個搜尋範圍。通常使用left和right來表示欲搜尋的上下界。

  • 因為我們都是用mid來測試條件是否成立。所以mid要可以達到答案範圍內的每個值。
  • 如果，left = 1, right = 30，且mid = left + (right - left) / 2，則mid的範圍是mid = 1(left = 1, right = 2)…, mid = 29(left = 29, right = 30)，mid就無法達到30。
  • 所以要讓mid達到上界，則right = 31。mid = 30(left = 30, right = 31)
  • 因為答案不可能達到(上界+1)，所以最後可以判斷這個(left == 上界+1)排除掉。














// setup search range
int left = 1, right = 31;
while(left < right) {
    int mid = left + (right - left) / 2;
    int result{0};
    // test mid
    
    // update the search range
    if(result >= k) right = mid;
    else left = mid + 1;
}

// 因為結果不可能出現31
return left == 31 ? -1 : left;

例如:1870. Minimum Speed to Arrive on Time
























class Solution {
    // speed : 1,  2, 3, [4], 5, 6, 7, 8, 9, ...
    // hour  : 10, 9, 9,  8,  8, 8, 7, 7, 7, ...
    //                >   <=
public:
    int minSpeedOnTime(vector<int>& dist, double hour) {
        int sz = dist.size();
        if(hour <= sz - 1) return -1;

        int left = 1, right = 1e9 + 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            int need{0};
            for(int i = 0; i < sz - 1; ++i)
                need += (dist[i] + (mid - 1)) / mid;
            double fneed = need + dist.back() * 1.0 / mid;

            if(fneed <= hour) right = mid;
            else left = mid + 1;
        }
        return left == 1e9 + 1 ? -1 : left;
    }
};

Update the Search Range

有了search range，就可以得出mid，這時就必須測試mid是否在範圍之內，然後更新left或是right來縮小搜尋範圍。通常mid得出的結果必須是遞增或是遞減數列，這樣才有機會使用binary search。

例如, mid的範圍如下，可以得到測試結果rtn為遞減數列。

// mid = 1, 2, 3, 4, 5, 6, 7, 8, 9,
// rtn = 9, 9, 8, 8, 7, 7, 6, 6, 5

再根據題目，通常會限制rtn為某個數，假設是7，因為mid通常在前一個，

// mid = 1, 2, 3, 4,  5, 6, 7, 8, 9,
// rtn = 9, 9, 8, 8, [7], 7, 6, 6, 5 
//                >   <=
//               mid

所以根據上面的圖示可以寫出






int k = 7;
if(rtn <= k) right = mid;
else left = mid + 1
    
return left;

最後答案就是left。

另一種情況是

// mid = 1, 2, 3, 4, 5,  6, 7, 8, 9,
// rtn = 9, 9, 8, 8, 7, [7], 6, 6, 5 
//                      >=   <
//                      mid

可以寫成

int k = 7;
if(rtn < k) right = mid;
else left = mid + 1;

return left - 1;

必須返回left - 1，因為最後left == right，會是下一個。

Maximum-Minimum or Minimum-Maximum problem

一個題目要求尋找一個答案的最小值，但是這個值是某個運算的最大值，通常都是binary search的題目。

例如:2560. House Robber IV
其中，robber的capability的定義是偷過的金額中最大值。但是必須返回某個條件下(最少必需偷k個房子)的最小值。Minimum capability(which is maximum of all stealed money)




























class Solution {
    // capability(maximum) 偷的金額中最大的
    // [2, 3, 5, 9], k = 2(minimum) 最少要偷兩間
    // 回傳 最小(minimum)的capability。 min-max problem --> binary search?
    // capability 2 ~ 9
    // mid = capability : 2, 3, 4,  5, 6, 7, 8, 9
    //  k                 1  1     [2]           2 (為了符合capability, 最多能偷的house數)
    //                       <      >=
public:
    int minCapability(vector<int>& nums, int k) {
        auto [minv, maxv] = minmax_element(nums.begin(), nums.end());
        int left = *minv, right = *maxv;
        while(left < right) {
            int mid = left + (right - left) / 2;
            int count = 0;
            for(int i = 0; i < nums.size(); ++i) {
                if(nums[i] <= mid) {
                    count++;
                    i++;
                }
            }
            if(count >= k) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

Example

278. First Bad Version(Easy)

找出第一個錯誤的版本。一定會有一個錯誤的版本。
n = 1, [1]:只有一個版本，則一定是錯誤版本。
n = 2, [1,2]:有兩種情況[X,X]都是錯誤版本和[O,X]一對一錯。
n = 3, [1,2,3]:有三種情況[XXX][OXX][OOX]
使用binary search，right一定會錯誤版本。












int firstBadVersion(int n) {
    int left = 1, right = n, mid;
    while(right > left) {
        mid = left + (right - left) / 2;
        if(isBadVersion(mid))
            right = mid; // right為錯誤版本
        else
            left = mid + 1;
    }  
    return right; // 因為是找錯誤版本
}

算中間點有兩種算法

mid = (left + right) / 2;

或是

mid = left + (right - left) / 2;

答案都會是一樣，差別在於如果left和right很大，則left + right有可能overflow，但是第二種方法不會。
right一定是指向錯誤的版本。所以code才會寫成以下的樣子。而且最後一定是return right。





if(isBadVersion(mid))
    right = mid;    // right為錯誤版本
else
    left = mid + 1; // 下一個版本。

c++的STL有提供binary search的function。
lower_bound和upper_bound，都是用binary search來找目標值，差別在於

lower_bound : 返回等於或大於目標值的最小位置。
upper_bound : 返回大於目標值的最小位置。

返回值為iterator。
所以取值必須用

value = *it;

在array中的index必須用

idx = it - nums.begin();

668. Kth Smallest Number in Multiplication Table(Hard)

在一個乘法表裡面(width(n) x height(m),都是1開頭遞增)找出第k個最小的數字。

例如:n = 3, m = 3, k = 5，其中第5個最小的數字為3。

leetcode668_example

解題思路:

  1. 在 1 ~ m*n的數字中，找出一個數字，剛好小於這個數字的數量等於k。=> binary search。
  2. 因為數字都是倍數關係，所以可以用 mid / i來算出小於mid的數量。



















int findKthNumber(int m, int n, int k) {
    // 第一個和最後一個不用算
    if(k == 1 || k == m * n) return k;
    
    int left = 1, right = m * n;
    while (left < right) {
        int mid = left + (right - left) / 2, cnt = 0;
        // 計算比mid小的數值有多少個
        for (int i = 1; i <= m; ++i) {
            cnt += (mid > n * i) ? n : (mid / i);
        }
        // 比較小，區間往上，所以left一定是下一個數
        if (cnt < k) left = mid + 1;
        // 大於等於，區間往下，所以right = mid
        else right = mid;
    }
    return right;        
}

540. Single Element in a Sorted Array(Medium)

給你一個排列過的整數數列nums，其中每個數都是兩兩一對，除了一個數只有一個，問你怎麼找出那一個數。題目又說希望執行效率事O(logN)。

例如:
nums = [1,1,2,3,3,4,4,8,8]，output = 2。

解題思路

  1. 一開始看到就想到XOR，這樣就可以找到那個數，但是時間是O(N)。
  2. 看到O(logN)，直覺就想到binary search。但是怎麼判斷範圍要往前還是往後是個問題。
  3. 先想一下special case。
    3-1. 題目說長度從1開始，因為兩兩一對只有一個是單獨，所以長度一定是奇數。
    3-2. 長度 == 1，那不用判斷一定是那一個。
    3-3. 長度 == 3，那不是第一個，就是最後一個。
    3-4. 長度 == 7，可以發現要找的數字，和mid和前後關係不太依樣。

  1. 判斷完mid之後，可以把數列變短，問題又是一樣。

照以上的思緒，程式碼如下:


























int singleNonDuplicate(vector<int>& nums) {
    auto n = nums.size();
    if(n == 1) return nums[0];
    int left = 0, right = n - 1, mid;
    while(left < right) {
        if(right - left <= 3) {
            if(nums[left] != nums[left + 1]) return nums[left];
            if(nums[right] != nums[right - 1]) return nums[right];
        }
        mid = left + ((right - left) >> 1);

        if(mid % 2) {
            if(nums[mid] == nums[mid + 1])
                right = mid - 1;
            else
                left = mid + 1;
        } else {
            if(nums[mid] != nums[mid + 1])
                right = mid;
            else
                left = mid;              
        }
    }
    return 0;
}

300. Longest Increasing Subsequence(Medium)

給你一個vector<int> nums找出，這個當中找出最長的strictly increasing subsequence.

  • subsequence的定義是，在nums中的前後順序依樣，但是可以不用連續。
  • strictly increasing，每個數字都比前一個大。
  1. 一開始的想法是，每看到一個數字就去map找比他還小的數字
  2. 然後，更新dp[i]和比他還小的數字連起來最長。
  3. 這個方法效率不好O(NlogN)。





















int lengthOfLIS(vector<int>& nums) {
    auto n = nums.size();
    if(n == 1) return 1;
    map<int, vector<int>> m;
        
    vector<int> dp(n, 1);
    int maxlen{1};
    m[nums[0]].push_back(0);
    for(int i = 0; i < n; ++i) {
        for(auto& item : m) {
            if(item.first >= nums[i]) break;
            for(auto& idx : item.second) {
                dp[i] = max(dp[i], dp[idx] + 1);
            }
        }
        maxlen = max(maxlen, dp[i]);
        m[nums[i]].push_back(i);
    }
        
    return maxlen;
}

網路上的解法

  1. 使用一個vector來記錄走過的subsequence
  2. 找出lower_bound(大於等於)換掉
  3. 不然就是推到最後面。









int lengthOfLIS(vector<int>& nums) {
    vector<int> v;
    for(auto& n : nums) {
        auto it = lower_bound(v.begin(), v.end(), n);
        if(it == v.end()) v.push_back(n);
        else *it = n;
    }        
    return v.size();
}

875. Koko Eating Bananas(Medium)

請參考原題目。

  1. 這題思考很久，最後看到題目提示是用binary search才恍然大悟。
  2. 因為速度k 和最後多少個小時h吃完成線性關係。也就是速度越快，所用的h越少，所以可以用binary search來完成。
  3. 定義left和right。因為piles最大值為1e9，h最小值為1，所以left = 1, right = 1e9
  4. 計算k的時候需要無條件進位，等於是(b + mid - 1)/ mid
  5. 最後是希望最小的k，所以設定right >= h

2022/04/25

  1. 因為吃的速度越快，需要的時間就越短
  2. 但是koko偏好吃慢一點, 如下圖所示就是2的位置。
  3. 計算時間使用無條件進位。












int minEatingSpeed(vector<int>& piles, int h) {
    int left = 1, right = 1e9;
    while(left < right) {
        int mid = left + (right - left) / 2;
        int t = 0;
        for(auto& n : piles) t += (n + mid - 1) / mid;
        if(t <= h) right = mid;
        else left = mid + 1;
    }
    return left;
}

1539. Kth Missing Positive Number

給你一個vector<int>為嚴格遞增序列(strictly increasing order)，找出第k個missing number。














int findKthPositive(vector<int>& arr, int k) {
    // 把right設定成arr.size(); 是因為當 k 比最大還大時
    // right還可以等於arr.size();
    int left = 0, right = arr.size();
    while(left < right) {
        int mid = left + (right - left) / 2;
        int val = arr[mid] - (mid + 1);
        // 等於也要，因為也在arr[mid - 1] ~ arr[mid] 中間的範圍內。
        if(val >= k) right = mid;
        else left = mid + 1;
    }
    return right + k;
}

1608. Special Array With X Elements Greater Than or Equal X

找出一個數x，使得在vector<int> nums中，有x個數大於等於x。
ex:
Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.

  1. 因為下面的程式使用了只有當 mid == cnt，才return正確值，反則return -1。所以mid一定要走訪到所有可能的答案[1~sz]。
  2. 當length = 2的情況，left = mid，所以right必須要等於sz + 1，才可以讓mid走訪所有可能的答案。
int specialArray(vector<int>& nums) {
    int sz = nums.size();
    int left = 1, right = sz + 1;
    while(left < right) {
        int mid = left + (right - left) / 2;
        int cnt = 0;
        int cnt = count_if(nums.begin(), nums.end(), [&](int& a) {
               return a >= mid; 
        });
        // 因為用了mid == cnt 才return，
        // 所以mid的位置就很重要，因為當length == 2時，mid == left
        // 所以right的位置要+1
        if(mid == cnt) return mid;
        else if(mid > cnt) right = mid;
        else left = mid + 1;
    }
    return -1;
}

34. Find First and Last Position of Element in Sorted Array

在一個排序的數列中，找出target的左右位置。

  1. 根據以下的圖，可以得知，在做binary search的比較關係。

  1. 有兩個special case
    2-1. 當數字出現在第一個，這個不會影響判斷

2-2. 當數字出現在最後一個位置。

因為我們都是拿mid來比較，會造成, mid只會停在倒數第二個的位置。

所以必須把right的位置往後移一個，讓mid有機會判斷到最後一個位置的數字。

並且答案為 left - 1，因為最後會停在 > target的位置。

vector<int> searchRange(vector<int>& nums, int target) {
    int sz = nums.size();
    if(sz == 0 || target < nums[0] || target > nums[sz - 1]) return {-1, -1};
    vector<int> rtn(2);
    int left = 0, right = sz - 1;
    while(left < right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] >= target) right = mid;
        else left = mid + 1;
    }
    rtn[0] = nums[left] == target ? left : -1;
        
    left = 0,  right = sz;
    while(left < right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] > target) right = mid;
        else left = mid + 1;
    }
    rtn[1] = nums[left - 1] == target ? left - 1 : -1;
        
    return rtn;
}

1760. Minimum Limit of Balls in a Bag

operatin的定義是，可以對數字進行切割成兩個。切割的兩個數字可以自己決定。
所有的operation次數不可以超過maxOperations。想辦法讓最大的數字最小化。

  1. 使用binary serach假設答案是某個數字。因為切割為多次，penalty就會越小。如下圖所示:

int minimumSize(vector<int>& nums, int maxOperations) {
    int left = 1, right = *max_element(nums.begin(), nums.end());
    while(left < right) {
        int mid = left + (right - left) / 2;
        int cnt = 0;
        for(auto& n : nums) cnt += (n - 1) / mid;
            
        if(cnt <= maxOperations) right = mid;
        else left = mid + 1;
    }
    return left;
}

2022/11/4

    // 使用binary search。則mid要搜尋什麼?
    // 1. 找penalty?
    // 2. 找ops (好像不太容易)
    // 把 left , mid, right所表達的意義遞增排序，就可以得到ops為遞減排序
    // penalty : 1, 2, 3, 4, 5, 6, 7
    // ops     : 8, 7, 6, 5, 5, [5], 4
    // 假設maxOperations為5，並選到了[5]這一個，
    // 因為往左還會有更小的penalty，所以使用小於等於，繼續往左移動
    // 相當於是lower_bound的概念。
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        while(left < right) {
            // mid 為欲達成的penalty，則所需的ops為?
            // 因為ops越多，penalty越少
            // ops 1 2 3 4 [5] 6 7 8 <-- 因為這個mid得到的ops次數 = 5
            // p   9 8 7 6 [6] 5 4 3 <-- mid

            int mid = left + (right - left) / 2;
            int ops = 0;
            for(auto& n : nums) 
                ops += (n - 1) / mid;

            if(ops <= maxOperations) right = mid;
            else left = mid + 1;
        }
        return left;
    }

275. H-Index II

    int hIndex(vector<int>& citations) {
        int sz = citations.size();
        int left = 0, right = sz + 1;
        // h index : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
        // cnt     : 8, 7, 7, 6, 6, 5, 5, 4, 3, 2, ...
        //                         >=  <      
        // h-index : h篇論文，每個都被引用至少h次
        //           所以h[越小]，[越多]論文被引用至少h次   
        while(left < right) {
            int mid = left + (right - left) / 2;
            int cnt = 0;
            for(auto& n : citations)
                if(n!= 0 && n >= mid) cnt++;
            if(cnt < mid) right = mid;
            else left = mid + 1;
        }
        return left - 1;
    }

2022/11/4

    // 使用binary search。則mid要搜尋什麼?
    // 1. 找penalty?
    // 2. 找ops (好像不太容易)
    // 把 left , mid, right所表達的意義遞增排序，就可以得到ops為遞減排序
    // 因為要找maxOperations，且越大越好，所以等於是找小於等於那一邊
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        while(left < right) {
            // mid 為欲達成的penalty，則所需的ops為?
            // 因為ops越多，penalty越少
            // ops 1 2 3 4 [5] 6 7 8 <-- 因為這個mid得到的ops次數 = 5
            // p   9 8 7 6 [6] 5 4 3 <-- mid

            int mid = left + (right - left) / 2;
            int ops = 0;
            for(auto& n : nums) 
                ops += (n - 1) / mid;

            if(ops <= maxOperations) right = mid;
            else left = mid + 1;
        }
        return left;
    }

658. Find K Closest Elements

給以一個排列過的遞增數列，找出K個最接近X的數，結果也要遞增排序。

這題一看直覺就是用sort來排序，但是效率比較差O(NlogN + KlogK + K)
比較好的解法是使用binary search。只要找出left，則整個數列就會出來。所以使用binary search找出答案array的left在哪裡。

所以我們可以列出四種狀況

case1 : x在left的左邊
case2 : x在left和right的中間，但是比較靠近left
case3 : x在left和right的中間，但是比較靠近right
case4 : x在right的右邊
其中，case1和case2必須把array往左邊移動。因為必須讓x在中間，case3和case4必須把array往右邊移動。
上面的情況是left和right不一樣的時候，使用兩種判斷式都可以正確的移動array。

另外一種情況是數字有重複，則使用abs來判斷就會失效。如下圖。

使用abs，三種情況都會是一樣。但是如果是使用

if(x - arr[mid] < arr[mid + k] - x) { }

或是使用

if(arr[mid] - x > x - arr[mid + k]) { }

因為 x - arr[mid] 和 arr[mid + k] - x，會有正負的差別，所以可以判斷出需要往左還是往右移動。

相等的時候為什麼是向左移動? 因為我們是使用arr[mid + k]。
arr[mid + k] 是在k之外的一個數值，如果相等表示需要向左移動。

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0, right = arr.size() - k;
    while (left < right) {
        int mid = (left + right) / 2;
        if (x - arr[mid] > arr[mid + k] - x)
            left = mid + 1; // 向右移動
        else
            right = mid; // 向左移動
    }
    // arr.begin() + left + k 不會取
    return vector<int>(arr.begin() + left, arr.begin() + left + k);
}

因為binary search只找了N-K的範圍長度。
return的答案占了K長度的vector。

Time Space
\(O(log(N-K))\) \(O(K)\)

1898. Maximum Number of Removable Characters

給你兩個字串s和p，其中p為s的subsequence。在給你一個vector<int> removeable，表示可以要依序刪除的index。試問最多依序可以刪幾個char還可以保持p為s的subsequence。

2022/11/07
一開始做這一題完全沒想法，看了答案之後覺得是一題好題目。

class Solution {
    // 圖1, mid為刪除char的個數，j為s中有p的個數
    // mid = 0, 1, [2], 3, 4, 5, 6, 7, 8, ...
    // j   = 4, 4, 4,   3, 3, 3, 2, 2, 1, ...
    //             >=   <

    // 圖2, 說明為什了是map[i] >= mid
    // string index 0, 1, 2, [3], 4, 5, 6, 7, 8
    //                        mid = 3, 刪除3個(0, 1, 2), 保留6個(3, 4, 5, 6, 7, 8)
    //              <--刪除-|  |------保留------> 
    //                     <  >=
    
    //             0, 1, 2
    // removable : 3, 1, 0
        
    //             0, 1, 2, [3], 4, 5
    //     m     : 2  1  M   0   M  M , M : 表示不會被刪除
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int sz = s.size();
        vector<int> map(sz, INT_MAX);
        for(int i = 0; i < removable.size(); ++i) map[removable[i]] = i;
        
        int left = 0, right = removable.size() + 1;
        while(left < right) {
            int mid = left + (right - left) / 2, j = 0;
            for(int i = 0; i < s.size() && j < p.size(); ++i) {
                // 圖2
                if(map[i] >= mid && s[i] == p[j]) ++j;
            }

            //圖1
            if(j >= p.size()) left = mid + 1;
            else right = mid;
        }
        return left - 1; // 圖1, 從上圖會選到p.size() - 1那一個，所以要選前一個
    }
};

792. Number of Matching Subsequences

找出vector<string> words中，會是s的subsequence的個數。

  1. 一開始我是用trie結果TLE
  2. 先建立每個char會出現的index，方便之後尋找。
  3. 使用 int x = -1， 則使用upper_bound第一次會找到第一個。
  4. 依序找出每個char會出現的位置。這邊也有Greedy的意味在。因為每次只會找到大於x的最小值。
int numMatchingSubseq(string s, vector<string>& words) {
    // 建立char和index的對應vector
    vector<vector<int>> alpha(26);
    for(int i = 0; i < s.size(); ++i) alpha[s[i] - 'a'].push_back(i);

    int rtn = 0;
    for(auto& word : words) {
        int found = true;
        int x = -1; //** 很重要，因為第一次會找到第一個
        for(auto& c : word) {
            auto it = upper_bound(alpha[c - 'a'].begin(), alpha[c - 'a'].end(), x);
            if(it == alpha[c - 'a'].end()) {found = false; break;}
            else x = *it;
        }
        if(found) rtn++;
    }

    return rtn;
}

2517. Maximum Tastiness of Candy Basket




































class Solution {
public:
    int maximumTastiness(vector<int>& price, int k) {
        sort(price.begin(), price.end());
        int left = 0, right = price.back() - price.front() + 1;
        while(left < right) {
            // 基於這個tastiness之下可以選到最多的candies
            int mid = left + (right - left) / 2; 
            int cnt{1};
            for(int i = 1, j = 0; i < price.size(); ++i) {
                // 因為排序過，所以最小差值只會發生在
                // 目前的(i)和選到的candy最大值(j)之間
                if(price[i] - price[j] >= mid) { 
                    cnt++;
                    j = i;
                }
            }

            if(cnt >= k) left = mid + 1;
            else right = mid;
        }
        return left - 1;
    }
};

// [13, 5, 1, 8, 21, 2], k = 3
// [1, 2, 5, 8, 13, 21] after sorting
// search range : 0, 21 - 1
// 
//         [1, 2, 5, 8, 13, 21]
// t : 10                        因為排序過，最小的差值只會出現在鄰近兩個之間。

// tastiness : 0, 1, 2, 3, [4], 5, 6, 
// cnt       : 5, 4, 4, 3,  3,  2, 1    tastiness越大，可以選的candy越少。
//                          >=  <

2448. Minimum Cost to Make Array Equal

給你一個vector<int> nums和cost，每對一個數字nums[i]加一或是減一的行為需要cost[i]，試問讓nums數字一樣的最小cost。

  1. 有想到用binary search但是對於二次曲線不知道怎麼用。參考lee215的解答。
  2. 首先想到讓vector的數字一樣，那個數字一定是在最小值和最大值之間。
int left = 0, right = *max_element(nums.begin(), nums.end());
  1. 如果x軸是平均數，y軸是cost則會得到一個二次向上凹的曲線。一般的binary search就不適用。
  2. 必須針對 mid, mid+1來判斷目前在曲線的那個部分。



long long y1 = f(mid), y2 = f(mid + 1);
if(y1 < y2) right = mid;
else left = mid + 1;
  • 完整解答。

























class Solution {
public:
    long long minCost(vector<int>& nums, vector<int>& cost) {
        long long l = 1, r = *max_element(nums.begin(), nums.end()), res = LONG_MAX, x;
        auto f = [&](int x) {
            long long res{};
            for(int i = 0; i < nums.size(); ++i)
                res += 1L * abs(nums[i] - x) * cost[i];
            return res;
        };
        while(l < r) {
            x = l + (r - l) / 2;
            long long y1 = f(x), y2 = f(x + 1);
            res = min({res, y1, y2});
            if(y1 < y2) r = x;
            else l = x + 1;
        }
        return res;
    }
    // time : O(N) + O(logk * (2N)) = O(N + 2NlogK) = O(NlogK)
    // N : size of nums
    // k : the difference between minimal and maximum value

    // space : O(1)
};

1851. Minimum Interval to Include Each Query

  1. 一開始我也打算使用binary search來解，但是卡住了。因為我用queries來尋找interval，但是這樣會有問題。
  2. 反過來使用intervals來尋找覆蓋到的queries就簡單多了。
  3. 先對intervals的長度來排序。
  4. 從最小的intervals取出來，看看是否有覆蓋的queries，有的話就跟新ans。






























class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        // O(NlogN)
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){ // O(NlogN)
            return a[1] - a[0] < b[1] - b[0]; // 從短到長排序
        });
        
        // O(MlogM)
        set<pair<int, int>> st;
        for(int i = 0; i < queries.size(); ++i) // O(QlogQ)
            st.insert(make_pair(queries[i], i)); // 把queries從小帶大排序
        
        //O(N(logM + MlogM))
        vector<int> ans(queries.size(), -1);
        for(int i = 0; i < intervals.size() && !st.empty(); ++i) {
            int s = intervals[i][0], e = intervals[i][1];
            int len = e - s + 1;
            auto it = st.lower_bound({s, 0});
            while(it != st.end() && it->first <= e) {
                ans[it->second] = len;
                advance(it, 1);
                st.erase(prev(it));
            }
        }
        return ans;
    }
};
// time :O(NlogN + MlogM + NMlogM)
// sapce : O(M)

852. Peak Index in a Mountain Array

  1. 根據montain array的定義，arr.front()和arr.back()不會是peak。
  2. 在peak的右邊一定滿足，arr[i] > arr[i + 1]
  3. 在peak的左邊一定滿足，arr[i] < arr[i + 1]
  4. 所以可以使用上面任一個條件來判斷。
  • 使用peak左側來判斷。






while(left < right) {
    int mid = left + (right - left) / 2;
    if(arr[mid] < arr[mid + 1]) left = mid + 1;
    else right = mid;
}
return left;
  • 使用peak右側來判斷


























class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int sz = arr.size();
        if(sz == 3) return 1;
        int left = 0, right = sz - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(arr[mid] > arr[mid + 1]) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};
//             *
// 1, 2, 3, 4, 5, 4, 3, 2, 1
// -------------
//             --------------
//               arr[i] > arr[i + 1]
// arr[i] < arr[i + 1]

// case1 : 4,   5  , left = mid + 1 = answer
//         l/m  r

// case2 : 5,   4,  right = left = 5 = answer
//        l/m   r
  • 這邊用左邊判斷取left，合理。但是用右邊判斷為什麼不用left - 1?
    • 這邊沒有target，所以之前的分析都不成立?
    • 只和自己的左邊和右邊比較，來更新left和right。
  • 使用arr[mid] > arr[mid + 1] 來判斷會得到以下關係。
// 0,10,5,2
// F, T,T,T
  • 使用arr[mid] < arr[mid + 1] 來判斷會得到以下關係
// 0,10,5,2
// T, F,F,F
  • 可以發現不管是使用哪個判斷式，最後會收斂在0,10也就是狀態轉換的邊界，所以答案不用left - 1。
  • 後來想想這種pattern其實和278-First-Bad-VersionEasy一樣，都是TTFFFF，找出TF的交界，答案會是left。

2141. Maximum Running Time of N Computers

  1. 參考官方解答。
  2. 假設現在可以跑target的時間，則n個computer必須要有 n * target的電量。
  3. 多少電量可以分配? 大於等於target的電池沒辦法額外使用?
    假設n個電腦可以跑到target的時間，那這個電池剩下的電量也就無法使用。所以
extra += min(target, batteries[i]);
  1. 判斷式為 extra >= n * target，則可以得到以下的關係
target : 1, 2, 3, [4], 5
result : T  T  T   T   F

因為要找出True的最大值，從上面的例子就是4，所以就可以得到以下的判斷式。





if(extra >= n * target)
    left = target + 1;
else
    right = target;
  1. 從上圖得知，最後結果為 left - 1。
























class Solution {
public:
    long long maxRunTime(int n, vector<int>& batteries) {
        long sum = accumulate(batteries.begin(), batteries.end(), 0L); // O(M)
        long left = 1, right = sum / n + 1; // K : range from left to right
        while(left < right) { // O(logK * M)
            long target = left + (right - left) / 2;
            long extra{};
            for(auto& b : batteries)
                extra += min((long)b, target);

            if(extra >= (long)(n * target)) 
                left = target + 1;
            else 
                right = target;
        }
        return left - 1;
    }
    // time : O(M + MlogK) = O(MlogK)
    // space : O(1)
};

// target : 1, 2, 3, 4, 5
// result : T  T  T  T  F
tags: leetcode 刷題
Select a repo