首页 > 代码库 > 441. 硬币楼梯 Arranging Coins
441. 硬币楼梯 Arranging Coins
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.
Example 1:
n = 5 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8 The coins can form the following rows: ¤ ¤ ¤ ¤ ¤ ¤ ¤ ¤ Because the 4th row is incomplete, we return 3.
题意:给出n,返回可以组成的完整楼梯的层数
sum = (1+x)*x/2
这里就是要求 sum <= n 了。我们反过来求层数x。如果直接开方来求会存在错误,必须因式分解求得准确的x值:
(1+x)*x/2 <= n
x + x*x <= 2*n
4*x*x + 4*x <= 8*n
(2*x + 1)*(2*x + 1) - 1 <= 8*n
x <= (sqrt(8*n + 1) - 1) / 2
其中Math.sqrt()是求平方根的函数。这样我们就求出了x,最后要记得强制转换为int型数。
static public int ArrangingCoins(int n) {
return (int)((Math.Sqrt(8 * (long)n + 1) - 1) / 2);
}
null
441. 硬币楼梯 Arranging Coins
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。