当前位置： 首页 > article >正文

算法日常刷题笔记（3）

article 2025/3/4 4:33:30

      为保持刷题的习惯 计划一天刷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 设为 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;
    }
};

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

可以形成最大正方形的矩形数目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 开始的内存数组的大小。所有内存单元开始都是空闲的。

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

  1. 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
  2. 释放 给定 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);
*/

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

有多少小于当前数字的数字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，无法完成任务，返回 -1
        if (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 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);
*/

统计特殊字母的数量

统计特殊字母的数量 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 不存在，则创建一个新的 TreeSet
            cuisineToFoods.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) {
        // 获取该菜系对应的 TreeSet
        TreeSet<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;  // 初始化最小差值为 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;
}

计算列车到站时间

计算列车到站时间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;
}

总结

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


http://www.kler.cn/a/569672.html

相关文章：

  • 【R语言】PCA主成分分析
  • 计算机毕业设计SpringBoot+Vue.js常规应急物资管理系统(源码+文档+PPT+讲解)
  • 梳理vite构建vue项目可选的配置和组件
  • 匿名内部类与Lambda表达式不理解点
  • 第34周：文献阅读
  • 基于SSM实现的bbs论坛系统功能实现九
  • git管理的项目 发布时有收费版/免费版/客户定制版，如何管理分支，通过merge(合并) 还是 cherry-pick(挑拣) 引入更新的代码？
  • 25考研数二408部分时间统计
  • 【漫话机器学习系列】109.线性无关（Linearly Independent）
  • DeepSeek 助力 Vue3 开发：打造丝滑的弹性布局（Flexbox）
  • Netty介绍
  • HTML——＜head＞标签中可放入的标签
  • 计算机毕业设计SpringBoot+Vue.js线上辅导班系统(源码+文档+PPT+讲解)
  • 线上服务器的文件下载到本地Windows电脑
  • Golang | 每日一练 (4)
  • 【uniapp】在UniApp中实现持久化存储：安卓--生成写入数据为jsontxt
  • 【tplink】校园网接路由器如何单独登录自己的账号，wan-lan和lan-lan区别
  • 从神经元到大语言模型及其应用
  • React + TypeScript AI Agent开发实战
  • docker高级