Google 面试题:序列重构

zzzrf

LintCode VIP 月卡 ¥39.9,→点此处链接选择购买月卡,输入优惠码 7EBE50,即可 39.9 购买,感兴趣的可以用一下~

判断是否序列 org 能唯一地由 seqs 重构得出. org 是一个由从 1 到 n 的正整数排列而成的序列,1≤n≤10^4 。 重构表示组合成 seqs 的一个最短的父序列 (意思是,一个最短的序列使得所有 seqs 里的序列都是它的子序列).
判断是否有且仅有一个能从 seqs 重构出来的序列,并且这个序列是 org 。

在线做题地址

样例 1:

输入:org = [1,2,3], seqs = [[1,2],[1,3]]
输出: false
解释:
[1,2,3] 并不是唯一可以被重构出的序列,还可以重构出 [1,3,2]

样例 2:

输入: org = [1,2,3], seqs = [[1,2]]
输出: false
解释:
能重构出的序列只有 [1,2].

样例 3:

输入: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
输出: true
解释:
序列 [1,2], [1,3], 和 [2,3] 可以唯一重构出 [1,2,3].

样例 4:

输入:org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
输出:true

[题解]

九章算法班里讲过的拓扑排序,只要保证 queue 里最多同时只有一个元素即可。 所以这是 queue 用 list 然后每次 pop 也可以,反正只有一个数。

public class Solution {
    /**
     * @param org: a permutation of the integers from 1 to n
     * @param seqs: a list of sequences
     * @return: true if it can be reconstructed only one or false
     */
    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        Map<Integer, Set<Integer>> graph = buildGraph(seqs);
        List<Integer> topoOrder = getTopoOrder(graph);
        
        if (topoOrder == null || topoOrder.size() != org.length) {
            return false;
        }
        for (int i = 0; i < org.length; i++) {
            if (org[i] != topoOrder.get(i)) {
                return false;
            }
        }
        return true;
    }
    
    private Map<Integer, Set<Integer>> buildGraph(int[][] seqs) {
        Map<Integer, Set<Integer>> graph = new HashMap();
        for (int[] seq : seqs) {
            for (int i = 0; i < seq.length; i++) {
                if (!graph.containsKey(seq[i])) {
                    graph.put(seq[i], new HashSet<Integer>());
                }
            }
        }
        for (int[] seq : seqs) {
            for (int i = 1; i < seq.length; i++) {
                graph.get(seq[i - 1]).add(seq[i]);
            }
        }
        return graph;
    }
    
    private Map<Integer, Integer> getIndegrees(Map<Integer, Set<Integer>> graph) {
        Map<Integer, Integer> indegrees = new HashMap();
        for (Integer node : graph.keySet()) {
            indegrees.put(node, 0);
        }
        for (Integer node : graph.keySet()) {
            for (Integer neighbor : graph.get(node)) {
                indegrees.put(neighbor, indegrees.get(neighbor) + 1);
            }
        }
        return indegrees;
    }
    
    private List<Integer> getTopoOrder(Map<Integer, Set<Integer>> graph) {
        Map<Integer, Integer> indegrees = getIndegrees(graph);
        Queue<Integer> queue = new LinkedList();
        List<Integer> topoOrder = new ArrayList();
        
        for (Integer node : graph.keySet()) {
            if (indegrees.get(node) == 0) {
                queue.offer(node);
                topoOrder.add(node);
            }
        }
        
        while (!queue.isEmpty()) {
            if (queue.size() > 1) {
                return null;
            }
            
            Integer node = queue.poll();
            for (Integer neighbor : graph.get(node)) {
                indegrees.put(neighbor, indegrees.get(neighbor) - 1);
                if (indegrees.get(neighbor) == 0) {
                    queue.offer(neighbor);
                    topoOrder.add(neighbor);
                }
            }
        }
        
        if (graph.size() == topoOrder.size()) {
            return topoOrder;
        }
        
        return null;
    }
}

更多题解参考

LintCode VIP 月卡 ¥39.9,→点此处链接选择购买月卡,输入优惠码 7EBE50,即可 39.9 购买,感兴趣的可以试用一下~

Google 的磁悬浮负载均衡器

holinhot:https://research.google/pubs/pub44824/ 想试一试这个磁悬浮负载均衡器, 文档我看了,说得很牛逼的样子,但是我找了很久没找到在哪下载啊。 难道不是开源的,只是出来水一下让大家看吗?holinhot:https://opensource.google/projects/list/featured 在这也没找…

Google Chrome Helper 问题

fox:macbook 疯狂风扇旋转,cpu100,一看是 Google Chrome Helper 占了 99 的 cpu,沙掉就好了。 这个问题几天内发生了两次了,查了一下似乎是一个历史遗留问题。 都 2020 年了,为啥还没修复这个问题。

谷歌云(Google Cloud)免费政策改变了?只有三个月了吗?

jememouse:https://cloud.google.com/free/docs/gcp-free-tier?hl=zh-cn 有没有朋友最近新建过,是否只有三个月了?Tink:是的 gqbre:握草。。 白嫖的日子一去不复返 trepwq:是…

Google+登录验证问题 - javascript

您好,我正在尝试在我的网站上实施Google+登录,除了PHP将检查用户的google ID和电子邮件以查看其是否拥有帐户,或者我需要为他们创建一个帐户之外,我已经完成了所有工作。我遇到的问题是如何验证来自客户端JavaScript的php接收的内容实际上是有效的?我的意思是,似乎有人可以轻松修改脚本以发送任何Google用户ID和电子邮件,然后以任何人的身…

Google Drive API访问我自己的帐户 - java

我希望在服务器/笔记本电脑上运行一个简单的过程,每天将文件每天上传一次到Google驱动器中。我不想分享此信息,不允许其他用户使用它等。我发现的所有示例似乎都涉及浏览到一个地址以获得用户(我)的许可,然后获取身份验证代码等并继续参考:Java quickstart有没有一种方法/示例可以做到这一点而无需浏览器,每次我只想为自己的帐户获得许可时都获得唯一的身份…