迫于就業(yè)的壓力，不得不先放下 iOS 開發(fā)的學(xué)習(xí)，開始走上漫漫刷題路。

今天我想聊聊 LeetCode 上的第279題－Perfect Squares，花了挺長時(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è)公式的發(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è)方法還是很簡單的。

DP

我剛刷題沒幾天，對(duì)于 DP 的推理過程還不是很熟練，琢磨了好久。一旦琢磨出來了，又覺得好簡單，換一題，又可以琢磨一年。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í)間又是這么長，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)注明出處。