你總共有 n 枚硬幣痊焊，你需要將它們擺成一個(gè)階梯形狀，第 k 行就必須正好有 k 枚硬幣忿峻。
給定一個(gè)數(shù)字 n薄啥，找出可形成完整階梯行的總行數(shù)。
n 是一個(gè)非負(fù)整數(shù)逛尚，并且在32位有符號(hào)整型的范圍內(nèi)垄惧。
示例 1:
n = 5
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤
因?yàn)榈谌胁煌暾苑祷?.
示例 2:
n = 8
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因?yàn)榈谒男胁煌暾履苑祷?.
有2種解法：
這道題要用硬幣去一層層堆樓梯到逊。其實(shí)很容易想到累加和。
題目的意思其實(shí)就是從1~x層完整樓梯硬幣數(shù)量加起來(lái)滤钱，要小于等于n觉壶，求最大的x。說(shuō)到加起來(lái)的數(shù)量件缸，很容易想到求累加和铜靶，我們知道求累加和的公式為：
sum = (1+x)*x/2
這里就是要求 sum <= n 了。我們反過(guò)來(lái)求層數(shù)x他炊。如果直接開(kāi)方來(lái)求會(huì)存在錯(cuò)誤争剿，必須因式分解求得準(zhǔn)確的x值：
(1+x)x/2 <= n
x + xx <= 2n
4xx + 4x <= 8n
(2x + 1)(2x + 1) - 1 <= 8n
x <= (sqrt(8n + 1) - 1) / 2
其中Math.sqrt()是求平方根的函數(shù)。這樣我們就求出了x
var arrangeCoins = function(n) {
//O(1)
return Math.floor((Math.sqrt(8*n + 1) - 1)/2);
};
var arrangeCoins = function(n) {
//O(n)
var i = 1;
while(n >= i){
n = n - i;
i++;
}
return i-1;
};
