力扣labuladong——一刷day76

本文主要是介绍力扣labuladong——一刷day76，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

文章目录

前言
一、力扣797. 所有可能的路径
二、力扣277.搜寻名人

前言

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

一、力扣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;
}