【数组】

二分查找

二分查找框架：

704. 二分查找

//闭区间写法:[left, right]
int left = 0, right = nums.size() - 1; //nums为vector<int>
while (left <= right) { //循环终止条件为left = right + 1
    int mid = (left + right) / 2;   //这样写可能会出现数值溢出，可改为下面一行形式
    // int mid = left + (right - left) / 2;
    if (target > nums[mid]) ...;        //left = mid + 1;
    else if (target < nums[mid]) ...;   //right = mid - 1;
    else if (target == nums[mid])...;   //return mid;
}

//开区间写法:[left, right)
int left = 0, right = nums.size(); //nums为vector<int>
while (left < right) {  //循环终止条件为left = right
    int mid = (left + right) / 2;   //这样写可能会出现数值溢出，可改为下面一行形式
    // int mid = left + (right - left) / 2;
    if (target > nums[mid]) ...;        //left = mid + 1;
    else if (target < nums[mid]) ...;   //right = mid;  右侧为开区间
    else if (target == nums[mid])...;   //return mid,若要继续收敛，可选择是往左还是往右收敛，见下面内容
}

写对二分查找的关键是搞清楚到底应该往左收敛还是往右收敛

• 往左收敛：

  int leftBound (vector<int> & nums, int target) {
      int left = 0, right = nums.size() - 1;
      while (left <= right) {
          int mid = (left + right) / 2;
          if (nums[mid] < target) left = mid + 1;
          else if (nums[mid] >= target) right = mid - 1;
          
      }
      if (left >= nums.size() || nums[left]!= target) return -1;  //边界判定
      return left;
  }

• 往右收敛：

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

题目：34. 在排序数组中查找元素的第一个和最后一个位置

392. 判断子序列

基础版：使用双指针遍历一遍模式串s和主串t

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int pt = 0, ps = 0;
        int hi = t.size() - 1;
        while (pt < hi+1) {
            if (t[pt] == s[ps]){
                ps++;   
            }
            pt++;
        }
        if (ps == s.size()) return true;
        else return false;
    }
};

进阶版：TODO

793. 阶乘函数后 K 个零：这道题是172. 阶乘后的零的扩展，我们先写172题。

172思路：题目需要计算$n!$结果中零的个数，也即计算结果中有多少2和5的因子的个数，但由于2远比5多，故我们只需计算5的因子个数即可，上面的问题转换成了求$n!$中因子为5的个数，我们计算一个数中因子为div的个数一般使用下面的方法：

int divisor(int num, int div) {
    //求因子div的个数
    int numb = 0;
    while (num % div == 0 && num / div != 0) {
        num = num / div;
        numb++;
    }
    return numb;
}

计算$n!$中5的因子个数，只需从0到n遍历一遍即可：

int trailingZeroes(int n) {
    int res = 0;
    for (int i=0; i <= n; i++) {
        res = res + divisor(i, 5);
    }
    return res;
}

793思路：在前面172的基础上，使用二分查找搜出满足条件的最小n和最大n，二者相减即可得到满足条件的n的数量，代码如下：

class Solution {
public:
    int preimageSizeFZF(int k) {
        //二分搜索找满足条件的最小的n和最大的n
        return rightBOund(k) - leftBound(k) + 1;
    }

    int leftBound(int target) {
        int lo = 0, hi = INT_MAX;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (trailingZeroes(mid) > target) hi = mid;
            else if (trailingZeroes(mid) < target) lo = mid + 1;
            else hi = mid;
            
        }
        return lo;
    }

    int rightBOund(int target) {
        int lo = 0, hi = INT_MAX;
        while ( lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (trailingZeroes(mid) > target) hi = mid;
            else if (trailingZeroes(mid) < target) lo = mid + 1;
            else lo = mid + 1;
        }
        return lo - 1;
    }

    int trailingZeroes(int n) {
        int res = 0;
        for (int d = n; d/5 > 0; d = d/5) {
            res += d/5;
        }
        return res;
    }

};

【注】此代码在int数值范围内能计算，若需提高计算能力，需将其转换到long数值范围内进行计算。

875. 爱吃香蕉的珂珂：此题中珂珂吃香蕉的速度是整型变量，且速度与最终的时间呈单调性，故可以使用二分查找，此题要找的是珂珂的最小速度，则应该找区间左侧值。另外需要注意计算每堆香蕉的时间是应该向上取整。

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int lo = 1;
        int maxValue = 0;
        for(int pile: piles) {
            maxValue = maxValue > pile ? maxValue : pile;
        }
        int hi = maxValue;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int times = computeTime(piles, mid);
            if (times < h) hi = mid;
            else if (times > h) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    int computeTime(vector<int>& piles, int k) {
        int times = 0;
        for (int i= 0; i <= piles.size() - 1; i++) {
            int pileTime = (piles[i]+ k - 1) / k;
            times += pileTime;
        }
        return times;
    }
};

滑动窗口

滑动窗口技巧指维护一个窗口，不断滑动，然后更新答案。滑动窗口就是一个队列算法框架如下：

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;

    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

更加具体的算法框架：

//滑动窗口算法框架
void slideWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c: t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    while (right < s.size()) {
        // c是将移入的字符
        char c = s[right];
        // 增大窗口
        right++;
        //进行窗口内数据的一系列更新
        ...

        // debug位置
        cout << "window:" << left << "," << right << endl;

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d是将移出窗口的字符
            char d = s[left];
            // 缩小窗口；
            left++;
            // 进行窗口内一系列更新
            ...
        }
    } 
}

3. 无重复字符的最长子串：滑动窗口的简单情况，只有一个window，没有need，根据上面的框架，写法如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> window;

        int left = 0, right = 0;
        int res = 0;
        while (right < s.size()) {
            char c = s[right];
            right ++;

            window[c]++;

            while (window[c] > 1) {
                char d = s[left];
                left++;

                window[d]--;
            }
            res = max(res, right - left);
        }
        return res;
    }
};