2023.12.24力扣每日一题——收集足够苹果的最小花园周长
2023.12.24
- 题目来源
- 我的题解
- 方法一 枚举
- 方法二 二分查找
题目来源
力扣每日一题2023.12.24；题序：1954
我的题解
方法一 枚举
假设边长为2n，周长则为8n。
n直接从1开始遍历到 ( 1 0 15 ) 1 3 (10^{15})^\frac{1}{3} (1015)31,为了简化计算，直接将右边界设为100000.
边长为2n的所有苹果之和计算：
对于坐标为(x,y)的树，有|x|+|y|个苹果，所有一块左上角坐标为(n,n)的正方形土地包括的苹果总数为： S n = ∑ x = − n n ∑ y = − n n ∣ x ∣ + ∣ y ∣ S_n=\sum_{x=-n}^{n}\sum_{y=-n}^{n}|x|+|y| Sn=∑x=−nn∑y=−nn∣x∣+∣y∣。
由于x和y是对称的，所以：
S n = 2 ∑ x = − n n ∑ y = − n n ∣ x ∣ S_n=2\sum_{x=-n}^{n}\sum_{y=-n}^{n}|x| Sn=2∑x=−nn∑y=−nn∣x∣
= 2 ∑ x = − n n ( 2 n + 1 ) ∣ x ∣ =2\sum_{x=-n}^{n}(2n+1)|x| =2∑x=−nn(2n+1)∣x∣
= 2 ( 2 n + 1 ) ∑ x = − n n ∣ x ∣ =2(2n+1)\sum_{x=-n}^{n}|x| =2(2n+1)∑x=−nn∣x∣
= 2 ( 2 n + 1 ) ( n + 1 ) =2(2n+1)(n+1) =2(2n+1)(n+1)
时间复杂度：O(m 1 3 ^\frac{1}{3} 31)
空间复杂度：O(1)
public long minimumPerimeter(long neededApples) {long res=1;for(;res<100000;res++){if(caulApples(res)<neededApples){continue;}else{break;}}return res*2*4;}public long caulApples(long len){long res=2*len*(len+1)*(2*len+1);return res;}
方法二 二分查找
因为Sn是随着n的增大而单调递增的，所以可以使用二分查找找到最小的n，使得Sn>=neededApples
时间复杂度：O(logm)
空间复杂度：O(1)
public long minimumPerimeter(long neededApples) {long left=1,right=100000; long ans=0; while(left<=right){long mid=((right-left)>>1)+left;long apples=caulApples(mid);if(apples>=neededApples){ans=mid;right=mid-1;}else if(apples<neededApples){left=mid+1;}}return left*2*4;
}
public long caulApples(long len){long res=2*len*(len+1)*(2*len+1);return res;
}
有任何问题，欢迎评论区交流，欢迎评论区提供其它解题思路（代码），也可以点个赞支持一下作者哈😄~