排列硬币Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

你总共有 n 枚硬币，并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯，其第 i 行必须正好有 i 枚硬币。阶梯的最后一行可能是不完整的。

给你一个数字 n ，计算并返回可形成完整阶梯行的总行数。

示例 1：

输入：n = 5
输出：2
解释：因为第三行不完整，所以返回 2 。

示例 2：

输入：n = 8
输出：3
解释：因为第四行不完整，所以返回 3 。

提示：

1 <= n <= 2³¹ - 1

# 思路

递归思想，每次加上比上一次大1的数，如果最终结果大于n，返回当前行的上一行i-1;

# 解法


class Solution {
    // java, 递归思想，每次加上比上一次大1的数，如果最终结果大于n，返回当前行的上一行i-1;

    long sum = 0;  //为防止越界，这里定义为long型数据。
    public int getNum(int n, int i){
        sum += i;
        if(sum > n) return i-1;  //当前sum大于n时，说明当前行节点数不够i，应该返回上一行的节点数i-1
        else if(n == sum) return i;
        return getNum(n, i+1);
    }

    public int arrangeCoins(int n) {
        return getNum(n, 0);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 总结

分析出几种情况，然后分别对各个情况实现