力扣labuladong——一刷day76

2023-12-21 21:21:12

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言


图这种数据结构有一些比较特殊的算法,比如二分图判断,有环图无环图的判断,拓扑排序,以及最经典的最小生成树,单源最短路径问题,更难的就是类似网络流这样的问题。

一、力扣797. 所有可能的路径

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        dfs(graph,0);
        return res;
    }
    public void dfs(int[][] graph, int cur){
        if(cur == graph.length-1){
            path.add(cur);
            res.add(new ArrayList<>(path));
            path.remove(path.size()-1);
            return;
        }
        for(int i = 0; i < graph[cur].length; i ++){
            path.add(cur);
            dfs(graph, graph[cur][i]);
            path.remove(path.size()-1);
        }
    }
}

二、力扣277.搜寻名人

int findCelebrity(int n) {
    if (n == 1) return 0;
    // 将所有候选人装进队列
    LinkedList<Integer> q = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        q.addLast(i);
    }
    // 一直排除,直到只剩下一个候选人停止循环
    while (q.size() >= 2) {
        // 每次取出两个候选人,排除一个
        int cand = q.removeFirst();
        int other = q.removeFirst();
        if (knows(cand, other) || !knows(other, cand)) {
            // cand 不可能是名人,排除,让 other 归队
            q.addFirst(other);
        } else {
            // other 不可能是名人,排除,让 cand 归队
            q.addFirst(cand);
        }
    }

    // 现在排除得只剩一个候选人,判断他是否真的是名人
    int cand = q.removeFirst();
    for (int other = 0; other < n; other++) {
        if (other == cand) {
            continue;
        }
        // 保证其他人都认识 cand,且 cand 不认识任何其他人
        if (!knows(other, cand) || knows(cand, other)) {
            return -1;
        }
    }
    // cand 是名人
    return cand;
}

文章来源:https://blog.csdn.net/ResNet156/article/details/135028721
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。