记录一个之前遇到的算法题，挺有意思的 希望可以帮到他人
打开手机拨号盘。显示如下图片。
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*之类寻路算法的思路去解决，后续有时间了再深入研究下。
最近略忙，过段时间优化了再贴优化后的代码。
网友评论