欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

441. 排列硬币

程序员文章站 2024-03-16 08:43:28
...

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

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

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

 

 

解:实际上就是相当于梯形体积计算。

      测试案例中有几个位数比较大的数,所以中间还需要在long和int之间进行强转型,不然会有200个测试案例溢出,从而导致答案错误。另外,二分法和自加上去的,基本都会超时,这里利用java Math.sqrt进行计算。

public class Solution {
    public int arrangeCoins(int n) {
        /* 数学推导
        (1+k)*k/2 = n
        k+k*k = 2*n
        k*k + k + 0.25 = 2*n + 0.25
        (k + 0.5) ^ 2 = 2*n +0.25
        k + 0.5 = sqrt(2*n + 0.25)
        k = sqrt(2*n + 0.25) - 0.5
        */
        return (int) (Math.sqrt(2*(long)n+0.25) - 0.5);
    }
}