迫于就業(yè)的壓力尿招，不得不先放下 iOS 開發(fā)的學(xué)習(xí)券腔，開始走上漫漫刷題路畔规。
今天我想聊聊 LeetCode 上的第279題－Perfect Squares局扶，花了挺長(zhǎng)時(shí)間的，試了很多方法叁扫，作為一個(gè)算法新手三妈，個(gè)人感覺這題很好，對(duì)我的水平提升很有幫助莫绣。我在這里和大家分享一下我的想法畴蒲。下面是題目：
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ... ) which sum to n.
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13,return 2 because 13 = 4 + 9.
大致意思就是，“給一個(gè)正數(shù) n对室， 找到和為 n 的平方數(shù), 給出最少的平方數(shù)個(gè)數(shù)”模燥。
BFS
我剛開始想到的是用 BFS，經(jīng)過一番實(shí)踐掩宜，感覺代碼是對(duì)的蔫骂，但是 Time Limit Exceeded。畢竟用了 2 層循環(huán)牺汤。于是我就找了個(gè)字典（Dictionary）來存已經(jīng)算過的節(jié)點(diǎn)辽旋，比如一個(gè)很大的數(shù) n，有很大幾率 n - i * i 這個(gè)節(jié)點(diǎn)和后面算出來的 m - j * j 是相等的檐迟。那么就不再重新計(jì)算补胚。但是，還是超時(shí)了追迟。這部分代碼2個(gè)小時(shí)前被我扔了溶其，我就不在這里重新寫了。
Lagrange's four-square theorem
這里算是完全用數(shù)學(xué)知識(shí)解決了這個(gè)問題敦间。不知道四平方和定理的請(qǐng)參考 wikipedia握联。話說童鞋們最好看英文版的 wiki桦沉，別翻譯成中文比較好。我也不說英文更專業(yè)金闽，雖然好像就是這么回事 ＝＝ 因?yàn)橛袀€(gè)公式非常重要纯露，而解這題全靠這個(gè)公式：
這個(gè)定理就是講，任何數(shù)都可以由4個(gè)平方數(shù)組成代芜，即 n = a^2 + b^2 + c^2 + d^2埠褪，所以這題的答案已經(jīng)限定在了 [1,4] 之間。
而上面這個(gè)公式的發(fā)明者－Adrien-Marie Legendre 又補(bǔ)充了這個(gè)定理：除了滿足以上這個(gè)公式的數(shù)以外的任何數(shù)都可以由3個(gè)平方數(shù)組成挤庇。所以钞速，這個(gè)答案又可以縮小范圍了。范圍都已經(jīng)縮小到 [1,3] 了嫡秕，我們開始求解渴语。
先排除4個(gè)的情況：
while myN & 3 == 0 {
myN >>= 2
}
if myN % 8 == 7 {
return 4
}
因?yàn)?和2的情況比較容易排除，先把1和2的排除昆咽。
var index = Int(sqrt(Double(n)))
while index > 0 {
let tmp = Double(n - index * index)
let sqrtTmp = Int(sqrt(tmp))
if n == sqrtTmp * sqrtTmp + index * index {
return sqrtTmp == 0 ? 1 : 2
}
index -= 1
}
上面的代碼就是說驾凶，如果一個(gè)數(shù)由2個(gè)平方數(shù)組成，如果其中一個(gè)平方數(shù)是0掷酗，那么就是1调违，如果不是0，那就是2泻轰。
剩下的就是3了技肩，直接 return 3 就行了。在知道這個(gè)數(shù)學(xué)公式的情況下浮声，這個(gè)方法還是很簡(jiǎn)單的虚婿。
DP
我剛刷題沒幾天，對(duì)于 DP 的推理過程還不是很熟練泳挥，琢磨了好久雳锋。一旦琢磨出來了，又覺得好簡(jiǎn)單羡洁，換一題玷过，又可以琢磨一年。lol
初級(jí)的 DP 的使用方式差不多就是 Recursion + Memorization筑煮，就是遞歸和緩存辛蚊。這里我們用一個(gè)數(shù)組來存儲(chǔ)已經(jīng)算過的數(shù)的最少平方數(shù)的個(gè)數(shù) (記作 minNum)。從1開始算（從0也沒事）真仲。
這里我們分2層來算袋马，外層循環(huán)是計(jì)算從1到 n的各個(gè)數(shù)的最少平方數(shù) minNum, 存入到數(shù)組中，數(shù)組的 index 表示數(shù) n秸应，里面的 val 表示 minNum虑凛。關(guān)鍵是求每個(gè)數(shù)的 minNum碑宴。這里我們用到遞歸，核心代碼就是：
let tmp = val - i * i
minNum = min(minNum, tmp == 0 ? 1 : 1+sta.record[tmp])
tmp 表示 val 減去一個(gè)平方數(shù)剩下的數(shù)桑谍，如果 tmp == 0延柠，就表示 val == i * i，即它由1個(gè)平方數(shù)組成锣披；如果 tmp != 0贞间，就那么我們就需要求以 tmp 為 val 的 minNum，也就是 tmp2 = tmp - i * i 雹仿，這個(gè) tmp2 就相當(dāng)于之前的 tmp增热。為了求 tmp 的 minNum，我們需要計(jì)算出 從1到 sqrt(val) 之間所有的可能值胧辽，然后取最小值峻仇。最后將那個(gè)最小值存放到數(shù)組中。最終代碼就是
func numSquares(n: Int) -> Int {
var record = [0,1]
while record.count <= n {
var val = record.count, minNum = record.count
for i in 1...Int(sqrt(Double(val))) {
let tmp = val - i * i
minNum = min(minNum, tmp == 0 ? 1 : 1+record[tmp])
}
record.append(minNum)
}
return record[n]
}
但是跑了之后又發(fā)現(xiàn)邑商，我特喵的沒錯(cuò)啊，怎么時(shí)間又是這么長(zhǎng)奠骄，1400ms。如果拿個(gè)稍微大點(diǎn)的數(shù)放到 playground 里跑一跑就會(huì)發(fā)現(xiàn)番刊，循環(huán)次數(shù)還是挺多的含鳞。所以這里就需要考慮到把數(shù)組存成 static，而 swift 是沒法在 function 里直接申明 static var n = 1 的芹务，我們需要把 static 放在 class/struct 里蝉绷，參見 SO 大神的解答，還有官方 doc枣抱。
可以把這個(gè) struct 放在 class Solution 里面熔吗，也可以放在外面，最后時(shí)間是 60ms 左右佳晶。從 1400 到 60桅狠，還是可以的。
struct sta {
static var record = [0,1]
}
也許從短短這么一篇文章你就已經(jīng)看出來了一些 swift 語言的特點(diǎn)轿秧，最大的特點(diǎn)就是類型安全中跌。求個(gè)根都要 Int(sqrt(Double(n)))，我以前是用 C++ 的菇篡，遇到這種情況還是有點(diǎn)膈應(yīng)的漩符。但其實(shí) swift 的優(yōu)點(diǎn)絕對(duì)是可以讓我安全無視這些小麻煩的，其實(shí)習(xí)慣了之后就感覺是更方便驱还，更安全了嗜暴。
最后
每篇文章我都在用心寫凸克，希望志同道合的童鞋能一起學(xué)習(xí)一起進(jìn)步。如果喜歡我就請(qǐng)關(guān)注我哦闷沥，點(diǎn)個(gè)??表示鼓勵(lì)吧～
最近貌似 RESTful 很火萎战，如果你對(duì) MongoDB 或者 RESTful 感興趣，請(qǐng)看我的這篇文章狐赡，我用 MongoDB 作為后臺(tái)數(shù)據(jù)庫撞鹉，用 AngularJS, Spark, Java 做了個(gè)網(wǎng)站 demo，建于 Heroku 上颖侄。每一種技術(shù)都是當(dāng)下最流行的技術(shù)鸟雏。
最后強(qiáng)烈推薦喜歡 swift，并想用 swift 寫算法的童鞋览祖，Swift Algorithm Club孝鹊，你值得擁有。
歡迎轉(zhuǎn)載展蒂，轉(zhuǎn)載請(qǐng)注明出處又活。
