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

珂珂喜欢吃香蕉。这里有 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

解答：二分查找

二分查找也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写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

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);

/* 
题解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;
}

第一次参与，加油
`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

};`

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
};

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

/**
 * @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
}

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
};

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;
    }
}

};

Navigation Menu

Repository navigation

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

解答：二分查找

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

sisterAn commented on Sep 18, 2020

解答：二分查找

Glittergalaxy commented on Sep 18, 2020

marlboroKay commented on Sep 18, 2020

xiaoyiyi123 commented on Sep 18, 2020

zo11o commented on Sep 22, 2020

LemonTency commented on Apr 4, 2021

laiyingzeng commented on Jun 18, 2021

Jet12138 commented on Sep 12, 2022

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions