441. Arranging Coins.md

441. Arranging Coins

思路

思路一

可以考虑用n不断减去1、2、3...直到不能再减，这样最后减去的那个数就是所求。

思路二

题目就是求满足k(k+1)/2 <= n的最大的k，即 k(k+1) <= 2n <= (k+1)(k+2)，所以k <= (int)sqrt(2n) <= k+1， 所以先判断(int)sqrt(2n)是否满足，若满足返回即可，否则返回(int)sqrt(2n) - 1。

思路三

在寻找满足k(k+1)/2 <= n的最大的k时也可以用二分搜索，代码略。

C++

思路一

class Solution {
public:
    int arrangeCoins(int n) {
        if(n <= 1) return n;
        int res = 1;
        while(n >= res){
            n -= res;
            res++;
        }
        return res - 1;
    }
};

思路二

class Solution {
public:
    int arrangeCoins(int n) {
        if(n <= 1) return n;
        int res = sqrt(2 * (double)n);
        long long i = res;
        if(i * (i + 1) / 2 <= n) return (int)i;
        return (int)(i - 1);
    }
};