2024年3月每日一题

每日一题

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;

/** Initialize your data structure here. */
public MyStack() {
queue1 = new LinkedList<Integer>();
queue2 = new LinkedList<Integer>();
}

/** Push element x onto stack. */
public void push(int x) {
queue2.offer(x);
while (!queue1.isEmpty()) {
queue2.offer(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}

/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue1.poll();
}

/** Get the top element. */
public int top() {
return queue1.peek();
}

/** Returns whether the stack is empty. */
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) { // 找到 k 个元素和不超过 mid 的子序列
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) { // ans 已达到最大值
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; //定义左右边界l r,最大可能分数res
while(true){
while(r < n && nums[r] >= nums[k]) r++; //向右寻找以nums[k]为最小值的好子数组
while(l >= 0 && nums[l] >= nums[k]) l--; //向左寻找以nums[k]为最小值的好子数组
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]); //更新nums[k] 为左右边界中的较大者
else if(l < 0) nums[k] = nums[r]; //左边遍历完了,更新nums[k]为右边界
else nums[k] = nums[l]; //右边遍历完了,更新nums[k]为左边界
}
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<>(); // number 的出现次数
private final Map<Integer, Integer> freq = new HashMap<>(); // number 的出现次数的出现次数

public FrequencyTracker() {}

public void update(int number, int delta) {
int c = cnt.merge(number, delta, Integer::sum);
freq.merge(c - delta, -1, Integer::sum); // 去掉一个旧的 cnt[number]
freq.merge(c, 1, Integer::sum); // 添加一个新的 cnt[number]
}

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; // 至少有一个 number 的出现次数恰好为 frequency
}
}

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]; // 每列的单调栈,为了能二分用 ArrayList
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; // 最后一个算出的 mn 就是 f[0][0]
}

// 开区间二分,见 https://www.bilibili.com/video/BV1AP41137w7/
private int search(List<int[]> st, int target) {
int left = -1, right = st.size(); // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
int mid = left + (right - left) / 2;
if (st.get(mid)[1] <= target) {
right = mid; // 范围缩小到 (left, mid)
} else {
left = mid; // 范围缩小到 (mid, right)
}
}
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]; // 从 start 出发,到各个点的最短路,如果不存在则为无穷大
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) {// 所有从 start 能到达的点都被更新了
return -1;
}
if (x == end) {// 找到终点,提前退出
return dis[x];
}
vis[x] = true; // 标记,在后续的循环中无需反复更新 x 到其余点的最短路长度
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; // + 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月每日一题结束


2024年3月每日一题
http://example.com/2024/03/01/3月/
作者
nianjx
发布于
2024年3月1日
许可协议