byu_rself

LC.P1020[飞地的数量] 思路找出矩阵最外围的陆地(即1)作为源点，向矩阵内部进行BFS搜索，将搜索到的陆地进行标记。 最后遍历矩阵，若为陆地且没有被标记，则为飞地。 方法一：多源BFS1234567891011121314151617181920212223242526272829303132333435363738class Solution { static int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; public int numEnclaves(int[][] grid) { int m = grid.length, n = grid[0].length; int ans = 0; Deque<int[]> queue = new ArrayDeque<>(); boolean[][] ...

LC.P2404[出现最频繁的偶数元素] 方法一：哈希表1234567891011121314151617class Solution { public int mostFrequentEven(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if (num % 2 == 0) map.merge(num, 1, Integer::sum); } int ans = -1, max = 0; for (Map.Entry<Integer, Integer> entry : map.entrySet()) { int x = entry.getKey(), cnt = entry.getValue(); if ((max < cnt) || ( ...

LC.P1147[段式回文] 思路采用贪心策略，从字符串的前后缀同时开始匹配，若相同，则分割，答案+2（因为题目要求尽可能多的分割），若遍历到字符串长度的一半时仍无法分割，则返回1。 方法一：递归12345678910111213class Solution { public int longestDecomposition(String text) { if (text.isEmpty()) return 0; // 若分割为空字符串，返回0 int n = text.length(); for (int i = 1; i <= n / 2; ++i) { // 若前后缀相等，则立刻分割 if (text.substring(0, i).equals(text.substring(n - i))) { return longestDecomposition(text.substring(i, n - i)) + 2; ...

LCR.P114[外星文字典] 方法一：拓扑排序1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556class Solution { int N = 26, M = N * N, idx = 0, cnt = 0; int[] he = new int[N], e = new int[M], ne = new int[M]; int[] in = new int[N], out = new int[N]; boolean[] visited = new boolean[N]; private void add(int a, int b) { e[idx] = b; ne[idx] = he[a]; he[a] = idx++; ++out[a]; ++in[b]; } public String ...

LC.P1041[困于环中的机器人] 方法一：模拟12345678910111213class Solution { public boolean isRobotBounded(String instructions) { int[] dist = new int[4]; int k = 0; for (int i = 0; i < instructions.length(); ++i) { char c = instructions.charAt(i); if (c == 'L') k = (k + 1) % 4; else if (c == 'R') k = (k + 3) % 4; else ++dist[k]; } return (k != 0) || (dist[0] == dist[2] && dist[1] = ...

LC.P802[找到最终的安全状态] 方法一：拓扑排序12345678910111213141516171819202122232425262728293031323334353637383940class Solution { int N = (int) 1e4 + 10, M = 4 * N; int[] he = new int[N], e = new int[M], ne = new int[M]; int idx; int[] cnt = new int[N]; private void add(int a, int b) { e[idx] = b; ne[idx] = he[a]; he[a] = idx++; } public List<Integer> eventualSafeNodes(int[][] graph) { int n = graph.length; Arrays.fill(he, -1); ...

LC.P1019[链表中的下一个更大节点] 思路利用单调栈，从右到左遍历链表的数据，若栈顶元素$<=$当前遍历到的元素，则弹出栈。 若栈中仍有元素，则存在下一个更大的节点；否则为0。 方法一：单调栈(List实现反转)1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { public int[] nextLa ...

LC.P851[喧闹和富有] 方法一：拓扑排序1234567891011121314151617181920212223242526272829303132333435363738class Solution { int N = 510, M = N * N + 10; int[] he = new int[N], e = new int[M], ne = new int[M]; int idx; private void add(int a, int b) { e[idx] = b; ne[idx] = he[a]; he[a] = idx; ++idx; } public int[] loudAndRich(int[][] richer, int[] quiet) { int n = quiet.length; int[] in = new int[n]; Arrays.fill(he, -1); ...

LC.P863[二叉树中所有距离为 K 的结点] 思路树是一类特殊的图，对二叉树中相邻的节点建图，边的权重为1。接着从目标节点出发遍历图，找到距离为k的节点。 方法一：建图+BFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { int N = 510, M = 4 * N, idx = 0; int[] he = new int[N], e = new int[M], ne = new ...

LC.P2399[检查相同字母间的距离] 方法一：暴力12345678910111213class Solution { public boolean checkDistances(String s, int[] distance) { int n = s.length(); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (s.charAt(i) == s.charAt(j) && distance[s.charAt(i) - 'a'] != j - i - 1) { return false; } } } return true; }} 时间 ...