441. 排列硬币
程序员文章站
2024-03-16 08:43:28
...
你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。
给定一个数字 n,找出可形成完整阶梯行的总行数。
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);
}
}
上一篇: Gson解析泛型对象时TypeToken的使用方法
下一篇: 367. 有效的完全平方数