byu_rself

LC.P2304[网格中的最小路径代价] 方法一：记忆化搜索1234567891011121314151617181920212223242526272829class Solution { int m, n; int[][] grid; int[][] moveCost; int[][] cache; public int minPathCost(int[][] grid, int[][] moveCost) { m = grid.length; n = grid[0].length; this.grid = grid; this.moveCost = moveCost; cache = new int[m][n]; int ans = Integer.MAX_VALUE; for (int j = 0; j < n; ++j) { ans = Math.min(ans, dfs(0, j)); ...

LC.P274[H指数] 方法一：二分查找123456789101112131415class Solution { public int hIndex(int[] citations) { int left = 0, right = citations.length; while (left < right) { int mid = left + right + 1 >> 1; int s = 0; for (int x : citations) { if (x >= mid) ++s; } if (s >= mid) left = mid; else right = mid - 1; } return left; }} 时间复杂度：$O(nlo ...

LC.P2216[美化数组的最少删除数] 方法一：遍历123456789class Solution { public int minDeletion(int[] nums) { int cnt = 0, n = nums.length; for (int i = 0; i < n; ++i) { if ((i - cnt) % 2 == 0 && i + 1 < n && nums[i] == nums[i + 1]) ++cnt; } return (n - cnt) % 2 == 0 ? cnt : cnt + 1; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$

二分查找lowerBound(nums, target) 核心要素 注意区间开闭，三种都可以 循环结束条件：当前区间内没有元素 下一次二分查找区间：不能再查找(区间不包含) $mid$，防止死循环 返回值：大于等于 $target$ 的第一个下标（注意循环不变量） 有序数组中二分查找的四种类型（下面的转换仅适用于数组中都是整数） 第一个大于等于 $x$ 的下标： $lowerBound(nums, x)$ 第一个大于 $x$ 的下标：可以转换为 第一个大于等于 $x+1$ 的下标，即 $lowerBound(nums,x+1)$ 最后一个小于 $x$ 的下标：可以转换为 第一个大于等于 $x$ 的下标的左边位置, 即 $lowerBound(nums,x) - 1$; 最后一个小于等于 $x$ 的下标：可以转换为 第一个大于等于 $x+1$ 的下标的左边位置, 即 $lowerBound(nums,x+1) - 1$; 闭区间写法1234567891011121314private int lowerBound(int[] nums, int target) { ...

LC.P2736[最大和查询] 方法一：排序+单调栈+二分12345678910111213141516171819202122232425262728293031323334353637383940414243444546class Solution { public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) { int n = nums1.length, m = queries.length; int[][] index = new int[n][2]; for (int i = 0; i < n; ++i) { index[i][0] = nums1[i]; index[i][1] = nums2[i]; } // 按 nums1 的值从大到小排序 Arrays.sort(index, (a, b) -> ...

LC.P34[在排序数组中查找元素的第一个和最后一个位置] 方法一：二分1234567891011121314151617181920212223242526class Solution { public int[] searchRange(int[] nums, int target) { int[] ans = new int[]{-1, -1}; int n = nums.length; if (n == 0) return ans; // 查找左边界 int left = 0, right = n - 1; while (left < right) { int mid = left + right >> 1; if (nums[mid] >= target) right = mid; else left = mid + 1; } ...

LC.P37[解数独] 方法一：回溯1234567891011121314151617181920212223242526272829303132333435363738394041424344class Solution { // 表示 行、列、3*3 的方格的数字是否被使用过 boolean[][] row = new boolean[9][10]; boolean[][] col = new boolean[9][10]; boolean[][][] box = new boolean[3][3][10]; char[][] board; public void solveSudoku(char[][] board) { this.board = board; for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] != ...

LC.P2760[最长奇偶子数组] 方法一：枚举123456789101112131415class Solution { public int longestAlternatingSubarray(int[] nums, int threshold) { int n = nums.length, ans = 0; for (int l = 0; l < n; ++l) { if (nums[l] % 2 == 0 && nums[l] <= threshold) { int r = l + 1; while (r < n && nums[r] % 2 != nums[r - 1] % 2 && nums[r] <= threshold) { ++r; } ...

LC.P882[细分图中的可到达节点] 方法一：Dijkstra12345678910111213141516171819202122232425262728293031323334353637383940class Solution { public int reachableNodes(int[][] edges, int maxMoves, int n) { List<int[]>[] g = new List[n]; Arrays.setAll(g, k -> new ArrayList<>()); for (var e : edges) { int a = e[0], b = e[1], cnt = e[2] + 1; g[a].add(new int[]{b, cnt}); g[b].add(new int[]{a, cnt}); } ...

LC.P407[接雨水II] 方法一：优先队列12345678910111213141516171819202122232425262728293031323334class Solution { private static final int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int trapRainWater(int[][] heights) { int m = heights.length, n = heights[0].length; boolean[][] visited = new boolean[m][n]; // 存放三元组 [x,y,h] PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] ...