文章目錄
- 前言
- 第86場雙周賽情況
- 題目複盤+題解
- 題1：6176. 出現最頻繁的偶數元素【easy】
- 題2：6176. 出現最頻繁的偶數元素【medium】
- 題3：6178. 将區間分為最少組數【medium】
- 題4：6206. 最長遞增子序列 II【hard，暫未ac】
前言
之後會參與leetcode周賽、雙周賽，希望自己能夠堅持下來，并以此來督促檢驗、提升自己的算法能力，加油！
第86場雙周賽情況
位址：第310場周賽
戰績：
第三題案例逾時了：
最後的情況：
目前競賽分數：
題目複盤+題解
題1：6176. 出現最頻繁的偶數元素【easy】
題目連結：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、哈希表+一遍周遊
複雜度分析：時間複雜度O(n)；空間複雜度O(n)
class Solution {
public int mostFrequentEven(int[] nums) {
int max = -1;
int res = -1;
Map<Integer, Integer> map = new HashMap<>();
for (int num: nums) {
//偶數
if ((num & 1) == 0) {
int val = map.getOrDefault(num, 0) + 1;
map.put(num, val);
if (val == max && num < res) {
res = num;
}
if (val > max) {
max = val;
res = num;
}
}
}
return res;
}
} 題2：6176. 出現最頻繁的偶數元素【medium】
題目連結：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、滑動視窗+哈希表
複雜度分析：時間複雜度O(n)；空間複雜度O(1)
class Solution {
public int partitionString(String s) {
char[] arr = s.toCharArray();
int[] tb = new int[26];
int res = 0;
for (int l = 0, r = 0; r < arr.length; r++) {
if (tb[arr[r] - 'a'] == 1) {
res++;
//清理工作
while (l < r) {
tb[arr[l] - 'a'] = 0;
l++;
}
//此時l == r
}
tb[arr[r] - 'a']++;
}
return res + 1;
}
} 題3：6178. 将區間分為最少組數【medium】
題目連結：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、暴力法【逾時，當時就卡住了】
複雜度分析：時間複雜度O(n2)；空間複雜度O(n)
public int minGroups(int[][] intervals) {
Arrays.sort(intervals, (o1, o2)->o1[0] - o2[0]);
boolean[] visited = new boolean[intervals.length];
int res = 0;
for (int i = 0; i < intervals.length; i++) {
if (visited[i]) continue;
int[] interval = intervals[i];
for (int j = i + 1; j < intervals.length; j++) {
if (intervals[j][0] > interval[1] && !visited[j]) {
visited[j] = true;
interval = intervals[j];
}
}
res++;
}
return res;
} 2、小根堆+排序
複雜度分析：時間複雜度O(nlogn)；空間複雜度O(n)；
class Solution {
//排序+小根堆
public int minGroups(int[][] intervals) {
//排序
Arrays.sort(intervals, (o1, o2)->o1[0] - o2[0]);
//小根堆（儲存right的值）
PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int[] arr: intervals) {
if (!queue.isEmpty()) {
//若是時間比最小的久那麼就移除最小的，加入最新的實作一個替換
if (arr[0] > queue.peek()) {
queue.poll();
}
}
queue.offer(arr[1]);
}
return queue.size();
}
} 複盤：當時根據開始時間排序是想到的，但是對應小根堆的一個貪心應用這個方式還是第一次碰到。
題4：6206. 最長遞增子序列 II【hard，暫未ac】
題目連結：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 思路：①線段樹。②樹狀數組。