byu_rself

LC.P2865[美丽塔I] 方法一：枚举123456789101112131415161718192021class Solution { public long maximumSumOfHeights(List<Integer> maxHeights) { long ans = 0; int n = maxHeights.size(); for (int i = 0; i < n; ++i) { int height = maxHeights.get(i); long t = height; for (int j = i - 1; j >= 0; --j) { height = Math.min(height, maxHeights.get(j)); t += height; } height ...

LC.P2765[最长交替子数组] 方法一：枚举123456789101112131415class Solution { public int alternatingSubarray(int[] nums) { int ans = -1, n = nums.length; for (int i = 0; i < n; ++i) { int k = 1, j = i; for ( ; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) { k *= -1; } if (j - i + 1 > 1) { ans = Math.max(ans, j - i + 1); } } return ans; &# ...

LC.P2171[拿出最少数目的魔法豆] 方法一：排序+枚举12345678910111213class Solution { public long minimumRemoval(int[] beans) { Arrays.sort(beans); long sum = 0; for (int x : beans) sum += x; long ans = sum; int n = beans.length; for (int i = 0; i < n; ++i) { ans = Math.min(ans, sum - (long) beans[i] * (n - i)); } return ans; }} 时间复杂度：$O(nlogn)$ 空间复杂度：$O(logn)$

LC.P2744[最大字符串配对数目] 方法一：哈希表123456789101112131415class Solution { public int maximumNumberOfStringPairs(String[] words) { int ans = 0; boolean[][] visited = new boolean[26][26]; for (String word : words) { int x = word.charAt(0) - 'a', y = word.charAt(1) - 'a'; if (visited[y][x]){ ++ans; } else { visited[x][y] = true; } } retur ...

LC.P2085[统计出现过一次的公共字符串] 方法一：哈希表1234567891011121314class Solution { public int countWords(String[] words1, String[] words2) { Map<String, Integer> map1 = new HashMap<>(), map2 = new HashMap<>(); for (String s : words1) map1.merge(s, 1, Integer::sum); for (String s : words2) map2.merge(s, 1, Integer::sum); int ans = 0; for (Map.Entry<String, Integer> e : map1.entrySet()) { if (e.getValue() == 1 && map2. ...

LC.P2645[构造有效字符串的最少插入数] 方法一：贪心+双指针1234567891011121314151617class Solution { public int addMinimum(String word) { String s = "abc"; int ans = 0, n = word.length(); for (int i = 0, j = 0; j < n; i = (i + 1) % 3) { if (word.charAt(j) != s.charAt(i)) { ++ans; } else { ++j; } } if (word.charAt(n - 1) != 'c') { ans += word.c ...

LC.P2696[删除子串后的字符串最小长度] 方法一：栈123456789101112131415class Solution { public int minLength(String s) { Deque<Character> stack = new ArrayDeque<>(); stack.push(' '); for (int i = 0; i < s.length(); ++i) { char c = s.charAt(i); if ((c == 'B' && stack.peek() == 'A') || (c == 'D' && stack.peek() == 'C')) { stack.pop(); } else & ...

LC.P2707[字符串中的额外字符] 方法一：哈希表+动态规划1234567891011121314151617181920class Solution { public int minExtraChar(String s, String[] dictionary) { Set<String> set = new HashSet<>(); for (String w : dictionary) { set.add(w); } int n = s.length(); int[] f = new int[n + 1]; f[0] = 0; for (int i = 1; i <= n; ++i) { f[i] = f[i - 1] + 1; for (int j = 0; j < i; ++j) { ...

LC.P447[回旋镖的数量] 方法一：哈希表+计数12345678910111213141516class Solution { public int numberOfBoomerangs(int[][] points) { int ans = 0; Map<Integer, Integer> cnt = new HashMap<>(); for (int[] p1 : points) { cnt.clear(); for (int[] p2 : points) { int d = (p1[0] - p2[0]) * (p1[0] - p2[0]) + (p1[1] - p2[1]) * (p1[1] - p2[1]); int c = cnt.getOrDefault(d, 0); ans += c * 2; ...

LC.P1944[队列中可以看到的人数] 方法一：单调栈123456789101112131415161718class Solution { public int[] canSeePersonsCount(int[] heights) { int n = heights.length; int[] ans = new int[n]; Deque<Integer> stack = new ArrayDeque<>(); for (int i = n - 1; i >= 0; --i) { while (!stack.isEmpty() && stack.peek() < heights[i]) { stack.pop(); ans[i]++; } if (!stack.isEmpty()) { ...