[leetcode]: 441. Arranging Coins

1.题目

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.
给n个硬币拼一个阶梯形状。第一行1个，第二行2个，第k行k个。问可以拼成一个几行的阶梯。
Example 1:
n = 5
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2。拼成一个2行的阶梯

Example 2:
n = 8
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3。拼成一个3行的阶梯。

2.分析

k行阶梯的硬币数为1+2+..+k=k*k+k<=2n
要求解这个k的大小。有两种方法。
方法1：数学方法求解。
k*k+k+1/4<=2n
(k+1/2)^2<=(2n+1/4)
k<=sqrt(2n+1/4)-1/2。
k 向下取整即可。
方法2：遍历或者二分查找。
已知k的范围为1-n，通过遍历或者二分查找找到最大的k满足k*k+k<=2n即可。

3.代码

方法1：

int arrangeCoins(int n) {
    return floor(sqrt((double)2 * n + 0.25) - 0.5);
}

方法2：

class Solution {
public:
    int arrangeCoins(int n) {
        if (n <= 1)
            return n;
        long long m = n;//避免溢出，统一转换成long long
        m *= 2;
        long long start = 1;
        long long end = n;
        while (start <= end) {
            long long mid = start + (end - start) / 2;
            if (mid*mid + mid <= m)
                start = mid + 1;
            else
                end = mid - 1;
        }
        return start - 1;
    }
};