byu_rself

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 ...

LC.P1031[两个非重叠子数组的最大和] 方法一：前缀和+枚举1234567891011121314151617class Solution { public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) { int n = nums.length; int[] s = new int[n +1]; for (int i = 0; i < n; ++i) s[i + 1] = s[i] + nums[i]; return Math.max(maxSubSum(s, firstLen, secondLen), maxSubSum(s, secondLen, firstLen)); } private int maxSubSum(int[] s, int firstLen, int secondLen) { int maxSumA = 0, ans = 0; ...

LC.P2418[按身高排序] 方法一：排序123456789101112131415class Solution { public String[] sortPeople(String[] names, int[] heights) { int n = names.length; int[][] index = new int[n][2]; for (int i = 0; i < n; ++i) { index[i] = new int[]{heights[i], i}; } Arrays.sort(index, (a, b) -> b[0] - a[0]); String[] ans = new String[n]; for (int i = 0; i < n; ++i) { ans[i] = names[index[i][1]]; & ...