Sequence Reconstruction

Leave a comment

December 19, 2016 by oneOokay

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example 1:

Input:
org: [1,2,3], seqs: [[1,2],[1,3]]

Output:
false

Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

Input:
org: [1,2,3], seqs: [[1,2]]

Output:
false

Explanation:
The reconstructed sequence can only be [1,2].

Example 3:

Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:
true

Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Example 4:

Input:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

Output:
true

Google的题目简直了=。=

这题很容易看出来是一个拓扑排序:

  1. 构建degrees和graph
  2. Queue来BFS

但是有很多陷阱!!!

最重要考的一个点是:如何确定unique拓扑排序这一点。因为拓扑排序一般而言并不是唯一的。如果要确定唯一的话,那么queue里面任何最多只能有一个元素在,这样确保了值存在唯一的拓扑排序。

  1. seqs里面存的并不是一定是int[2],可能为空,可能为int[1],也可能为其他;当为int[1]的时候,直接把它加到degrees和graph map里面就可以。
  2. 不能用ArrayList[]了,因为根本不知道org里面的元素,所以只能用HashMap,当然你要用一个ArrayList[10000]也不是不可以,但是没必要)
  3. 所以当用HashMap的时候呢,遇到的所有的值都要确保它在graph map和degrees map里面存在
  4. seqs里面可能给你其他多余的数,生成的graph的数目可能会多过org.length,所以在开始while loop之前可以直接进行一步判断。
  5. HashMap的Iteration
一般情况下只需要根据key来遍历,然后根据key取value
        for (int key : degrees.keySet()){
            if (degrees.get(key) == 0){
                queue.offer(key);
            }
        }
另一种是用Iterator:这个比较麻烦,要各种转化
        Iterator iter = degrees.entrySet().iterator();
        while(iter.hasNext()){
            Map.Entry pair = (Map.Entry)iter.next();
            if ((int)pair.getValue() == 0){
                queue.offer((int)pair.getKey());
            }
        }

public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        if (seqs == null || seqs.length == 0){//陷阱1:seqs里面的每一个int[]
不一定是相同长度的;所以这里不能加seqs.length[0] == 0
            return false;
        }
        
        HashMap<Integer, ArrayList> graph = new HashMap<Integer, ArrayList>();
        HashMap<Integer, Integer> degrees = new HashMap<Integer, Integer>();
        for (int i = 0; i < seqs.length; i ++){
            if (seqs[i].length == 1){//陷阱2:seqs里面可能有int[1]
                if(!degrees.containsKey(seqs[i][0]))
                    degrees.put(seqs[i][0], 0);
                if (!graph.containsKey(seqs[i][0]))
                    graph.put(seqs[i][0], new ArrayList<>());
            }else {
                for(int j = 0; j < seqs[i].length - 1; j ++){
                    int first = seqs[i][j];
                    int second = seqs[i][j + 1];
                    if (!graph.containsKey(first)){//陷阱3:因为是用HashMap,
所以要把first也放到graph里面去
                        graph.put(first, new ArrayList());
                    }
                    if (!graph.containsKey(second)){
                        graph.put(second, new ArrayList());
                    }
                    graph.get(first).add(second);
                    if (!degrees.containsKey(second)){//陷阱4:同样所有的点
都也要在degrees里面
                        degrees.put(second, 0);
                    }
                    if (!degrees.containsKey(first)){
                        degrees.put(first, 0);
                    }
                    degrees.put(second, degrees.get(second) + 1);
                }
            }
        }
        //陷阱4:seqs可能会给你并不存在于org的数,这里可以直接进行判断了。
        if(degrees.size() != org.length || graph.size() != org.length) 
           return false;
        Queue<Integer> queue = new LinkedList<>();
        for (int key : degrees.keySet()){//HashMap的遍历
            if (degrees.get(key) == 0){
                queue.offer(key);
            }
        }
        int index = 0;
        while(!queue.isEmpty()){
            if (queue.size() > 1){//确保拓扑排序的唯一性
                return false;
            }
            
            int cur = queue.poll();
            if (org[index] != cur) return false;//直接在poll的时候与org进行对比
            ArrayList<Integer> next = graph.get(cur);
            for(int i = 0; i < next.size(); i ++){
                int pointer = (int)next.get(i);
                degrees.put(pointer, degrees.get(pointer) - 1);
                if (degrees.get(pointer) == 0){
                    queue.offer(pointer);
                }
            }
            index ++;
        }
        return index == org.length;//最后判断是否能够重组成org,因为可能有单独的
没有联通的点,他们就不可能会进入到queue里面导致最终的拓扑排序出来的数字少于org
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: