leetcode 441. 排列硬币

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

https://leetcode.com/problems/arranging-coins/

题目描述：你总共有n枚硬币，你需要将它们摆成一个阶梯形状，第k行就必须正好有k枚硬币。

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

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

样例输入：n=5，样例输出2，因为第三行不完整。

样例输入：n=8，样例输出3，因为第四行不完整。

---

思路：数学推导一下。

因为 S = 1+2+…+n = n(n + 1)/2

所以 2S = n^2 + n => 2S + 1/4 = n^2 + n + 1/4 => 2S + 1/4 = (n + 1/2)^2 => n = sqrt(2S + 1/4) - 1/2

class Solution {
    public int arrangeCoins(int n) {
        return (int) (Math.sqrt((double) (n) * 2 + 0.25) - 0.5);
    }
}

Sub

扫码关注微信公众号，随时随地，掌握最新技术资讯

微信