leetCode第310场周赛

最新推荐文章于 2025-05-07 11:37:05 发布

圆圆爱跳舞

最新推荐文章于 2025-05-07 11:37:05 发布

阅读量266

点赞数

文章标签：哈希表算法区间划分字符串处理最频繁元素

本文链接：https://blog.csdn.net/errors_F/article/details/126804376

版权

这篇博客探讨了三个算法问题：1) 寻找数组中最频繁出现的偶数；2) 字符串的最优划分，确保每个子字符串中字符唯一；3) 将不相交区间划分为最少的组。这些问题都涉及到了哈希表的使用，通过统计和比较找出最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

T1：出现最频繁的偶数元素
给你一个整数数组 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
解释：不存在偶数元素。
这个题目的思路非常简单，就是用map记录每个元素出现的次数，并找出出现次数最多的值。然后再在map中找最大值对应的第一次出现的元素。（因为要求次数相同时返回的是较小的，所以这个题用map，如果题目对返回的值不做要求，只要求最频繁出现，则可以用unordered_map）。

class Solution {
public:
    int mostFrequentEven(vector<int>& nums) {
        int n = nums.size();
        map<int,int>hash;
        int sum = 0;
        int res = -1;
        for(auto c : nums){
            if(c % 2 ==0){
                hash[c]++;
                sum = max(sum ,hash[c]);
            }
        }
        for(auto&[c,count]:hash){
            if(count == sum){
                res = c;
                break;
            }
        }
        return res;
    }
};

T2：子字符串的最优划分
给你一个字符串 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时，就清空该哈希表，然后进行下一次计数。

class Solution {
public:
    int partitionString(string s) {
        int res = 0;
        map<char,int>hash;
        for(int i = 0 ; i < s.size() ; i++){
            if(!hash.count(s[i])){
            hash[s[i]]++;
            }
            else{
                hash.clear();
                res++;
                hash[s[i]]++;
            }
        }
        
        return res+1;
    }
};

T3：将区间分为最少组数
给你一个二维整数数组 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，结束位置-1，这样就可以得到一个类似下图粉色数字的数组（未标记位置为0），对这个数组求前缀和就可以知道每个位置区间的个数。这样我们找到某一位置区间重合的最大个数就好了。

在这里插入图片描述

class Solution {
public:
    const int N = 1e6+10;
    int minGroups(vector<vector<int>>& intervals) {
        int res = 0 ;
        vector<int>a(N);
        for(auto c : intervals){
            a[c[0]]++;
            a[c[1]+1]--;
        }
        vector<int>pre(N);
        pre[0] = a[0];
        for(int i = 1; i < a.size();i++){
            pre[i] = pre[i-1] + a[i];
            res = max(res,pre[i]);
        }
        return res;
    }
};