算法日常刷题笔记（3）

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

第一天 设计有序流

设计有序流 leetcode /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 设为 1 ptr = 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; } };

---

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

可以形成最大正方形的矩形数目 leetcode /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; }

---

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

统计范围内的元音字符串数 leetcode /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; }

---

第二天 设计内存分配器

设计内存分配器 leetcode /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; // 将这些连续的空闲内存单元标记为 mID for (int j = startIndex; j <= i; j++) { obj->memory[j] = mID; } return startIndex; } } else { // 如果遇到已分配的内存单元，连续空闲计数重置为 0 consecutiveFree = 0; } } // 没有找到足够的连续空闲内存单元，返回 -1 return -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); */

---

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

有多少小于当前数字的数字 leetcode /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; }

---

最少的后缀翻转次数

最少的后缀翻转次数 leetcode /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; }

---

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

完成所有任务需要的最少轮数 leetcode /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，无法完成任务，返回 -1 if (number == 1) { return -1; } // 计算完成这些任务所需的最少轮数 ans += (number + 2) / 3; // 更新 i 的值，继续处理下一组相同难度的任务 i = j; } return ans; }

---

第三天 设计浏览器历史记录

设计浏览器历史记录 leetcode /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 5000 typedef 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); */

---

统计特殊字母的数量

统计特殊字母的数量 I leetcode /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; }

---

千位分隔数

千位分隔数 leetcode /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; }

---

按奇偶数排序数组

按奇偶排序数组 leetcode /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; }

---

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

给定数字能组成的最大时间 leetcode /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 解析器 leetcode /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; }

---

第五天 设计食物评分系统

设计食物评分系统 leetcode /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] pareTo(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 不存在，则创建一个新的 TreeSet cuisineToFoods puteIfAbsent(cuisine, k -> new TreeSet<>((a, b) -> { int ratingA = foodToRating.get(a); int ratingB = foodToRating.get(b); // 先按评分降序排序 if (ratingA != ratingB) { return ratingB - ratingA; } // 评分相同时按字典序升序排序 return a pareTo(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) { // 获取该菜系对应的 TreeSet TreeSet<String> foodSet = cuisineToFoods.get(cuisine); if (foodSet == null || foodSet.isEmpty()) { return null; } // 返回该 TreeSet 中第一个元素，即评分最高且字典序最小的食物 return foodSet.first(); } }

---

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

转变数组后最接近目标值的数组和 leetcode /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; // 初始化最小差值为 target while (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; }

---

计算列车到站时间

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

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

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

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

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

---

特殊数组

特殊数组 I leetcode /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; }

---

第六天 回文质数

回文质数 leetcode /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; } } };

---

最长平衡字符串

最长平衡子字符串 leetcode /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; }

---

找出与数组相加的整数

找出与数组相加的整数 I leetcode /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]; }

---

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

最小操作次数使数组元素相等 leetcode /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; }

---

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

通过删除字母匹配到字典里最长单词 leetcode /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]; }

---

铺瓷砖*

铺瓷砖 leetcode /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; }

---

总结

        这一周的练习比较费力 经常遇到使用栈和哈希的题目 使用c的代码量比较多 所以想要再继续学习一下C++的语法 后面备考的难度会越来越高 题目做起来 理解起来属实很费力