byu_rself

LC.P664[奇怪的打印机] 方法一：动态规划123456789101112131415161718class Solution { public int strangePrinter(String s) { int n = s.length(); int[][] f = new int[n + 1][n + 1]; for (int len = 1; len <= n; ++len) { for (int l = 0; l + len - 1 < n; ++l) { int r = l + len - 1; f[l][r] = f[l + 1][r] + 1; for (int k = l + 1; k <= r; ++k) { if (s.charAt(l) == s.charAt(k)) { ...

LC.P1267[统计参与通信的服务器] 方法一：模拟1234567891011121314151617181920212223class Solution { public int countServers(int[][] grid) { int m = grid.length, n = grid[0].length; int[] cntRow = new int[m], cntCol = new int[n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { ++cntRow[i]; ++cntCol[j]; } } } i ...

LC.P375[猜数字大小II] 方法一：记忆化搜索1234567891011121314151617181920class Solution { int[][] cache; public int getMoneyAmount(int n) { cache = new int[n + 1][n + 1]; return dfs(1, n); } private int dfs(int l, int r) { if (l >= r) return 0; if (cache[l][r] != 0) return cache[l][r]; int ans = Integer.MAX_VALUE; for (int x = l; x <= r; ++x) { int cur = Math.max(dfs(l, x - 1), dfs(x + 1, r)) + x; ans ...

LC.P1782[统计点对的数目] 方法一：排序+双指针+哈希表123456789101112131415161718192021222324252627282930313233343536373839404142434445class Solution { public int[] countPairs(int n, int[][] edges, int[] queries) { // degree[i] 表示与点 i 相连的边的数目 int[] degree = new int[n + 1]; // 节点编号从 1 到 n Map<Integer, Integer> cntE = new HashMap<>(); for (int[] e : edges) { int x = e[0], y = e[1]; if (x > y) { // 交换 x 和 y，因为 1-2 和 2- ...

LC.P849[到最近的人的最大距离] 方法一：贪心1234567891011121314class Solution { public int maxDistToClosest(int[] seats) { int last = -1, d = 0, n = seats.length, ans = 1; for (int i = 0; i < n; ++i) { if (seats[i] == 1) { if (last == -1) ans = Math.max(ans, i); // 坐左边 else ans = Math.max(ans, (i - last) / 2); // 坐中间 last = i; } } ans = Math.max(ans, n - last - 1); // 坐右边 retur ...

LC.P672[灯泡开关II] 方法一：找规律123456789101112class Solution { public int flipLights(int n, int presses) { // 不按开关 if (presses == 0) return 1; // 1个灯泡 if (n == 1) return 2; // 2个灯泡 else if (n == 2) return presses == 1 ? 3 : 4; // n >= 3 else return presses == 1 ? 4 : presses == 2 ? 7 : 8; }} 时间复杂度：$O(1)$ 空间复杂度：$O(1)$

LC.P667[优美的排列II] 方法一：脑筋急转弯1234567891011121314151617class Solution { public int[] constructArray(int n, int k) { int[] ans = new int[n]; int index = 0; // 前面部分相差为1 for (int i = 1; i < n - k; ++i) { ans[index++] = i; } for (int i = n - k, j = n; i <= j; ++i, --j) { ans[index++] = i; if (i != j) { ans[index++] = j; } } return ans;
...

LC.P2237[移动片段得到字符串] 方法一：双指针123456789101112class Solution { public boolean canChange(String start, String target) { int n = start.length(); for (int i = 0, j = 0; ; ++i, ++j) { while (i < n && start.charAt(i) == '_') ++i; while (j < n && target.charAt(j) == '_') ++j; if (i == n && j == n) return true; if (i == n || j == n || start.charAt(i) != target.charAt(j)) return fals ...

LC.P629[K个逆序对数组] 方法一：动态规划1234567891011121314151617class Solution { private static final int MOD = (int) 1e9 + 7; public int kInversePairs(int n, int k) { int[][] dp = new int[n + 1][k + 1], sum = new int[n + 1][k + 1]; dp[1][0] = 1; Arrays.fill(sum[1], 1); for (int i = 2; i <= n; ++i) { for (int j = 0; j <= k; ++j) { dp[i][j] = j < i ? sum[i - 1][j] : (sum[i - 1][j] - sum[i - 1][j - (i - 1) - 1] + MOD) % MOD ...

LC.P396[旋转函数] 方法一：前缀和+滑动窗口1234567891011121314class Solution { public int maxRotateFunction(int[] nums) { int n = nums.length, ans = 0; int[] sum = new int[n * 2 + 1]; for (int i = 1; i <= 2 * n; ++i) sum[i] = sum[i - 1] + nums[(i - 1) % n]; for (int i = 1; i <= n; ++i) ans += nums[i - 1] * (i - 1); for (int i = n + 1, cur = ans; i < 2 * n; ++i) { cur += nums[(i - 1) % n] * (n - 1); cur -= sum[i - 1] - sum[i - n]; ...