Leetcode441. 排列硬币
1. 问题描述
2. 思路
- 线性扫描
- 二分查找
前n行如果全部有硬币,总数为:n * (n - 1))/ 2
3. 代码
3.1 思路1
func arrangeCoins(n int) int {
var res int
count := 1
for n >= count {
n = n - count
count++
res++
}
return res
}
3.2 思路2
func arrangeCoins(n int) int {
left, right := 0, n
for left <= right {
mid := left + (right - left) / 2
if mid * (mid + 1) / 2 == n {
return mid
} else if mid * (mid + 1) / 2 < n {
left = mid + 1
} else {
right = mid - 1
}
}
return right
}
func arrangeCoins(n int) int {
return sort.Search(n, func(k int) bool {
k++;
return k*(k+1) > 2*n
})
}
|