为保持刷题的习惯 计划一天刷3-5题 然后一周总计汇总一下 这是第一篇笔记 笔记时间为2月10日到2月17日
第一天
袋子里最少数目的球
袋子里最少数目的球
https://leetcode.cn/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;
}比较串中最小字母的出现频次
比较字符串最小字母出现频次https://leetcode.cn/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;
}最接近的因数
最接近的因数https://leetcode.cn/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 + 1for (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 + 2for (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;
}第二天
在链表中插入最大公约数
在链表中插入最大公约数https://leetcode.cn/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;}长按键入
长按键入https://leetcode.cn/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;}检查是否所有字符出现次数相同
检查是否所有字符出现次数相同https://leetcode.cn/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;
}第三天
三维体投影面积
三维形体投影面积https://leetcode.cn/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;}最长交替子数组
最长交替子数组https://leetcode.cn/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;
}盒子中小球的最大数量
盒子中小球的最大数量https://leetcode.cn/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;
}第四天
岛屿的周长
岛屿的周长https://leetcode.cn/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;
}求根节点到叶节点数字之和
求根节点到叶节点数字之和https://leetcode.cn/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);
}有相同颜色的相邻元素数目
有相同颜色的相邻元素数目https://leetcode.cn/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;}第五天
两球之间的磁力
两球之间的磁力https://leetcode.cn/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;
}准时到达的列车最小时速
准时到达的列车最小时速https://leetcode.cn/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;
}最小展台数量
最小展台数量https://leetcode.cn/problems/600YaG/
力扣嘉年华将举办一系列展览活动，后勤部将负责为每场展览提供所需要的展台。 已知后勤部得到了一份需求清单，记录了近期展览所需要的展台类型，
demand[i][j]表示第i天展览时第j个展台的类型。 在满足每一天展台需求的基础上，请返回后勤部需要准备的 最小 展台数量。注意：
- 同一展台在不同天中可以重复使用。
#include <stdio.h>
#include <string.h>// 假设展台类型字符为小写字母，共有 26 种
#define NUM_TYPES 26int 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;
}第六天
球会落在何处
球会落何处https://leetcode.cn/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;
}有效的括号
有效的括号https://leetcode.cn/problems/valid-parentheses/
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
bool isValid(char* s) {int length = strlen(s);// 如果字符串长度为奇数，直接返回 falseif (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 {// 匹配失败，释放栈内存并返回 falsefree(stack);return false;}}}// 释放栈内存free(stack);// 如果栈为空，说明所有括号都匹配成功return top == -1;
}将整数减少到零需要的最少操作数
将整数减少到零需要的最少操作数https://leetcode.cn/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) {// 处理连续的 1if ((n & 3) == 3) {// 如果最后两位是 11，加 1 让连续的 1 进位消除n++;operations++;} else if ((n & 1) == 1) {// 如果最后一位是 1，减 1 消除这个 1n--;operations++;} else {// 如果最后一位是 0，右移一位n >>= 1;}}return operations;
}第七天
选择建筑的方案数
选择建筑的方案数https://leetcode.cn/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;
}奇偶频次间的最大值
奇偶频次间的最大差值 Ihttps://leetcode.cn/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%的元素https://leetcode.cn/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];
}周末总结
第一周的任务完成了 时间上还是不太充裕 都是一天完成了三道题 然后基本都是简单题 中等的就有些费力了 再接再励吧 今天也开学了 希望继续保持这个习惯 然后能够规划好后面的学习