刷题笔记18——数组查缺补漏、二分搜索变体

人就是这样的，想来想去，犹豫来犹豫去，觉得自己没有准备好，勇气没攒够，其实只要迈出去了那一步，就会发现其实所有的一切，早就准备好了。——巫哲Q《撒野》

528. 按权重随机选择

• 轮盘赌

class Solution {
    int wsum;
    int[] res;
    public Solution(int[] w) {
        res = w;  
        wsum=0;
        for(int i=0;i<res.length;i++){
            wsum += res[i];
        }
    }
    
    public int pickIndex() {
        double randnum = (double)(Math.random() * wsum);
        int temp = res[0];
        for(int i=0;i<res.length;i++){
            if(temp<randnum){
                temp = temp+res[i+1];
            }
            else{
                return i;
            }
        }
        return 0;
    }
}

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

二分搜索的出现变体形式(使……最大值最小，将最大值的范围作为数组，使用左右指针进行逼近)

1011. 在 D 天内送达包裹的能力

• 想到了思路但是不敢写是什么毛病，总觉得自己是错的

class Solution {
    public int shipWithinDays(int[] weights, int days) {
        int sumnum = 0;
        int maxnum = 0;
        for(int i=0;i<weights.length;i++){
            sumnum += weights[i];
            maxnum = maxnum>weights[i]?maxnum:weights[i];
        }

        int left = maxnum;
        int right = sumnum;
        while(left<=right){
            if(isPackage(weights,days,(left+right)/2)){
                right = (left+right)/2-1;
            }else{
                left = (left+right)/2+1;
            }
        }
        return left;
    }

    boolean isPackage(int[] weights,int days,int lowweight){
        int day = 0;
        int sumweight=0;
        int i=0;
        while(i<weights.length){
            if(sumweight+weights[i]<=lowweight){
                sumweight += weights[i];
                i++;
            }
            else{
                day++;
                sumweight = 0;
            }
        }
        return day<days;
    }
}
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
28
29
30
31
32
33
34
35
36
37
38

410. 分割数组的最大值

class Solution {
    public int splitArray(int[] nums, int k) {
        int maxnum = 0;
        int sumnum = 0;
        for(int i=0;i<nums.length;i++){
            maxnum = maxnum>nums[i]?maxnum:nums[i];
            sumnum += nums[i];
        }

        int left = maxnum;
        int right = sumnum;
        while(left<=right){
            if(isMin((left+right)/2,nums,k)){
                right = (left+right)/2-1;
            }
            else{
                left = (left+right)/2+1;
            } 
        }
        return left;
    }

    boolean isMin(int sum, int[] nums,int k){
        int s = 0;
        int t = 0;
        int i = 0;
        while(i<nums.length){
            if(s+nums[i]<=sum){
                s += nums[i];
                i++;
            }
            else{
                s = 0;
                t++;
            }
        }
        return t<k;
    }
}

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
28
29
30
31
32
33
34
35
36
37
38
39
40

875. 爱吃香蕉的珂珂

• 调试的错误是：两整数进行相除向上取整时，需要对整数先转double，然后结果再int
  int avgnum = (int)Math.ceil((double)sumnum/h);
• 结果中出现如下报错时，我修改了数据类型为long，问题解决
  

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        long sumnum=0;
        int maxnum=0;
        for(int i=0;i<piles.length;i++){
            maxnum = maxnum>piles[i]?maxnum:piles[i];
            sumnum += piles[i];
        }
        int avgnum = (int)Math.ceil((double)sumnum/h);

        int left = avgnum;
        int right = maxnum;
        while(left<=right){
            if(ismeet((left+right)/2,piles,h)){
                right = (left+right)/2 -1;
            }
            else{
                left = (left+right)/2 + 1;
            }
        }
        return left;
    }

    boolean ismeet(int vol,int[] piles,int h){
        int time = 0;
        for(int i=0;i<piles.length;i++){
            time += (int)Math.ceil((double)piles[i]/vol);
        }
        return time<=h;
    }
}  
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
28
29
30
31