[LeetCode] DFS／BFS 题目

MengMa

Clone Graph


看了答案。还要再写写BFS。
复杂度分析：
DFS, BFS
In both algorithms, each vertex and each edge are visited constant times. So, both run in O(|V|+|E|) time.

DFS代码：

1. public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
   
2.         return helper(node, new HashMap<UndirectedGraphNode, UndirectedGraphNode>());
   
3.     }
   
4.     private UndirectedGraphNode helper(UndirectedGraphNode root, HashMap<UndirectedGraphNode, UndirectedGraphNode> visited)
   
5.     {
   
6.         if(root == null) return root;
   
7.         UndirectedGraphNode node = new UndirectedGraphNode(root.label);
   
8.         visited.put(root, node);
   
9.         for(UndirectedGraphNode nd : root.neighbors)
   
10.         {
    
11.             if(visited.containsKey(nd))
    
12.                 node.neighbors.add(visited.get(nd));
    
13.             else
    
14.                 node.neighbors.add(helper(nd, visited));
    
15.         }
    
16.         return node;
    
17.     }

复制代码

BFS??

MengMa

Word Ladder


思路： http://www.programcreek.com/2012/12/leetcode-word-ladder/

对于给定单词，进行BFS，新建了一个pair类，该类记录了pair.word到给定 单词start的距离。当pair.word == end时，终止并返回pair.distance.

在生成new pair时，基本对当前pair.word的每一个字符进行改变，同时判断生成的词是否在字典里，如果是的话就建立一个新pair。
pair.word为新词，distance为原distance + 1

1. public class Solution {
   
2.     public class Pair
   
3.     {
   
4.         String word;
   
5.         int distance;
   
6.         Pair() {word = ""; distance = 0;}
   
7.         Pair(String s, int d) {word = s; distance = d;}
   
8.     }
   
9.     public int ladderLength(String start, String end, HashSet<String> dict) {
   
10.         if (dict.size() == 0) return 0;
    
11.         LinkedList<Pair> queue = new LinkedList<Pair>();
    
12.         queue.add(new Pair(start, 1));
    
13.         while(!queue.isEmpty())
    
14.         {
    
15.             Pair curPair = queue.pop();
    
16.             String curWord = curPair.word;
    
17.             int curDistance = curPair.distance;
    
18.             if(curWord.equals(end)){
    
19.                 return curDistance;
    
20.             }
    
21.             for(int i=0; i<curWord.length(); i++)
    
22.             {
    
23.                 char[] curCharArr = curWord.toCharArray();
    
24.                 for(char c='a'; c<='z'; c++)
    
25.                 {
    
26.                     curCharArr【i】 = c;
    
27.                     String newWord = new String(curCharArr);
    
28.                     if(dict.contains(newWord))
    
29.                     {
    
30.                         queue.add(new Pair(newWord, curDistance + 1));
    
31.                         dict.remove(newWord);
    
32.                     }
    
33.                 }
    
34.             }
    
35.         }
    
36.         return 0;
    
37.     }
    
38. }

复制代码

时间复杂度是O(min(26^L, size(dict))，空间也是O(min(26^L, size(dict))

MengMa

Surrounded Regions

思路：[eaglesky1990]
此题如果直接从surrouned regions入手用BFS或DFS都比较麻烦，因为不知道结果是终止于X还是边界上的O, 只有终止于X时才应该翻转O。更简单的思路是用排除法，先考虑那些没有被surrounded的O, 找他们比较简单，直接从边界上的O开始BFS或DFS遍历即可，把他们都变成'B'（啥mark都可以，只要别是'O'或'X'），然后遍历棋盘每个棋子，把遇到的'O'变成'X‘， ’B‘还原成'O'即可。
代码:

1. public class Solution {
   
2.     public class Pair
   
3.     {
   
4.         int x;
   
5.         int y;
   
6.         Pair() {x =-1; y = -1;}
   
7.         Pair(int m, int n) {x=m;y=n;}
   
8.     }
   
9.     private void helper(char[][] board, int w, int l)
   
10.     {
    
11.         int width = board.length;
    
12.         int length = board[0].length;
    
13.         Deque<Pair> dq = new LinkedList<Pair>();
    
14.         dq.add(new Pair(w, l));
    
15.         board[w][l] = 'B';
    
16.         while(!dq.isEmpty())
    
17.         {
    
18.             Pair cur = dq.removeFirst();
    
19.             List<Pair> adjs = new ArrayList<Pair>();
    
20.             adjs.add(new Pair(cur.x - 1, cur.y));
    
21.             adjs.add(new Pair(cur.x + 1, cur.y));
    
22.             adjs.add(new Pair(cur.x, cur.y - 1));
    
23.             adjs.add(new Pair(cur.x, cur.y + 1));
    
24. 
    
25.             for(int i = 0; i < 4; ++i)
    
26.             {
    
27.                 int adjW = adjs.get(i).x;
    
28.                 int adjL = adjs.get(i).y;
    
29.                 if(adjW >= 0 && adjW < width && adjL >= 0 && adjL < length && board[adjW][adjL] == 'O')
    
30.                 {
    
31.                     dq.add(new Pair(adjW, adjL));
    
32.                     board[adjW][adjL] = 'B';
    
33.                 }
    
34.             }
    
35.         }
    
36.     }
    
37.     public void solve(char[][] board) {
    
38.         int width = board.length;
    
39.         if(width == 0) return;
    
40.         int length = board[0].length;
    
41.         if(length == 0) return;
    
42.         for(int i = 0; i < length; ++i) //two vertical line
    
43.         {
    
44.             if(board[0]【i】 == 'O')
    
45.                 helper(board, 0, i);
    
46.             if(board[width-1]【i】 == 'O')
    
47.                 helper(board, width - 1, i);
    
48.         }
    
49.         for(int i = 0; i < width; ++i) //two horizontal line
    
50.         {
    
51.             if(board【i】[0] == 'O')
    
52.                 helper(board, i, 0);
    
53.             if(board【i】[length - 1] == 'O')
    
54.                 helper(board, i, length - 1);
    
55.         }
    
56.         for(int i = 0; i < width; ++i)
    
57.         {
    
58.             for(int j = 0; j < length; ++j)
    
59.             {
    
60.                 if(board【i】[j] == 'O')
    
61.                     board【i】[j] = 'X';
    
62.                 else if(board【i】[j] == 'B')
    
63.                     board【i】[j] = 'O';
    
64.             }
    
65.         }
    
66.     }
    
67. }

复制代码