[每日LeetCode] 441. Arranging Coins

  |   0 评论   |   248 浏览

原文链接 [每日LeetCode] 441. Arranging Coins

Description:

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:

n = 5

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

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

Example 2:

n = 8

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

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

思路:本题要求排列硬币,求最大阶梯数。

  • 思路一:简单粗暴的方法啊,从第一行开始,一行一行的从n中减去,如果此时剩余的硬币没法满足下一行需要的硬币数了,返回当前行数即可。

  • 思路二:看到其他的解法,直接使用求根公式求解。列出公式n = (1 + x) * x / 2, 用一元二次方程的求根公式可以得到 x = (-1 + sqrt(8 * n + 1)) / 2, 然后取整后就是能填满的行数。


C++代码(思路一)

class Solution {
public:
    int arrangeCoins(int n) {
        int cur = 1, rem = n - 1;
        while (rem >= cur + 1) {
            ++cur;
            rem -= cur;
        }
        return n == 0 ? 0 : cur;
    }
};

运行时间:12ms

运行内存:8.3M


C++代码(思路二)

class Solution {
public:
    int arrangeCoins(int n) {
        return (int)((-1 + sqrt(1 + 8 * (long)n)) / 2);
    }
};

运行时间:4ms

运行内存:8.3M

评论

发表评论