列表

详情

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

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。

你将会买下正中心坐标是 (0, 0) 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。

给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。

|x| 的值定义为：

 

示例 1：

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

示例 2：

输入：neededApples = 13
输出：16

示例 3：

输入：neededApples = 1000000000
输出：5040

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: long long minimumPerimeter(long long neededApples) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2.8 MB, 提交时间: 2023-12-24 10:48:37 

impl Solution {
    pub fn minimum_perimeter(needed_apples: i64) -> i64 {
        let mut n = (needed_apples as f64 / 4.0).cbrt() as i64;
        if 2 * n * (n + 1) * (2 * n + 1) < needed_apples {
            n += 1;
        }
        8 * n
    }
}

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-12-24 10:48:25 

func minimumPerimeter(neededApples int64) int64 {
    n := int64(math.Cbrt(float64(neededApples) / 4))
    if 2*n*(n+1)*(2*n+1) < neededApples {
        n++
    }
    return 8 * n
}

javascript 解法, 执行用时: 64 ms, 内存消耗: 41 MB, 提交时间: 2023-12-24 10:48:12 

/**
 * @param {number} neededApples
 * @return {number}
 */
var minimumPerimeter = function(neededApples) {
    let n = Math.floor(Math.cbrt(neededApples / 4));
    if (2 * n * (n + 1) * (2 * n + 1) < neededApples) {
        n++;
    }
    return 8 * n;
};

java 解法, 执行用时: 1 ms, 内存消耗: 39.6 MB, 提交时间: 2023-12-24 10:47:55 

class Solution {
    public long minimumPerimeter(long neededApples) {
        long n = (long) Math.cbrt(neededApples / 4.0);
        if (2 * n * (n + 1) * (2 * n + 1) < neededApples) {
            n++;
        }
        return 8 * n;
    }
}

python3 解法, 执行用时: 40 ms, 内存消耗: 16 MB, 提交时间: 2023-05-30 10:11:48 

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

cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2023-05-30 10:11:35 

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

cpp 解法, 执行用时: 12 ms, 内存消耗: 5.8 MB, 提交时间: 2023-05-30 10:11:22 

class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
        long long n = 1;
        for(; 2 * n * (n + 1) * (2 * n + 1) < neededApples; ++n);
        return n * 8;
    }
};

python3 解法, 执行用时: 1444 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-30 10:11:06 

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

上一题

© 2024 leetcode.cn