题目描述
传送门
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
1
2
3
4
5
6
7
8
| n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
|
示例 2:
1
2
3
4
5
6
7
8
9
| n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.
|
解题思路
两个坑吧算是：1.注意题目给定的范围，因为涉及到前n项求和，所以在极限测试的时候会超出限制，所以采用long的形式进行定义，后期再进行强转返回。2.当right>=left的条件不满足的时候，退出while循环后返回的是right，而不是mid，因为由大向小缩进，所以right代表的是最后的结果。这两点注意之后就没啥了，常规的二分法。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int arrangeCoins(int n) {
long left,mid,right,sum;
left=1;
right=n;
mid=0;
while(right>=left){
mid=left+(right-left)/2;
sum=(1+mid)*mid/2;
if(sum>n){
right=mid-1;
}
else if(sum==n){
return (int)mid;
}
else {
left=mid+1;
}
}
return (int)right;
}
}
|