1. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1:
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2:
输入：nums = [2,0,1]
输出：[0,1,2]
我的解法（哈希）
class Solution {
public void sortColors(int[] nums) {
// 记录每个元素的个数
Map<Integer,Integer> map = new HashMap<>();
for(int num : nums){
map.put(num, map.getOrDefault(num, 0) + 1);
}
int zero = map.getOrDefault(0, 0);
int one = map.getOrDefault(1, 0);
int two = map.getOrDefault(2, 0);
for(int i = 0; i < zero; ++i) nums[i] = 0;
for(int i = zero; i < zero + one; ++i) nums[i] = 1;
for(int i = zero + one; i < zero + one + two; ++i) nums[i] = 2;
}
}
2. 分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
我的解法（贪心）
class Solution {
public int findContentChildren(int[] g, int[] s) {
/**
* 贪心
* 尽量让大饼干满足胃口大的孩子，避免浪费饼干尺寸
*/
Arrays.sort(g);
Arrays.sort(s);
int index = s.length - 1;
int res = 0;
for(int i = g.length - 1; i >= 0; i--){
if(index >= 0 && g[i] <= s[index]){
index--;
res++;
}
}
return res;
}
}
3. 摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例 1:
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例 2:
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例 3:
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2
我的解法（贪心）
class Solution {
public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if(n < 2) return n;
int res = 0;
int pre = nums[1] - nums[0];
res = pre == 0 ? 1 : 2;
for(int i = 2; i < n; ++i){
int temp = nums[i] - nums[i - 1];
if((pre <= 0 && temp > 0) || (pre >= 0 && temp < 0)){
res++;
pre = temp;
}
}
return res;
}
}
这道题最好画个图，而且不要过分在乎细节，不然很难受。因为这道题本质上其实是求发生变化的次数。
4. 任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。
然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。
你需要计算完成所有任务所需要的 最短时间 。
输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。
示例 2:
输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
示例 3:文章来源：https://www.toymoban.com/news/detail-440512.html
输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
我的解法（贪心）文章来源地址https://www.toymoban.com/news/detail-440512.html
class Solution {
public int leastInterval(char[] tasks, int n) {
/**
1. 将任务按照类型分组，A-Z正好可以用一个数组int[26]保存每个类型的数量
2. 对数组进行排序（升序），得到数量最大任务数量为 maxCount
那根据规则可知，至少要花费的时间为 (maxCount - 1) * (n + 1) + 1
例如数量最大的为任务A=3,间隔n=2，所以执行完任务A至少需要：
time = A-X-X-A-X-X-A (X标识冷冻间隔，不能为A)
3. 继续下一个任务，因为任务A是数量最大的，所以下一个任务要么等于要么小于
a. 任务B数量等于任务A time++ = A-B-X-A-B-X-A-B
b. 任务B数量小于任务A (为 2) time = A-B-X-A-B-X-A
4. 但是我们需要考虑一种特殊情况
A-B-C-A-B-c-A
这时候任务空白间隔(X)已经插满了，如果还有任务要怎么处理
假设后面还有 D D E E F F G G
如下：
A-B-C-D-E-F-G-A-B-C-D-E-F-G-A
其实后面的任务不管还有多少，至少有一个限制，每个类型的任务数量不会超过A
也就是说:
A-B-C-A-B-C-A
在每一个完整间隔（A-B-C）后面插入都不会出现冷冻消耗，因为每个完整间隔之间
间隔任务数都大于 n
所以最后的时间 Math.max(time, task.length)
*/
if (tasks.length <= 1 || n < 1) return tasks.length;
int[] counts = new int[26];
for(int i = 0; i < tasks.length; ++i){
counts[tasks[i] - 'A']++;
}
Arrays.sort(counts);
int maxCount = counts[25];
int time = (maxCount - 1) * (n + 1) + 1;
int i = 24;
while(i >= 0 && counts[i] == maxCount){
time++;
i--;
}
return Math.max(time, tasks.length);
}
}
到了这里，关于算法练习随记（七）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
