vampire`blogs

原始思路 12345678910111213141516171819202122232425262728293031class Solution { Set<Integer> set = new HashSet<>(); boolean[] st; public boolean canVisitAllRooms(List<List<Integer>> rooms) { int n = rooms.size(); st = new boolean[n]; set.add(0); return dfs(0, n, rooms); } public boolean dfs(int cur, int n, List<List<Integer>> rooms) { if (set.size() == n) { // 拥有所有钥匙 re ...

leetcode-145. 二叉树的后序遍历 12345678910111213141516171819202122232425class Solution { List<Integer> result = new ArrayList<>(); public List<Integer> postorderTraversal(TreeNode root) { dfs(root); return result; } public void dfs(TreeNode root){ if(root == null){ return; } if(root.left != null){ dfs(root.left); } if(root.right != null){ dfs(root. ...

AcWing 854. Floyd求最短路 基础模板 12345678910111213141516171819202122232425262728293031323334353637383940// 基础模板,伪代码class Main{ public static void main(String[] args){ int inf = 1000000000; // n个点,定义邻接矩阵 int[][] dist = new int[n+1][n+1]; // 初始化邻接矩阵 for(int i = 0; i < n; i++){ for(int j = 0; j < n; i++){ if(i==j){ // 自己到自己为0 dist[i][j] = 0; }else{ ...

acwing-852. spfa判断负环 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081import java.util.*;class Main{ static int inf = 1000000000; // 定义邻接表 static int[] e; static int[] w; static int[] ne; static int[] h; static int idx = 0; //定义距离 static int[] dist; //定义已经访问过的点 static boolean[] st; //定义一个最小堆 static LinkedList<Integer> queue = new LinkedList< ...

acwing-851. spfa求最短路 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879import java.util.*;class Main{ static int inf = 1000000000; // 定义邻接表 static int[] e; static int[] w; static int[] ne; static int[] h; static int idx = 0; //定义距离 static int[] dist; //定义已经访问过的点 static boolean[] st; //定义一个最小堆 static LinkedList<Integer> queue = new LinkedList<> ...

leetcode-1161. 最大层内元素和 1234567891011121314151617181920212223242526272829303132class Solution { public int maxLevelSum(TreeNode root) { if (root == null) { return 0; } int max = Integer.MIN_VALUE; int result = 0; int level = 0; LinkedList<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (queue.size() > 0) { int n = queue.size(); int count = 0; ...

leetcode-1557. 可以到达所有点的最少点数目 使用逆向集合存储点的入度 1234567891011121314151617181920class Solution { public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) { List<Integer> result = new ArrayList<>(); List<Set<Integer>> rgraph = new ArrayList<>(); for (int i = 0; i < n; i++) { rgraph.add(new HashSet<>()); } for (int i = 0; i < edges.size(); i++) { ...

leetcode-面试题 04.01. 节点间通路 12345678910111213141516171819202122232425262728293031class Solution { List<Set<Integer>> g = new ArrayList<>(); public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) { for (int i = 0; i < n; i++) { g.add(new HashSet<Integer>()); } for (int[] arr : graph) { g.get(arr[0]).add(arr[1]); } return dfs(n, start, sta ...

leetcode-802. 找到最终的安全状态 出度为零的点是安全的点 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class Solution { public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; //记录所有安全的点 Set<Integer> safe = new HashSet<>(); // 计算所有点的出度,将出度为0的加入到队列中 LinkedList<Integer> queue = new LinkedList<>(); //新建两个List存放图正向节点和边的反向节点 List<Set<Integer>> g = ...

leetcode-1535. 找出数组游戏的赢家 原始思路 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950class Solution { Map<Integer, Integer> map = new HashMap<>(); public int getWinner(int[] arr, int k) { LinkedList<Integer> list = new LinkedList<>(); int max = -100000000; for (int i = 0; i < arr.length; i++) { list.add(arr[i]); max = Math.max(max, arr[i]); } boolean ...