力扣周赛310场题解
- 前言
- 6176. 出现最频繁的偶数元素
- 6177. 子字符串的最优划分
前言 今天参加了力扣的第310场周赛,也是感觉到了这周的题的一个难度,有些题有想法,但是实际上让我去写的时候还是不知道该怎么下手,这周也算是对算法练习的一个总结吧,确实,赛场时间段内没AC出来一道,但是当下午自己再做的时候,很容易就AC了两道,剩下两道也是有点难度,正在研究,那今天就先分享两道吧,加油!
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
解释:不存在偶数元素。
【刷题记录|力扣周赛310场题解】提示:
1 <= nums.length <= 2000
0 <= nums[i] <= 105
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/most-frequent-even-element
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解法:排序 + HashMap
排序,使数组有序,就算出现相同次数的偶数,返回的也是前面的,只需要比较出现的次数,如果相同就返回最小的即可。
使用Map来记录偶数出现的次数,同时也可以过滤奇数。最后筛选只需要使用map中的元素即可。
class Solution {
public int mostFrequentEven(int[] nums) {
Arrays.sort(nums);
// 排序
Map map = new HashMap<>();
for(int i : nums) {
if(i % 2 == 0) {// 过滤掉所有奇数
map.put(i, map.getOrDefault(i, 0) + 1);
}
}
int res = -1,max = Integer.MIN_VALUE;
for (Integer key : map.keySet()) {
int value = https://www.it610.com/article/map.get(key);
if (value> max) {
// 如果出现次数大于前一个出现的次数
// 更新记录
max = value;
res = key;
} else if (value =https://www.it610.com/article/= max) {
// 如果出现次数相等,那么取最小的元素
res = Math.min(res,key);
}
}
return 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 仅由小写英文字母组成
解法一:Set集合 + 一次遍历
我们可以使用Set集合来决定一个子串是否含有重复的字符。
class Solution {
public int partitionString(String s) {
char[] chars = s.toCharArray();
Set set = new HashSet<>();
// 这里初始化为1是因为,如果最后一次没有重复的字符的话
// 不会执行if里面的逻辑
int count = 1;
for(int i = 0;
i < chars.length;
i++) {
// 如果添加失败,说明重复
if(!set.add(chars[i])) {
// 清空set集合
set.clear();
// 将当前字符加入set集合
set.add(chars[i]);
// 次数 + 1
count++;
}
}
return count;
}
}
推荐阅读
- Leetcode|Leetcode989: 数组形式的整数加法 (简单题)python3
- 补题大全|2021CCPC网络赛题解加总结
- 算法|字节跳动VQScore算法拿下ICME 2021“压缩UGC视频质量评估”比赛第一名
- #|基于改进的蚂蚁群算法求解最短路径问题、二次分配问题、背包问题【Matlab&Python代码实现】
- #|基于粒子群算法的电力系统无功优化研究(IEEE14节点)(Matlab代码实现)
- 20_表达式引擎|【java表达式引擎】四、高性能、轻量级的AviatorScript
- 算法|计算建模之EM算法
- python|典型相关分析(CCA)及其python实现
- 数据结构与算法|数据结构学习笔记 6-1 手撕AVL树 与 LeetCode真题(Java)