网站seo外链接,网页打不开connection,wordpress 多数据库,网络网站建设价格文章目录 Tag题目来源解题思路方法一#xff1a;二分枚举答案 写在最后 Tag
【二分枚举答案】【二维网格】【2023-12-24】 题目来源
1954. 收集足够苹果的最小花园周长 解题思路
方法一#xff1a;二分枚举答案
思路
通过如下过程#xff0c;我们可以求出边长为 2n 时二分枚举答案 写在最后 Tag
【二分枚举答案】【二维网格】【2023-12-24】 题目来源
1954. 收集足够苹果的最小花园周长 解题思路
方法一二分枚举答案
思路
通过如下过程我们可以求出边长为 2n 时二维网格可以容纳的苹果数量为 2 n ( n 1 ) ( 2 n 1 ) 2n(n1)(2n1) 2n(n1)(2n1)
图片来源 【图解】O(1) 做法Python/Java/C/Go/JS/Rust。 随着边长的增大二维网格可以容纳的苹果数量也在增大。于是我们可以二分枚举二维网格的边长找出可以容纳 neededApples 个苹果的最小二维网格边长。
二分边界为 [1, 100000]其中 100000 是根据边长为 2n 的二维网格可以容纳苹果 2n(n1)(2n1) 估算得到。
算法
#define ll long long
class Solution {
public:long long minimumPerimeter(long long neededApples) {int l 1, r 100000;int ans 0;while(l r){int mid (l r) 1;if((ll) 2*mid*(mid1)*(2*mid1) neededApples){ans mid;r mid - 1;}else{l mid 1;}}return ans * 8;}
};复杂度分析
时间复杂度 O ( l o g m ) O(logm) O(logm) m n e e d e d A p p l e s 3 m \sqrt[3]{neededApples} m3neededApples 。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
