[leetcode]: 441. Arranging Coins

太过爱你忘了你带给我的痛 2022-06-15 06:15 125阅读 0赞

# 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;
        }
    };