蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.
但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.
蛇形遍历数组, 我的思路是使用两个点坐标再加上一个方向变量, 两个点同时在边缘上移动, 然后连线.
但是, 其实这个问题本质就是从一点出发, 不断地 walk, 一次只 walk 一步, 需要保留方向状态. 如果一次 walk 完斜线, 则不用方向状态, 因为可以根据 walk 的起点来判断.
分而治之算法(divide and conquer)是计算机算法领域最常用最有效的算法之一, 体现到编程上就是树(数据结构), 递归函数. 一般的代码模板是这样的:
func recursive(N){ if(!N){return;} a, b = split(N); // divide proc(a); // conquer a recursive(b); // process b }
对于寻路, 分段处理最终达成目标这种模式的问题, 一般的代码模板是:
func recursive(N){ if(!N){return;} a, b = split(N); // divide r = proc(a); // conquer a if(r){recursive(r + b);} // conquer remain + b recursive(b); // process b }
多了一步:
if(r){recursive(r + b);}
因为前一段的剩余, 要和后一段组成新的问题, 然后被处理.