腾讯&leetcode875：爱吃香蕉的珂珂

[sisterAn]

珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。

珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。

珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。

返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。

示例 1：

输入: piles = [3,6,7,11], H = 8
输出: 4

示例 2：

输入: piles = [30,11,23,4,20], H = 5
输出: 30

示例 3：

输入: piles = [30,11,23,4,20], H = 6
输出: 23

提示：

• 1 <= piles.length <= 10^4
• piles.length <= H <= 10^9
• 1 <= piles[i] <= 10^9

附赠leetcode地址：leetcode

[sisterAn]

解答：二分查找

二分查找也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字，让你猜我写的是什么？你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。

该算法要求待查找的数组已排序，实现步骤如下：

• 选择数组中的中间数
• 查找数与中间数对比，决定下一步操作
• 重复上一步，直到查找成功或失败

对应于本题，二分查找查找的是珂珂吃香蕉的速度 K （不需要排序），我们已知的是：

• 珂珂吃掉香蕉的最小速度 （ low ） 是 1
• 最大速度是几堆香蕉中数量最多的那一堆 ( high )

const minEatingSpeed = (piles, H) => {
    // 计算堆中香蕉最大值
    let maxVal = 1;
    for (let pile of piles) {
        maxVal = Math.max(maxVal, pile);
    }

    // 速度最小的时候，耗时最长
    let low = 1
    // 速度最大的时候，耗时最短
    let high = maxVal

    while (low < high) {
        let mid = Math.floor((low+high)/2)
        if (calculateTime(piles, mid) > H) {
            // 耗时太多，说明速度太慢了，进入下一轮搜索
            low = mid + 1
        } else {
            high = mid
        }
    }
    return low
}

// 计算吃掉香蕉所需的总耗时
const calculateTime = (piles, speed) => {
    let times = 0
    for (let pile of piles) {
        // 向上取整
        times += Math.ceil(pile / speed)

    }
    return times
}

复杂度分析：

• 时间复杂度：O(nlogm)，其中 n 是香蕉堆的数量，m 最大的香蕉堆的大小
• 空间复杂度：O(1)

leetcode

[Glittergalaxy]

const piles = [3,6,7,11];
const H = 8;

const getSpeed = (piles, H) => {
  if (H === piles.length) {
    return Math.max(...piles);
  } else if (H < piles.length) {
    return false;
  } else {
    const max = Math.max(...piles);
    const min = Math.min(...piles);
    const ratio = H / piles.length;
    const minSpeed = Math.ceil(min / ratio);
    const maxSpeed = Math.ceil(max / ratio);
    for (speed = minSpeed; speed <= maxSpeed; speed++) {
      let totalTime = 0;
      for (let i = 0; i < piles.length; i++) {
        totalTime += Math.ceil(piles[i] / speed);
      }
      if (totalTime === H) {
        return speed;
      }
    }
  }
};

const a = getSpeed(piles, H);
console.log(a);

[marlboroKay]

/* 
题解1（易于理解，但不是最优解）
以[3,6,7,11] 堆为例，
1.假设1小时吃1根，则总时间是 3/1 + 6/1 + 7/1 + 11/1 = 27 
2.假设1小时吃2根，则总时间是 3/2 + 6/2 + 7/2 + 11/2 => 2（向上取整） + 3 + 4 + 6 = 15
3.假设1小时吃3根，则总时间是 3/3 + 6/3 + 7/3 + 11/3 => 1 + 2 + 3 + 4 = 10
4.假设1小时吃4根，则总时间是 3/4 + 6/4 + 7/4 + 11/4 => 1 + 2 + 2 + 3 = 8 （满足）
...后面速度越快，时间越短
*/

var minEatingSpeed = function(piles, H) {
  let index = 1;
  while(true){
    let resH = 0;
    for(let i = 0; i < piles.length; i++){
      resH += Math.ceil(piles[i] / index);
    }
    if(resH <= H){
      return index;
    }
    index++;
  }
};


/* 
题解2（利用二分查找）
二分需要注意的点：
循环退出条件、mid 的取值，low 和 high 的更新
low 设置为1根开始，high 设置为piles的最大值；
mid = (low + high) / 2;
循环推出条件：low >= high;
利用enoughEat 方法，判断H（有效时间内）能否吃完；
能吃完，则将mid 赋值给 high，否则low = mid + 1；
*/

const enoughEat = function enoughEat(piles, speed, H){
  let resH = 0;
  piles.forEach(item => {
    resH += Math.ceil(item / speed)
  });
  return resH <= H;
}
var minEatingSpeed = function(piles, H) {
  let low = 1;
  let high = Math.max(...piles);
  while(low < high){
    let mid = Math.floor((low + high) / 2);
    if(enoughEat(piles, mid, H)){
      high = mid;
    }else{
      low = mid + 1;
    }
  }
  return high;
}

[xiaoyiyi123]

第一次参与，加油 `var minEatingSpeed = function(piles, H) { var left = 1, right = Math.max(...piles);

var findHour = (mid)=>{
    var hour = 0;
    for(let item of piles){
        hour += Math.ceil(item/mid)
    }
    return hour;
}
while(left < right){
    var mid = Math.floor((left+right)/2);
    var hour = findHour(mid); 
    if(hour <= H){
        right = mid;
    }else{
        left = mid+1;
    }
}

return right

};`

[zo11o]

var minEatingSpeed = function (piles, H) {
    // res 的取值范围：[piles.length, Math.max(piles)] 双闭区间
    // 二分法从最大的 
    if (piles.length == 1) {
        return Math.ceil(piles[0] / H); 
    }
    var res;
    var len = piles.length;
    var resMin = piles.length;
    var resMax = Math.max(...piles);
    piles.sort((a, b) => b - a)
    // 二分法 resMin ~ resMax
    let mid
    while (resMax > resMin) {
        let mid = resMin + Math.ceil((resMax - resMin) / 2);
        let count = 0;
        piles.forEach(o => {
            count += Math.ceil(o / mid);
        })

        if (count == H) {
            for (var i = resMin; i <= mid; i++) {
                let _c = 0
                piles.forEach(o => {
                    _c += Math.ceil(o / i);
                })
                if (_c <= H) {
                    return i
                }
            }

            return mid
        } else if (count > H) {
            resMin = mid
        } else if (count < H) {
            resMax = mid
        }
    }
    return resMin
};

超出时间限制，但是记录一下吧

[LemonTency]

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
//二分查找
var minEatingSpeed = function(piles, h) {
    const { length } = piles
    let start = 1
    let end = Math.max.apply(null,piles)
    let mid

    while(start + 1 < end){
        mid = parseInt((start) + (end - start)/2)
        let times = spendTimes(piles,mid)
        if(times <= h){
            end = mid
        }else if(times > h){
            start = mid
        }
    }

    //只剩相邻两种情况
    if(spendTimes(piles,start) < h){
        return start
    }
    return end
};

var spendTimes = function(piles,speed){
    const { length } = piles
    let sum = 0
    for(let i = 0; i < length; i++){
        sum = sum + Math.ceil(piles[i]/speed)
    }
    return sum
}

[laiyingzeng]

var minEatingSpeed = function(piles, h) {
  let low = 0, high = Math.max(...piles)
  let mid
  while(high - low > 1) {
    mid = Math.floor((low+high)/2)
    let sum = 0
    for(let i of piles) {
      sum = sum + Math.ceil(i/mid)
    }
    if(sum > h) low = mid
    else high = mid
  }
  return high
};

[Jet12138]

var minEatingSpeed = function(piles, h) { // 思路： 从最小速度，整数递增到最大速度，遍历出来一个刚好<=h时间把piles吃完的速度。 if(h === piles.length){ return Math.max(...piles); }

let ratio = Math.floor(h/(piles.length));
let minspeed = Math.ceil(Math.min(...piles)/ratio);
let maxspeed = Math.ceil(Math.max(...piles)/ratio);

for(let i = minspeed; i<=maxspeed; i++){
    let time = 0;
    for(let pile of piles){
        time += Math.ceil(pile/i);
    }
    if(time <= h){
        return i;
    }
}

};