【題目描述】
你總共有 n 枚硬幣锌介，你需要將它們擺成一個階梯形狀，第 k 行就必須正好有 k 枚硬幣膀钠。
給定一個數(shù)字 n掏湾，找出可形成完整階梯行的總行數(shù)裹虫。
n 是一個非負整數(shù)，并且在32位有符號整型的范圍內(nèi)融击。
【示例1】
n = 5
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤
因為第三行不完整筑公，所以返回2.
【示例2】
n = 8
硬幣可排列成以下幾行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因為第四行不完整，所以返回3.
【思路1】
1尊浪、時間復(fù)雜度O(n)
2匣屡、空間復(fù)雜度O(1)
代碼實現(xiàn)：
func arrangeCoins(_ n: Int) -> Int {
if n == 0 { return 0 }
if n <= 2 { return 1 }
var res = 0
for i in 1..<n {
if n-res < i {
return i-1
} else if n-res == i {
return i
}
res+=i
}
return 0
}
func arrangeCoins(_ n: Int) -> Int {
if n == 0 { return 0 }
if n <= 2 { return 1 }
var res = 0
var num = 0
while res <= n {
num+=1
res+=num
}
return num - 1
}
【思路2】
1、數(shù)學(xué)方法
2拇涤、根據(jù)等差數(shù)列之和
代碼實現(xiàn)：
func arrangeCoins(_ n: Int) -> Int {//數(shù)學(xué)方法
return Int((-1+sqrt(Double(1+8*n)))/2)
}
