byu_rself

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

LC.P2312[卖木头块] 方法一：动态规划12345678910111213141516171819class Solution { public long sellingWood(int m, int n, int[][] prices) { int[][] pr = new int[m + 1][n + 1]; for (int[] p : prices) { pr[p[0]][p[1]] = p[2]; } long[][] f = new long[m + 1][n + 1]; for (int i = 1; i <= m; ++i) { for (int j = 1; j <=n; ++j) { f[i][j] = pr[i][j]; // 垂直切割 for (int k = 1; k < ...

LC.P2789[合并后数组中的最大元素] 方法一：贪心+倒序遍历12345678910class Solution { public long maxArrayValue(int[] nums) { int n = nums.length; long sum = nums[n - 1]; for (int i = n - 2; i >= 0; --i) { sum = nums[i] <= sum ? sum + nums[i] : nums[i]; } return sum; }} 时间复杂度：$O(n)$ 空间复杂度：$O(1)$