leetcode

どーも!

今回もLeetCodeをやっていこうと思います!

441. Arranging Coins

今回の問題はArranging Coinsです。

これは、手元にあるn枚のコインを1, 2, 3, 4....と階段のように並べていき、最終的に階段上になるのは何行か?

を求める問題です。

もし階段の途中までしかできない場合、その行はノーカウントになります。

以下、上記リンクからの例です。

n = 5

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

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

コインの枚数が5枚の場合、階段上に並べると、1, 2の行は行が完結しますが、3段目はあと1個足りません。

そのため、この場合は完成している分の2が答えとなります。

さて、それでわアルゴリズム考えます。

アルゴリズム

アルゴリズムとしては、nからループ回数をそのまま引いていき、nが負の値になるタイミングの一度をのぞき、そのループ回数が答えとなるはずです。

イメージだと以下です。

n = 5

¤           ## 5-1 = 4 返す値に+1
¤ ¤         ## 4-2 = 2 返す値に+1
¤ ¤         ## 2-3 = -1 ここで−になったので、この回はノーカン!

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

あまりガッツリとした解説ではないですが、わかりやすいかと思います!

階段の完成した分だけnから引いていく..といった感じですね!

それでは最後に提出したコードを置いておきます!

ご参考ください!

提出したコード

class Solution:
    def arrangeCoins(self, n: int) -> int:
        i = 0
        while n >= 0:
            i = i + 1
            n = n-i
        return i-1

## 結果
Runtime: 888 ms, faster than 41.35% of Python3 online submissions for Arranging Coins.
Memory Usage: 14.3 MB, less than 9.84% of Python3 online submissions for Arranging Coins.

おすすめの記事