思路

33. 搜索旋转排序数组

数组分为递增的两个部分，前半部分都大于等于nums[0], 后半部分都小于nums[0], 我们先二分出分界点，然后根据target和nums[0]的大小关系，在对应的部分二分出target所在的位置。

278. 第一个错误的版本

给定函数isBadVersion(i)，如果第i个版本是有bug的，则返回true，否则返回false。所以版本1到n的前半部分是没有bug的，后半部分是有bug的，只要二分出有bug的第一个版本即可。

275. H 指数 II

给定论文的被引次数，按照升序排列，我们要二分出其h指数，h指数是指这些论文中有h篇论文至少被引用了h次的最大的那个h。之所以说是最大的h，因为如果有h篇论文被引用h次，那么也肯定有任意a<=h满足至少a篇论文被引用a次，所以不妨假设我们要找到的答案是x，所以从0~x是一定满足该条件的，x+1~n则不满足。所以我们只需要二分出x即可。

162. 寻找峰值

与其说这道题是一道二分的题目，我觉得这道题更像是一个双指针的题目：
给定一个区间[l, r]，设mid = (l + r) / 2;
如果说nums[mid] > nums[mid + 1] 就说明峰值一定在l~mid之间；
反之若nums[mid] < nums[mid + 1] 则说明峰值一定在mid + 1 ~ r之间；
所以我们每次都选择一定有峰值的那半部分，直到区间缩小到峰值的那一点。

287. 寻找重复数

= = 表达能力有限，找到一个思路相同的题解，见： 287. 寻找重复的数

代码

33. 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        // 二分到最小值
        while(l < r){
            int mid = (l + r) / 2;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        // 从前半区间找到target
        if(target >= nums[0]) l = 0, r -- ;
        // 从后半区间找到target
        else r = nums.size() - 1;
        while(l < r){
            int mid = (l + r) / 2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        // 如果找到了target，返回下标
        if(nums[r] == target) return r;
        // 没找到
        return -1;
    }
};

278. 第一个错误的版本

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        // 对版本进行二分查找
        int l = 1, r = n;
        while(l < r){
            // 0LL 防止int溢出
            int mid = (0LL + l + r) / 2;
            // 二分出最早出现bug的版本
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

275. H 指数 II

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int l = 0, r = n;
        while(l < r){
            // 二分出h指数
            int mid = (l + r + 1) / 2;
            // citations[n - mid]是引用数第mid多的论文的引用数
            // citations[n - mid] >= mid，成立则表示有mid篇论文的引用数至少为mid
            if(citations[n - mid] >= mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

162. 寻找峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = (l + r) / 2;
            // 如果mid点高于mid+1，则说明峰值在nums[l, mid]中。
            if(nums[mid] > nums[mid + 1]) r = mid;
            // 反之，峰值则在nums[mid + 1, r]中。
            else l = mid + 1;
        }
        return l;
    }
};

287. 寻找重复数

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while(l < r){
            int mid = (l + r) / 2;
            // 记录大小在[l, mid]中的数的个数。
            int lcnt = 0;
            for(auto t : nums)
                if(l <= t && t <= mid) lcnt ++ ;
            if(lcnt > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

专题一【二分查找】（1）

模板请参考：二分查找模板
二分查找：在一个区间内，有一半是满足某一性质的，另一半是不满足这个性质的，所以我们可以使用二分查找，找到这两段区间的间断点。

本周题目：
34. 在排序数组中查找元素的第一个和最后一个位置
35. 搜索插入位置
74. 搜索二维矩阵
69. x的平方根
153. 寻找旋转排序数组中的最小值

题目思路

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

给定target，找到有序数组中值等于target的区间范围，所以我们要找的是数组中大于等于target的第一个元素的位置和小于等于target的最后一个元素的位置。两次二分即可。

35. 搜索插入位置

找到一个值在有序数组中插入的位置，就是找到这个数组中第一个大于等于这个数的元素位置。

如果要使用模板的话，我们可以将二分的范围设置为0 ~ n, 因为我们的mid = (l + r) / 2，所以只有当l = r = n的时候mid=n，而这样也就退出了循环。这样n这个位置就相当于一个虚拟的哨兵，如果数组中元素都小于target的话，数组中没有大于等于target的数，l和r二分后就会等于n，那么我们就将这个数插入到数组的末尾，也就是n这个位置上。

74. 搜索二维矩阵

这道题给的是一个有序的二维数组，我们只需要将一维坐标映射到二维坐标即可。具体做法是，假设矩阵是m * n的，那么给定一个坐标x，其在二维矩阵中的坐标就是(x / n, x % n)

69. x的平方根

给定一个正整数x，让我们找到 $\lfloor sqrt(x) \rfloor$, 所以问题就是二分出0~x中小于等于$sqrt(x)$的最大的那个数。

153. 寻找旋转排序数组中的最小值

将一个升序数组在某一点进行旋转，使其前半部分移至后半部分，两个部分依然升序。如果数组进行的旋转，那么这个数组的前半部分必然是大于等于nums[0]的，而后半部分必然是小于nums[0]的，所以我们只要二分出第一个小于nums[0]的数即可。

与35题相似，如果数组没有进行翻转，也就是说这个数组是完全升序的，那么我们同样可以将二分的范围设置为0 ~ n, 这样因为数组中没有小于nums[0]的数，二分之后l = r = n，返回nums[0]即可。

代码

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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        vector<int> res;
        // 二分出大于等于target的第一个数的位置。
        while(l < r){
            int mid = (l + r) / 2;
            if(nums[mid] >=  target) r = mid;
            else l = mid + 1;
        }
        // 如果nums[l] == target则存储答案，如果nums[l] > target，则数组中没有target这个数。
        if(nums[l] == target) res.push_back(l);
        l = 0, r = n - 1;
        while(l < r){
            int mid = (l + r + 1) / 2;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        // 同上
        if(nums[l] == target) res.push_back(l);
        // 如果数组中没有target这个数，则返回{-1, -1}
        if(res.empty()) res = {-1, -1};
        return res;
    }
};

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 注意这里设置的范围，如果nums[i] != target， 则二分后 l = r = nums.size()
        int l = 0, r = nums.size();
        // 二分出大于等于target的第一个数
        while(l < r){
            int mid = (l + r) / 2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

74. 搜索二维矩阵

class Solution {
public:
    typedef pair<int, int> PII;

    int n, m;
    // 坐标转换
    PII change(int x){
        return {x / m, x % m};
    }
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty() || matrix[0].empty()) return false;
        n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;
        // 二分出大于等于target的第一个数
        while(l < r){
            int mid = (l + r) / 2;
            // 坐标转换
            auto t = change(mid);
            if(matrix[t.first][t.second] >= target) r = mid;
            else l = mid + 1;
        }
        auto t = change(l);
        // 如果二分出来的数等于target，则返回true；否则返回false
        return matrix[t.first][t.second] == target;
    }
};

69. x的平方根

class Solution {
public:
    int mySqrt(int x) {
        long long l = 0, r = x;
        // 二分出a，a^2 <= x的最大的数 
        while(l < r){
            long long mid = (l + r + 1) / 2;
            // 注意这里使用了除法，防止mid * mid溢出int的范围
            if(mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

153. 寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        // 注意这里的范围，我们要二分的是小于nums[0]的第一个数
        int l = 0, r = n;
        while(l < r){
            int mid = (l + r) / 2;
            if(nums[mid] < nums[0]) r = mid;
            else l = mid + 1; 
        }
        // 如果数组升序，则不存在这样的数，l = r = nums.size()，nums[0]就是数组中最小的数
        if(r == n) return nums[0];
        return nums[l];
    }
};

二分查找

• 原理
  > 给定某一数组，数组的前一半或者后一半满足某一性质，比如说数组“nums = {1, 2, 3, 4, 5}”中，nums[0: 2]是满足小于等于3的，而另一半则不满足，我们则可以利用二分查找来找到nums[2]这个位置。反之nums[2:4]都是满足大于等于3的，我们也可以利用二分查找找到nums[2]这个位置。

• 总结
  > 给定某一个数组，数组的左子数组或右子数组满足某个性质，我们利用二分查找找到满足这一性质的左子数组的最后一个数的位置，或者是满足这一性质的右子数组的最前一个数的位置
  

模板

// nums升序排列,查找大于等于target的第一个数

int binary_search1(vector<int> &nums， int target){
    int l = 0, r = nums.size() - 1; // 查找的范围
    while(l < r){
        int mid = (l + r) / 2;
        if(nums[mid] >= target) r = mid; // nums[mid]满足这一性质，答案在mid或者mid前面
        else l = mid + 1; // 不满足，则前面的数都不满足。
    }
    return l; // 大于等于target的第一个数的位置就是l或者r
}

// nums升序排列,查找小于target的第一个数
int binary_search2(vector<int> &nums， int target){
    int l = 0, r = nums.size() - 1;
    while(l < r){
        int mid = (l + r + 1) / 2; // 注意这里，如果下一行是l = mid 则括号里面要+1
        if(nums[mid] < target) l = mid;
        else r = mid - 1;
    }
    return l;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    int OFFSET = 1e4 + 10;
    vector<int> tr = vector<int>(2 * OFFSET);
    int lowbit(int x){
        return x & -x;
    }
    int query(int x){
        int res = 0;
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
    void change(int x, int c){
        for(int i = x; i < tr.size(); i += lowbit(i)) tr[i] += c;
        return;
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        for(int i = nums.size() - 1; i >= 0; i -- ){
            int t = nums[i] + OFFSET;
            res[i] = query(t - 1);
            change(t, 1);
        }
        return res;
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~\\
class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> res;
        res.push_back(1);
        int m = primes.size();
        vector<int> idx(m);
        while(res.size() < n){
            int t = 2e9;
            for(int i = 0; i < m; i ++ )
                t = min(t, primes[i] * res[idx[i]]);
            res.push_back(t);
            for(int i = 0; i < m; i ++ )
                if(primes[i] * res[idx[i]] == t) idx[i] ++ ;
        }
        return res.back();
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~\
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size();
        vector<vector<int>> f(n, vector<int>(n));
        for(int len = 3; len <= n; len ++ )
            for(int i = 0; i + len - 1 < n; i ++ ){
                int j = i + len - 1;
                for(int k = i + 1; k < j; k ++ )
                    f[i][j] = max(f[i][j], f[i][k] + f[k][j] + nums[i] * nums[k] * nums[j]);
            }
        return f[0][n - 1];
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    vector<vector<int>> g;
    vector<int> d1, d2, p1, p2;
    vector<int> up;

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        g.resize(n);
        d1 = d2 = p1 = p2 = up = vector<int>(n, -1);
        for(auto edge : edges){
            int a = edge[0], b = edge[1];
            g[a].push_back(b);
            g[b].push_back(a);
        }
        dfs1(0, -1);
        dfs2(0, -1);
        int mind = 2e9;
        for(int i = 0; i < n; i ++ ) mind = min(mind, max(d1[i], up[i]));
        vector<int> res;
        for(int i = 0; i < n; i ++ )
            if(max(d1[i], up[i]) == mind) res.push_back(i);
        return res;
    }

    int dfs1(int u, int p){
        for(auto t : g[u]){
            if(t == p) continue;
            int d = dfs1(t, u);
            d ++ ; // 从u-》t
            if(d > d1[u]){
                d2[u] = d1[u], d1[u] = d;
                p2[u] = p1[u], p1[u] = t;
            }
            else if(d > d2[u])
                d2[u] = d, p2[u] = t;
        }
        if(d1[u] == -1) d1[u] = d2[u] = 0; //叶子节点
        return d1[u];
    }

    void dfs2(int u, int p){
        up[u] = 0;
        if(p != -1) up[u] = up[p] + 1;
        if(p != -1 && p1[p] != u) up[u] = max(up[u], d1[p] + 1);
        if(p != -1 && p2[p] != u) up[u] = max(up[u], d2[p] + 1);
        for(auto t : g[u])
            if(t != p) dfs2(t, u);
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> f(n + 1, vector<int>(3));
        f[0][1] = f[0][2] = -2e9;
        for(int i = 1; i <= n; i ++ ){
            int w = prices[i - 1];
            f[i][0] = max(f[i - 1][0], f[i - 1][2]);
            f[i][1] = max(f[i - 1][0] - w, f[i - 1][1]);
            f[i][2] = f[i - 1][1] + w;
        }
        return max(f[n][0], f[n][2]);
    }
};

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
class NumArray {
public:
    vector<int> tr;

    int lowbit(int x){
        return x & -x;
    }

    int query(int x){
        int res = 0;
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }

    void change(int x, int c){
        for(int i = x; i < tr.size(); i += lowbit(i)) tr[i] += c;
    }
    NumArray(vector<int>& nums) {
        int n = nums.size();
        tr.resize(n + 1);
        for(int i = 1; i <= n; i ++ ){
            tr[i] = nums[i - 1];
            for(int j = i - 1; j > i - lowbit(i); j -= lowbit(j))
                tr[i] += tr[j];
        }
    }

    void update(int i, int val) {
        i ++ ;
        int t = query(i) - query(i - 1);
        int c = val - t;
        change(i, c);
    }

    int sumRange(int i, int j) {
        i ++ , j ++ ;
        return query(j) - query(i - 1);
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(i,val);
 * int param_2 = obj->sumRange(i,j);
 */

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~\
class Solution {
public:
    string add(string a, string b){
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string res;
        for(int i = 0, t = 0; i < a.size() || i < b.size() || t; i ++ ){
            if(i < a.size()) t += a[i] - '0';
            if(i < b.size()) t += b[i] - '0';
            res += t % 10 + '0';
            t /= 10;
        }
        reverse(res.begin(), res.end());
        return res;
    }
    bool isAdditiveNumber(string num) {
        for(int i = 0; i < num.size(); i ++ )
            for(int j = i + 1; j + 1 < num.size(); j ++ ){
                string a = num.substr(0, i + 1);
                string b = num.substr(i + 1, j - (i + 1) + 1);
                if(a.front() == '0' && a.size() > 1) break;
                if(b.front() == '0' && b.size() > 1) break;
                int k = j + 1;
                while(k < num.size()){
                    string c = add(a, b);
                    if(c != num.substr(k, c.size())) break;
                    a = b, b = c;
                    k += c.size();
                }
                if(k == num.size()) return true;
            }
        return false;
    }
};