二分答案 狒狒吃香蕉

答案具有单调性

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxv=Integer.MIN_VALUE;
        for(int i=0;i<piles.length;i++){
            maxv=Math.max(maxv,piles[i]);
        }
        int left=1;int right=maxv;
        while(left<right){
            int mid=left+right>>1;
            if(check(piles,mid,h)){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    public boolean check(int[] piles,int k,int h){
        int cnt=0;
        for(int i=0;i<piles.length;i++){
            if(piles[i]%k==0){
                cnt+=piles[i]/k;
            }else{
                cnt+=piles[i]/k+1;
            }
        }
        return cnt<=h;
    }
}

加权随机，返回对应的元素下标

[1,total]之间随机生成一个数x ，找到大于x的最小的前缀下标

class Solution {
    int[] prefix;
    int n;
    int [] ww;
    public Solution(int[] w) {
        n=w.length;
        ww=w;

        prefix=new int[w.length+1];
        for(int i=0;i<w.length;i++){
            prefix[i+1]=prefix[i]+w[i];
        }
    }

    public int pickIndex() {
        int x=new Random().nextInt(prefix[n])+1;
        int left=1;int right=prefix.length-1;
        while(left<right){//最小的前缀大于等于x
            int mid=left+right>>1;
            if(prefix[mid]>=x){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left-1;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(w);
 * int param_1 = obj.pickIndex();
 */