DFS

  • 边界相关问题，可以直接从边界开始DFS

  • 其他就是普通dfs就行

    岛屿相关

    200. 岛屿数量

    这是一道基础题
    答案：普通递归DFS，访问过的陆地标记为’x’.

    547. 省份数量 （多练）

    变形的DFS，需要改变打开下一层节点的方式

    130. 被围绕的区域/围棋

    思路：我们可以想到，所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上，具体地说。对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O。

    417. 太平洋大西洋水流问题（不会做，看答案，多练）

    思路：和130思路一样，从边界开始找相连接的

    面试题 16.19. 水域大小

    基础题+对角线方向的搜索

    695. 岛屿的最大面积

    基础题，和200思路重复。

    拓扑排序

    207. 课程表

  • 本题是一道经典的「拓扑排序」问题。

    • 对于任何有向图而言，其拓扑排序为其所有节点的一个线性排序（对于同一个有向图而言可能存在多个这样的节点排序）。该排序满足这样的条件：对于图中的任意两个节点u和v，若存在一条有向边从u指向v，则在拓扑排序中u一定出现在v前面。
    • 拓扑排序主要用来解决有向图的依赖解析（dependency resolution）问题。举个例子，对于有循环依赖（环）的有向图，就不可能存在拓扑排序。所以可以根据拓扑排序是否存在判断有向图是否存在循环依赖。

  • 算法：

    • 节点三个状态: unvisitied, visiting, done
    • dfs 访问，回溯的时候done
    • 如果在访问的过程中
      • 打开的节点是visiting，则出现环，return false
      • 打开的节点是unvisitied，

        210. 课程表 II（不会做，看答案，多练）

  • 思路和207一样，区别在于要保存拓扑排序的结果

  • 放入返回数组的时候，从右往左放入课程，因为DFS到头，表示该课程不是任何课程的前置了，所以放在最右边。

    Tricky

    934. 最短的桥 （不会做，看答案，多练）

    思路：DFS搜出一座岛，并且将岛周围的0放入Queue中，接下来基于Queue来做BFS，看最少几步到另一座岛。

    365. 水壶问题（不会做，看答案，多练）

    思路：

  • 将两个水壶的水量当作状态 （c1, c2）

  • 每个状态有6种操作可以去往另一个状态
  • 这样子就构造出来了一副图

  • 接下来，使用DFS搜索这张图，判断target是否可到达。

    394. 字符串解码(栈)

    思路

  • 使用栈

  • 数字 -> 抽取数字然后入栈
  • [ 和 字母 -> 直接入栈

  • ] -> 开始出栈 和 数字, 解码字符串

    BFS

    210. 课程表 II（不会做，看答案，多练）

  • BFS 建立每个课程的前置课程数量数组 以这个为层展开BFS

    剑指 Offer 13. 机器人的运动范围

  • 思路：基础BFS，使用数组 比 HashSet快。

    785. 判断二分图

  • 思路：

    • 同一条边的两个节点必定在不同的集合中
    • 给节点上色，如果相连且在相同的集合中，返回false
    • 最后遍历完成，返回true

      815. 公交路线

  • 构造图

  • BFS搜索每一辆bus，需要从起点开始乘几辆车可以上车
  • 最后，遍历可以到达终点的所以bus，取最小值。