byu_rself

LCR.P21[删除链表的倒数第N个结点] 方法一：遍历1234567891011121314151617181920212223242526/** * 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 removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0, head), p = h ...

LC.P1572[矩阵对角线元素的和] 方法一：模拟12345678910class Solution { public int diagonalSum(int[][] mat) { int n = mat.length, ans = 0; for (int i = 0, j = n - 1; i < n; ++i, --j) { ans += mat[i][i] + mat[i][j]; if (i == j) ans -= mat[i][i]; } return ans; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

LCR.P91[粉刷房子] 方法一：动态规划123456789101112131415class Solution { public int minCost(int[][] costs) { int red = 0, blue = 0, green = 0; for (int[] cost : costs) { int r = Math.min(blue, green) + cost[0]; int b = Math.min(red, green) + cost[1]; int g = Math.min(red, blue) + cost[2]; red = r; blue = b; green = g; } return Math.min(red, Math.min(blue, green)); }} 时间复杂度：$O(n ...

LC.P312[戳气球] 方法一：动态规划123456789101112131415161718class Solution { public int maxCoins(int[] nums) { int n = nums.length; int[] arr = new int[n + 2]; arr[0] = arr[n + 1] = 1; for (int i = 1; i <= n; i++) arr[i] = nums[i - 1]; int[][] dp = new int[n + 2][n + 2]; for (int len = 3; len <= n + 2; ++len) { for (int l = 0; l + len - 1 <= n + 1; ++l) { int r = l + len - 1; for (int k = l + 1 ...

LC.P1289[下降路径最小和II] 方法一：动态规划1234567891011121314151617181920212223242526class Solution { public int minFallingPathSum(int[][] grid) { int n = grid.length; int[][] f = new int[n][n]; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { f[i][j] = Integer.MAX_VALUE; } } System.arraycopy(grid[0], 0, f[0], 0, n); for (int i = 1; i < n; ++i) { for (int j = 0; j ...

Offer.P20[表示数值的字符串] 方法一：模拟12345678910111213141516171819202122232425262728class Solution { public boolean isNumber(String s) { boolean isNum = false, isDot = false, iseOrE = false; char[] cs = s.trim().toCharArray(); for (int i = 0; i < cs.length; ++i) { if (cs[i] >= '0' && cs[i] <= '9') { isNum = true; } else if (cs[i] == '.') { // 只能有一个小数点 || 小 ...

LC.P1281[整数的各位积和之差] 方法一：模拟123456789101112class Solution { public int subtractProductAndSum(int n) { int prod = 1, sum = 0; while (n > 0) { int x = n % 10; n /= 10; prod *= x; sum += x; } return prod - sum; }} 时间复杂度：$O(logn)$ 空间复杂度：$O(1)$

LC.P75[颜色分类] 方法一：哈希表12345678910111213class Solution { public void sortColors(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); for (int num : nums) map.merge(num, 1, Integer::sum); int i = 0; for (int key : map.keySet()) { int cnt = map.get(key); while (cnt-- > 0) { nums[i++] = key; } } }} 时间复杂度：$O(n)$ 空间复杂度：$O(n)$ 方法二：双指针12345678910111213141 ...

LC.P31[下一个排列] 方法一：双指针1234567891011121314151617181920212223242526272829class Solution { public void nextPermutation(int[] nums) { int n = nums.length, i = n - 2; // 从后往前找到第一个 (i, i + 1) 满足 nums[i] < nums[i + 1] while (i >= 0 && nums[i] >= nums[i + 1]) --i; if (i >= 0) { int j = n - 1; // 在 [i + 1, n) 中从后往前找到第一个元素 j，满足nums[i] < nums[j] while (j >= 0 && nums[j] <= nums[i]) --j; ...

LC.P1749[任意子数组和的绝对值的最大值] 方法一：动态规划1234567891011121314class Solution { public int maxAbsoluteSum(int[] nums) { int n = nums.length, ans = Math.abs(nums[0]); int[] f = new int[n], g = new int[n]; f[0] = nums[0]; g[0] = nums[0]; for (int i = 1; i < n; ++i) { f[i] = Math.max(f[i - 1], 0) + nums[i]; g[i] = Math.min(g[i - 1], 0) + nums[i]; ans = Math.max(ans, Math.max(f[i], Math.abs(g[i]))); } re ...