原创算法解析：拨号盘走格问题（Swift解法）

记录一个之前遇到的算法题，挺有意思的希望可以帮到他人
打开手机拨号盘。显示如下图片。

image.png

给定图中任意一个数字D都可以作为起始点。每次可以朝上下左右任意方向移动一格，不可斜着移动，每次移动N步，记录可能移动的组合。
例如D=1 N=3 则可能的组合为[121,123,125,141,145,147]。
例如D=5 N=1 则可能的组合为[5]。

问题的难点在于：
最终组合数组的个数会随着N的增加而会呈几何增长，因为当每走一步后，上下左右的可能性就完全不同，需要避免已经走过的线路。
走N步也间接表明了最后每个组合将是一个N位数，
且当无论是起始数字还是半路上走到的数字除5和8以外都有限制，例如1无法往上、左方向走，9无法往下、右方向走，0只能往上走。

所以我的思路是：先牺牲一点空间复杂度，生成一个数字为key，相邻可能性为value的Dictonary对象。即1的走向是[2,4]，2的走向是[1,5,3]，3的走向是[2,6] 以此类推。当拿到初始数字时根据key进行可能性的寻迹，用递归的方式深入每一位数并生成路径上的组合，应该就可以实现了。

//创建一个形似拨号盘的二维数组
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
}

准备工作到此结束，有了createNeighborDic方法返回的Dictionary对象，后面寻迹的方法就相对好做一点了。

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方法里每个参数：
array：起始的周边组合，第一次运行时直接给进D的组合，例如当D=1是给[2,4], D=6时给[3,5,9], D=8时给[5,7,0,9]。这些在createNeighborDic方法返回的字典中都可以取到。

dic：通过createNeighborDic获取来的每个数字组合的字典，传进去供每个途径的数字获取相应的数字组合。

n: 即步数，在append方法每运行一次后进行一次减1。当减到小于2时(因为第一步由手工赋值进去)认为走满了N步，保存途径的数字。当n大于2时，说明还需要继续走步，则递归调用自身方法。

tempNum: 每个组合的数字集合，此处使用了一个系统函数pow(a,b)，即a的b次方。因为最终每个组合的呈现是以十进制数字的方式。在每一次的走步过程中需要进行每个数字格的n-2次方计算。

最后这个getNeighborByLenght就是主函数，接收d和n参数并调用append方法进行数字格的走步和记录。

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
}

代码运行结果：

image.png

对比结果和要求基本上符合。但该解法也有可以改进的地方。
1.利用了全局变量resultArray进行存每次生成的组合，最好是能放在主函数内部。这样运行时可以不依赖到函数所在的方法实体。并且每次运行不需要做清空操作。但由于使用了递归的做法，每次都去传递这个数组对象感觉也不太好。

2.append方法中的形参需要在每次运行中进行变化，这里采用的方式是用var对象接收，但这样只是一个权益之计，可能会导致可变参数和不可变参数之间的界线模糊。应该选用let 和 var区分开哪些是可变哪些是不可变。

3.使用Dictionary存储了数字格走步的可能性牺牲了空间复杂度，算式有些投机取巧，当拨号盘不再局限于0~9而是成千上万后，这个方式的劣势就出现了。按道理应该应用一些A* D*之类寻路算法的思路去解决，后续有时间了再深入研究下。

最近略忙，过段时间优化了再贴优化后的代码。

原创 算法解析：拨号盘走格问题 （Swift解法）

原创算法解析：拨号盘走格问题（Swift解法）