题目要求
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
| You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.
Given n, find the total number of full staircase rows that can be formed.
n is a non-negative integer and fits within the range of a 32-bit signed integer.
Example 1:
n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.
|
用n个硬币搭台阶，要求第k级台阶必须有k个硬币。问n个硬币最多能够搭多少级台阶？
如五个硬币最多能够搭两级台阶，8个硬币最多搭三级台阶。
思路和代码
反过来讲，如果要搭k级台阶，那么k级台阶共包含(k+1) * k / 2个硬币。因此我们只需要找到可以搭建的台阶的边界，并采用二分法将边界不断缩小直到达到最大的台阶数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int arrangeCoins(int n) {
long rgt = (int) (Math.sqrt(n) * Math.sqrt(2) + 1);
long lft = 0;
while(lft <= rgt) {
long mid = lft + (rgt -lft) / 2;
long total = (mid + 1) * mid / 2;
if(total <= n) {
lft = mid + 1;
}else {
rgt = mid - 1;
}
}
return (int)lft-1;
}
|