找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6516|回复: 7
收起左侧

[米群网刷题小分队] [LeetCode] DFS/BFS 题目

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-9-2014 12:00 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-12-2014 08:15 PM 编辑

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??

本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-12-2014 08:16 PM | 显示全部楼层
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))

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-13-2014 09:24 PM | 显示全部楼层
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.             for(int i = 0; i < 4; ++i)
  25.             {
  26.                 int adjW = adjs.get(i).x;
  27.                 int adjL = adjs.get(i).y;
  28.                 if(adjW >= 0 && adjW < width && adjL >= 0 && adjL < length && board[adjW][adjL] == 'O')
  29.                 {
  30.                     dq.add(new Pair(adjW, adjL));
  31.                     board[adjW][adjL] = 'B';
  32.                 }
  33.             }
  34.         }
  35.     }
  36.     public void solve(char[][] board) {
  37.         int width = board.length;
  38.         if(width == 0) return;
  39.         int length = board[0].length;
  40.         if(length == 0) return;
  41.         for(int i = 0; i < length; ++i) //two vertical line
  42.         {
  43.             if(board[0]【i】 == 'O')
  44.                 helper(board, 0, i);
  45.             if(board[width-1]【i】 == 'O')
  46.                 helper(board, width - 1, i);
  47.         }
  48.         for(int i = 0; i < width; ++i) //two horizontal line
  49.         {
  50.             if(board【i】[0] == 'O')
  51.                 helper(board, i, 0);
  52.             if(board【i】[length - 1] == 'O')
  53.                 helper(board, i, length - 1);
  54.         }
  55.         for(int i = 0; i < width; ++i)
  56.         {
  57.             for(int j = 0; j < length; ++j)
  58.             {
  59.                 if(board【i】[j] == 'O')
  60.                     board【i】[j] = 'X';
  61.                 else if(board【i】[j] == 'B')
  62.                     board【i】[j] = 'O';
  63.             }
  64.         }
  65.     }
  66. }
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表