[Easy]LeetCode#441. 排列硬币

[Easy]LeetCode#441. 排列硬币

题目原地址

你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。

给定一个数字 n,找出可形成完整阶梯行的总行数。

n 是一个非负整数,并且在32位有符号整型的范围内。

示例 1:

n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整,所以返回2.
  • 基本算法,这个easy,最简单的就是递减
func arrangeCoins(n int) int {
    res := 0
    for i := 1; n >= i; i++ {
        n -= i
        res = i
    }
    return res
}
  • 二分搜索,使用二分法找到前l行之和正好大于给定数n的情况
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
}