- 前言
- 一、题目一
- 1.题目描述
- 2.解题思路
- 3.代码详解
- 二、题目二
- 1.题目描述
- 2.解题思路
- 3.代码详解
- 三、题目三
- 1.题目描述
- 2.解题思路
- 3.代码详解
- 四、题目四
- 1.题目描述
- 2.解题思路
- 3.代码详解
- 五、星球推荐
前言
刷题坚持每一天，以下题目引用自：力扣（LeetCode）
原题链接：1984. 学生分数的最小差值
给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。
从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。
返回可能的 最小差值 。
2.解题思路示例 1：
输入：nums = [90], k = 1
输出：0
解释：选出 1 名学生的分数，仅有 1 种方法：
[90] 最高分和最低分之间的差值是 90 - 90 = 0
可能的最小差值是 0
3.代码详解思路：
先排序，循环计算窗口内的最大值与最小值的差，比较得出最小差。
int cmp(const void* q1, const void* q2){
return *(int*)q1 - *(int*)q2;
}
int minimumDifference(int* nums, int numsSize, int k){
if(numsSize == 1) return 0;
qsort(nums, numsSize, sizeof(int), cmp);
int ans = 100001;
for(int i = 0; i <= numsSize-k; ++i){
int ret = nums[i+k-1] - nums[i];
ans = ans > ret ? ret : ans;
}
return ans;
}
二、题目二 1.题目描述
原题链接：1763. 最长的美好子字符串
当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，“abABB” 是美好字符串，因为 ‘A’ 和 ‘a’ 同时出现了，且 ‘B’ 和 ‘b’ 也同时出现了。然而，“abA” 不是美好字符串因为 ‘b’ 出现了，而 ‘B’ 没有出现。
给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。
2.解题思路示例 1：
输入：s = “YazaAay”
输出：“aAa”
解释：“aAa” 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 ‘a’ 和大写形式 ‘A’ 也同时出现了。
“aAa” 是最长的美好子字符串。
3.代码详解思路：
利用窗口枚举每一个子串，判断子串是否为漂亮串。
bool isBeautifulString(char* str ,int size) {
int hash[58] = {0};
for (int i = 0; i < size; ++i){
++hash[str[i]-'A'];
}
for (int i = 0; i < size; ++i) {
if (str[i] >= 'a'){
if(hash[str[i]-'A'-32] == 0){
return false;
}
}
else if(str[i] <= 'Z'){
if(hash[str[i]-'A'+32] == 0)
return false;
}
}
return true;
}
char * longestNiceSubstring(char * s){
int len = strlen(s);
if(len == 1) return "";
int i = 0, j = 0;
int max = 0;
char* sub = (char*)malloc(sizeof(char)*101);
int idx = 0;
for(i = 0; i < len; ++i){
idx = 0;
char ret[101];
for(j = i; j < len; ++j){
ret[idx++] = s[j];
if(idx >= 2){
ret[idx] = ' ';
if(isBeautifulString(ret, idx)){
if(idx > max){
max = idx;
strcpy(sub, ret);
}
}
}
}
}
return max == 0 ? "" : sub;
}
三、题目三 1.题目描述
原题链接：2269. 找到一个数字的 K 美丽值
一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目：
- 子字符串长度为 k 。
- 子字符串能整除 num 。
给你整数 num 和 k ，请你返回 num 的 k 美丽值。
注意：
- 允许有 前缀 0 。
- 0 不能整除任何值。
一个 子字符串 是一个字符串里的连续一段字符序列。
2.解题思路示例 1：
输入：num = 240, k = 2
输出：2
解释：以下是 num 里长度为 k 的子字符串：
“240” 中的 “24” ：24 能整除 240 。
“240” 中的 “40” ：40 能整除 240 。
所以，k 美丽值为 2 。
3.代码详解思路：
先把数字转字符串，把窗口长度的字符转数字，进行取余判断是否能整除。
int divisorSubstrings(int num, int k){
char str[11];
sprintf(str, "%d", num);
int len = strlen(str);
int ans = 0;
for(int i = 0; i+k-1 < len; ++i){
char bu[k+1];
strncpy(bu, str+i, k);
bu[k] = ' ';
if(atoi(bu) != 0 && !(num % atoi(bu)))
++ans;
}
return ans;
}
四、题目四 1.题目描述
原题链接：995. K 连续位的最小翻转次数
给定一个二进制数组 nums 和一个整数 k 。
k位翻转 就是从 nums 中选择一个长度为 k 的 子数组 ，同时把子数组中的每一个 0 都改成 1 ，把子数组中的每一个 1 都改成 0 。
返回数组中不存在 0 所需的最小 k位翻转 次数。如果不可能，则返回 -1 。
子数组 是数组的 连续 部分。
2.解题思路示例 1：
输入：nums = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
3.代码详解思路：
参考官解，什么是差分数组。
用rev记录翻转次数，1翻转奇数次为0，0翻转偶数次为0，这两种情况都需要再次翻转。
int minKBitFlips(int* nums, int numsSize, int K) {
int diff[numsSize + 1];
memset(diff, 0, sizeof(diff));
int ans = 0, rev = 0;
for (int i = 0; i < numsSize; ++i) {
rev += diff[i];
if (((nums[i] + rev) & 1) == 0) {
if (i + K > numsSize) {
return -1;
}
++ans;
++rev;
--diff[i + K];
}
}
return ans;
}
五、星球推荐
星球链接：英雄算法联盟
星球里有什么?
【朋友圈】一个极致精准的自律、编程、算法的小圈子。
【算法集训】以月为单位组织算法集训，每天四题，风雨无阻。
【排行榜】每天、每周都会有榜单，激励大家不断进步，不断成长。
【个人规划】每个人都写好自己的规划，也可以查看他人的规划，时刻警醒自己不掉队。
【打卡挑战】每日一题打卡、每日早起打卡、算法集训打卡、规划完成情况打卡。
在星球里做什么?
目前星球人数达到520+，在星球里你能够遇到一群志同道合之人，因为都是花钱进来的，你不会看到任何浑水摸鱼的人，每个人都有自己的每月规划，星主每月都会组织算法集训，每天一起刷题，你可以看到别人的解题报告，取其之长，补己之短。
