🏆 第 310 场力扣周赛
image.png
连掉几场后，终于上分了

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

思路：哈希表

  1. class Solution {
  2.     public int mostFrequentEven(int[] nums) {
  3.         Map<Integer, Integer> map = new HashMap<>();
  4.         for (int x : nums) {
  5.             map.merge(x, 1, Integer::sum);
  6.         }
  8.         int max = 0, res = 0x3f3f3f3f;
  9.         for (int x : map.keySet()) {
  10.             if (x % 2 == 0) {
  11.                 if (map.get(x) > max) {
  12.                     max = map.get(x);
  13.                     res = x;
  14.                 } else if (map.get(x) == max) {
  15.                     res = Math.min(res, x);
  16.                 }
  17.             }
  18.         }
  19.         return res == 0x3f3f3f3f ? -1 : res;
  20.     }
  21. }

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 仅由小写英文字母组成

思路：贪心

  1. class Solution {
  2.     public int partitionString(String s) {
  3.         int c = 0, n = s.length();
  4.         boolean[] st = new boolean[26];
  5.         for (int i = 0; i < n; i++) {
  6.             int j = i;
  7.             while (j < n && st[s.charAt(j) - 'a'] == false) {
  8.                 st[s.charAt(j) - 'a'] = true;
  9.                 j++;
  10.             }
  11.             c++;
  12.             i = j - 1;
  13.             Arrays.fill(st, false);
  14.         }
  15.         return c;
  16.     }
  17. }

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

思路：板子题
见区间分组

  1. class Solution {
  2.     public int minGroups(int[][] p) {
  3.         Map<Integer, Integer> map = new TreeMap<>();
  4.         int n = p.length;
  5.         for (int i = 0; i < n; i++) {
  6.             int a = p[i][0], b = p[i][1];
  7.             map.merge(a, 1, Integer::sum);
  8.             map.merge(b + 1, -1, Integer::sum);
  9.         }
  10.         int max = 0, cnt = 0;
  11.         for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
  12.             cnt += pair.getValue();
  13.             if (max < cnt)
  14.                 max = cnt;
  15.         }
  16.         return max;
  17.     }
  18. }

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

  1. // 线段树实现
  2. class Solution {
  3.     class Node {
  4.         int l, r;
  5.         Node left, right;
  6.         int max;
  8.         Node(int l, int r) {
  9.             this.l = l;
  10.             this.r = r;
  11.         }
  13.         int query(int ll, int rr) {
  14.             if (ll <= l && rr >= r)
  15.                 return max;
  16.             else {
  17.                 int mid = l + r >> 1;
  18.                 if (left == null) left = new Node(l, mid);
  19.                 if (right == null) right = new Node(mid + 1, r);
  21.                 int res = 0;
  22.                 if (ll <= mid) res = left.query(ll, rr);
  23.                 if (rr > mid) res = Math.max(res, right.query(ll, rr));
  24.                 return res;
  25.             }
  26.         }
  28.         void modify(int idx, int x) {
  29.             if (idx <= l && idx >= r)
  30.                 max = Math.max(max, x);
  31.             else {
  32.                 int mid = l + r >> 1;
  33.                 if (left == null) left = new Node(l, mid);
  34.                 if (right == null) right = new Node(mid + 1, r);
  35.                 if (idx <= mid) left.modify(idx, x);
  36.                 if (idx > mid) right.modify(idx, x);
  37.                 pushup();
  38.             }
  39.         }
  41.         void pushup() {
  42.             this.max = Math.max(left.max, right.max);
  43.         }
  44.     }
  46.     Node root = new Node(0, (int)(1e5));
  47.     public int lengthOfLIS(int[] nums, int k) {
  48.         int max = 0;
  49.         for (int x : nums) {
  50.             int l = Math.max(0, x - k), r = x - 1;
  51.             int t = root.query(l, r);
  52.             if (t + 1 > max)
  53.                 max = t + 1;
  54.             root.modify(x, t + 1);
  55.         }
  56.         return max;
  57.     }
  58. }
  1. // 树状数组实现
  2. class Solution {
  3.     public int lengthOfLIS(int[] nums, int k) {
  4.         int max = 0;
  5.         BIT bit = new BIT((int)(1e5));
  6.         for (int x : nums) {
  7.             int l = Math.max(1, x - k), r = x - 1;
  8.             int t = bit.query(l, r);
  9.             max = Math.max(t + 1, max);
  10.             bit.modify(x, t + 1);
  11.         }
  12.         return max;
  13.     }
  15.     class BIT {
  16.         int[] tr, a;
  17.         int n;
  19.         BIT(int n) {
  20.             this.n = n;
  21.             tr = new int[n + 1];
  22.             a = new int[n + 1];
  23.         }
  25.         void modify(int idx, int x) {
  26.             a[idx] = x;
  27.             for (int i = idx; i <= n; i += lowbit(i)) {
  28.                 if (x >= tr[i])
  29.                     tr[i] = x;
  30.                 else {
  31.                     tr[i] = x;
  32.                     for (int j = 1; j < lowbit(i); j <<= 1)
  33.                         tr[i] = Math.max(tr[i], tr[i - j]);
  34.                 }
  35.             }
  36.         }
  38.         int query(int l, int r) {
  39.             if (l > r) return 0;
  40.             else if (l == r) return a[l];
  41.             else if (l == r - lowbit(r) + 1) return tr[r];
  42.             else if (l < r - lowbit(r) + 1) return Math.max(tr[r], query(l, r - lowbit(r)));
  43.             else return Math.max(a[r], query(l, r - 1));
  44.         }
  46.         int lowbit(int x) {
  47.             return x & -x;
  48.         }
  49.     }
  50. }