🏆 第 310 场力扣周赛

🏆 第 310 场力扣周赛

连掉几场后，终于上分了

6176. 出现最频繁的偶数元素

给你一个整数数组 nums ，返回出现最频繁的偶数元素。
如果存在多个满足条件的元素，只需要返回 最小 的一个。如果不存在这样的元素，返回 -1 。

示例 1：
输入：nums = [0,1,2,2,4,4,1] 输出：2 解释： 数组中的偶数元素为 0、2 和 4 ，在这些元素中，2 和 4 出现次数最多。 返回最小的那个，即返回 2 。
示例 2：
输入：nums = [4,4,4,9,2,4] 输出：4 解释：4 是出现最频繁的偶数元素。
示例 3：
输入：nums = [29,47,21,41,13,37,25,7] 输出：-1 解释：不存在偶数元素。

提示：

• 1 <= nums.length <= 2000
• 0 <= nums[i] <= 105

思路：哈希表

class Solution {
    public int mostFrequentEven(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            map.merge(x, 1, Integer::sum);
        }
        int max = 0, res = 0x3f3f3f3f;
        for (int x : map.keySet()) {
            if (x % 2 == 0) {
                if (map.get(x) > max) {
                    max = map.get(x);
                    res = x;
                } else if (map.get(x) == max) {
                    res = Math.min(res, x);
                }
            }
        }
        return res == 0x3f3f3f3f ? -1 : res;
    }
}

6177. 子字符串的最优划分

给你一个字符串 s ，请你将该字符串划分成一个或多个 子字符串 ，并满足每个子字符串中的字符都是 唯一 的。也就是说，在单个子字符串中，字母的出现次数都不超过 一次 。
满足题目要求的情况下，返回 最少 需要划分多少个子字符串。
注意，划分后，原字符串中的每个字符都应该恰好属于一个子字符串。

示例 1：
输入：s = “abacaba” 输出：4 解释： 两种可行的划分方法分别是 (“a”,”ba”,”cab”,”a”) 和 (“ab”,”a”,”ca”,”ba”) 。 可以证明最少需要划分 4 个子字符串。
示例 2：
输入：s = “ssssss” 输出：6 解释： 只存在一种可行的划分方法 (“s”,”s”,”s”,”s”,”s”,”s”) 。

提示：

• 1 <= s.length <= 105
• s 仅由小写英文字母组成

思路：贪心

class Solution {
    public int partitionString(String s) {
        int c = 0, n = s.length();
        boolean[] st = new boolean[26];
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && st[s.charAt(j) - 'a'] == false) {
                st[s.charAt(j) - 'a'] = true;
                j++;
            }
            c++;
            i = j - 1;
            Arrays.fill(st, false);
        }
        return c;
    }
}

6178. 将区间分为最少组数

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。
你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。
请你返回 最少 需要划分成多少个组。
如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是 相交 的。比方说区间 [1, 5] 和 [5, 8] 相交。

示例 1：
输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]] 输出：3 解释：我们可以将区间划分为如下的区间组： - 第 1 组：[1, 5] ，[6, 8] 。 - 第 2 组：[2, 3] ，[5, 10] 。 - 第 3 组：[1, 10] 。 可以证明无法将区间划分为少于 3 个组。
示例 2：
输入：intervals = [[1,3],[5,6],[8,10],[11,13]] 输出：1 解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。

提示：

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 106

思路：板子题
见区间分组

class Solution {
    public int minGroups(int[][] p) {
        Map<Integer, Integer> map = new TreeMap<>();
        int n = p.length;
        for (int i = 0; i < n; i++) {
            int a = p[i][0], b = p[i][1];
            map.merge(a, 1, Integer::sum);
            map.merge(b + 1, -1, Integer::sum);
        }
        int max = 0, cnt = 0;
        for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
            cnt += pair.getValue();
            if (max < cnt)
                max = cnt;
        }
        return max;
    }
}

6206. 最长递增子序列 II

给你一个整数数组 nums 和一个整数 k 。
找到 nums 中满足以下要求的最长子序列：

• 子序列 严格递增
• 子序列中相邻元素的差值 不超过 k 。

请你返回满足上述要求的 最长子序列 的长度。
子序列 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。

示例 1：
输入：nums = [4,2,1,4,3,4,5,8,15], k = 3 输出：5 解释： 满足要求的最长子序列是 [1,3,4,5,8] 。 子序列长度为 5 ，所以我们返回 5 。 注意子序列 [1,3,4,5,8,15] 不满足要求，因为 15 - 8 = 7 大于 3 。
示例 2：
输入：nums = [7,4,5,1,8,12,4,7], k = 5 输出：4 解释： 满足要求的最长子序列是 [4,5,8,12] 。 子序列长度为 4 ，所以我们返回 4 。
示例 3：
输入：nums = [1,5], k = 1 输出：1 解释： 满足要求的最长子序列是 [1] 。 子序列长度为 1 ，所以我们返回 1 。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 105

思路：
DP + RMQ

// 线段树实现
class Solution {
    class Node {
        int l, r;
        Node left, right;
        int max;
        Node(int l, int r) {
            this.l = l;
            this.r = r;
        }
        int query(int ll, int rr) {
            if (ll <= l && rr >= r)
                return max;
            else {
                int mid = l + r >> 1;
                if (left == null) left = new Node(l, mid);
                if (right == null) right = new Node(mid + 1, r);
                int res = 0;
                if (ll <= mid) res = left.query(ll, rr);
                if (rr > mid) res = Math.max(res, right.query(ll, rr));
                return res;
            }
        }
        void modify(int idx, int x) {
            if (idx <= l && idx >= r)
                max = Math.max(max, x);
            else {
                int mid = l + r >> 1;
                if (left == null) left = new Node(l, mid);
                if (right == null) right = new Node(mid + 1, r);
                if (idx <= mid) left.modify(idx, x);
                if (idx > mid) right.modify(idx, x);
                pushup();
            }
        }
        void pushup() {
            this.max = Math.max(left.max, right.max);
        }
    }
    Node root = new Node(0, (int)(1e5));
    public int lengthOfLIS(int[] nums, int k) {
        int max = 0;
        for (int x : nums) {
            int l = Math.max(0, x - k), r = x - 1;
            int t = root.query(l, r);
            if (t + 1 > max)
                max = t + 1;
            root.modify(x, t + 1);
        }
        return max;
    }
}

// 树状数组实现
class Solution {
    public int lengthOfLIS(int[] nums, int k) {
        int max = 0;
        BIT bit = new BIT((int)(1e5));
        for (int x : nums) {
            int l = Math.max(1, x - k), r = x - 1;
            int t = bit.query(l, r);
            max = Math.max(t + 1, max);
            bit.modify(x, t + 1);
        }
        return max;
    }
    class BIT {
        int[] tr, a;
        int n;
        BIT(int n) {
            this.n = n;
            tr = new int[n + 1];
            a = new int[n + 1];
        }
        void modify(int idx, int x) {
            a[idx] = x;
            for (int i = idx; i <= n; i += lowbit(i)) {
                if (x >= tr[i])
                    tr[i] = x;
                else {
                    tr[i] = x;
                    for (int j = 1; j < lowbit(i); j <<= 1)
                        tr[i] = Math.max(tr[i], tr[i - j]);
                }
            }
        }
        int query(int l, int r) {
            if (l > r) return 0;
            else if (l == r) return a[l];
            else if (l == r - lowbit(r) + 1) return tr[r];
            else if (l < r - lowbit(r) + 1) return Math.max(tr[r], query(l, r - lowbit(r)));
            else return Math.max(a[r], query(l, r - 1));
        }
        int lowbit(int x) {
            return x & -x;
        }
    }
}