收集足够苹果的最小花园周长(LeetCode日记)

LeetCode-1954-收集足够苹果的最小花园周长

题目信息:

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 $(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<=10^{15}$
  相关标签 ：数学，二分查找

题解

首先我们要承认这样一个事实：如果正方形土地的右上角坐标为 $(n,n)$，即边长为 $2n$，周长为 $8n$，那么其中包含的苹果总数为：$$S_n=2n(n+1)(2n+1)$$
下面我们来证明一下这个公式：
对于坐标为 $(x,y)$ 的树，它有 $\mid x\mid +\mid y\mid$ 个苹果。因此，一块右上角坐标为 $(n,n)$ 的正方形土地包含的苹果总数为：(x与y对称)
$$\begin{array}{rl}{S}_n& =2\sum _{x=?n}^n\sum _{y=?n}^n|x|+|y|\\ & =2\sum _{x=?n}^n\sum _{y=?n}^n|x|\\ & =2\sum _{x=?n}^n(2n+1)|x|\\ & =2(2n+1)\sum _{x=?n}^n|x|\\ & =2n(n+1)(2n+1)\end{array}$$
基于这样的思路，我们可以有两种方法来实现算法：暴力枚举与二分查找。

方法1：暴力枚举

从小到大枚举 $n$，直到 $2n(n+1)(2n+1)\ge neededApples$ 为止。

实现代码(Python)

class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        n = 1
        while 2 * n * (n + 1) * (2 * n + 1) < neededApples:
            n += 1
        l = n * 8
        return l

复杂度分析：

• 时间复杂度：$O(m^{1/3})$ 其中 ，m为题目中所提到的 $neededApples$。
• 空间复杂度：$O(1)$

方法2：二分查找

由于 $S_n$是随着 $n$ 单调递增的，那么我们可以通过二分查找的方法，找出最小的满足 $Sn\ge neededApplesS的$n值即为答案。
?通过提示我们可知： $1<=neededApples<=10^{15}$ ， 我们计算的坐标$(n,n)$一定会存在一个上界，可以使用我们上文计算的式子$S_n=2n(n+1)(2n+1)$来进行推理得到最大的n。

实现代码(Python)

class Solution:
    def minimumPerimeter(self, neededApples: int) -> int:
        low, high, n = 1, 100000, 0
        while left <= right:
            mid = (low + high) // 2
            if 2 * mid * (mid + 1) * (mid * 2 + 1) >= neededApples:
                n = mid
                high = mid - 1
            else:
                low = mid + 1
        return n * 8

复杂度分析：

• 时间复杂度：$O(lo{g}_{2}m)$ 其中 ，m为题目中所提到的 $neededApples$。
• 空间复杂度：$O(1)$

题记：

---

• 研究生在读，我会尽量保持LeetCode每日一题的思路和代码输出。希望大家多多支持。
• 水平有限，希望各位大佬能够批评指正。您的教诲是我进步的船帆。
• 希望各位跟我一样的小白能跟我一起参与到做题和讨论中来。共同进步是我所能期盼的最高愿想。
• 您的点赞和关注是我坚持分享的动力泉源，希望能将这件简单平凡的事一直做下去。感谢大家。

---