lintcode 814. Shortest Path in Undirected Graph 之python 和 java 实现

分享

最近没有动力学习，今天看到小宝贝那么努力学注会，顿感羞愧。

虽然收到了offercall，但还没有确定之前，还是好好刷刷题。既然有自己的目标，就应该给出自己的态度。

1
2
3
4
5
6
7
814. 无向图中的最短路径

给出一个undirected graph，其中每条边的长度为1，并从图中给出两个节点。我们需要找到给定两个节点之间最短路径的长度。

样例

给定图= {1,2,4#2,1,4#3,5#4,1,2#5,3}，nodeA = 3, nodeB = 5。

首先想到的是深度优先搜索。写了好久，关于如何确定遍历完一层，res++的地方没理清楚。于是在网上搜了下资料，有c和java版的，就看了下别人的代码，再用python给实现一下。
AC了 哈哈。其实我也不知道刷题用什么好，Python简洁好写，在写代码时候比Java省不少事，之前有个快排的题，同样思路，我用Java和Python分别实现，发现Python比Java短了不只一倍，看着很舒服，有点像伪代码。但是Java代码AC了，用了60ms多，但是Python 超时，6000多ms..

很尴尬。

个人还是喜欢Python，希望笔试不要出现这种问题。

1
2
3
4
5
6
7
8
9
10
思路：广度优先搜索，用到队列
1 取A结点入队，标记已访问，res=0，up_last = A
2 当队列不为空时：
	repeat:
		取队头元素——>now_node
		如果 now_node = B
		取now_node的邻接nodes:
			将没有访问的node,全入队并标记访问，然后last指向最后一个
		如果当前指针now_node等于层指针up_last，层指针指向last,并且res++
3 return

这里Python不叫指针，一般和Java一样，叫引用或者别的啥，我叫指针只是形象一些。

看代码也比较简单
python3.5 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    """
    @param graph: a list of Undirected graph node
    @param A: nodeA
    @param B: nodeB
    @return:  the length of the shortest path
    """
    def shortestPath(self, graph, A, B):
        import queue
        # Write your code here
        conti = queue.Queue()
        visited = []
        conti.put(A)
        visited.append(A)
        last = A
        up_last = A
        res=0
        while not conti.empty():
            now = conti.get()
            if now == B:
                return res
            for i in now.neighbors:
                if i not in visited:
                    conti.put(i)
                    visited.append(i)
                    last = i
            if up_last==now:
                up_last = last
                res +=1
        return res

java 参考https://blog.csdn.net/u014115273/article/details/80299072，对比看下吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * Definition for graph node.
 * class GraphNode {
 *     int label;
 *     ArrayList<UndirectedGraphNode> neighbors;
 *     UndirectedGraphNode(int x) { 
 *         label = x; neighbors = new ArrayList<UndirectedGraphNode>(); 
 *     }
 * };
 */
public class Solution {
    /**
     * @param graph: a list of Undirected graph node
     * @param A: nodeA
     * @param B: nodeB
     * @return:  the length of the shortest path
     */
    public int shortestPath(List<UndirectedGraphNode> graph, UndirectedGraphNode A, UndirectedGraphNode B) {
        // Write your code here
        Queue<UndirectedGraphNode> queue = new LinkedList<>();
        Set<UndirectedGraphNode> visited = new HashSet<>();  

        int res = 0;

        UndirectedGraphNode last = null;
        UndirectedGraphNode upperLast = null;

        queue.offer(A);
        visited.add(A);
        upperLast = A;

        while(!queue.isEmpty()){
            UndirectedGraphNode now = queue.poll();

            if(now.label == B.label){
                return res;
            }

            for(UndirectedGraphNode next: now.neighbors){
                if(!visited.contains(next)){
                    queue.offer(next);
                    visited.add(next);
                    last = next;
                }
            }

            if(now == upperLast){
                upperLast = last;
                res++;
            }

        }    

        return -1;//not connected
    }
}