[Easy]LeetCode#441. 排列硬币
题目原地址
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
示例 1:
1
2
3
4
5
6
| n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
|
基本算法，这个easy，最简单的就是递减
1
2
3
4
5
6
7
8
| func arrangeCoins(n int) int {
res := 0
for i := 1; n >= i; i++ {
n -= i
res = i
}
return res
}
|
二分搜索，使用二分法找到前l行之和正好大于给定数n的情况
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
| func arrangeCoins(n int) int {
if n == 0 {
return 0
}
if n <0 {
return -1
}
left, right := 1, n
for left <= right {
mid := left + (right-left)/2
sum := mid * (1+mid)/2
if sum > n {
right = mid-1
}
if sum < n {
left = mid +1
}
if sum == n {
return mid
}
}
return left-1
}
|
执拗前行