byu_rself

LC.P1003[检查替换后的词是否有效] 方法一：栈1234567891011121314class Solution { public boolean isValid(String s) { int n = s.length(); if (n % 3 != 0) return false; StringBuilder stack = new StringBuilder(); for (char c : s.toCharArray()) { stack.append(c); if (stack.length() >= 3 && "abc".equals(stack.substring(stack.length() - 3))) { stack.delete(stack.length() - 3, stack.length()); } ...

LC.P138[复制带随机指针的链表] 方法一：哈希表12345678910111213141516171819202122232425262728293031323334/*// Definition for a Node.class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; }}*/class Solution { public Node copyRandomList(Node head) { if (head == null) return null; Node p = head; // key:原节点 value:新节点 Map<Node, Node> map = new HashMap ...

LC.P388[文件的最长绝对路径] 方法一：栈12345678910111213141516171819202122232425262728class Solution { public int lengthLongestPath(String input) { int n = input.length(), pos = 0, ans = 0; Deque<Integer> stack = new ArrayDeque<>(); while (pos < n) { int depth = 1; while (pos < n && input.charAt(pos) == '\t') { ++pos; ++depth; } boolean isFile = false; ...

LC.P970[强整数] 方法一：哈希表+枚举12345678910111213class Solution { public List<Integer> powerfulIntegers(int x, int y, int bound) { Set<Integer> set = new HashSet<>(); for (int i = 1; i <= bound; i *= x) { for (int j = 1; i + j <= bound; j *= y) { set.add(i + j); if (y == 1) break; } if (x == 1) break; } return new ArrayList<>(set); }}

LC.P391[完美矩形] 方法一：扫描线12345678910111213141516171819202122232425262728293031323334353637383940414243444546class Solution { public boolean isRectangleCover(int[][] rectangles) { int n = rectangles.length; int[][] point = new int[n * 2][4]; // 存储形式：(x,y1,y2,flag) for (int i = 0, idx = 0; i < n; ++i) { int[] rectangle = rectangles[i]; point[idx++] = new int[]{rectangle[0], rectangle[1], rectangle[3], 1}; point[idx++] ...

LC.P2423[删除字符使频率相同] 方法一：暴力+哈希表1234567891011121314151617181920212223242526class Solution { public boolean equalFrequency(String word) { int n = word.length(); for (int i = 0; i < n; ++i) { Map<Character, Integer> map = new HashMap<>(); for (int j = 0; j < n; ++j) { if (j != i) { map.merge(word.charAt(j), 1, Integer::sum); } } if (check( ...

LC.P850[矩形面积II] 方法一：扫描线12345678910111213141516171819202122232425262728293031323334353637class Solution { private static final int MOD = (int) 1e9 + 7; public int rectangleArea(int[][] rectangles) { List<Integer> list = new ArrayList<>(); for (int[] rectangle : rectangles) { list.add(rectangle[0]); list.add(rectangle[2]); } Collections.sort(list); long ans = 0; for (int i = 1; i < list.size(); ...

LC.P1172[餐盘栈] 方法一：构造12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152class DinnerPlates { // 栈的大小 private final int capacity; private final List<Deque<Integer>> stacks; // 最小堆，保存未满栈的下标 private final PriorityQueue<Integer> idx; public DinnerPlates(int capacity) { this.capacity = capacity; this.stacks = new ArrayList<>(); this.idx = new PriorityQueue<>(); } public ...

LC.P1048[最长字符串链] 方法一：动态规划+记忆化搜索1234567891011121314151617181920212223class Solution { Map<String, Integer> map = new HashMap<>(); public int longestStrChain(String[] words) { for (String word : words) map.put(word, 0); int ans = 0; for (String s : map.keySet()) { ans = Math.max(ans, dfs(s)); } return ans; } private int dfs(String s) { int ans = map.get(s); if (ans > 0) return ans; ...

LCR.P115[序列重建] 方法一：拓扑排序12345678910111213141516171819202122232425262728293031323334class Solution { int N = (int) 1e4 + 10, M = N, idx; int[] he = new int[N], e = new int[M], ne = new int[M], in = new int[N]; private void add(int a, int b) { e[idx] = b; ne[idx] = he[a]; he[a] = idx++; ++in[b]; } public boolean sequenceReconstruction(int[] nums, int[][] sequences) { Arrays.fill(he, -1); int n = nums.length; for (in ...