byu_rself

LCR.P30[O(1)时间插入、删除和获取随机元素] 方法一：哈希表+List模拟12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455class RandomizedSet { Map<Integer, Integer> map; List<Integer> list; Random random; /** * Initialize your data structure here. */ public RandomizedSet() { map = new HashMap<>(); list = new ArrayList<>(); random = new Random(); } /** * Inserts a value to the set. R ...

LCR.P29[循环有序列表的插入] 方法一：模拟12345678910111213141516171819202122232425262728293031323334353637383940414243444546/*// Definition for a Node.class Node { public int val; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _next) { val = _val; next = _next; }};*/class Solution { public Node insert(Node head, int insertVal) { Node node = new Node(insertVal ...

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