每日一题
3 - 1
2369. 检查数组是否存在有效划分 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| class Solution { public boolean validPartition(int[] nums) { int n = nums.length; boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { if (i >= 2) { dp[i] = dp[i - 2] && validTwo(nums[i - 2], nums[i - 1]); } if (i >= 3) { dp[i] = dp[i] || (dp[i - 3] && validThree(nums[i - 3], nums[i - 2], nums[i - 1])); } } return dp[n]; } public boolean validTwo(int num1, int num2) { return num1 == num2; } public boolean validThree(int num1, int num2, int num3) { return (num1 == num2 && num1 == num3) || (num1 + 1 == num2 && num2 + 1 == num3); } }
|
3 - 2
2368. 受限条件下可到达节点的数目 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
| class Solution { int cnt = 0;
public int reachableNodes(int n, int[][] edges, int[] restricted) { boolean[] isrestricted = new boolean[n]; for (int x : restricted) { isrestricted[x] = true; }
List<Integer>[] g = new List[n]; for (int i = 0; i < n; i++) { g[i] = new ArrayList<Integer>(); } for (int[] v : edges) { g[v[0]].add(v[1]); g[v[1]].add(v[0]); } dfs(0, -1, isrestricted, g); return cnt; }
public void dfs(int x, int f, boolean[] isrestricted, List<Integer>[] g) { cnt++; for (int y : g[x]) { if (y != f && !isrestricted[y]) { dfs(y, x, isrestricted, g); } } } }
|
3 - 3
225. 用队列实现栈 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| class MyStack { Queue<Integer> queue1; Queue<Integer> queue2;
public MyStack() { queue1 = new LinkedList<Integer>(); queue2 = new LinkedList<Integer>(); } public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } Queue<Integer> temp = queue1; queue1 = queue2; queue2 = temp; } public int pop() { return queue1.poll(); } public int top() { return queue1.peek(); } public boolean empty() { return queue1.isEmpty(); } }
|
3 - 4
232. 用栈实现队列 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| class MyQueue { Deque<Integer> inStack; Deque<Integer> outStack;
public MyQueue() { inStack = new ArrayDeque<Integer>(); outStack = new ArrayDeque<Integer>(); }
public void push(int x) { inStack.push(x); }
public int pop() { if (outStack.isEmpty()) { in2out(); } return outStack.pop(); }
public int peek() { if (outStack.isEmpty()) { in2out(); } return outStack.peek(); }
public boolean empty() { return inStack.isEmpty() && outStack.isEmpty(); }
private void in2out() { while (!inStack.isEmpty()) { outStack.push(inStack.pop()); } } }
|
3 - 5
1976. 到达目的地的方案数 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
| class Solution { public int countPaths(int n, int[][] roads) { int mod = 1000000007; List<int[]>[] e = new List[n]; for (int i = 0; i < n; i++) { e[i] = new ArrayList<int[]>(); } for (int[] road : roads) { int x = road[0], y = road[1], t = road[2]; e[x].add(new int[]{y, t}); e[y].add(new int[]{x, t}); } long[] dis = new long[n]; Arrays.fill(dis, Long.MAX_VALUE); int[] ways = new int[n];
PriorityQueue<long[]> pq = new PriorityQueue<long[]>((a, b) -> Long.compare(a[0], b[0])); pq.offer(new long[]{0, 0}); dis[0] = 0; ways[0] = 1;
while (!pq.isEmpty()) { long[] arr = pq.poll(); long t = arr[0]; int u = (int) arr[1]; if (t > dis[u]) { continue; } for (int[] next : e[u]) { int v = next[0], w = next[1]; if (t + w < dis[v]) { dis[v] = t + w; ways[v] = ways[u]; pq.offer(new long[]{t + w, v}); } else if (t + w == dis[v]) { ways[v] = (ways[u] + ways[v]) % mod; } } } return ways[n - 1]; } }
|
3 - 6
2917. 找出数组中的 K-or 值 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int findKOr(int[] nums, int k) { int ans = 0; for (int i = 0; i < 31; i++) { int cnt1 = 0; for (int x : nums) { cnt1 += x >> i & 1; } if (cnt1 >= k) { ans |= 1 << i; } } return ans; } }
|
3 - 7
2575. 找出字符串的可整除数组 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public int[] divisibilityArray(String word, int m) { char[] s = word.toCharArray(); int[] ans = new int[s.length]; long x = 0; for(int i = 0; i< s.length; i++){ x = (x*10 + (s[i] - '0')) % m; if(x == 0) ans[i] = 1; } return ans; } }
|
3 - 8
2834. 找出美丽数组的最小和 - 力扣(LeetCode)
1 2 3 4 5 6
| class Solution { public int minimumPossibleSum(int n, int k) { long m = Math.min(k / 2, n); return (int) ((m * (m + 1) + (n - m - 1 + k * 2) * (n - m)) / 2 % 1_000_000_007); } }
|
3 - 9
2386. 找出数组的第 K 大和 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| class Solution { public long kSum(int[] nums, int k) { long sum = 0, right = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] >= 0) { sum += nums[i]; } else { nums[i] = -nums[i]; } right += nums[i]; } Arrays.sort(nums);
long left = -1; while (left + 1 < right) { long mid = (left + right) / 2; cnt = k - 1; dfs(0, mid, nums); if (cnt == 0) { right = mid; } else { left = mid; } } return sum - right; }
private int cnt;
private void dfs(int i, long s, int[] nums) { if (cnt == 0 || i == nums.length || s < nums[i]) { return; } cnt--; dfs(i + 1, s - nums[i], nums); dfs(i + 1, s, nums); } }
|
3 - 10*
299. 猜数字游戏 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public String getHint(String secret, String guess) { int n = secret.length(); int a = 0, b = 0; int[] cnt1 = new int[10], cnt2 = new int[10]; for (int i = 0; i < n; i++) { int c1 = secret.charAt(i) - '0', c2= guess.charAt(i) - '0'; if (c1 == c2) { a++; } else { cnt1[c1]++; cnt2[c2]++; } } for (int i = 0; i < 10; i++) b += Math.min(cnt1[i], cnt2[i]); return a + "A" + b + "B"; } }
|
3 - 11
2129. 将标题首字母大写 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public String capitalizeTitle(String s1) { StringBuilder ans = new StringBuilder(); for(String s : s1.split(" ")){ if(!ans.isEmpty()) ans.append(' '); if(s.length() > 2){ ans.append(s.substring(0, 1).toUpperCase()); s = s.substring(1); } ans.append(s.toLowerCase()); } return ans.toString(); } }
|
3 - 12
1261. 在受污染的二叉树中查找元素 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class FindElements { private final Set<Integer> s = new HashSet<>();
public FindElements(TreeNode root) { dfs(root, 0); }
public boolean find(int target) { return s.contains(target); }
private void dfs(TreeNode node, int val) { if (node == null) { return; } s.add(val); dfs(node.left, val * 2 + 1); dfs(node.right, val * 2 + 2); } }
|
3 - 13
2864. 最大二进制奇数 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public class Solution { public String maximumOddBinaryNumber(String s) { int cnt = 0; for(int i = 0; i < s.length(); i++) cnt += s.charAt(i) - '0'; StringBuilder sb = new StringBuilder(); for(int i = 0; i < cnt - 1; i++){ sb.append(1); } for(int i = 0; i < s.length() - cnt; i++){ sb.append('0'); } sb.append('1'); return sb.toString(); } }
|
3 - 14
2789. 合并后数组中的最大元素 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9
| class Solution { public long maxArrayValue(int[] nums) { long sum = nums[nums.length - 1]; for(int i = nums.length - 2; i >= 0; i--){ sum = nums[i] <= sum ? nums[i] + sum : nums[i]; } return sum; } }
|
3 - 15
2312. 卖木头块 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class 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 < j; k++) f[i][j] = Math.max(f[i][j], f[i][k] + f[i][j - k]); for (int k = 1; k < i; k++) f[i][j] = Math.max(f[i][j], f[k][j] + f[i - k][j]); } } return f[m][n]; } }
|
3 - 16
2684. 矩阵中移动的最大次数 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| class Solution { private int ans;
public int maxMoves(int[][] grid) { for (int i = 0; i < grid.length; i++) { dfs(i, 0, grid); } return ans; }
private void dfs(int i, int j, int[][] grid) { ans = Math.max(ans, j); if (ans == grid[0].length - 1) { return; } for (int k = Math.max(i - 1, 0); k < Math.min(i + 2, grid.length); k++) { if (grid[k][j + 1] > grid[i][j]) { dfs(k, j + 1, grid); } } grid[i][j] = 0; } }
|
3 - 17
310. 最小高度树 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
| class Solution { int N = 20010, M = N * 2, idx = 0; int[] he = new int[N], e = new int[M], ne = new int[M]; int[] f1 = new int[N], f2 = new int[N], g = new int[N], p = new int[N]; void add(int a, int b) { e[idx] = b; ne[idx] = he[a]; he[a] = idx++; } public List<Integer> findMinHeightTrees(int n, int[][] edges) { Arrays.fill(he, -1); for (int[] e : edges) { int a = e[0], b = e[1]; add(a, b); add(b, a); } dfs1(0, -1); dfs2(0, -1); List<Integer> ans = new ArrayList<>(); int min = n; for (int i = 0; i < n; i++) { int cur = Math.max(f1[i], g[i]); if (cur < min) { min = cur; ans.clear(); ans.add(i); } else if (cur == min) { ans.add(i); } } return ans; } int dfs1(int u, int fa) { for (int i = he[u]; i != -1; i = ne[i]) { int j = e[i]; if (j == fa) continue; int sub = dfs1(j, u) + 1; if (sub > f1[u]) { f2[u] = f1[u]; f1[u] = sub; p[u] = j; } else if (sub > f2[u]) { f2[u] = sub; } } return f1[u]; } void dfs2(int u, int fa) { for (int i = he[u]; i != -1; i = ne[i]) { int j = e[i]; if (j == fa) continue; if (p[u] != j) g[j] = Math.max(g[j], f1[u] + 1); else g[j] = Math.max(g[j], f2[u] + 1); g[j] = Math.max(g[j], g[u] + 1); dfs2(j, u); } } }
|
3 - 18
303. 区域和检索 - 数组不可变 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13
| class NumArray { public int[] sum; public int n; public NumArray(int[] nums) { this.n = nums.length; sum = new int[n + 1]; for(int i = 0; i < n; i++) sum[i + 1] = sum[i] + nums[i]; } public int sumRange(int left, int right) { return sum[right + 1] - sum[left]; } }
|
3 - 19
1793. 好子数组的最大分数 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int maximumScore(int[] nums, int k) { int l = k, r = k, n = nums.length, res = 0; while(true){ while(r < n && nums[r] >= nums[k]) r++; while(l >= 0 && nums[l] >= nums[k]) l--; res = Math.max(res, (r - l - 1) * nums[k]); if(l < 0 && r == n) break; if(l >= 0 && r < n) nums[k] = Math.max(nums[l], nums[r]); else if(l < 0) nums[k] = nums[r]; else nums[k] = nums[l]; } return res; } }
|
3 - 20
1969. 数组元素的最小非零乘积 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public int minNonZeroProduct(int p) { if(p == 1) return 1; long mod = 1000000000 + 7; long x = fastPow(2, p, mod) - 1; long y = (long) 1 << (p - 1); return (int)(fastPow(x - 1, y - 1, mod)*x % mod); } public long fastPow(long x, long n, long mod){ long res = 1; while(n != 0){ if((n & 1) != 0) res = res*x%mod; x = x * x %mod; n >>= 1; } return res; } }
|
3 - 21
2671. 频率跟踪器 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| class FrequencyTracker { private final Map<Integer, Integer> cnt = new HashMap<>(); private final Map<Integer, Integer> freq = new HashMap<>();
public FrequencyTracker() {}
public void update(int number, int delta) { int c = cnt.merge(number, delta, Integer::sum); freq.merge(c - delta, -1, Integer::sum); freq.merge(c, 1, Integer::sum); }
public void add(int number) { update(number, 1); }
public void deleteOne(int number) { if (cnt.getOrDefault(number, 0) > 0) { update(number, -1); } }
public boolean hasFrequency(int frequency) { return freq.getOrDefault(frequency, 0) > 0; } }
|
3 - 22
2617. 网格图中最少访问的格子数 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
| class Solution { public int minimumVisitedCells(int[][] grid) { int m = grid.length; int n = grid[0].length; int mn = 0; List<int[]>[] colStacks = new ArrayList[n]; Arrays.setAll(colStacks, i -> new ArrayList<int[]>()); List<int[]> rowSt = new ArrayList<>(); for (int i = m - 1; i >= 0; i--) { rowSt.clear(); for (int j = n - 1; j >= 0; j--) { int g = grid[i][j]; List<int[]> colSt = colStacks[j]; mn = i < m - 1 || j < n - 1 ? Integer.MAX_VALUE : 1; if (g > 0) { int k = search(rowSt, j + g); if (k < rowSt.size()) { mn = rowSt.get(k)[0] + 1; } k = search(colSt, i + g); if (k < colSt.size()) { mn = Math.min(mn, colSt.get(k)[0] + 1); } } if (mn < Integer.MAX_VALUE) { while (!rowSt.isEmpty() && mn <= rowSt.get(rowSt.size() - 1)[0]) { rowSt.remove(rowSt.size() - 1); } rowSt.add(new int[]{mn, j}); while (!colSt.isEmpty() && mn <= colSt.get(colSt.size() - 1)[0]) { colSt.remove(colSt.size() - 1); } colSt.add(new int[]{mn, i}); } } } return mn < Integer.MAX_VALUE ? mn : -1; }
private int search(List<int[]> st, int target) { int left = -1, right = st.size(); while (left + 1 < right) { int mid = left + (right - left) / 2; if (st.get(mid)[1] <= target) { right = mid; } else { left = mid; } } return right; } }
|
3 - 23
2549. 统计桌面上的不同数字 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public int distinctIntegers(int n) { int[] nums = new int[n + 1]; nums[n] = 1; for (int k = 0; k < n; k++) { for (int x = 1; x <= n; x++) { if (nums[x] == 0) { continue; } for (int i = 1; i <= n; i++) { if (x % i == 1) { nums[i] = 1; } } } } return Arrays.stream(nums).sum(); } }
|
3 - 24
322. 零钱兑换 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public int coinChange(int[] coins, int amount) { int[] f = new int[amount + 1]; Arrays.fill(f,65534); f[0] = 0; int n = coins.length; for(int i = 0 ; i < n ; i++) { for (int j = 0; j <= amount; j++) { if(j >= coins[i]) { f[j] = Math.min(f[j] , f[j - coins[i]] + 1); } } } return f[amount] == 65534 ? -1 : f[amount]; } }
|
2 - 25
518. 零钱兑换 II - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| class Solution { public int change(int amount, int[] coins) { int[] f = new int[amount + 1]; f[0] = 1; for(int i = 0 ; i < coins.length ; i++) { for(int j = coins[i] ; j <= amount ; j++) { f[j] += f[j - coins[i]]; } } return f[amount]; } }
|
3 - 26
2642. 设计可以求最短路径的图类 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| class Graph { private static final int INF = Integer.MAX_VALUE / 2;
private final int[][] g;
public Graph(int n, int[][] edges) { g = new int[n][n]; for (int[] row : g) { Arrays.fill(row, INF); } for (int[] e : edges) { addEdge(e); } }
public void addEdge(int[] e) { g[e[0]][e[1]] = e[2]; }
public int shortestPath(int start, int end) { int n = g.length; int[] dis = new int[n]; Arrays.fill(dis, INF); dis[start] = 0; boolean[] vis = new boolean[n]; while (true) { int x = -1; for (int i = 0; i < n; i++) { if (!vis[i] && (x < 0 || dis[i] < dis[x])) { x = i; } } if (x < 0 || dis[x] == INF) { return -1; } if (x == end) { return dis[x]; } vis[x] = true; for (int y = 0; y < n; y++) { dis[y] = Math.min(dis[y], dis[x] + g[x][y]); } } } }
|
3 - 27*
2580. 统计将重叠区间合并成组的方案数 - 力扣(LeetCode)
此题目可以视为,如果两个集合之间有交集,那么就可以视为是一个集合,有一点像当初做过的那道“甲板上的战舰”,且它k集合(归类之后)都可以在A或者B两个组进行选择所以它组合的方案有2^k个。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int countWays(int[][] ranges) { Arrays.sort(ranges, (a, b) -> a[0] - b[0]); int ans = 1; int maxR = -1; for (int[] p : ranges) { if (p[0] > maxR) { ans = ans * 2 % 1_000_000_007; } maxR = Math.max(maxR, p[1]); } return ans; } }
|
3 - 28
1997. 访问完所有房间的第一 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public int firstDayBeenInAllRooms(int[] nextVisit) { final long MOD = 1_000_000_007; int n = nextVisit.length; long[] s = new long[n]; for (int i = 0; i < n - 1; i++) { int j = nextVisit[i]; s[i + 1] = (s[i] * 2 - s[j] + 2 + MOD) % MOD; } return (int) s[n - 1]; } }
|
3 - 29
2908. 元素和最小的山形三元组 I - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int minimumSum(int[] nums) { int n = nums.length, res = 1000; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] < nums[j] && nums[k] < nums[j]) { res = Math.min(res, nums[i] + nums[j] + nums[k]); } } } } return res < 1000 ? res : -1; } }
|
3 - 30*
2952. 需要添加的硬币的最小数量 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public int minimumAddedCoins(int[] coins, int target) { Arrays.sort(coins); int ans = 0; int x = 1; int length = coins.length, index = 0; while(x <= target){ if(index < length && coins[index] <= x){ x += coins[index]; index++; }else{ x *= 2; ans++; } } return ans; } }
|
3 - 31
331. 验证二叉树的前序序列化 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| class Solution { public boolean isValidSerialization(String preorder) { int n = preorder.length(); int i = 0; Deque<Integer> stack = new LinkedList<Integer>(); stack.push(1); while (i < n) { if (stack.isEmpty()) { return false; } if (preorder.charAt(i) == ',') { i++; } else if (preorder.charAt(i) == '#'){ int top = stack.pop() - 1; if (top > 0) { stack.push(top); } i++; } else { while (i < n && preorder.charAt(i) != ',') { i++; } int top = stack.pop() - 1; if (top > 0) { stack.push(top); } stack.push(2); } } return stack.isEmpty(); } }
|
2024年3月每日一题结束