byu_rself

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()) { ...

LC.P2397[被列覆盖的最多行数] 方法一：二进制枚举12345678910111213141516171819202122232425class Solution { public int maximumRows(int[][] matrix, int numSelect) { int m = matrix.length, n = matrix[0].length; int[] rows = new int[m]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == 1) { rows[i] |= 1 << j; } } } int ans = 0; ...

LC.P2487[从链表中移除节点] 方法一：单调栈12345678910111213141516171819202122232425262728/** * 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 ListNode removeNodes(ListNode head) { ListNode dummy = new ListNode(0, head); Deque< ...

LC.P576[出界的路径数] 方法一：记忆化搜索123456789101112131415161718192021222324252627282930313233class Solution { int m, n; int[][][] cache; static int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; static final int MOD = (int) 1e9 + 7; public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { this.m = m; this.n = n; cache = new int[m][n][maxMove + 1]; for (int i = 0; i < ...

LC.P2706[购买两块巧克力] 方法一：一次遍历123456789101112131415class Solution { public int buyChoco(int[] prices, int money) { int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE; for (int x : prices) { if (x < a) { b = a; a = x; } else if (x < b) { b = x; } } int cost = a + b; return money < cost ? money : money - cost; }} 时间复杂度：$O(n)$ ...

LC.P816[模糊坐标] 方法一：枚举1234567891011121314151617181920212223242526272829class Solution { String s; public List<String> ambiguousCoordinates(String ss) { s = ss.substring(1, ss.length() - 1); int n = s.length(); List<String> ans = new ArrayList<>(); for (int i = 0; i < n - 1; ++i) { for (String x : search(0, i)) { for (String y : search(i + 1, n - 1)) { ans.add(String.format(& ...

LC.P1775[通过最少操作次数使数组的和相等] 方法一：贪心+计数12345678910111213141516171819202122232425262728class Solution { public int minOperations(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; if (6 * m < n || 6 * n < m) return -1; int d = 0; for (int x : nums2) d += x; for (int x : nums1) d -= x; // 交换，统一让 nums1 的数变大，nums2 的数变小 if (d < 0) { d = -d; int[] temp = nums1; nums1 = nums2; ...

LC.P1349[参加考试的最大学生数] 方法一：记忆化搜索+状态压缩123456789101112131415161718192021222324252627282930313233343536373839class Solution { int[][] cache; public int maxStudents(char[][] seats) { int m = seats.length, n = seats[0].length; int[] a = new int[m]; // a[i] 是第 i 排可用椅子的下标集合 for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (seats[i][j] == '.') { a[i] |= 1 << j; ...

LC.P1447[最简分数] 方法一：数学123456789101112131415class Solution { public List<String> simplifiedFractions(int n) { List<String> ans = new ArrayList<>(); for (int i = 1; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { if (gcd(i, j) == 1) ans.add(i + "/" + j); } } return ans; } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);  ...