05 August 2008
简单DP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int arrangeCoins(int n) {
if (n <= 0) {
return -1;
}
long usedCoins = 0;
long currentRowCoins = 1;
int rows = 0;
while (usedCoins < n) {
if (n - usedCoins >= currentRowCoins) {
rows++;
}
usedCoins += currentRowCoins;
currentRowCoins += 1;
}
return rows;
}
}
1
2
3
4
5
6
7
8
9
10
class Solution {
public int arrangeCoins(int n) {
int i = 0;
while (n > 0) {
i += 1;
n -= i;
}
return n == 0 ? i : i-1;
}
}
通过求和公式做Binary Search
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public int arrangeCoins(int n) {
if (n <= 0) {
throw new IllegalArgumentException("Input should be positive");
}
if (n == 1) {
return 1;
}
if (n <= 3) {
return n == 2 ? 1 : 2;
}
// 以上都是corner cases，因为从right从n/2开始，需要特别处理
long left = 2;
long right = n / 2;
long usedCoins = 0;
while (left + 1 < right) {
long mid = left + (right - left) / 2;
usedCoins = mid * (mid + 1) / 2;
if (usedCoins == n) {
return (int)mid;
} else if (usedCoins > n) {
right = mid;
} else {
left = mid;
}
}
if (right * (right + 1) / 2 <= n) {
return (int)right;
}
return (int)left;
}
}