《五月集训》第六天——滑动窗口
目录
- —、第一题
-
- 1. 原题链接
- 2. 解题思路
- 3. 代码
- 二、第二题
-
- 1. 原题链接
- 2. 解题思路
- 3. 代码
- 三、第三题
-
- 1. 原题链接
- 2. 解题思路
- 3. 代码
- 四、第四题
-
- 1. 原题链接
- 2. 解题思路
- 3. 代码
- 五、星球推荐
坚持每一天,提升自己。大家一块加油!!!
—、第一题
1. 原题链接
原题链接:1984. 学生分数的最小差值
给你一个 下标从 0 开始 的整数数组 nums ,其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数,使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。
2. 解题思路
排序+滑动窗口,先进行排序,后根据滑动窗口里最大和最小值,得到差值与上次差值进行比较取小。
3. 代码
int cmp(const void* q1, const void* q2){ return *(int*)q1 - *(int*)q2;}int minimumDifference(int* nums, int numsSize, int k){ qsort(nums, numsSize, sizeof(int), cmp); int i, j; int min = 100001; for(i = 0; i + k-1 < numsSize; ++i){if(nums[i + k-1] - nums[i] < min){ min = nums[i + k-1] - nums[i];} } return min;}
二、第二题
1. 原题链接
原题链接:1876. 长度为三且各字符不同的子字符串
如果一个字符串不含有任何重复字符,我们称这个字符串为 好 字符串。
给你一个字符串 s ,请你返回 s 中长度为 3 的 好子字符串 的数量。
注意,如果相同的好子字符串出现多次,每一次都应该被记入答案之中。
子字符串 是一个字符串中连续的字符序列。
2. 解题思路
循环这个固定的滑动窗口,当窗口里三个字符互不相同时,计数加一。
3. 代码
int countGoodSubstrings(char * s){ int len = strlen(s); int i; int flag = 0; for(i = 0; i < len-2; ++i){if(s[i] != s[i+1] && s[i] != s[i+2] && s[i+1] != s[i+2]) ++flag; } return flag;}
三、第三题
1. 原题链接
原题链接:1839. 所有元音按顺序排布的最长子字符串
当一个字符串满足如下条件时,我们称它是 美丽的 :
所有 5 个英文元音字母(‘a’ ,‘e’ ,‘i’ ,‘o’ ,‘u’)都必须 至少 出现一次。
这些元音字母的顺序都必须按照 字典序 升序排布(也就是说所有的 ‘a’ 都在 ‘e’ 前面,所有的 ‘e’ 都在 ‘i’ 前面,以此类推)
比方说,字符串 “aeiou” 和 “aaaaaaeiiiioou” 都是 美丽的 ,但是 “uaeio” ,“aeoiu” 和 “aaaeeeooo” 不是美丽的 。
给你一个只包含英文元音字母的字符串 word ,请你返回 word 中 最长美丽子字符串的长度 。如果不存在这样的子字符串,请返回 0 。
子字符串 是字符串中一个连续的字符序列。
2. 解题思路
遍历word
,以相邻两个元音字符为满足条件进行计数,来统计最长的美丽字符串。
3. 代码
int longestBeautifulSubstring(char * word){ char wel[6] = "aeiou"; int flag = 0; int i; int max = 0, count = 0; for(i = 0; word[i] != '\0'; ++i){if(word[i] == wel[flag] || word[i] == wel[flag+1]){ if(count == 0 && word[i] == wel[1]) continue; // (1) if(word[i] == wel[flag+1] && flag < 4) ++flag; // (2) ++count; if(count > max && count >= 5 && flag == 4) max = count;}else { flag = 0; if(word[i] == 'a') count = 1; else count = 0;} } return max;}
- (1) 防止第一个字符不为
a
。 - (2) 元音字符窗口进行移动。
四、第四题
1. 原题链接
原题链接:1052. 爱生气的书店老板
有一个书店老板,他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ,其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量,所有这些顾客在第 i 分钟结束后离开。
在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。
当书店老板生气时,那一分钟的顾客就会不满意,若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 minutes 分钟不生气,但却只能使用一次。
请你返回 这一天营业下来,最多有多少客户能够感到满意 。
2. 解题思路
先统计i
时间不生气的总人数,在根据连续minutes
分钟不生气做滑动窗口,统计连续minutes
分钟不生气最大的人数。返回不生气的总人数+
连续minutes
分钟不生气最大的人数。
3. 代码
#define max(a, b) ((a) > (b) ? (a) : (b))int maxSatisfied(int* customers, int customersSize, int* grumpy, int grumpySize, int minutes){ int i; int angry = 0; int conti = 0; int win = 0; for(i = 0; i < grumpySize; ++i){if(grumpy[i] == 0) angry += customers[i]; } for(i = 0; i < grumpySize; ++i){if(i < minutes){ conti += customers[i] * grumpy[i]; win = conti;}else{ conti += customers[i] * grumpy[i] - customers[i-minutes] * grumpy[i-minutes]; win = max(win, conti);} } return angry+win;}
五、星球推荐
星球链接:英雄算法联盟
星球里有什么?
【朋友圈】一个极致精准的自律、编程、算法的小圈子。
【算法集训】以月为单位组织算法集训,每天四题,风雨无阻。
【排行榜】每天、每周都会有榜单,激励大家不断进步,不断成长。
【个人规划】每个人都写好自己的规划,也可以查看他人的规划,时刻警醒自己不掉队。
【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
目前星球人数达到310+,在星球里你能够遇到一群志同道合之人,因为都是花钱进来的,你不会看到任何浑水摸鱼的人,每个人都有自己的每月规划,星主每月都会组织算法集训,每天一起刷题,你可以看到别人的解题报告,取其之长,补己之短。