二分猜答案
单调序列上找值
69. x 的平方根 mid
给你一个非负整数 x ,计算并返回 x 的 算术平方根。 由于返回类型是整数,结果只保留整数部分,小数部分将被舍去。
解法 1 二分
从一个单调序列上找一个值, 二分
找的右边界
Java
class Solution {
public int mySqrt(int x) {
long l = 0, h = x;
while (l < h) {
long m = l + (h - l + 1 >> 1);
if (m * m <= x) l = m;
else h = m - 1;
}
return (int) l;
}
}
解法 2 牛顿迭代法
令
, 也就是求函数 的零点
借助泰勒级数, 不断地求过点的切线与 轴的交点, 再求函数 在交点横坐标处的切线, 直到 逼近 0
点:
切线:
即
令
java
class Solution {
public int mySqrt(int x) {
int c = x;
double x0 = c;
while (x0 * x0 - c > 1e6) {
x0 = 0.5 * (x0 + c / x0);
}
return (int) x0;
}
}
满足条件的上界/下界
875. 爱吃香蕉的珂珂 mid
剑指 Offer II 073. 狒狒吃香蕉
珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i]根香蕉。警卫已经离开了,将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 k 根。如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数)。
java
class Solution {
public int minEatingSpeed(int[] piles, int h) {
int r = Integer.MIN_VALUE;
for (int e : piles) {
r = Math.max(r, e);
}
int l = 1;
while (l < r) {
int m = l + (r - l >> 1);
if (check(piles, h, m)) r = m;
else l = m + 1;
}
return l;
}
private boolean check(int[] piles, int h, int k) {
int sum = 0;
for (int e : piles) {
sum += (e + k - 1) / k;
}
return sum <= h;
}
}