剑指offer专项突击版第24天

剑指 Offer II 071. 按权重生成随机数

二分+前缀和

看了几遍题目愣是没看明白，最后看的题解明白了！

题意就是按照 $w[i]$ 的权重选取下标 $i$，这个问题可以转化成：所有小球连续排放在一条线上，下标 $i$ 种类的球有 $w[i]$ 个（相同种类的球是连续排放的），那么第 $n$ 个球下标就为 $n$ ，$n$取值范围为 $[1,total]$ $total$ 为球总数。随机选取一个球然后判断球是哪个种类即可。

1. 首先使用等概率 $rand()$ 选取一个数（可看成一个下标），范围为 $[0,total]$ （ $total$ 为球总数）。
2. 为了方便二分判断这里使用前缀和，比如：有两种球 $[1,3]$，分别用 $a$ 和 $b$ 表示，将球排成一条线 $abbb$，前缀和就是 $[1,4]$ ，如果随机到 $3$ 可以观察到这个位置的球是 $b$ 那么就返回的是下标$1$，若随机到 $1$ 即球 $a$ ，则返回下标 $0$ 。
3. 然后用二分判断这个球是哪个种类即可（就是原数组下标），返回第一个大于等于 $x$ 的前缀和下标（球的种类）。

class Solution {
private:
    vector<int> pre_sum;    
public:
    Solution(vector<int>& w) {
        pre_sum.resize(w.size());
        pre_sum[0] = w[0];
        for(int i = 1; i < w.size(); i++) {
            pre_sum[i] = pre_sum[i-1] + w[i];
        }
    }
    
    int find(int x) {
        int l = 0, r = pre_sum.size()-1;
        while(l < r) { //最终l与r相遇于大于等于pre_sum[mid]的位置
            int mid = l+r>>1;
            if(pre_sum[mid] < x) l = mid+1;
            else r = mid; 
        }
        return l;
    }

    int pickIndex() {
        int idx = rand()%pre_sum.back()+1;
        return find(idx);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

---

剑指 Offer II 072. 求平方根

这里平方根取整，等同于最后一个使得 $mid\ast mid<=x$ 的 $mid$ 。

class Solution {
public:
    int mySqrt(int x) {
        long long l = 0, r = x;
        while(l < r) { //l与r最终在 mid*mid <= x 的mid位置相遇
            long long mid = l+r+1>>1;
            if(mid*mid <= x) l = mid;  //停的位置性质是什么,看谁=mid所对应的判断条件
            else r = mid-1;
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

---

剑指 Offer II 073. 狒狒吃香蕉

二分

根据题意结合样例可以知道，求最小的速度 $k$ 在至多 $h$ 小时吃完。那么我们二分范围就是 $[1,1e9]$ ，使用 $check$ 判断 $mid$ 速度是否可以吃完，若可以我们就缩小范围即 $r=mid$，反之 $l=mid+1$ 。

class Solution {
public:
    bool check(vector<int> &piles, int &h, int &mid) { 
        int time = 0;
        for(int num: piles) {
            if(num%mid) time += num/mid + 1;
            else time += num/mid;
        }
        return time <= h;
    }
    int minEatingSpeed(vector<int>& piles, int h) {
        int l = 1, r = 1e9+5;
        while(l < r) {
            int mid = l + r >> 1;
            if(check(piles,h,mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20