且听疯吟

leetcode biweekly contest 87

2022-11-01

leetcode biweekly contest 87

今天周赛的题目质量还算蛮高，最后一题很少出线段树的模板题目了

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

地址

https://leetcode.cn/problems/most-frequent-even-element/

题意

哈希统计

思路

  1. 直接统计偶数元素的个数，并求出出现次数最多的偶数。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        map<int,int> cnt;
        for (auto v : nums) {
            if (v % 2 == 0) {
                cnt[v]++;
            }
        }
        int ans = -1, freq = 0;
        for (auto [x, f] : cnt) {
            if (f > freq) {
                ans = x;
                freq = f;
            }
        }
        return ans;
    }
};

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

地址

https://leetcode.cn/problems/optimal-partition-of-string/

题意

贪心 + 直接遍历

思路

  1. 感觉没啥好说的，直接切分即可，遍历到字符出现多次的情形，则进行切分。根据贪心理论，两个相同的字符一定不能出现在不同的
  2. 复杂度分析：
  • 时间复杂度：时间复杂度为 $O(n)$，$n$ 表示字符串的长度。
  • 空间复杂度：空间复杂度为 $O(|\Sigma|)$，$|\Sigma|$ 表示字符集的大小。

代码

class Solution {
public:
    int partitionString(string s) {
        vector<int> cnt(26);
        int ans = 1;
        for (int i = 0; i < s.size(); i++) {
            if (cnt[s[i] - 'a'] == 0) {
                cnt[s[i] - 'a']++;
            } else {
                cnt = vector<int>(26);
                ans++;
                cnt[s[i] - 'a']++;
            }
        }
        return ans;
    }
};

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

地址

https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/

题意

查分数组

思路

  1. 本体与某个 CPU 调度的题目基本上一模一样的原理，本质上就是求区间中最大的重叠次数即可，只需要求出最大重叠此时一定可以划分为不同的区间。
  2. 复杂度分析
  • 时间复杂度：时间复杂度为 $O(n \log n)$，$n$ 为数组的长度。
  • 空间复杂度：空间复杂度为 $O(n)$，$n$ 为数组的长度。

代码

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        map<int, int> cnt;
        for (auto v : intervals) {
            cnt[v[0]]++;
            cnt[v[1] + 1]--;
        }
        int curr = 0, ans = 0;
        for (auto [_, x] : cnt) {
            curr += x;
            ans = max(ans, curr);
        }
        return ans;
    }
};

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

地址

https://leetcode.cn/problems/longest-increasing-subsequence-ii/

题意

线段树模板

思路

  1. 典型的线段树模板，我们设 $dp[i]$ 表示以 $i$ 为结尾的元素所能构成最长子序列，对于当前的元素 $x$，我们需要查询以区间 $[x-k,x -1]$ 中的元素为结尾的最长递增子序列的长度，即我们需要查询 $dp[x-k, \cdots, x -1]$ 这样元素的最大值 $maxVal$，同时将 $dp[x] = maxVal + 1$，可以得到递推公式如下:
    $$
    dp[x] = \max_{j = x - k}^{x-1} dp[j]
    $$
    所以很容易采用线段树来进行范围查询和范围更新，非常典型的线段树模板题目。方法二维动态开点的线段树模板。
  2. 复杂度分析：
  • 时间复杂度：$O(n \log \max(nums))$，其中 $n$ 表示数组的长度，$\max(nums)$ 表示数组中的最大元素。
  • 空间复杂度：$O(\max(nums))$，$\max(nums)$ 表示数组中的最大元素。

代码

#define CHL(x) (x * 2)
#define CHR(x) (x * 2 + 1)
const int MAXN = 4e5 + 7;

struct SegTreeNode {
    int l, r;
    int maxVal;
};

SegTreeNode tree[MAXN];

void pushUpTree(int idx) {
    tree[idx].maxVal = max(tree[CHL(idx)].maxVal, tree[CHR(idx)].maxVal);
}

void buildTree(int idx, int l, int r) {
    if (l > r) {
        return;
    }
    if (l == r) {
        tree[idx].l = tree[idx].r = l;
        tree[idx].maxVal = 0;
        return;
    }
    tree[idx].l = l;
    tree[idx].r = r;
    
    int mid = (l + r) / 2;
    buildTree(CHL(idx), l, mid);
    buildTree(CHR(idx), mid + 1, r);
    pushUpTree(idx);
}

void updateTree(int x, int val, int idx) {
    if (x < tree[idx].l || x > tree[idx].r) {
        return;
    }
    if (x == tree[idx].l && x == tree[idx].r) {
        tree[idx].maxVal = val;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (x <= mid) {
        updateTree(x, val, CHL(idx));
    } else {
        updateTree(x, val, CHR(idx));
    }
    pushUpTree(idx);
}

int queryTree(int l, int r, int idx) {
    if (r < tree[idx].l || l > tree[idx].r) {
        return 0;
    }
    if (l <= tree[idx].l && r >= tree[idx].r) {
        return tree[idx].maxVal;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (r <= mid) {
        return queryTree(l, r, CHL(idx));
    } else if (l > mid) {
        return queryTree(l, r, CHR(idx));
    } else {
        return max(queryTree(l, mid, CHL(idx)), queryTree(mid + 1, r, CHR(idx)));
    }
}

class Solution {
public:
    int lengthOfLIS(vector<int>& nums, int k) {
        int maxN = *max_element(nums.begin(), nums.end());
        buildTree(1, 0, maxN);
        int ans = 0;
        for (auto x : nums) {
            int len = queryTree(max(0, x - k), x - 1, 1);
            ans = max(ans, len + 1);
            updateTree(x, len + 1, 1);
        }
        return ans;
    }
};
class Solution {
public:
    void update(int x, int val, int idx, int l, int r) {
        if (x < l || x > r) {
            return;
        }
        if (l == r && l == x) {
            tree[idx] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid) {
            update(x, val, idx * 2, l, mid);
        } else {
            update(x, val, idx * 2 + 1, mid + 1, r);
        }
        tree[idx] = max(tree[idx * 2], tree[idx * 2 + 1]);
    }

    int query(int left, int right, int idx, int l, int r) {
        if (left > r || right < l) {
            return 0;
        }
        if (left <= l && r <= right) {
            return tree[idx];
        }
        int mid = (l + r) / 2;
        if (right <= mid) {
            return query(left, right, idx * 2, l, mid);
        } else if (left > mid) {
            return query(left, right, idx * 2 + 1, mid + 1, r);
        } else {
            return max(query(left, mid, idx * 2, l, mid), \
                       query(mid + 1, right, idx * 2 + 1, mid + 1, r));
        }
    }
    int lengthOfLIS(vector<int>& nums, int k) {
        int maxNum = *max_element(nums.begin(), nums.end());
        int ans = 0;
        for (auto x : nums) {
            int len = query(max(0, x - k), x - 1, 1, 0, maxNum);
            ans = max(ans, len + 1);
            update(x, len + 1, 1, 0, maxNum);
        }
        return ans;
    }
private:
    unordered_map<int,int> tree;
};

欢迎关注和打赏，感谢支持！

Tags: 力扣周赛
← leetcode contest 311 中国银联专场竞赛（2023届校园招聘专场） →

扫描二维码，分享此文章