算法日常刷题笔记（1）

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

第一天 袋子里最少数目的球

袋子里最少数目的球 leetcode /problems/minimum-limit-of-balls-in-a-bag/

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。 比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。

你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

// 计算将数组元素拆分到指定开销所需的操作次数 int getOperations(int* nums, int numsSize, int cost) { int operations = 0; for (int i = 0; i < numsSize; i++) { // 计算将 nums[i] 拆分到开销不超过 cost 所需的操作次数 operations += (nums[i] - 1) / cost; } return operations; } // 查找最小开销 int minimumSize(int* nums, int numsSize, int maxOperations) { int left = 1; int right = 0; // 找到数组中的最大值作为右边界 for (int i = 0; i < numsSize; i++) { if (nums[i] > right) { right = nums[i]; } } while (left < right) { int mid = left + (right - left) / 2; int operations = getOperations(nums, numsSize, mid); if (operations <= maxOperations) { right = mid; } else { left = mid + 1; } } return left; }

---

比较串中最小字母的出现频次

比较字符串最小字母出现频次 leetcode /problems/compare-strings-by-frequency-of-the-smallest-character/

定义一个函数 f(s)，统计 s  中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。

例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。

现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。

请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

暴力破解

/** * Note: The returned array must be malloced, assume caller calls free(). */ int f(char* s){ int arr[26]; memset(arr,0,sizeof(int) * 26); for(int i = 0;i < strlen(s);i++){ arr[s[i] - 'a'] ++; } for(int i = 0;i < 26;i++){ if(arr[i] != 0){ return arr[i]; } } return 0; } int* numSmallerByFrequency(char** queries, int queriesSize, char** words, int wordsSize, int* returnSize) { int* ans = malloc(sizeof(int) * queriesSize); *returnSize = queriesSize; int fWord[wordsSize]; for(int i = 0;i < wordsSize;i++){ fWord[i] = f(words[i]); } for(int i = 0;i < queriesSize;i++){ int f1 = f(queries[i]); int number = 0; for(int j = 0;j < wordsSize;j++){ int f2 = fWord[j]; if(f2 > f1){number ++;} } ans[i] = number; } return ans; }

 优化解

官方题解 优化了两个地方 一个求最小频次 使用一遍遍历找最小元素和相关频次 一个是使用后缀和来比较数量 不需要遍历 效率更高

int f(const char* s) { int cnt = 0; char ch = 'z'; for (int i = 0; s[i] != '\0'; i++) { char c = s[i]; if (c < ch) { ch = c; cnt = 1; } else if (c == ch) { cnt++; } } return cnt; } int* numSmallerByFrequency(char ** queries, int queriesSize, char ** words, int wordsSize, int* returnSize) { int count[12] = {0}; for (int i = 0; i < wordsSize; i++) { count[f(words[i])]++; } for (int i = 9; i >= 1; i--) { count[i] += count[i + 1]; } int* res = (int *)malloc(sizeof(int) * queriesSize); for (int i = 0; i < queriesSize; i++) { res[i] = count[f(queries[i]) + 1]; } *returnSize = queriesSize; return res; }

---

 最接近的因数

最接近的因数 leetcode /problems/closest-divisors/

给你一个整数 num，请你找出同时满足下面全部要求的两个整数：

两数乘积等于  num + 1 或 num + 2以绝对差进行度量，两数大小最接近

你可以按任意顺序返回这两个整数。

暴力破解

/** * Note: The returned array must be malloced, assume caller calls free(). */ int* closestDivisors(int num, int* returnSize) { int* ans = (int*)malloc(sizeof(int) * 2); *returnSize = 2; int minDiff = INT_MAX; // 处理 num + 1 for (int i = (int)sqrt(num + 1); i >= 1; i--) { if ((num + 1) % i == 0) { int diff = abs(i - (num + 1) / i); if (diff < minDiff) { minDiff = diff; ans[0] = i; ans[1] = (num + 1) / i; } break; } } // 处理 num + 2 for (int i = (int)sqrt(num + 2); i >= 1; i--) { if ((num + 2) % i == 0) { int diff = abs(i - (num + 2) / i); if (diff < minDiff) { minDiff = diff; ans[0] = i; ans[1] = (num + 2) / i; } break; } } return ans; }

---

第二天 在链表中插入最大公约数

在链表中插入最大公约数 leetcode /problems/insert-greatest-common-divisors-in-linked-list/

给你一个链表的头 head ，每个结点包含一个整数值。

在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。

请你返回插入之后的链表。

两个数的 最大公约数 是可以被两个数字整除的最大正整数。

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int gcd(int a, int b) { // 欧几里得算法 while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } struct ListNode* insertGreatestCommonDivisors(struct ListNode* head) { if (head == NULL || head->next == NULL) { return head; } struct ListNode* node1 = head; struct ListNode* node2 = head->next; while (node2 != NULL) { struct ListNode* newNode = (struct ListNode *)malloc(sizeof(struct ListNode)); newNode->val = gcd(node1->val, node2->val); newNode->next = node2; node1->next = newNode; node1 = node2; node2 = node2->next; } return head; }

---

 长按键入

长按键入 leetcode /problems/long-pressed-name/

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

bool isLongPressedName(char* name, char* typed) { char* Pname = name; char* Ptype = typed; while (*Pname != '\0' && *Ptype != '\0') { if (*Pname == *Ptype) { Pname++; Ptype++; } else { if (Ptype > typed && *Ptype == *(Ptype - 1)) { Ptype++; } else { return false; } } } // 检查 name 是否遍历完 if (*Pname != '\0') { return false; } // 检查 typed 剩余字符是否都是重复的 while (*Ptype != '\0') { if (Ptype > typed && *Ptype == *(Ptype - 1)) { Ptype++; } else { return false; } } return true; }

---

检查是否所有字符出现次数相同

检查是否所有字符出现次数相同 leetcode /problems/check-if-all-characters-have-equal-number-of-occurrences/

给你一个字符串 s ，如果 s 是一个 好 字符串，请你返回 true ，否则请返回 false 。

如果 s 中出现过的 所有 字符的出现次数 相同 ，那么我们称字符串 s 是 好 字符串。

bool areOccurrencesEqual(char* s) { int arr[26]; memset(arr, 0, sizeof(int) * 26); for (int i = 0; i < strlen(s); i++) { arr[s[i] - 'a']++; } int firstNonZeroCount = -1; for (int i = 0; i < 26; i++) { if (arr[i] != 0) { firstNonZeroCount = arr[i]; break; } } for (int i = 0; i < 26; i++) { if (arr[i] != 0 && arr[i] != firstNonZeroCount) { return false; } } return true; }

---

第三天 三维体投影面积

三维形体投影面积 leetcode /problems/projection-area-of-3d-shapes/

在 n x n 的网格 grid 中，我们放置了一些与 x，y，z 三轴对齐的 1 x 1 x 1 立方体。

每个值 v = grid[i][j] 表示 v 个正方体叠放在单元格 (i, j) 上。

现在，我们查看这些立方体在 xy 、yz 和 zx 平面上的投影。

投影 就像影子，将 三维 形体映射到一个 二维 平面上。从顶部、前面和侧面看立方体时，我们会看到“影子”。

返回 所有三个投影的总面积 。

int projectionArea(int** grid, int gridSize, int* gridColSize) { int area = gridSize * gridColSize[0]; for(int i = 0;i < gridSize;i++){ int max = grid[i][0]; for(int j = 0;j < gridColSize[0];j++){ if(grid[i][j] == 0){area--;} if(grid[i][j] > max){ max = grid[i][j]; } } area += max; } for(int i = 0;i < gridColSize[0];i++){ int max = grid[0][i]; for(int j = 0;j < gridSize;j++){ if(grid[j][i] > max){ max = grid[j][i]; } } area += max; } return area; }

---

 最长交替子数组

最长交替子数组 leetcode /problems/longest-alternating-subarray/

给你一个下标从 0 开始的整数数组 nums 。如果 nums 中长度为 m 的子数组 s 满足以下条件，我们称它是一个 交替子数组 ：

m 大于 1 。s1 = s0 + 1 。下标从 0 开始的子数组 s 与数组 [s0, s1, s0, s1,...,s(m-1) % 2] 一样。也就是说，s1 - s0 = 1 ，s2 - s1 = -1 ，s3 - s2 = 1 ，s4 - s3 = -1 ，以此类推，直到 s[m - 1] - s[m - 2] = (-1)m 。

请你返回 nums 中所有 交替 子数组中，最长的长度，如果不存在交替子数组，请你返回 -1 。

子数组是一个数组中一段连续 非空 的元素序列

int max(int a,int b){return a>b?a:b;} int alternatingSubarray(int* nums, int numsSize) { int maxLength = -1; int left = 0; int right = 1; while (right < numsSize) { if (nums[right] - nums[right - 1] == 1) { int expectedDiff = -1; right++; while (right < numsSize) { if (nums[right] - nums[right - 1] == expectedDiff) { expectedDiff = -expectedDiff; right++; } else { break; } } maxLength = max(maxLength, right - left); left = right - 1; } else { left = right; right++; } } return maxLength; }

---

盒子中小球的最大数量

盒子中小球的最大数量 leetcode /problems/maximum-number-of-balls-in-a-box/

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

int fun(int n){ int sum = 0; while(n){ sum += n%10; n /= 10; } return sum; } int countBalls(int lowLimit, int highLimit) { int max_num = 0; int arr[50] = {0}; for(int i = lowLimit;i <= highLimit;i++){ arr[fun(i)] += 1; max_num = max_num > arr[fun(i)] ? max_num : arr[fun(i)]; } return max_num; }

---

第四天 岛屿的周长

岛屿的周长 leetcode /problems/island-perimeter/

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

暴力破解 

int islandPerimeter(int** grid, int gridSize, int* gridColSize) { int length = 0; int div[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; for(int i = 0;i < gridSize;i++){ for(int j = 0;j < gridColSize[0];j++){ if(grid[i][j] == 0){ // continue; }else{ if(i == 0 || i == gridSize - 1){ if(gridSize == 1){length += 2;}else{length++;}} if(j == 0 || j == gridColSize[0] - 1){if(gridColSize[0] == 1){length += 2;}else{length++;}} for(int k = 0;k < 4;k++){ int dx = i + div[k][0]; int dy = j + div[k][1]; if(dx >= 0 && dx < gridSize && dy >= 0 && dy <gridColSize[0]){ if(grid[dx][dy] == 0){ length ++; } } } } } } return length; }

 优化解

使用深度优先搜素

int dfs(int **grid,int i, int j, int m, int n){ if(i<0||j<0||i>=m||j>=n||grid[i][j]==0) return 1; if(grid[i][j]==2) return 0; grid[i][j]=2; return dfs(grid,i+1,j,m,n)+dfs(grid,i-1,j,m,n)+dfs(grid,i,j+1,m,n)+dfs(grid,i,j-1,m,n); } int islandPerimeter(int** grid, int gridSize, int* gridColSize) { int m=gridSize,n=gridColSize[0]; int ans=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==1) ans+=dfs(grid,i,j,m,n); } }return ans; }

---

求根节点到叶节点数字之和

求根节点到叶节点数字之和 leetcode /problems/3Etpl5/

 给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

叶节点 是指没有子节点的节点。

解法一

/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ int fun(struct TreeNode* node,int sum){ if (node == NULL) { return 0; } // 更新当前路径组成的数字 sum = sum * 10 + node->val; // 如果是叶子节点，直接返回当前路径组成的数字 if (node->left == NULL && node->right == NULL) { return sum; } // 递归计算左子树和右子树的路径和 return fun(node->left, sum) + fun(node->right, sum); } int sumNumbers(struct TreeNode* root){ if(root == NULL){return 0;} return fun(root,0); }

 解法二

深度优先搜素

int dfs(struct TreeNode* root, int path) { path = path * 10 + root->val; if (root->left == NULL && root->right == NULL) return path; int res = 0; if (root->left) res += dfs(root->left, path); if (root->right) res += dfs(root->right, path); return res; } int sumNumbers(struct TreeNode* root) { int path = 0; if (root == NULL) return path; return dfs(root, path); }

---

 有相同颜色的相邻元素数目

有相同颜色的相邻元素数目 leetcode /problems/number-of-adjacent-elements-with-the-same-color/

给你一个下标从 0 开始、长度为 n 的数组 nums 。一开始，所有元素都是 未染色 （值为 0 ）的。

给你一个二维整数数组 queries ，其中 queries[i] = [indexi, colori] 。

对于每个操作，你需要将数组 nums 中下标为 indexi 的格子染色为 colori 。

请你返回一个长度与 queries 相等的数组 answer ，其中 answer[i]是前 i 个操作 之后 ，相邻元素颜色相同的数目。

更正式的，answer[i] 是执行完前 i 个操作后，0 <= j < n - 1 的下标 j 中，满足 nums[j] == nums[j + 1] 且 nums[j] != 0 的数目。

/** * Note: The returned array must be malloced, assume caller calls free(). */ int* colorTheArray(int n, int** queries, int queriesSize, int* queriesColSize, int* returnSize) { int* ans = (int*)malloc(sizeof(int)*queriesSize); *returnSize = queriesSize; int* nums = (int*)malloc(sizeof(int)*n); memset(nums,0,sizeof(int)*n); int count = 0; for(int i = 0;i < queriesSize;i++){ int index = queries[i][0]; int color = queries[i][1]; // 移除旧颜色对相邻相同颜色元素对数量的影响 if (index > 0 && nums[index] != 0 && nums[index] == nums[index - 1]) { count--; } if (index < n - 1 && nums[index] != 0 && nums[index] == nums[index + 1]) { count--; } // 更新颜色 nums[index] = color; // 计算新颜色对相邻相同颜色元素对数量的影响 if (index > 0 && nums[index] == nums[index - 1]) { count++; } if (index < n - 1 && nums[index] == nums[index + 1]) { count++; } ans[i] = count; } return ans; }

---

第五天 两球之间的磁力

两球之间的磁力 leetcode /problems/magnetic-force-between-two-balls/

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。

int comp(const void *a, const void *b) { return (*(const int *)a - *(const int *)b); } // 检查在给定距离下是否可以放置 m 个球 int canPlace(int* position, int positionSize, int m, int distance) { int count = 1; int lastPos = position[0]; for (int i = 1; i < positionSize; i++) { if (position[i] - lastPos >= distance) { count++; lastPos = position[i]; } } return count >= m; } // 计算最大距离的函数 int maxDistance(int* position, int positionSize, int m) { // 首先对数组进行排序 qsort(position, positionSize, sizeof(int), comp); int left = 1; int right = position[positionSize - 1] - position[0]; int result = 0; // 二分查找最大距离 while (left <= right) { int mid = left + (right - left) / 2; if (canPlace(position, positionSize, m, mid)) { result = mid; left = mid + 1; } else { right = mid - 1; } } return result; }

---

 准时到达的列车最小时速

准时到达的列车最小时速 leetcode /problems/minimum-speed-to-arrive-on-time/

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。

返回能满足你在时限前到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。

// 计算以给定速度行驶完所有列车所需的总时间 double calculateTime(int* dist, int distSize, int speed) { double totalTime = 0; for (int i = 0; i < distSize - 1; i++) { // 前 n - 1 趟列车，需要向上取整等待到整点 totalTime += ceil((double)dist[i] / speed); } // 最后一趟列车不需要等待 totalTime += (double)dist[distSize - 1] / speed; return totalTime; } // 二分查找最小正整数时速 int minSpeedOnTime(int* dist, int distSize, double hour) { if (hour <= distSize - 1) { return -1; } int left = 1, right = 1e7; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; double time = calculateTime(dist, distSize, mid); if (time <= hour) { // 如果当前速度能按时到达，记录结果并尝试更小的速度 result = mid; right = mid - 1; } else { // 如果当前速度不能按时到达，尝试更大的速度 left = mid + 1; } } return result; }  最小展台数量

最小展台数量 leetcode /problems/600YaG/

力扣嘉年华将举办一系列展览活动，后勤部将负责为每场展览提供所需要的展台。 已知后勤部得到了一份需求清单，记录了近期展览所需要的展台类型， demand[i][j] 表示第 i 天展览时第 j 个展台的类型。 在满足每一天展台需求的基础上，请返回后勤部需要准备的 最小 展台数量。

注意：

同一展台在不同天中可以重复使用。 #include <stdio.h> #include <string.h> // 假设展台类型字符为小写字母，共有 26 种 #define NUM_TYPES 26 int minNumBooths(char** demand, int demandSize) { int maxCount[NUM_TYPES] = {0}; // 遍历每一天的需求 for (int i = 0; i < demandSize; i++) { int currentCount[NUM_TYPES] = {0}; // 遍历当天需求字符串中的每个字符 for (int j = 0; demand[i][j] != '\0'; j++) { // 计算字符对应的索引 int index = demand[i][j] - 'a'; // 增加该类型展台的当前计数 currentCount[index]++; } // 更新每种展台类型的最大计数 for (int k = 0; k < NUM_TYPES; k++) { if (currentCount[k] > maxCount[k]) { maxCount[k] = currentCount[k]; } } } int total = 0; // 计算所有展台类型的最大计数之和 for (int i = 0; i < NUM_TYPES; i++) { total += maxCount[i]; } return total; }

---

第六天 球会落在何处

球会落何处 leetcode /problems/where-will-the-ball-fall/

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

int canMove(int** grid, int row, int col, int gridSize, int colSize) { int direction = grid[row][col]; if ((direction == 1 && (col == colSize - 1 || grid[row][col + 1] == -1)) || (direction == -1 && (col == 0 || grid[row][col - 1] == 1))) { return 0; // 不能移动 } return 1; // 可以移动 } /** * Note: The returned array must be malloced, assume caller calls free(). */ int* findBall(int** grid, int gridSize, int* gridColSize, int* returnSize) { int colSize = gridColSize[0]; int* ans = (int*)malloc(sizeof(int) * colSize); *returnSize = colSize; for (int i = 0; i < colSize; i++) { int drow = 0; int dcol = i; // 模拟球的下落过程 while (drow < gridSize) { if (!canMove(grid, drow, dcol, gridSize, colSize)) { ans[i] = -1; // 球被卡住，无法下落 break; } dcol += grid[drow][dcol]; // 根据当前格子的方向更新列坐标 drow++; // 向下移动一行 } if (drow == gridSize) { ans[i] = dcol; // 球成功到达底部 } } return ans; }

---

 有效的括号

有效的括号 leetcode /problems/valid-parentheses/

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 bool isValid(char* s) { int length = strlen(s); // 如果字符串长度为奇数，直接返回 false if (length % 2 != 0) { return false; } // 分配和字符串长度相同的空间作为栈 char* stack = (char*)malloc(length * sizeof(char)); if (stack == NULL) { return false; } int top = -1; // 栈顶指针初始化为 -1，表示栈为空 for (int i = 0; i < length; i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { // 遇到左括号，入栈 stack[++top] = s[i]; } else { // 遇到右括号，检查栈是否为空 if (top == -1) { free(stack); return false; } // 根据右括号类型进行匹配检查 if ((s[i] == ')' && stack[top] == '(') || (s[i] == ']' && stack[top] == '[') || (s[i] == '}' && stack[top] == '{')) { // 匹配成功，出栈 top--; } else { // 匹配失败，释放栈内存并返回 false free(stack); return false; } } } // 释放栈内存 free(stack); // 如果栈为空，说明所有括号都匹配成功 return top == -1; }

---

将整数减少到零需要的最少操作数

将整数减少到零需要的最少操作数 leetcode /problems/minimum-operations-to-reduce-an-integer-to-0/

 给你一个正整数 n ，你可以执行下述操作 任意 次：

n 加上或减去 2 的某个 幂

返回使 n 等于 0 需要执行的 最少 操作数。

如果 x == 2i 且其中 i >= 0 ，则数字 x 是 2 的幂。

int minOperations(int n) { int operations = 0; while (n > 0) { // 处理连续的 1 if ((n & 3) == 3) { // 如果最后两位是 11，加 1 让连续的 1 进位消除 n++; operations++; } else if ((n & 1) == 1) { // 如果最后一位是 1，减 1 消除这个 1 n--; operations++; } else { // 如果最后一位是 0，右移一位 n >>= 1; } } return operations; }

---

第七天 选择建筑的方案数

选择建筑的方案数 leetcode /problems/number-of-ways-to-select-buildings/

给你一个下标从 0 开始的二进制字符串 s ，它表示一条街沿途的建筑类型，其中：

s[i] = '0' 表示第 i 栋建筑是一栋办公楼，s[i] = '1' 表示第 i 栋建筑是一间餐厅。

作为市政厅的官员，你需要随机 选择 3 栋建筑。然而，为了确保多样性，选出来的 3 栋建筑 相邻 的两栋不能是同一类型。

比方说，给你 s = "001101" ，我们不能选择第 1 ，3 和 5 栋建筑，因为得到的子序列是 "011" ，有相邻两栋建筑是同一类型，所以 不合 题意。

请你返回可以选择 3 栋建筑的 有效方案数 。

long long numberOfWays(char* s) { int length = strlen(s); int total0 = 0, total1 = 0; // 统计字符串中 0 和 1 的总数 for (int i = 0; i < length; i++) { if (s[i] == '0') { total0++; } else { total1++; } } long long ans = 0; int left0 = 0, left1 = 0; // 再次遍历字符串，计算满足条件的三元组数量 for (int i = 0; i < length; i++) { if (s[i] == '0') { // 当前位置为 0，满足条件的三元组数量为左侧 1 的数量乘以右侧 1 的数量 ans += (long long)left1 * (total1 - left1); left0++; } else { // 当前位置为 1，满足条件的三元组数量为左侧 0 的数量乘以右侧 0 的数量 ans += (long long)left0 * (total0 - left0); left1++; } } return ans; }

---

奇偶频次间的最大值

奇偶频次间的最大差值 I leetcode /problems/maximum-difference-between-even-and-odd-frequency-i/

给你一个由小写英文字母组成的字符串 s 。请你找出字符串中两个字符的出现频次之间的 最大 差值，这两个字符需要满足：

一个字符在字符串中出现 偶数次 。另一个字符在字符串中出现 奇数次 。

返回 最大 差值，计算方法是出现 奇数次 字符的次数 减去 出现 偶数次 字符的次数。

int maxDifference(char* s) { int cnt[26] = {0}, c1 = 0, c2 = 100; while (* s) ++ cnt[* s ++ - 97]; for (int i = 0; i < 26; ++ i) if (cnt[i] & 1) c1 = cnt[i] > c1 ? cnt[i] : c1; else if (cnt[i] != 0) c2 = cnt[i] < c2 ? cnt[i] : c2; return c1 - c2; }

---

有序数组中出现次数超过25%的元素

有序数组中出现次数超过25%的元素 leetcode /problems/element-appearing-more-than-25-in-sorted-array/

 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

int findSpecialInteger(int* arr, int arrSize) { int p = arrSize *0.25; int length = 0; for(int i = 1;i < arrSize;i++){ if(arr[i] == arr[i - 1]){ length ++; } else{ length = 0; } if(length == p){ return arr[i]; } } return arr[0]; }

---

周末总结

        第一周的任务完成了 时间上还是不太充裕 都是一天完成了三道题 然后基本都是简单题 中等的就有些费力了 再接再励吧 今天也开学了 希望继续保持这个习惯 然后能够规划好后面的学习