[Leetcode][441. 排列硬币] 4种解法:暴力,二分查找,数学,位运算

By Long Luo

Leetcode 441. 排列硬币 的题解,有4种解决方法,前3种比较容易想到,位运算 比较难想到。

方法一:暴力

思路和算法

模拟硬币排列过程,从ans=1ans = 1开始,逐行ans+1ans + 1,当硬币不足排列当前行时退出,注意返回时需要ans1 ans - 1,因为在排列完上一行时已经+1+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(n)O(\sqrt{n}),因为总行数一定不超过2(n+1)2(\sqrt{n}+1)
  • 空间复杂度O(1)O(1)

方法二:二分查找

思路和算法

ii行必须有ii个硬币(最后一行除外),总行数的增加所需要的硬币数是单调递增的,到第ii行时总共使用的硬币数量为total=i×(i+1)2total = \frac{i \times (i + 1)}{2},我们的目标是寻找一个ii使得totalntotal \leq n,可以利用二分加速在11n+12\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(logn)
  • 空间复杂度O(1)O(1)

方法三:数学

思路和算法

xx行放满一共可以得到(x+1)×x2\frac{(x + 1) \times x}{2}个硬币,则有:

(x+1)×x2=n\frac{(x + 1) \times x}{2} = n

整理得一元二次方程

x2+x2n=0x^2 + x - 2n = 0

因为n1n \ge 1,所以判别式

Δ=b24ac=8n+1>0\Delta = b^2 - 4ac = 8n + 1 > 0

解得x1=18n+12x_1 = \frac{-1 - \sqrt{8n + 1}}{2}, x2=1+8n+12x_2 = \frac{-1 + \sqrt{8n + 1}}{2}

x1<0x_1 < 0,舍去不用,x2x_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)
  • 空间复杂度O(1)O(1)

方法四:位运算

思路与算法:

  1. 因为1n23111 \leq n \leq 2^{31} - 1,那么最长的数是3131位,显然sqrt(2311)=log(sqrt(2311))=16sqrt(2^{31} - 1) = log(sqrt(2^{31} - 1)) = 16,也就是说答案最长也不会超过1616位;
  2. 创建一个maskmask,第1515位设为11,其余为00
  3. 先依次给ansans按位从高到低设11,检查ans×(ans+1)>nans \times (ans + 1) > nans=0ans = 0
  4. mask依次右移,直至00,即为我们的答案。

代码如下所示:

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)
  • 空间复杂度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. 😉😃💗