算法日常刷题笔记（3）

为保持刷题的习惯计划一天刷3-5题然后一周总计汇总一下这是第三篇笔记笔记时间为2月24日到3月2日

第一天

设计有序流

设计有序流https://leetcode.cn/problems/design-an-ordered-stream/

有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流，以任意顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。

实现 OrderedStream 类：

OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。

否则，返回一个空列表。

#include <vector>
#include <string>using namespace std;class OrderedStream {
private:vector<string> stream;int ptr;public:OrderedStream(int n) {// 初始化一个大小为 n + 1 的向量，用于存储 (id, value) 对，索引从 1 开始stream.resize(n + 1);// 将当前指针 ptr 设为 1ptr = 1;}vector<string> insert(int idKey, string value) {// 将 value 存储到 stream 中对应的 idKey 位置stream[idKey] = value;vector<string> result;// 检查当前指针 ptr 位置是否有值while (ptr < stream.size() && !stream[ptr].empty()) {// 如果有值，将该值添加到结果列表中result.push_back(stream[ptr]);// 指针向后移动一位ptr++;}return result;}
};

可以形成最大正方形的矩形数目

可以形成最大正方形的矩形数目https://leetcode.cn/problems/number-of-rectangles-that-can-form-the-largest-square/

给你一个数组 rectangles ，其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。

如果存在 k 同时满足 k <= li 和 k <= wi ，就可以将第 i 个矩形切成边长为 k 的正方形。例如，矩形 [4,6] 可以切成边长最大为 4 的正方形。

设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。

请你统计有多少个矩形能够切出边长为 maxLen 的正方形，并返回矩形数目。

int countGoodRectangles(int** rectangles, int rectanglesSize, int* rectanglesColSize) {int nums = 0;int max = 0;for(int i = 0;i < rectanglesSize;i ++){int k = rectangles[i][0] < rectangles[i][1] ? rectangles[i][0] : rectangles[i][1];if(k > max){nums = 1;max = k;}else if(k == max){nums ++;}}return nums;
}

统计范围内的元音字符串数

统计范围内的元音字符串数https://leetcode.cn/problems/count-vowel-strings-in-ranges/

给你一个下标从 0 开始的字符串数组 words 以及一个二维整数数组 queries 。

每个查询 queries[i] = [li, ri] 会要求我们统计在 words 中下标在 li 到 ri 范围内（包含这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i 个元素对应第 i 个查询的答案。

注意：元音字母是 'a'、'e'、'i'、'o' 和 'u' 。

/*** Note: The returned array must be malloced, assume caller calls free().*/bool isA(char n){if(n == 'a' ||n == 'e' ||n == 'i' ||n == 'o' ||n == 'u'){return true;}else{return false;}}
int* vowelStrings(char** words, int wordsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {int* ans = (int*)malloc(sizeof(int)*queriesSize);*returnSize = queriesSize;int arr[wordsSize];arr[0] = isA(words[0][0]) && isA(words[0][strlen(words[0]) - 1]) ? 1 : 0;for(int i = 1; i < wordsSize;i ++){int length =  strlen(words[i]);arr[i] = arr[i - 1]; if(isA(words[i][0]) && isA(words[i][length - 1])){arr[i] ++; }}for(int i = 0;i < queriesSize; i++){ans[i] = (arr[queries[i][1]] - arr[queries[i][0]]);if(isA(words[queries[i][0]][0]) && isA(words[queries[i][0]][strlen(words[queries[i][0]]) - 1])){ans[i] ++; }}return ans;
}

第二天

设计内存分配器

设计内存分配器https://leetcode.cn/problems/design-memory-allocator/

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

分配一块大小为 size 的连续空闲内存单元并赋 id mID 。
释放给定 id mID 对应的所有内存单元。

注意：

多个块可以被分配到同一个 mID 。
你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
int freeMemory(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

// 定义 Allocator 结构体，包含一个整数数组表示内存，以及数组的大小
typedef struct {int *memory;int size;
} Allocator;// 创建一个 Allocator 实例，初始化内存数组
Allocator* allocatorCreate(int n) {// 分配 Allocator 结构体的内存Allocator *obj = (Allocator *)malloc(sizeof(Allocator));if (obj == NULL) {return NULL;}// 分配内存数组的内存，并将其初始化为 0，表示所有内存单元初始都是空闲的obj->memory = (int *)calloc(n, sizeof(int));if (obj->memory == NULL) {free(obj);return NULL;}// 记录内存数组的大小obj->size = n;return obj;
}// 分配指定大小的连续空闲内存单元，并标记为指定的 mID
int allocatorAllocate(Allocator* obj, int size, int mID) {int consecutiveFree = 0;// 遍历内存数组，查找连续的空闲内存单元for (int i = 0; i < obj->size; i++) {if (obj->memory[i] == 0) {consecutiveFree++;// 当找到连续的空闲内存单元数量达到所需大小时if (consecutiveFree == size) {int startIndex = i - size + 1;// 将这些连续的空闲内存单元标记为 mIDfor (int j = startIndex; j <= i; j++) {obj->memory[j] = mID;}return startIndex;}} else {// 如果遇到已分配的内存单元，连续空闲计数重置为 0consecutiveFree = 0;}}// 没有找到足够的连续空闲内存单元，返回 -1return -1;
}// 释放指定 mID 对应的所有内存单元
int allocatorFreeMemory(Allocator* obj, int mID) {int freedCount = 0;// 遍历内存数组，查找所有标记为 mID 的内存单元for (int i = 0; i < obj->size; i++) {if (obj->memory[i] == mID) {// 将标记为 mID 的内存单元重置为 0，表示空闲obj->memory[i] = 0;freedCount++;}}return freedCount;
}// 释放 Allocator 实例占用的内存
void allocatorFree(Allocator* obj) {// 先释放内存数组的内存free(obj->memory);// 再释放 Allocator 结构体的内存free(obj);
}/*** Your Allocator struct will be instantiated and called as such:* Allocator* obj = allocatorCreate(n);* int param_1 = allocatorAllocate(obj, size, mID);* int param_2 = allocatorFreeMemory(obj, mID);* allocatorFree(obj);
*/

有多少小于当前数字的数字

有多少小于当前数字的数字https://leetcode.cn/problems/how-many-numbers-are-smaller-than-the-current-number/

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

/*** Note: The returned array must be malloced, assume caller calls free().*/
int comp(const void * a,const void * b){return *(int *) a - *(int *) b;
}int* smallerNumbersThanCurrent(int* nums, int numsSize, int* returnSize) {int arr[numsSize];int* ans = (int *)malloc(sizeof(int) * numsSize);*returnSize = numsSize;for(int i = 0;i < numsSize;i++){arr[i] = nums[i];}qsort(arr,numsSize,sizeof(int),comp);for(int i = 0;i < numsSize;i++){for(int j = 0;j < numsSize;j++){if(nums[i] == arr[j]){ans[i] = j;break;}}}return ans;}

最少的后缀翻转次数

最少的后缀翻转次数https://leetcode.cn/problems/minimum-suffix-flips/

给你一个长度为 n 、下标从 0 开始的二进制字符串 target 。你自己有另一个长度为 n 的二进制字符串 s ，最初每一位上都是 0 。你想要让 s 和 target 相等。

在一步操作，你可以选择下标 i（0 <= i < n）并翻转在 闭区间 [i, n - 1] 内的所有位。翻转意味着 '0' 变为 '1' ，而 '1' 变为 '0' 。

返回使 s 与 target 相等需要的最少翻转次数。

int minFlips(char* target) {int length = strlen(target);int ans = 0;for(int i = 0;i < length;i++){if(target[i] != target[i + 1] || target[i + 1] == '\0'){ans ++;}}if(target[0] == '0'){ans --;}return ans;
}

完成所有任务需要的最少的轮数

完成所有任务需要的最少轮数https://leetcode.cn/problems/minimum-rounds-to-complete-all-tasks/

给你一个下标从 0 开始的整数数组 tasks ，其中 tasks[i] 表示任务的难度级别。在每一轮中，你可以完成 2 个或者 3 个 相同难度级别 的任务。

返回完成所有任务需要的最少轮数，如果无法完成所有任务，返回 -1 。

// 比较函数，用于 qsort 排序
int comp(const void * a, const void * b) {return *(int *) a - *(int *) b;
}int minimumRounds(int* tasks, int tasksSize) {int ans = 0;// 对任务数组进行排序qsort(tasks, tasksSize, sizeof(int), comp);for (int i = 0; i < tasksSize; ) {int j = i + 1;// 统计相同难度任务的数量while (j < tasksSize && tasks[j] == tasks[i]) {j++;}int number = j - i;// 如果相同难度任务的数量为 1，无法完成任务，返回 -1if (number == 1) {return -1;}// 计算完成这些任务所需的最少轮数ans += (number + 2) / 3;// 更新 i 的值，继续处理下一组相同难度的任务i = j;}return ans;
}

第三天

设计浏览器历史记录

设计浏览器历史记录https://leetcode.cn/problems/design-browser-history/

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
void visit(string url) 从当前页跳转访问 url 对应的页面。执行此操作会把浏览历史前进的记录全部删除。
string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退至多 steps 步以后的 url 。
string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进至多 steps步以后的 url 。

#define MAX_HISTORY_SIZE 5000typedef struct {char history[MAX_HISTORY_SIZE][201];  // 假设每个 URL 最长为 200 个字符int current;  // 当前所在的历史记录位置int size;     // 历史记录的大小
} BrowserHistory;// 创建浏览器历史记录对象
BrowserHistory* browserHistoryCreate(char* homepage) {BrowserHistory* obj = (BrowserHistory*)malloc(sizeof(BrowserHistory));strcpy(obj->history[0], homepage);obj->current = 0;obj->size = 1;return obj;
}// 访问新页面
void browserHistoryVisit(BrowserHistory* obj, char* url) {// 清除当前位置之后的历史记录obj->current++;strcpy(obj->history[obj->current], url);obj->size = obj->current + 1;
}// 后退操作
char* browserHistoryBack(BrowserHistory* obj, int steps) {if (obj->current - steps < 0) {obj->current = 0;} else {obj->current -= steps;}return obj->history[obj->current];
}// 前进操作
char* browserHistoryForward(BrowserHistory* obj, int steps) {if (obj->current + steps >= obj->size) {obj->current = obj->size - 1;} else {obj->current += steps;}return obj->history[obj->current];
}// 释放浏览器历史记录对象
void browserHistoryFree(BrowserHistory* obj) {free(obj);
}/*** Your BrowserHistory struct will be instantiated and called as such:* BrowserHistory* obj = browserHistoryCreate(homepage);* browserHistoryVisit(obj, url);* char* param_2 = browserHistoryBack(obj, steps);* char* param_3 = browserHistoryForward(obj, steps);* browserHistoryFree(obj);
*/

统计特殊字母的数量

统计特殊字母的数量 Ihttps://leetcode.cn/problems/count-the-number-of-special-characters-i/

给你一个字符串 word。如果 word 中同时存在某个字母的小写形式和大写形式，则称这个字母为 特殊字母 。

返回 word 中 特殊字母 的数量。

int numberOfSpecialChars(char* word) {int number = 0;int arr[26][2];memset(arr,0,sizeof(int)*26);for(int i = 0;i < strlen(word);i ++){char a =  word[i];if(a - 'a' >= 0){arr[a - 'a'][0] ++;}else{arr[a - 'A'][1] ++;}}for(int i = 0;i < 26;i ++){if(arr[i][0] > 0 && arr[i][1] > 0){number ++;}}return number;}

千位分隔数

千位分隔数https://leetcode.cn/problems/thousand-separator/

给你一个整数 n，请你每隔三位添加点（即 "." 符号）作为千位分隔符，并将结果以字符串格式返回。

char* thousandSeparator(int n) {// 先将整数转换为字符串char num_str[20];sprintf(num_str, "%d", n);int len = strlen(num_str);// 计算结果字符串的长度int result_len = len + (len - 1) / 3;char *result = (char *)malloc((result_len + 1) * sizeof(char));if (result == NULL) {return NULL;}int j = result_len - 1;int count = 0;// 从原字符串的末尾开始遍历for (int i = len - 1; i >= 0; i--) {result[j--] = num_str[i];count++;// 每三位添加一个点if (count % 3 == 0 && i > 0) {result[j--] = '.';}}result[result_len] = '\0';return result;}

按奇偶数排序数组

按奇偶排序数组https://leetcode.cn/problems/sort-array-by-parity/

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

/*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortArrayByParity(int* nums, int numsSize, int* returnSize) {int* ans = (int*)malloc(sizeof(int) * numsSize);*returnSize = numsSize;int n = 0,m = 0;int arr[numsSize];for(int i = 0;i < numsSize;i++){if(nums[i] % 2 ==0){ans[n ++] = nums[i];}else{arr[m ++] = nums[i];}} for(int i = 0;i < m;i ++){ans[n + i] = arr[i];}return ans;}

第四天

给定数字能组成的最大时间

给定数字能组成的最大时间https://leetcode.cn/problems/largest-time-for-given-digits/

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。

24 小时格式为 "HH:MM" ，其中 HH 在 00 到 23 之间，MM 在 00 到 59 之间。最小的 24 小时制时间是 00:00 ，而最大的是 23:59 。从 00:00 （午夜）开始算起，过得越久，时间越大。

以长度为 5 的字符串，按 "HH:MM" 格式返回答案。如果不能确定有效时间，则返回空字符串。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 比较函数，用于 qsort
int comp(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}// 交换两个整数的值
void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 生成下一个排列
int next_permutation(int *arr, int n) {int i = n - 2;while (i >= 0 && arr[i] >= arr[i + 1]) {i--;}if (i < 0) {return 0;}int j = n - 1;while (arr[j] <= arr[i]) {j--;}swap(&arr[i], &arr[j]);int left = i + 1, right = n - 1;while (left < right) {swap(&arr[left], &arr[right]);left++;right--;}return 1;
}char* largestTimeFromDigits(int* arr, int arrSize) {char* ans = (char*)malloc(sizeof(char) * 6);ans[0] = '\0';int max_time = -1;// 对数组进行排序，方便生成全排列qsort(arr, arrSize, sizeof(int), comp);do {int hour = arr[0] * 10 + arr[1];int minute = arr[2] * 10 + arr[3];if (hour >= 0 && hour < 24 && minute >= 0 && minute < 60) {int current_time = hour * 60 + minute;if (current_time > max_time) {max_time = current_time;sprintf(ans, "%02d:%02d", hour, minute);}}} while (next_permutation(arr, arrSize));return ans;
}

负二进制转换

给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。

注意，除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

void reverseString(char *str) {int len = strlen(str);for (int i = 0; i < len / 2; i++) {char temp = str[i];str[i] = str[len - i - 1];str[len - i - 1] = temp;}
}char* baseNeg2(int n) {if (n == 0) {char *result = (char *)malloc(2 * sizeof(char));result[0] = '0';result[1] = '\0';return result;}char *result = (char *)malloc(32 * sizeof(char));  // 假设最大 32 位int index = 0;while (n != 0) {int remainder = n % -2;n /= -2;if (remainder < 0) {remainder += 2;n += 1;}result[index++] = remainder + '0';}result[index] = '\0';reverseString(result);return result;
}

设计Goal解析器

设计 Goal 解析器https://leetcode.cn/problems/goal-parser-interpretation/

请你设计一个可以解释字符串 command 的 Goal 解析器 。command 由 "G"、"()" 和/或 "(al)" 按某种顺序组成。Goal 解析器会将 "G" 解释为字符串 "G"、"()" 解释为字符串 "o" ，"(al)" 解释为字符串 "al" 。然后，按原顺序将经解释得到的字符串连接成一个字符串。

给你字符串 command ，返回 Goal 解析器 对 command 的解释结果。

char* interpret(char* command) {int len = strlen(command);// 因为每个 "()" 或 "(al)" 最多替换成 "o" 或 "al"，长度最多是原字符串的两倍char* ans = (char*)malloc((2 * len + 1) * sizeof(char));if (ans == NULL) {return NULL;}int ansIndex = 0;for (int i = 0; i < len; i++) {if (command[i] == 'G') {ans[ansIndex++] = 'G';} else if (command[i] == '(') {if (command[i + 1] == ')') {ans[ansIndex++] = 'o';i++;  // 跳过右括号} else if (command[i + 1] == 'a' && command[i + 2] == 'l' && command[i + 3] == ')') {ans[ansIndex++] = 'a';ans[ansIndex++] = 'l';i += 3;  // 跳过 "al)"}}}ans[ansIndex] = '\0';return ans;
}

第五天

设计食物评分系统

设计食物评分系统https://leetcode.cn/problems/design-a-food-rating-system/

设计一个支持下述操作的食物评分系统：

修改系统中列出的某种食物的评分。
返回系统中某一类烹饪方式下评分最高的食物。

实现 FoodRatings 类：

FoodRatings(String[] foods, String[] cuisines, int[] ratings) 初始化系统。食物由 foods、cuisines 和 ratings 描述，长度均为 n 。
foods[i] 是第 i 种食物的名字。
cuisines[i] 是第 i 种食物的烹饪方式。
ratings[i] 是第 i 种食物的最初评分。

void changeRating(String food, int newRating) 修改名字为 food 的食物的评分。
String highestRated(String cuisine) 返回指定烹饪方式 cuisine 下评分最高的食物的名字。如果存在并列，返回 字典序较小 的名字。

注意，字符串 x 的字典序比字符串 y 更小的前提是：x 在字典中出现的位置在 y 之前，也就是说，要么 x 是 y 的前缀，或者在满足 x[i] != y[i] 的第一个位置 i 处，x[i] 在字母表中出现的位置在 y[i] 之前。

暴力破解（未通过）

class FoodRatings {String[] foods;String[] cuisines;int[] ratings;public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {this.foods = foods;this.cuisines = cuisines;this.ratings = ratings;}public void changeRating(String food, int newRating) {for(int i = 0;i < foods.length;i ++){if(foods[i].equals(food)){ratings[i] = newRating;break;}}}public String highestRated(String cuisine) {int max = 0;for(int i = 0;i < cuisines.length;i ++){if(cuisines[i].equals(cuisine)){max = i;break;}}for(int i = 0;i < cuisines.length;i ++){if(cuisines[i].equals(cuisine)){if(ratings[max] < ratings[i]){max = i;}else if(ratings[max] == ratings[i]){if(foods[i].compareTo(foods[max]) < 0){max = i;}}}}return foods[max];}
}/*** Your FoodRatings object will be instantiated and called as such:* FoodRatings obj = new FoodRatings(foods, cuisines, ratings);* obj.changeRating(food,newRating);* String param_2 = obj.highestRated(cuisine);*/

优化解（哈希）

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;class FoodRatings {// 存储食物到评分的映射private Map<String, Integer> foodToRating;// 存储食物到菜系的映射private Map<String, String> foodToCuisine;// 存储菜系到该菜系下食物的 TreeSet 映射private Map<String, TreeSet<String>> cuisineToFoods;public FoodRatings(String[] foods, String[] cuisines, int[] ratings) {foodToRating = new HashMap<>();foodToCuisine = new HashMap<>();cuisineToFoods = new HashMap<>();for (int i = 0; i < foods.length; i++) {String food = foods[i];String cuisine = cuisines[i];int rating = ratings[i];// 存储食物到评分的映射foodToRating.put(food, rating);// 存储食物到菜系的映射foodToCuisine.put(food, cuisine);// 如果该菜系对应的 TreeSet 不存在，则创建一个新的 TreeSetcuisineToFoods.computeIfAbsent(cuisine, k -> new TreeSet<>((a, b) -> {int ratingA = foodToRating.get(a);int ratingB = foodToRating.get(b);// 先按评分降序排序if (ratingA != ratingB) {return ratingB - ratingA;}// 评分相同时按字典序升序排序return a.compareTo(b);}));// 将食物添加到该菜系对应的 TreeSet 中cuisineToFoods.get(cuisine).add(food);}}public void changeRating(String food, int newRating) {// 获取该食物所属的菜系String cuisine = foodToCuisine.get(food);// 从该菜系对应的 TreeSet 中移除该食物cuisineToFoods.get(cuisine).remove(food);// 更新该食物的评分foodToRating.put(food, newRating);// 将更新后的食物重新添加到该菜系对应的 TreeSet 中cuisineToFoods.get(cuisine).add(food);}public String highestRated(String cuisine) {// 获取该菜系对应的 TreeSetTreeSet<String> foodSet = cuisineToFoods.get(cuisine);if (foodSet == null || foodSet.isEmpty()) {return null;}// 返回该 TreeSet 中第一个元素，即评分最高且字典序最小的食物return foodSet.first();}
}

转变数组后最接近目标值的数组和

转变数组后最接近目标值的数组和https://leetcode.cn/problems/sum-of-mutated-array-closest-to-target/

给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近 target （最接近表示两者之差的绝对值最小）。

如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。

请注意，答案不一定是 arr 中的数字。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>// 计算将数组中所有大于 value 的值变成 value 后数组的和
int calculateSum(int* arr, int arrSize, int value) {int sum = 0;for (int i = 0; i < arrSize; i++) {if (arr[i] > value) {sum += value;} else {sum += arr[i];}}return sum;
}// 找到数组中的最大值
int findMax(int* arr, int arrSize) {int max = arr[0];for (int i = 1; i < arrSize; i++) {if (arr[i] > max) {max = arr[i];}}return max;
}int findBestValue(int* arr, int arrSize, int target) {int left = 0;int right = findMax(arr, arrSize);int bestValue = 0;int minDiff = target;  // 初始化最小差值为 targetwhile (left <= right) {int mid = left + (right - left) / 2;int sum = calculateSum(arr, arrSize, mid);int diff = abs(sum - target);if (diff < minDiff || (diff == minDiff && mid < bestValue)) {minDiff = diff;bestValue = mid;}if (sum < target) {left = mid + 1;} else {right = mid - 1;}}return bestValue;
}

计算列车到站时间

计算列车到站时间https://leetcode.cn/problems/calculate-delayed-arrival-time/

给你一个正整数 arrivalTime 表示列车正点到站的时间（单位：小时），另给你一个正整数 delayedTime 表示列车延误的小时数。

返回列车实际到站的时间。

注意，该问题中的时间采用 24 小时制。

int findDelayedArrivalTime(int arrivalTime, int delayedTime) {return (arrivalTime + delayedTime) % 24;
}

特殊数组

特殊数组 Ihttps://leetcode.cn/problems/special-array-i/

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组。换句话说，每一对中的元素必须有一个是偶数，另一个是奇数。

你有一个整数数组 nums。如果 nums 是一个 特殊数组 ，返回 true，否则返回 false。

bool isArraySpecial(int* nums, int numsSize) {if(numsSize == 1){return true;}for(int i = 0;i < numsSize - 1;i ++){if((nums[i] + nums[i + 1]) % 2 != 1){return false;}}return true;
}

第六天

回文质数

回文质数https://leetcode.cn/problems/prime-palindrome/

给你一个整数 n ，返回大于或等于 n 的最小 回文质数。

一个整数如果恰好有两个除数：1 和它本身，那么它是质数。注意，1 不是质数。

例如，2、3、5、7、11 和 13 都是质数。

一个整数如果从左向右读和从右向左读是相同的，那么它是 回文数 。

例如，101 和 12321 都是回文数。

测试用例保证答案总是存在，并且在 [2, 2 * 108] 范围内。

#include <iostream>
#include <cmath>class Solution {
public:// 判断一个数是否为质数bool isPrime(int num) {if (num < 2) return false;if (num == 2 || num == 3) return true;if (num % 2 == 0 || num % 3 == 0) return false;// 只需要检查 6k ± 1 形式的数for (int i = 5; i * i <= num; i += 6) {if (num % i == 0 || num % (i + 2) == 0) return false;}return true;}// 判断一个数是否为回文数bool isPalindrome(int num) {int original = num;int reversed = 0;while (num > 0) {reversed = reversed * 10 + num % 10;num /= 10;}return original == reversed;}int primePalindrome(int n) {// 处理 n 为 2 的情况if (n <= 2) return 2;// 确保从奇数开始if (n % 2 == 0) n++;while (true) {int length = std::to_string(n).length();// 跳过偶数位数的回文数（除 11 外）if (length % 2 == 0 && length > 2 && n != 11) {n = std::pow(10, length) + 1;}if (isPrime(n) && isPalindrome(n)) {return n;}n += 2;}}
};

最长平衡字符串

最长平衡子字符串https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/

给你一个仅由 0 和 1 组成的二进制字符串 s 。

如果子字符串中 所有的 0 都在 1 之前且其中 0 的数量等于 1 的数量，则认为 s 的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。

返回 s 中最长的平衡子字符串长度。

子字符串是字符串中的一个连续字符序列。

int findTheLongestBalancedSubstring(char* s) {int length = 0;int nums_0 = 0;int nums_1 = 0;for (int i = 0; i < strlen(s); i++) {if (s[i] == '0') {// 如果当前是 0，且前面有 1，说明一个平衡子字符串结束，更新最大长度并重置计数if (nums_1 > 0) {int n = (nums_0 < nums_1) ? 2 * nums_0 : 2 * nums_1;if (n > length) {length = n;}nums_0 = 0;nums_1 = 0;}nums_0++;} else {// 当前是 1，增加 1 的计数nums_1++;}}// 处理字符串结尾的情况int n = (nums_0 < nums_1) ? 2 * nums_0 : 2 * nums_1;if (n > length) {length = n;}return length;
}

找出与数组相加的整数

找出与数组相加的整数 Ihttps://leetcode.cn/problems/find-the-integer-added-to-array-i/

给你两个长度相等的数组 nums1 和 nums2。

数组 nums1 中的每个元素都与变量 x 所表示的整数相加。如果 x 为负数，则表现为元素值的减少。

在与 x 相加后，nums1 和 nums2 相等。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组相等。

返回整数 x 。

int comp(const void* a,const void* b){return *(int*)a - *(int*)b;
}int addedInteger(int* nums1, int nums1Size, int* nums2, int nums2Size) {qsort(nums1,nums1Size,sizeof(int),comp);qsort(nums2,nums1Size,sizeof(int),comp);return nums2[0] - nums1[0];}

第七天

最少操作数使得数组元素相等

最小操作次数使数组元素相等https://leetcode.cn/problems/minimum-moves-to-equal-array-elements-ii/

给你一个长度为 n 的整数数组 nums ，返回使所有数组元素相等需要的最小操作数。

在一次操作中，你可以使数组中的一个元素加 1 或者减 1 。

测试用例经过设计以使答案在 32 位 整数范围内。

int comp(const void* a,const void* b){return *(int*)a - *(int*)b;
}int minMoves2(int* nums, int numsSize) {qsort(nums,numsSize,sizeof(int),comp);int n = 0;if(numsSize % 2 == 0){n = (nums[(numsSize/2) - 1] + nums[numsSize/2])/2;}else{n = nums[(numsSize-1)/2];}int ans = 0;for(int i = 0;i < numsSize;i ++){ans += abs(nums[i] - n);}return ans;
}

通过删除字母匹配字典里最长单词

通过删除字母匹配到字典里最长单词https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串

int isSubsequence(char *s, char *target) {int i = 0, j = 0;int lenS = strlen(s);int lenTarget = strlen(target);while (i < lenS && j < lenTarget) {if (s[i] == target[j]) {j++;}i++;}return j == lenTarget;
}char* findLongestWord(char* s, char** dictionary, int dictionarySize) {if (dictionarySize == 0) {return "";}int ans = -1;  // 初始化为 -1 表示还没有找到合适的字符串int length = strlen(s);for (int i = 0; i < dictionarySize; i++) {if (isSubsequence(s, dictionary[i])) {if (ans == -1) {ans = i;} else {int curLen = strlen(dictionary[i]);int ansLen = strlen(dictionary[ans]);if (curLen > ansLen || (curLen == ansLen && strcmp(dictionary[i], dictionary[ans]) < 0)) {ans = i;}}}}return ans == -1 ? "" : dictionary[ans];
}

铺瓷砖*

铺瓷砖https://leetcode.cn/problems/tiling-a-rectangle-with-the-fewest-squares/

给定一个大小为 n x m 的长方形，返回贴满矩形所需的整数边正方形的最小数量。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>// 回溯函数
void backtrack(int **covered, int n, int m, int x, int y, int count, int *ans) {// 如果当前的正方形数量已经大于等于记录的最小数量，直接返回if (count >= *ans) return;// 找到第一个未被覆盖的点while (x < n && covered[x][y]) {y++;if (y == m) {x++;y = 0;}}// 如果已经覆盖了整个矩形，更新最小数量if (x == n) {*ans = count;return;}// 尝试不同边长的正方形for (int len = 1; len <= n - x && len <= m - y; len++) {// 检查当前边长的正方形是否可以放置int valid = 1;for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {if (covered[x + i][y + j]) {valid = 0;break;}}if (!valid) break;}// 如果可以放置，标记该正方形并继续回溯if (valid) {for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {covered[x + i][y + j] = 1;}}backtrack(covered, n, m, x, y, count + 1, ans);// 回溯，撤销标记for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {covered[x + i][y + j] = 0;}}}}
}int tilingRectangle(int n, int m) {// 处理特殊情况if (n == m) return 1;// 初始化覆盖数组int **covered = (int **)malloc(n * sizeof(int *));for (int i = 0; i < n; i++) {covered[i] = (int *)calloc(m, sizeof(int));}int ans = INT_MAX;// 调用回溯函数backtrack(covered, n, m, 0, 0, 0, &ans);// 释放内存for (int i = 0; i < n; i++) {free(covered[i]);}free(covered);return ans;
}