Leetcode Daily 20250725-20250731

Leetcode 20250725-20250731每日一题的记录，使用Java解题

3487. 删除后的最大子数组元素和

20250725
题目链接

参考：执行用时前排代码

思路

将大于等于0的数字加入HashSet，同时统计小于0的数字的最大值

最终如果HashSet非空，求HashSet所有元素的和；如果为空，返回小于0的数字的最大值

复杂度

• 时间复杂度：遍历一遍数组+HashSet，$O(N)$
• 空间复杂度：HashSet，$O(N)$

其他

Java int最大值和最小值
int a = Integer.MAX_VALUE;,int b = Integer.MIN_VALUE;

优化

题目数据范围$-100\leq nunms[i] \leq100$，用一个boolean数组储存当前数字是否出现过，遍历时更新状态

代码

class Solution {
    public int maxSum(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int ans = 0;
        int t = Integer.MIN_VALUE;
        for (int i : nums) {
            if (i >= 0 && !set.contains(i)) {
                set.add(i);
                ans += i;
            } else if (i < 0 && i > t) {
                t = i;
            }
        }
        if (set.isEmpty()) {
            return t;
        } else {
            return ans;
        }
    }
}

优化后

class Solution {
    public int maxSum(int[] nums) {
        boolean[] hasn = new boolean[102];
        int ans = 0;
        int t = Integer.MIN_VALUE;
        for (int i : nums) {
            if (i > 0) {
                if (!hasn[i]) {
                    hasn[i] = true;
                    ans += i;
                }
            } else {
                t = Math.max(t, i);
            }
        }
        if (ans == 0) {
            return t;
        }
        return ans;
    }
}

---

3480. 删除一个冲突对后最大子数组数目

20250726
题目链接

TODO

---

2210. 统计数组中峰和谷的数量

20250727
题目链接

参考：灵茶山艾府

思路

用一个l数组存当前数字左边的不相等元素的下标，用一个r数组存当前数字右边不相等元素的下标，l[0] = - 1，r[n - 1] = n

从下标1开始遍历数组，如果当前元素与前一个元素不同，并且满足当前元素大于l[i]下标和r[i]下标的元素或者小于l[i]下标和r[i]下标的元素，数量加1

复杂度

• 时间复杂度：遍历数组，$O(N)$
• 空间复杂度：l和r数组，$O(N)$

优化1

将连续相同元素压缩为1个元素，在原数组内操作

遍历去重后的数组，如果当前元素同时大于左右或者同时小于左右相邻元素，则数量加1

优化2

用3个指针分别表示左边最近不相等邻居pre，当前元素cur和右边最近不相等邻居nxt

遍历时使nxt为cur后第1个元素，如果nxt与cur对应元素相等则cur向后遍历。
如果相等时，判断cur对应元素是否同时大于（小于）pre和nxt对应元素，如果满足则答案加1，更新pre为cur

由于初始化时pre为0，cur为1，所以要判断pre是否与cur相等

代码

class Solution {
    public int countHillValley(int[] nums) {
        int ans = 0;
        int[] l = new int[nums.length];
        int[] r = new int[nums.length];
        l[0] = -1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                l[i] = l[i - 1];
            } else {
                l[i] = i - 1;
            }
        }
        r[nums.length - 1] = nums.length;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] == nums[i + 1]) {
                r[i] = r[i + 1];
            } else {
                r[i] = i + 1;
            }
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (l[i] >= 0 && r[i] < nums.length) {
                if (nums[l[i]] > nums[i] && nums[r[i]] > nums[i] && nums[i] != nums[i - 1]) {
                    ans++;
                } else if (nums[l[i]] < nums[i] && nums[r[i]] < nums[i] && nums[i] != nums[i - 1]) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

优化1

class Solution {
    public int countHillValley(int[] nums) {
        int l = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[l++] = nums[i];
            }
        }
        int ans = 0;
        for (int i = 1; i < l - 1; i++) {
            if ((nums[i] > nums[i - 1]) == (nums[i] > nums[i + 1])) {
                ans++;
            }
        }
        return ans;
    }
}

优化2

class Solution {
    public int countHillValley(int[] nums) {
        int ans = 0;
        int pre = nums[0];
        for (int i = 1; i < nums.length - 1; i++) {
            int cur = nums[i];
            int nxt = nums[i + 1];
            if (cur == nxt) {
                continue;
            }
            if (!(pre == cur) && (cur > pre) == (cur > nxt)) {
                ans++;
            }

            pre = cur;
        }
        return ans;
    }
}

---

2044. 统计按位或能得到最大值的子集数目

20250728
题目链接

参考：官方题解

执行用时前排代码

思路

整个数组所有元素按位或一定是最大值，先求出最大值

二进制压缩状态，如果当前子集所有元素按位或等于最大值，答案加1

复杂度

• 时间复杂度：全部子集$2^{n}$个，平均每个子集元素个数与n线性相关，整体复杂度$O(2^{N} \times N)$
• 空间复杂度：$O(1)$

优化

DFS，从下标为0开始递归，如果当前的值已经等于最大值，则答案加上$2^{n - i}$并返回，注意递归到数组最后一个元素返回，每一层递归选择是否将当前元素加入子集

优化后的时间复杂度为$O(2^{n})$，空间复杂度为$O(N)$（搜索深度最多为n）

代码

class Solution {
    public int countMaxOrSubsets(int[] nums) {
        int maxv = nums[0];
        int cnt = 0;
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            maxv = maxv | nums[i];
        }
        for (int i = 1; i < (1 << n); i++) {
            int tem = 0;
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    tem = tem | nums[j];
                }
            }
            if (tem == maxv) {
                cnt++;
            }
        }
        return cnt;
    }
}

优化后

class Solution {
    int cnt;
    public int countMaxOrSubsets(int[] nums) {
        int maxv = nums[0];
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            maxv = maxv | nums[i];
        }
        cnt = 0;
        dfs(0, 0, maxv, nums);
        return cnt;
    }
    private void dfs(int i, int sum, int ma, int[] nums) {
        if (sum == ma) {
            cnt += 1 << (nums.length - i);
            return;
        }
        if (i == nums.length) {
            return;
        }
        dfs(i + 1, sum, ma, nums);
        dfs(i + 1, sum | nums[i], ma, nums);
    }
}

---

2411. 按位或最大的最小子数组长度

20250729
题目链接

思路

数字最大是$10^{9}$，不会大于$(2^{10})^{3}=2^{30}$，可以用一个长度为31的数组bt表示当前位的"1"的个数

从后向前遍历数组，当前元素对应bt数组中为1的位加1。滑动窗口，如果删除窗口结尾元素后，bt数组不存在某个元素归零，则可以删除当前元素，继续向前滑动窗口；如果存在某个元素归零，则表示当前子数组按位或距离最大值缺了某一位，不可以向前滑动窗口

复杂度

• 时间复杂度：对于每一个二进制数，统计它的每一位需要$O(\log{C})$，C为二进制数最大值，总体为$O(N\log{C})$
• 空间复杂度：不算返回值，$O(\log{C})$

TODO $O(N)$优化

代码

class Solution {
    public int[] smallestSubarrays(int[] nums) {
        int n = nums.length;
        int[] bt = new int[31];
        int[] ans = new int[n];
        int p = n - 1;
        for (int i = n - 1; i >= 0 ; i--) {
            for (int j = 0, t = nums[i]; t > 0; j++, t = t >> 1) {
                if ((t & 1) == 1) {
                    bt[j]++;
                }
            }
            for (int j = p; j > i; j--) {
                boolean flag = true;
                for (int k = 0, t = nums[j]; t > 0; k++, t = t >> 1) {
                    if ((t & 1) == 1) {
                        if (bt[k] == 1) {
                            flag = false;
                            break;
                        }
                    }
                }
                if (flag) {
                    for (int k = 0, t = nums[j]; t > 0; k++, t = t >> 1) {
                        if ((t & 1) == 1) {
                            bt[k]--;
                        }
                    }
                    p--;
                } else {
                    break;
                }
            }
            ans[i] = p - i + 1;
        }
        return ans;
    }
}

---

2419. 按位与最大的最长子数组

20250730
题目链接

参考：执行用时前排代码

思路

数组中的最大值与小于它的数取与必然减小，因此题目换句话说是求最大值连续最长长度

先求出最大值，然后统计与最大值相等的连续序列的长度，并求序列长度的最大值

复杂度

• 时间复杂度：遍历数组$O(N)$
• 空间复杂度：$O(1)$

优化

一次遍历的方法

滑动窗口取元素相等的序列的左右端点，如果当前序列的元素大于最大值，则更新最大值和答案长度为当前窗口长度；如果当前序列的元素等于最大值，则取当前序列长度与之前答案长度的最大值

代码

class Solution {
    public int longestSubarray(int[] nums) {
        int ans = 1;
        int n = nums.length;
        int m = nums[0];
        for (int i = 1; i < n; i++) {
            m = Math.max(m, nums[i]);
        }
        int tem = 1;
        for (int i = 1; i < n; i++) {
            if (m == nums[i] && m == nums[i - 1]) {
                tem++;
            } else {
                ans = Math.max(ans, tem);
                tem = 1;
            }
        }
        ans = Math.max(ans, tem);
        return ans;
    }
}

优化后

class Solution {
    public int longestSubarray(int[] nums) {
        int ans = 1;
        int n = nums.length;
        int m = nums[0];
        int i = 0, j = 0;
        int tem = 0;
        while (i < n) {
            j = i;
            while (j < n && nums[j] == nums[i]) {
                j++;
            }
            if (nums[i] > m) {
                m = nums[i];
                ans = j - i;
            } else if (nums[i] == m) {
                ans = Math.max(ans, j - i);
            }
            i = j;
        }
        return ans;
    }
}

---

2683. 相邻值的按位异或

20250731
题目链接

思路

• 如果$a \oplus b = c$，则$a \oplus c = b$

$o[0] \oplus o[1] = d[0]$，可以假设o[0]等于d[0]，因此$o[1] = o[0] \oplus d[0]$、$o[2] = o[1] \oplus d[1]$
…$o[n - 1] = o[n - 2] \oplus d[n - 2]$、$o[0](expected) = o[n - 1] \oplus d[n - 1]$

最后判断o[0](expected)与o[0]是否相等即可

复杂度

• 时间复杂度：遍历数组，$O(N)$
• 空间复杂度：$O(1)$

代码

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int a = derived[0];
        for (int i = 0; i < derived.length; i++) {
            a = a ^ derived[i];
        }
        return a == derived[0];
    }
}

---

如有错误欢迎批评指正