BFS Problems

BFS

why prefer `start + (end - start) / 2` than `(start + end) / 2`？

当start和end都是很大的integer时，加在一起会overflow。前者不会，因为只要end >= start，前者就不会overflow。（而我们binary search的while loop条件就是start + 1 < end，所以不会爆）

Number of Islands

非常裸的BFS 背诵

具有普适性的方法：在二维地图上运用坐标和BFS搜索
优点在于，不管是以0/1表示岛屿还有水域，还是别的字母，还是超过两种的字符…无论地图格子里的内容形式是什么，运用坐标搜索只在乎你的x-y轴，即array的纵向和横向长度。

坐标的实现可以构建一个类public Class Coordinate
上下左右的pathing方向int[] directionX = {0, 0, 1, -1}和int[] directionY = {1, -1, 0, 0}
相同大小的2D array标记是否走过该格子boolean[][] visited节省空间的话就用原来的，注意标记的方法
BFS用queue存放要走的格子，每次放入后，该格子标记为visited[i][j] = True
用一个方法判断pathing时的方向是否有效private boolean inBound

注意：
The default value for a Boolean (object) is null.
The default value for a boolean (primitive) is false.

Number of distinct islands (这个用了DFS)

形状一样得两个岛屿算成一种类型，但是不能够旋转或者镜面，就是单纯的形状一样

全部顶到左上角，hash function哈希一下形状，哈希值一样的就同一种
记录路径，因为对于所有的寻找，dfs都是同一个function，所以路径一样的岛屿形状一样。分别赋予四个方向1234，最后每个岛屿的哈希路径就是比如321234
用ArrayList<Integer> shape记录路径哈希值

每次enter和exit dfs 都要记录！

public void explore(int r, int c, int di) {
      if (0 <= r && r < grid.length && 0 <= c && c < grid[0].length &&
              grid[r][c] == 1 && !seen[r][c]) {
          seen[r][c] = true;
          shape.add(di);
          explore(r+1, c, 1);
          explore(r-1, c, 2);
          explore(r, c+1, 3);
          explore(r, c-1, 4);
          shape.add(0);
      }
  }

Flood Fill

和number of islands很相似
把指定的cell放进queue，然后循环queue，搜索上下左右，颜色相同的再放进去。
每次从queue拿出来的时候，更换newColor
注意处理特殊情况：当color = newColor如果不处理就会time limit exceed，因为你每次拿出来，更换了color，但其实是一样的颜色，下次拿出邻居，邻居又会搜索到这个cell，再放进去，没完没了

Union Find

Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

问题：

what is the TreeNode like? can use integer value as an example?
return type? level-order traversal，是不是可以用list<list<V(Integer)>>

注意当每一次搜索的子节点都放进queue以后，如何保证把同一个level的节点值放进同一个list？在while loop里面加一个for loop

  while (!queue.isEmpty()) {
      int size = queue.size();
      List<Integer> level = new ArrayList<>();
      for (int i = 0; i < size; i++) {
          TreeNode curr = queue.remove();
          .....
      }
  }

老师追问的问题：在二叉树中找一个相同的Node（地址相同，这个要问！！！）

Binary Tree Zigzag level order traversal

大致上和level traversal一样，我自己加了一个boolean每一层判断是否需要reverse，然后加了一个private void toReverse(List<Integer> level)
参考答案是用了ArrayList中add(int index, e element)这个方法其实可以让你一直在index0初添加新的元素，把剩下的往右边推，就相当于可以逆着往里添加，省去了额外reverse的麻烦 public void add(int index, E element)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Binary Tree Vertical order traversal

不能用dfs因为sublist中的顺序，要按照树节点的位置排列，上层优先，左边优先
最好不要用TreeMap因为徒增时间复杂度，get，put，remove都是O（logn）
min和max用来记录树的左右边界

Vertical Order Traversal of a Binary Tree

题目要求在同一纵轴上，list中的顺序为树的从上到下；在同一个位置，val小优先。
min & max 储存

Course Schedule

拓扑排序

用int[] inDegree存每一门课有多少个prerequisite，index是这门课，degree是prerequisite的数量
用Map<Integer, List<Integer>>存一门课是多少门课的prerequisite，有点像outDegree
用一个countint selectedCourse计数已经上了的课，最后return selectedCourse == numCourse来返回是否能够成功上完所有的课

接下来是BFS
先放进queue的是inDegree[i] == 0即不需要prerequisite的课程
while loop
注意：在下一步之前，判断if (!map.containsKey(i)) continue

因为原题目中的list是以edge的方式，如果有些课没有pre-req或者不是别人的pre-req，不一定会出现在map中，我们map只储存了在list中罗列的edge（但是inDegree不同，new int[numCourses]包含了所有课）
该课程之后可以上的课，inDegree[i]--;
放进queue的条件：inDegree == 0;

Course Schedule II

拓扑排序

返回一个ordering course list
在上一题的基础上添加一个ArrayList

Knight Shortest Path

？？？找不到这道题

Sequence Reconstruction

拓扑排序 unique tolopolical ordering
曾经sequences用int[][]现在用的是List<list<Integer>>，注意一个是int[i]一个是list.get(i)

可以考虑的问题：

seqs里面的subsequences长度不定，每次要for loop储存该subsequences里面i与i+1的indegree以及map
在不知道total n 的情况下，用Map<Integer, Integer> inDegree，没办法用int[]
while时如果queue吐出来大于一个数，说明不是unique order，return false
while时如果queue吐出来的数和org对应的不一样，return false
有一个顿悟：原意是org[index]与queue吐出来的比较，但是注意，一旦要涉及array和index，就要顺手先检验index与array.length的关系，这是一个绑定，为了防止indexoutofbound exception!

if (index == org.length || curr != org[index++]) return false;

注意：
HashSet的boolean add(E e)： If this set already contains the element, the call leaves the set unchanged and returns false

所以在subsequences有多个元素时，可以直接用add作if条件：

  if (map.get(seq[i]).add(seq[i + 1])) 
      indegree.put(seq[i + 1], indegree.get(seq[i + 1]) + 1);

最后检查return index == org.length && index == map.size()
index == org.length是为了检查org里面的都刚好loop完了，不多不少
index == map.size()是为了检查map里面所有的key即所有在sequences里面出现过的数字都已经loop完了，没有剩下

Clone Graph

Topological Sorting

Word Ladder

枚举法：

如果endword不在wordList中就返回0，因为永远不可能到达
用一个Set<String> reached放已经到达过的单词，类似queue
while循环条件是reached不包含endword每一次reached里面的就是一个level（一步转换能够达到的&且属于wordList里面的单词），有点像Tree里面的一层，这一层和上一层之间差一步。

对于里面的每一个单词，的每一位字母，都尝试从a到z去替换，判断是否在wordList之内

for (char ch = 'a'; ch <= 'z'; ch++) {
  chars[i] = ch;
  String word = new String(chars);  //将character转换成string
}

如果在wordlist中，装进这一层的Set<String> toAdd，且从wordList中移除（一定要移除吗?）为了防止循环？
distance++
如果toAdd是空的，说明没有可以往下走的了，但此时还在while loop中说明还没有抵达endword，于是直接返回0，到达不了。

另一个方法：

重点在于如何实现“只改变一个字母，从一个单词转变到另外一个单词”
创造generic word，把一个单词的一个字母用*代替
Dog ----> D*g <---- Dig所以BFS时找到adjacent nodes for Dug等于找到所有generic states for Dug
preprocessing：找到所有可能的generic states，存在map中，key: intermediate word; valuw: the list of words which have the same intermediate word
防止循环，用visited map

01 Matrix

和level traversal的实现很像，但是意义不一样。这里的level指的就是距离
和 number of islands 也很像
Queue<int[]>queue里面装的是坐标[x,y]
先把所有的0的坐标放进queue，这就是距离最近的一层，不是0的要在ArrayList res里面标记-1，表示没有走过
设定level = 1
while loop时要在size()里面循环，也就是把这一层（这个距离内）全部过一遍
需要有上下左右的方向，所以需要另一个for loop以及helper method inBound
从这一层(全是0)能够探索到的新格子都是距离为1，所以在把它们放进queue的同时，可以更新它们的结果queue.offer(new int[] {newX, newY}; res[newX][newY] = level)

The maze II

网上的笔记：

难点在于对于一滚到底的实现方法
用一个二位数组 dists，其中dists[i][j]表示到达 (i,j) 这个位置时需要的最小步数，我们都初始化为整型最大值，在后在遍历的过程中不断用较小值来更新每个位置的步数值
最后看终点位置的步数值，如果还是整型最大值的话，说明没法在终点处停下来，return -1，否则就返回步数值
注意在压入栈的时候，我们对x和y进行了判断，只有当其不是终点的时候才压入栈，这样是做了优化，因为如果小球已经滚到终点了，我们就不要让它再滚了，就不把终点位置压入栈，免得它还滚

答案补充：

有两种方法把坐标位置放进queue，一种是Queue<int[]>；一种是哈希，横坐标 * 100 + 纵坐标；这道题用100是因为题目限制了迷宫的长宽均不超过100.如果没有这个限制，就不能这样做。
这样写的好处是，当某些BFS需要查重，这个方法较快。建一个Set<Integer>就可以快速查重。

Find K closest elements

直接用现成的Arrays.binarySearch(int[] a, int key)或者Collections.binarySearch(int[] a, int key) 如果这个数在数组里，返回index；如果不在，返回-(insertion point) - 1insertion point指的是这个值应该被插入的index； the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. 这样保证了 return value will be >= 0 if and only if the key is found.

宽度优先搜索和题目总结

BFS

why prefer `start + (end - start) / 2` than `(start + end) / 2`？

Number of Islands

非常裸的BFS 背诵

Number of distinct islands (这个用了DFS)

Flood Fill

Union Find

Binary Tree Level Order Traversal

Binary Tree Zigzag level order traversal

Binary Tree Vertical order traversal

Vertical Order Traversal of a Binary Tree

Course Schedule

Course Schedule II

Knight Shortest Path

Sequence Reconstruction

Clone Graph

Topological Sorting

Word Ladder

01 Matrix

The maze II

Find K closest elements

FEATURED TAGS

BFS

why prefer start + (end - start) / 2 than (start + end) / 2？

Number of Islands

非常裸的BFS 背诵

Number of distinct islands (这个用了DFS)

Flood Fill

Union Find

Binary Tree Level Order Traversal

Binary Tree Zigzag level order traversal

Binary Tree Vertical order traversal

Vertical Order Traversal of a Binary Tree

Course Schedule

Course Schedule II

Knight Shortest Path

Sequence Reconstruction

Clone Graph

Topological Sorting

Word Ladder

01 Matrix

The maze II

Find K closest elements

FEATURED TAGS

why prefer `start + (end - start) / 2` than `(start + end) / 2`？