分类目录:

二维网格问题的解法

经常有面试问题是二维网格问题,比如迷宫问题、迷宫最短路径问题、N皇后问题等等。求解时主要有以下要素:

  • 遍历:对每个格子(位置)进行遍历。
  • 搜索相邻的格子。

总体的搜索可以有深度优先(DFS)和广度优先(BFS)之分。

根据我自己的经验,在有限的时间内解答这类问题时,要注意以下几点:

二维数组的行列顺序

二维数组是按照先行后列的顺序存储的:

void func(int[][] data) {

阅读全文

深度优先遍历和广度优先遍历

深度优先遍历(DFS)和广度优先遍历(BFS)是两种遍历或搜索树和图的方法,常用于,呃,面试中……

深度优先遍历(DFS:Depth First Search)

DFS的遍历顺序又分为三种。下面以N代表当前结点,L代表左侧子结点,R代表右侧子结点。

  • 先序(preorder):先处理当前结点,然后对子结点从左向右处理。NLR,从上向下,从左向右
  • 中序(inorder):先处理左侧子结点,然后处理当

阅读全文

回溯算法

回溯算法是一种可以找到全部或部分解的通用算法。跟暴力穷举法相比,由于可以对搜索域剪枝,因此效率要高。所谓回溯,就是走到某处后如果发现此路不通,会立即退回到上一步,而不是像暴力法那样仍不管不顾地都试一次。因此,回溯法是一种选优搜索法,又称为试探法。

回溯算法的编写格式:

boolean backtrack(candidate) { // 递归终止条件 if (isSolution

阅读全文