leetcode-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:

1
2
3
4
5
6
7
8
n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

1
2
3
4
5
6
7
8
9
n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

分析

题意是给出 n 个硬币，第一行放1个，第二行放2个，以此类推，问有多少行能放满，简单粗暴的方法是一行行地从 n 个硬币中减去，最后返回行数即可，时间复杂度是 $O(n)$；也可以利用等差数列的和的公式解决。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int arrangeCoins(int n) {
        int current = 1, remains = n - 1;
        while (remains >= current+1) {
            current++;
            remains -= current;
        }
        return n == 0 ? 0: current;
    }
}

解决方案2(Java)

$n = \frac{(1+x)x}{2}$ => $x = \frac{\sqrt{8n+1}-1}{2}$

1
2
3
4
5
class Solution {
    public int arrangeCoins(int n) {
        return (int)((Math.sqrt(8*(long)n+1)-1)/2);
    }
}

题目来源