Medium

题目描述

在一个表示为无限二维网格的花园中，每个整数坐标处都种植了一棵苹果树。种植在整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。

你将购买一个以 (0, 0) 为中心的轴对齐正方形土地。

给定一个整数 neededApples，返回能够在其内部或周长上至少包含 neededApples 个苹果的土地的最小周长。

|x| 的值定义为：

  • 如果 x >= 0，则 |x| = x
  • 如果 x < 0，则 |x| = -x

示例 1：

输入：neededApples = 1
输出：8
解释：边长为 1 的正方形不包含任何苹果。
但是，边长为 2 的正方形内有 12 个苹果（如上图所示）。
周长为 2 * 4 = 8。

示例 2：

输入：neededApples = 13
输出：16

示例 3：

输入：neededApples = 1000000000
输出：5040

约束条件：

  • 1 <= neededApples <= 10^15

提示：

  • 找出边长为 L 的正方形内苹果数量的公式
  • 遍历正方形的可能长度，直到收集到足够的苹果

解题思路

这道题需要找到以原点为中心的正方形内苹果总数的数学规律。

数学分析： 对于边长为 2n 的正方形（半边长为 n），我们需要计算所有满足 |i| ≤ n 且 |j| ≤ n 的点 (i,j) 的苹果数量之和。

每个点 (i,j) 的苹果数量为 |i| + |j|。我们可以将这个问题分解：

  1. 当 i=0 时，苹果数量为 ∑(j=-n到n) |j| = 2∑(j=1到n) j = 2 × n(n+1)/2 = n(n+1)
  2. 当 j=0 时，类似地得到 n(n+1)
  3. 其他象限的苹果可以通过对称性计算

通过数学推导，边长为 2n 的正方形内总苹果数为：2n(n+1)(2n+1)

解法选择：

  1. 暴力枚举法：从 n=1 开始逐个计算，直到满足条件
  2. 二分搜索法：由于苹果数量随 n 单调递增，可以用二分查找最小的 n

推荐使用二分搜索法，时间复杂度更优。

注意正方形的周长为 8n（边长 2n × 4 条边）。

代码实现

class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
        long long left = 1, right = 100000;
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            long long apples = 2 * mid * (mid + 1) * (2 * mid + 1);
            
            if (apples >= neededApples) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return 8 * left;
    }
};

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

public class Solution {
    public long MinimumPerimeter(long neededApples) {
        long left = 1, right = 100000;
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            long apples = 2 * mid * (mid + 1) * (2 * mid + 1);
            
            if (apples >= neededApples) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return 8 * left;
    }
}

/**
 * @param {number} neededApples
 * @return {number}
 */
var minimumPerimeter = function(neededApples) {
    let left = 1, right = 100000;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let apples = 2 * mid * (mid + 1) * (2 * mid + 1);
        
        if (apples >= neededApples) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return 8 * left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(log n)，其中 n 是答案的半边长，二分搜索的复杂度
空间复杂度O(1)，只使用常量额外空间