[Leetcode][441. 排列硬币] 4种解法:暴力,二分查找,数学,位运算
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// BF O(sqrtn) O(1)
public int arrangeCoins_bf(int n) {
int ans = 1;
while (n >= ans) {
n -= ans;
ans++;
}
return ans - 1;
}
复杂度分析
- 时间复杂度:\(O(\sqrt{n})\),因为总行数一定不超过 \(2(\sqrt{n}+1)\)。
- 空间复杂度:\(O(1)\)。
方法二:二分查找
思路和算法
第 \(i\) 行必须有 \(i\) 个硬币(最后一行除外),总行数的增加所需要的硬币数是单调递增的,到第 \(i\) 行时总共使用的硬币数量为 \(total = \frac{i \times (i + 1)}{2}\),我们的目标是寻找一个 \(i\) 使得 \(total \leq n\),可以利用二分加速在 \(1\) 到 \(\frac{n + 1}{2}\) 之间查找。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// BS O(logn) O(1)
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\) 行放满一共可以得到 \(\frac{(x + 1) \times x}{2}\) 个硬币,则有:
\[ \frac{(x + 1) \times x}{2} = n \]
整理得一元二次方程
\[ x^2 + x - 2n = 0 \]
因为 \(n \ge 1\),所以判别式
\[ \Delta = b^2 - 4ac = 8n + 1 > 0 \]
解得 \(x_1 = \frac{-1 - \sqrt{8n + 1}}{2}\),\(x_2 = \frac{-1 + \sqrt{8n + 1}}{2}\)
\(x_1 < 0\),舍去不用,\(x_2\) 即为硬币可以排列成的行数。
因为需要可以完整排列的行数,所以需要向下取整。1
2
3
4
5// Math O(1) O(1)
public int arrangeCoins_math(int n) {
int val = (int) (Math.sqrt((long) 8 * n + 1) - 1);
return val / 2;
}
复杂度分析
- 时间复杂度:\(O(1)\)。
- 空间复杂度:\(O(1)\)。
方法四:位运算
思路与算法:
- 因为 \(1 \leq n \leq 2^{31} - 1\),那么最长的数是 \(31\) 位,显然 \(sqrt(2^{31} - 1) = log(sqrt(2^{31} - 1)) = 16\),也就是说答案最长也不会超过 \(16\) 位;
- 创建一个 \(mask\),第\(15\)位设为 \(1\),其余为 \(0\);
- 先依次给 \(ans\) 按位从高到低设 \(1\),检查 \(ans \times (ans + 1) > n\),\(ans = 0\);
- \(mask\) 依次右移,直至 \(0\),即为我们的答案。
代码如下所示:1
2
3
4
5
6
7
8
9
10
11
12
13
14// Bit O(1) O(1)
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. 😉😃💗