byu_rself

LC.P416[分割等和子集] 方法一：记忆化搜索1234567891011121314151617181920212223242526272829303132class Solution { private int[][] cache; private int[] nums; private int n; public boolean canPartition(int[] nums) { int sum = 0; for (int num : nums) sum += num; if (sum % 2 != 0) { return false; } this.n = nums.length; this.nums = nums; cache = new int[n][sum / 2 + 1]; for (int[] c : cache) { Arrays.fi ...

LC.P2874[有序三元组中的最大值II] 方法一：贪心+前后缀数组1234567891011121314151617class Solution { public long maximumTripletValue(int[] nums) { int n = nums.length; int[] leftMax = new int[n]; // [0, i)的最大值 int[] rightMax = new int[n]; // (i, n)的最大值 for (int i = 1; i < n; ++i) { leftMax[i] = Math.max(leftMax[i - 1], nums[i - 1]); rightMax[n - i - 1] = Math.max(rightMax[n - i], nums[n - i]); } long ans = 0; for (int j = 1 ...

LC.P3128[直角三角形] 方法一：乘法原理12345678910111213141516171819202122class Solution { public long numberOfRightTriangles(int[][] grid) { int m = grid.length, n = grid[0].length; int[] rows = new int[m]; int[] cols = new int[n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { rows[i] += grid[i][j]; cols[j] += grid[i][j]; } } long ans = 0; for (int i = 0; i ...

LCP.P40[心算挑战] 方法一：排序+贪心123456789101112131415161718192021222324252627282930313233343536class Solution { int[] cards; int cnt, n; public int maxmiumScore(int[] cards, int cnt) { this.cards = cards; this.cnt = cnt; Arrays.sort(cards); this.n = cards.length; int sum = 0; for (int i = n - cnt; i < n; ++i) { sum += cards[i]; } if (sum % 2 == 0) return sum; int x = cards[n - cnt]; int an ...

LC.P3115[质数的最大距离] 方法一：遍历1234567891011121314151617181920212223242526class Solution { public int maximumPrimeDifference(int[] nums) { int n = nums.length, left = 0, right = 0; for (int i = 0; i < n; ++i) { if (isPrime(nums[i])) { left = i; break; } } for (int i = n - 1; i >= 0; --i) { if (isPrime(nums[i])) { right = i; break; ...

LC.P2225[找出输掉零场或一场比赛的玩家] 方法一：哈希表+排序12345678910111213141516171819class Solution { public List<List<Integer>> findWinners(int[][] matches) { Map<Integer, Integer> map = new HashMap<>(); for (int[] m : matches) { int a = m[0], b = m[1]; map.putIfAbsent(a, 0); map.merge(b, 1, Integer::sum); } List<Integer> a = new ArrayList<>(), b = new ArrayList<>(); for (Map.Entry< ...

LC.P826[安排工作以达到最大收益] 方法一：排序+双指针12345678910111213141516171819class Solution { public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) { int n = difficulty.length; int[][] index = new int[n][2]; for (int i = 0; i < n; ++i) { index[i] = new int[]{difficulty[i], profit[i]}; } Arrays.sort(index, (a, b) -> a[0] - b[0]); Arrays.sort(worker); int ans = 0, j = 0, maxProfit = 0; f ...

LC.P994[腐烂的橘子] 方法一：BFS12345678910111213141516171819202122232425262728293031323334class Solution { static final int dirs[][] = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public int orangesRotting(int[][] grid) { int m = grid.length, n = grid[0].length, ans = 0, cnt = 0; Deque<int[]> queue = new ArrayDeque<>(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ...

LC.P377[组合总和IV] 方法一：记忆化搜索这道题本质是LC.P70[爬楼梯] 123456789101112131415161718192021222324class Solution { int[] cache; int[] nums; public int combinationSum4(int[] nums, int target) { cache = new int[target + 1]; this.nums = nums; Arrays.fill(cache, -1); return dfs(target); } private int dfs(int i) { if (i == 0) return 1; if (cache[i] != -1) return cache[i]; int ans = 0; for (int x : nums) { if (x ...

LC.P216[组合总和III] 方法一：回溯+剪枝12345678910111213141516171819202122232425262728293031class Solution { List<List<Integer>> ans = new ArrayList<>(); List<Integer> path = new ArrayList<>(); int k; public List<List<Integer>> combinationSum3(int k, int n) { this.k = k; dfs(1, n); return ans; } private void dfs(int i, int s) { if (s == 0) { if (path.size() == k) { a ...