【LeetCode通關(guān)全記錄】441. 排列硬幣
題目地址：441. 排列硬幣
解法1：暴力迭代（最容易實(shí)現(xiàn)）
本題最容易實(shí)現(xiàn)的辦法就是設(shè)置一個(gè)計(jì)數(shù)器記錄行數(shù)涩金，每次循環(huán)給計(jì)數(shù)器加1并從總數(shù)中減去計(jì)數(shù)器的值，直到計(jì)數(shù)器的值比總數(shù)大時(shí)跳出循環(huán)蝉绷。
func arrangeCoins(n int) int {
if n <= 1 {
return 1
}
m := 1
for n >= m {
n -= m
m++
}
return m - 1
}
執(zhí)行用時(shí): 8 ms（超過(guò)40%的Golang提交記錄）
內(nèi)存消耗: 2.2 MB（超過(guò)61%的Golang提交記錄）
時(shí)間復(fù)雜度：O(n)鸭廷，for循環(huán)的執(zhí)行次數(shù)與n成正比；
空間復(fù)雜度：O(1)熔吗，只使用了常數(shù)個(gè)數(shù)的存儲(chǔ)空間。
解法2：二分+等差數(shù)列求和（最容易想到）
看到這道題的第一反應(yīng)就是等差數(shù)列求和佳晶，求和公式為(i * (i + 1)) / 2桅狠，但是沒(méi)有想到這個(gè)求和公式該怎么用于是改用解法1，把解法1寫(xiě)出來(lái)之后看了官方題解才明白原來(lái)本題中等差數(shù)列求和需要配合二分查找來(lái)使用轿秧。
func arrangeCoins(n int) int {
return sort.Search(n, func(i int) bool {
i++
return i * (i + 1) > 2 * n
})
}
執(zhí)行用時(shí): 4 ms（超過(guò)73%的Golang提交記錄）
內(nèi)存消耗: 2.2 MB（超過(guò)100%的Golang提交記錄）
時(shí)間復(fù)雜度：O(logn)中跌，二分查找的時(shí)間復(fù)雜度為O(logn)；
空間復(fù)雜度：O(1)菇篡，只使用了常數(shù)個(gè)數(shù)的存儲(chǔ)空間漩符。
解法3：等差數(shù)列求和+求根公式（效率最高）
這種解法是從官方題解中看到的，詳細(xì)解法可以看官方題解驱还，大概就是使用等差數(shù)列求和公式列方程并解一元二次方程嗜暴。不得不說(shuō)這是一種十分聰明的解法，明明是初中數(shù)學(xué)知識(shí)結(jié)果很難想到可以應(yīng)用在這道題里??
func arrangeCoins(n int) int {
return int((math.Sqrt(float64(8*n + 1)) - 1) / 2)
}
執(zhí)行用時(shí): 0 ms（超過(guò)100%的Golang提交記錄）
內(nèi)存消耗: 2.2 MB（超過(guò)99.25%的Golang提交記錄）
時(shí)間復(fù)雜度：O(1)议蟆，不考慮math.Sqrt()函數(shù)的內(nèi)部實(shí)現(xiàn)的話該算法的執(zhí)行效率不受問(wèn)題規(guī)模的影響闷沥；
空間復(fù)雜度：O(1)，只使用了常數(shù)個(gè)數(shù)的存儲(chǔ)空間咐容。
