byu_rself

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; }} 时间 ...

LC.P773[滑动谜题] 方法一：BFS12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class Solution { int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}; public int slidingPuzzle(int[][] board) { StringBuilder sb = new StringBuilder(); for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { s ...

LC.P1239[串联字符串的最大长度] 方法一：剪枝DFS1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859class Solution { static Map<Integer, Integer> map = new HashMap<>(); int n; int ans = Integer.MIN_VALUE; int[] hash; private int get(int cur) { if (map.containsKey(cur)) return map.get(cur); int ans = 0; for (int i = cur; i > 0; i -= lowbit(i)) ans++; map.put(cur, ans); return ans; ...