By Long Luo
Leetcode 441. 排列硬币 的题解,有4种解决方法,前3种比较容易想到,位运算 比较难想到。
方法一:暴力
思路和算法
模拟硬币排列过程,从 ans=1 开始,逐行 ans+1,当硬币不足排列当前行时退出,注意返回时需要 ans−1,因为在排列完上一行时已经 +1 了,返回时需要 −1。
1 2 3 4 5 6 7 8 9 10
| public int arrangeCoins_bf(int n) { int ans = 1; while (n >= ans) { n -= ans; ans++; }
return ans - 1; }
|
复杂度分析
- 时间复杂度:O(n),因为总行数一定不超过 2(n+1)。
- 空间复杂度:O(1)。
方法二:二分查找
思路和算法
第 i 行必须有 i 个硬币(最后一行除外),总行数的增加所需要的硬币数是单调递增的,到第 i 行时总共使用的硬币数量为 total=2i×(i+1),我们的目标是寻找一个 i 使得 total≤n,可以利用二分加速在 1 到 2n+1 之间查找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| public int arrangeCoins_bs(int n) { long left = 1; long right = ((long) n + 1) / 2; while (left < right) { long mid = left + (right - left + 1) / 2; long sum = mid * (mid + 1) / 2; if (sum <= n) { left = mid; } else { right = mid - 1; } }
return (int) left; }
|
复杂度分析
- 时间复杂度:O(logn)。
- 空间复杂度:O(1)。
方法三:数学
思路和算法
第 x 行放满一共可以得到 2(x+1)×x 个硬币,则有:
2(x+1)×x=n
整理得一元二次方程
x2+x−2n=0
因为 n≥1,所以判别式
Δ=b2−4ac=8n+1>0
解得 x1=2−1−8n+1,x2=2−1+8n+1
x1<0,舍去不用,x2 即为硬币可以排列成的行数。
因为需要可以完整排列的行数,所以需要向下取整。
1 2 3 4 5
| public int arrangeCoins_math(int n) { int val = (int) (Math.sqrt((long) 8 * n + 1) - 1); return val / 2; }
|
复杂度分析
- 时间复杂度:O(1)。
- 空间复杂度:O(1)。
方法四:位运算
思路与算法:
- 因为 1≤n≤231−1,那么最长的数是 31 位,显然 sqrt(231−1)=log(sqrt(231−1))=16,也就是说答案最长也不会超过 16 位;
- 创建一个 mask,第15位设为 1,其余为 0;
- 先依次给 ans 按位从高到低设 1,检查 ans×(ans+1)>n,ans=0;
- mask 依次右移,直至 0,即为我们的答案。
代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| public static int arrangeCoins_bit(int n) { int mask = 1 << 15; long ans = 0; while (mask > 0) { ans |= mask; if (ans * (ans + 1) / 2 > n) { ans ^= mask; } mask >>= 1; }
return (int) ans; }
|
复杂度分析
- 时间复杂度:O(1)。
- 空间复杂度:O(1)。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗