記錄一個(gè)之前遇到的算法題，挺有意思的 希望可以幫到他人
打開手機(jī)撥號(hào)盤。顯示如下圖片。

image.png

給定圖中任意一個(gè)數(shù)字D都可以作為起始點(diǎn)。每次可以朝上下左右任意方向移動(dòng)一格，不可斜著移動(dòng)，每次移動(dòng)N步，記錄可能移動(dòng)的組合。
例如D=1 N=3 則可能的組合為[121,123,125,141,145,147]。
例如D=5 N=1 則可能的組合為[5]。

問題的難點(diǎn)在于：
最終組合數(shù)組的個(gè)數(shù)會(huì)隨著N的增加而會(huì)呈幾何增長，因?yàn)楫?dāng)每走一步后，上下左右的可能性就完全不同，需要避免已經(jīng)走過的線路。
走N步也間接表明了最后每個(gè)組合將是一個(gè)N位數(shù)，
且當(dāng)無論是起始數(shù)字還是半路上走到的數(shù)字除5和8以外都有限制，例如1無法往上、左方向走，9無法往下、右方向走，0只能往上走。

所以我的思路是：先犧牲一點(diǎn)空間復(fù)雜度，生成一個(gè)數(shù)字為key，相鄰可能性為value的Dictonary對(duì)象。即1的走向是[2,4]，2的走向是[1,5,3]，3的走向是[2,6] 以此類推。當(dāng)拿到初始數(shù)字時(shí)根據(jù)key進(jìn)行可能性的尋跡，用遞歸的方式深入每一位數(shù)并生成路徑上的組合，應(yīng)該就可以實(shí)現(xiàn)了。

//創(chuàng)建一個(gè)形似撥號(hào)盤的二維數(shù)組
let keyPad = [[1, 2, 3],[4, 5, 6],[7, 8, 9],[-1,0,-1]]

//Create Neighbors of every Number
func createNeighborDic() ->Dictionary<Int,Array<Int>> {
    
    var dic = Dictionary<Int,Array<Int>>.init()
    
    for i in 0...keyPad.count-1 {
        for j in 0...keyPad[i].count-1 {
            let key = keyPad[i][j]
            if key != -1 {
                dic[key] = getNeighbor(target: key, dX: i, dY: j)
            }
        }
    }
    return dic
}

//Forward up down left right get number nearby
func getNeighbor(target:Int,dX:Int,dY:Int) -> [Int] {
    var neighbors:[Int] = []
    
    if (dX - 1) >= 0 {
        //up
        let next = keyPad[dX - 1][dY]
        if next != -1 {
            neighbors.append(next)
        }
    }
    
    if (dX + 1) <= 3 {
        //down
        let next = keyPad[dX + 1][dY]
        if next != -1 {
            neighbors.append(next)
        }
    }
    
    if (dY - 1) >= 0 {
        //left
        let next = keyPad[dX][dY - 1]
        if next != -1 {
            neighbors.append(next)
        }
    }
    
    if (dY + 1) <= 2 {
        //right
        let next = keyPad[dX][dY + 1]
        if next != -1 {
            neighbors.append(next)
        }
    }
    
    return neighbors
}

準(zhǔn)備工作到此結(jié)束，有了createNeighborDic方法返回的Dictionary對(duì)象，后面尋跡的方法就相對(duì)好做一點(diǎn)了。

func append(array:[Int],dic:Dictionary<Int,Array<Int>>,n:Int,num:Int) -> Void {
    var tempNum = num
    //Deep
    var tempN = n
    if tempN > 0 {
        for item in array {
            tempNum = tempNum + item * Int(pow(10.0, Double(n-2)))
            
            if tempN > 2 {
                //If still not deep enough. Continue geting the deep Neighbors
                tempN = tempN - 1
                let tempArray = dic[item]!
                
                append(array: tempArray, dic: dic, n: tempN, num: tempNum)
                //Reset temp value
                tempNum = num
                tempN = n
                
            } else {
                resultArray.append(tempNum)
                //After Got Result, Reset temp value
                tempNum = tempNum - item
            }
        }
    }
}

解釋下append方法里每個(gè)參數(shù)：
array：起始的周邊組合，第一次運(yùn)行時(shí)直接給進(jìn)D的組合，例如當(dāng)D=1是給[2,4], D=6時(shí)給[3,5,9], D=8時(shí)給[5,7,0,9]。這些在createNeighborDic方法返回的字典中都可以取到。

dic：通過createNeighborDic獲取來的每個(gè)數(shù)字組合的字典，傳進(jìn)去供每個(gè)途徑的數(shù)字獲取相應(yīng)的數(shù)字組合。

n: 即步數(shù)，在append方法每運(yùn)行一次后進(jìn)行一次減1。當(dāng)減到小于2時(shí)(因?yàn)榈谝徊接墒止べx值進(jìn)去)認(rèn)為走滿了N步，保存途徑的數(shù)字。當(dāng)n大于2時(shí)，說明還需要繼續(xù)走步，則遞歸調(diào)用自身方法。

tempNum: 每個(gè)組合的數(shù)字集合，此處使用了一個(gè)系統(tǒng)函數(shù)pow(a,b)，即a的b次方。因?yàn)樽罱K每個(gè)組合的呈現(xiàn)是以十進(jìn)制數(shù)字的方式。在每一次的走步過程中需要進(jìn)行每個(gè)數(shù)字格的n-2次方計(jì)算。

最后這個(gè)getNeighborByLenght就是主函數(shù)，接收d和n參數(shù)并調(diào)用append方法進(jìn)行數(shù)字格的走步和記錄。

func getNeighborByLenght(d:Int,n:Int) -> [Int] {
    print("d = \(d)  n = \(n)")
    if n == 1 {
        return [d]
    }
    
    //Got Dictionary with all number neighbors
    let dic:Dictionary<Int,Array<Int>> = createNeighborDic()
    
    //Got Neighbors of d
    let first = dic[d]
    
    //Init First Number
    let initNumber = Int(pow(10.0,Double(n - 1))) * d
    
    //Append Left Number
    append(array: first!, dic: dic, n: n, num: initNumber)
    return resultArray
}

代碼運(yùn)行結(jié)果：

image.png

對(duì)比結(jié)果和要求基本上符合。但該解法也有可以改進(jìn)的地方。
1.利用了全局變量resultArray進(jìn)行存每次生成的組合，最好是能放在主函數(shù)內(nèi)部。這樣運(yùn)行時(shí)可以不依賴到函數(shù)所在的方法實(shí)體。并且每次運(yùn)行不需要做清空操作。但由于使用了遞歸的做法，每次都去傳遞這個(gè)數(shù)組對(duì)象感覺也不太好。

2.append方法中的形參需要在每次運(yùn)行中進(jìn)行變化，這里采用的方式是用var對(duì)象接收，但這樣只是一個(gè)權(quán)益之計(jì)，可能會(huì)導(dǎo)致可變參數(shù)和不可變參數(shù)之間的界線模糊。應(yīng)該選用let 和 var區(qū)分開哪些是可變哪些是不可變。

3.使用Dictionary存儲(chǔ)了數(shù)字格走步的可能性犧牲了空間復(fù)雜度，算式有些投機(jī)取巧，當(dāng)撥號(hào)盤不再局限于0~9而是成千上萬后，這個(gè)方式的劣勢就出現(xiàn)了。按道理應(yīng)該應(yīng)用一些A* D*之類尋路算法的思路去解決，后續(xù)有時(shí)間了再深入研究下。

最近略忙，過段時(shí)間優(yōu)化了再貼優(yōu)化后的代碼。