收集足够苹果的最小花园周长
难度:
标签:
题目描述
给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。
你将会买下正中心坐标是 (0, 0) 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。
给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。
|x| 的值定义为：
- 如果
x >= 0，那么值为x - 如果
x < 0，那么值为-x
示例 1：
输入：neededApples = 1 输出：8 解释：边长长度为 1 的正方形不包含任何苹果。 但是边长为 2 的正方形包含 12 个苹果（如上图所示）。 周长为 2 * 4 = 8 。
示例 2：
输入：neededApples = 13 输出：16
示例 3：
输入：neededApples = 1000000000 输出：5040
提示：
1 <= neededApples <= 1015
代码结果
运行时间: 36 ms, 内存: 15.9 MB
/*
* 题目思路:
* 1. 与 Java 代码相同，使用流的方式进行计算。
*/
import java.util.stream.IntStream;
public class Solution {
public long minPerimeter(int neededApples) {
long[] apples = {0};
int[] n = {0};
IntStream.iterate(1, i -> i + 1)
.filter(i -> {
apples[0] += 4L * i * (i + 1);
n[0] = i;
return apples[0] >= neededApples;
})
.findFirst();
return 8L * n[0];
}
}
解释
方法:
此题解采用二分查找的方式确定最小的正方形边长，使其包含的苹果总数至少为neededApples。首先，设置两个指针l和r分别代表可能的正方形边长的下限和上限。通过迭代的方式，我们计算每一个中间值mid所代表的正方形边长能够包含的苹果数量，这是通过特定的公式计算得出的。如果这个数量满足所需的苹果数量neededApples，我们则尝试减小正方形的边长（通过调整r）；反之，我们增大边长（调整l）。这个迭代过程一直进行到l和r相遇，此时，l（或r）即为所求的最小边长，而最小周长为这个边长的四倍乘以2。
时间复杂度:
O(log(maxL))
空间复杂度:
O(1)
代码细节讲解
🦆
二分查找策略中，为什么将100000作为正方形边长的上限？这个数字是如何确定的？
▷🦆
在二分查找的过程中，mid的苹果数量计算公式是怎样的？请详细解释这个公式的由来和它代表的含义。
▷🦆
题解中提到的二分查找迭代次数大约为16.6次，这是如何计算得出的？请解释这个计算过程。
▷🦆
在缩小搜索范围的条件`if 2 * mid * (mid + 1) * (2 * mid + 1) >= neededApples:`中，为什么选择这样的形式来估计包含的苹果数量？
▷