为保持刷题的习惯 计划一天刷3-5题 然后一周总计汇总一下 这是第二篇笔记 笔记时间为2月17日到2月23日
第一天
找到初始输入字符串
找到初始输入字符串 I
https://leetcode.cn/problems/find-the-original-typed-string-i/
Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。
尽管 Alice 尽可能集中注意力，她仍然可能会犯错 至多 一次。
给你一个字符串
word，它表示 最终 显示在 Alice 显示屏上的结果。请你返回 Alice 一开始可能想要输入字符串的总方案数。
int possibleStringCount(char* word) {int ans = 1; while (* word) if (* word ++ == * word) ++ ans;return ans;
}Excel 表列序号
Excel 表列序号https://leetcode.cn/problems/excel-sheet-column-number/
给你一个字符串
columnTitle，表示 Excel 表格中的列名称。返回 该列名称对应的列序号 。例如：
A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28
int titleToNumber(char* columnTitle) {int length = strlen(columnTitle);int ans = 0;int n = 0;for(int i = length -1;i >= 0;i--){ans += (columnTitle[i] - 'A' + 1) * pow(26,n++);}return ans;}K次取反后最大化的数组和
K 次取反后最大化的数组和https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
int comp(const void* a,const void* b){return *(const int*)a - *(const int *)b;
}int largestSumAfterKNegations(int* nums, int numsSize, int k) {int max_v = 0;qsort(nums,numsSize,sizeof(int),comp);for (int i = 0; i < numsSize && k > 0; i++) {if (nums[i] < 0) {nums[i] = -nums[i];k--;} else {break;}}qsort(nums,numsSize,sizeof(int),comp);if(k % 2 == 1){nums[0] = -nums[0];}for(int i = 0; i < numsSize;i++){max_v += nums[i];}return max_v;
}第二天
区间查询数字的频率
2080. 区间内查询数字的频率https://leetcode.cn/problems/range-frequency-queries/
请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现
RangeFreqQuery类：
RangeFreqQuery(int[] arr)用下标从 0 开始的整数数组arr构造一个类的实例。int query(int left, int right, int value)返回子数组arr[left...right]中value的 频率 。一个 子数组 指的是数组中一段连续的元素。
arr[left...right]指的是nums中包含下标left和right在内 的中间一段连续元素。
class RangeFreqQuery {// 用于存储每个值出现的所有索引private Map<Integer, List<Integer>> indexMap;public RangeFreqQuery(int[] arr) {indexMap = new HashMap<>();// 遍历数组，记录每个值出现的索引for (int i = 0; i < arr.length; i++) {int num = arr[i];// 如果该值还没有对应的索引列表，创建一个新的列表indexMap.computeIfAbsent(num, k -> new ArrayList<>()).add(i);}}public int query(int left, int right, int value) {// 如果该值没有出现过，直接返回 0if (!indexMap.containsKey(value)) {return 0;}// 获取该值出现的所有索引列表List<Integer> indices = indexMap.get(value);// 找到第一个大于等于 left 的索引int leftIndex = binarySearchLeft(indices, left);// 找到第一个大于 right 的索引int rightIndex = binarySearchRight(indices, right);// 计算在 [left, right] 范围内该值出现的次数return rightIndex - leftIndex;}// 二分查找第一个大于等于 target 的索引private int binarySearchLeft(List<Integer> list, int target) {int left = 0, right = list.size();while (left < right) {int mid = left + (right - left) / 2;if (list.get(mid) < target) {left = mid + 1;} else {right = mid;}}return left;}// 二分查找第一个大于 target 的索引private int binarySearchRight(List<Integer> list, int target) {int left = 0, right = list.size();while (left < right) {int mid = left + (right - left) / 2;if (list.get(mid) <= target) {left = mid + 1;} else {right = mid;}}return left;}
}寻找右区间
436. 寻找右区间https://leetcode.cn/problems/find-right-interval/
给你一个区间数组
intervals，其中intervals[i] = [starti, endi]，且每个starti都 不同 。区间
i的 右侧区间 是满足startj >= endi，且startj最小 的区间j。注意i可能等于j。返回一个由每个区间
i对应的 右侧区间 下标组成的数组。如果某个区间i不存在对应的 右侧区间 ，则下标i处的值设为-1
// 自定义结构体用于存储区间起始位置和其对应的下标
typedef struct {int start;int index;
} StartIndex;// 比较函数，用于qsort排序
int compare(const void *a, const void *b) {StartIndex *sa = (StartIndex *)a;StartIndex *sb = (StartIndex *)b;return sa->start - sb->start;
}// 二分查找函数，找到满足startj >= endi的最小startj对应的下标
int binarySearch(StartIndex *starts, int n, int target) {int left = 0, right = n - 1;int result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (starts[mid].start >= target) {result = starts[mid].index;right = mid - 1;} else {left = mid + 1;}}return result;
}// 主函数，计算每个区间的右侧区间下标
int* findRightInterval(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize) {// 分配内存用于存储每个区间的起始位置和其对应的下标StartIndex *starts = (StartIndex *)malloc(intervalsSize * sizeof(StartIndex));for (int i = 0; i < intervalsSize; i++) {starts[i].start = intervals[i][0];starts[i].index = i;}// 对起始位置进行排序qsort(starts, intervalsSize, sizeof(StartIndex), compare);// 分配内存用于存储结果数组int *result = (int *)malloc(intervalsSize * sizeof(int));*returnSize = intervalsSize;// 对每个区间进行二分查找，找到其右侧区间的下标for (int i = 0; i < intervalsSize; i++) {int end = intervals[i][1];result[i] = binarySearch(starts, intervalsSize, end);}// 释放之前分配的内存free(starts);return result;
}下一个更大元素Ⅱ
下一个更大元素 IIhttps://leetcode.cn/problems/next-greater-element-ii/
给定一个循环数组
nums（nums[nums.length - 1]的下一个元素是nums[0]），返回nums中每个元素的 下一个更大元素 。数字
x的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出-1。
暴力破解
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {int* ans = (int*)malloc(sizeof(int) * numsSize);*returnSize = numsSize;int max = 0;for(int i = 0;i < numsSize;i++){if(nums[i] > nums[max]){max = i;}for(int j = i + 1;j < numsSize*2;j++){if(nums[j%numsSize] > nums[i]){ans[i] = nums[j%numsSize];break;}}}for(int i = 0;i < numsSize;i++){if(nums[i] == nums[max]){ans[i] = -1;}}return ans;
}优化解
int* nextGreaterElements(int* nums, int numsSize, int* returnSize) {int* ans = malloc(numsSize * sizeof(int));memset(ans, -1, numsSize * sizeof(int));int* st = malloc(numsSize * sizeof(int));int top = 0;for (int i = 2 * numsSize - 1; i >= 0; i--) {int x = nums[i % numsSize];while (top && x >= st[top - 1]) {top--;}if (top && i < numsSize) {ans[i] = st[top - 1];}st[top++] = x;}free(st);*returnSize = numsSize;return ans;
}第三天
数组列表中的最大距离
数组列表中的最大距离https://leetcode.cn/problems/maximum-distance-in-arrays/
给定
m个数组，每个数组都已经按照升序排好序了。现在你需要从两个不同的数组中选择两个整数（每个数组选一个）并且计算它们的距离。两个整数
a和b之间的距离定义为它们差的绝对值|a-b|。返回最大距离。
示例 1：
输入：[[1,2,3],[4,5],[1,2,3]] 输出：4 解释： 一种得到答案 4 的方法是从第一个数组或者第三个数组中选择 1，同时从第二个数组中选择 5
int maxDistance(int** arrays, int arraysSize, int* arraysColSize) {int res = 0;int n = arraysColSize[0];int min_val = arrays[0][0];int max_val = arrays[0][arraysColSize[0] - 1];for (int i = 1; i < arraysSize; i++) {n = arraysColSize[i];res = fmax(res, fmax(abs(arrays[i][n - 1] - min_val), abs(max_val - arrays[i][0])));min_val = fmin(min_val, arrays[i][0]);max_val = fmax(max_val, arrays[i][n - 1]);}return res;
}
优质数对的总数
优质数对的总数 Ihttps://leetcode.cn/problems/find-the-number-of-good-pairs-i/
给你两个整数数组
nums1和nums2，长度分别为n和m。同时给你一个正整数k。如果
nums1[i]可以除尽nums2[j] * k，则称数对(i, j)为 优质数对（0 <= i <= n - 1,0 <= j <= m - 1）。返回 优质数对 的总数。
int numberOfPairs(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {int nums = 0;for(int i = 0;i < nums1Size;i++){for(int j = 0;j < nums2Size;j ++){if(nums1[i] % (nums2[j] * k) == 0){nums ++;}}}return nums;
}移除石头游戏
移除石头游戏https://leetcode.cn/problems/stone-removal-game/
Alice 和 Bob 在玩一个游戏，他们俩轮流从一堆石头中移除石头，Alice 先进行操作。
- Alice 在第一次操作中移除 恰好 10 个石头。
- 接下来的每次操作中，每位玩家移除的石头数 恰好 为另一位玩家上一次操作的石头数减 1 。
第一位没法进行操作的玩家输掉这个游戏。
给你一个正整数
n表示一开始石头的数目，如果 Alice 赢下这个游戏，请你返回true，否则返回false。
bool canAliceWin(int n) {// Alice 第一次移除 10 个石头int aliceRemove = 10;// 先检查 Alice 第一次操作是否可行if (n < aliceRemove) {return false;}n -= aliceRemove;while (1) {// Bob 移除的石头数为 Alice 上一次移除的石头数减 1int bobRemove = aliceRemove - 1;if (n < bobRemove) {// Bob 无法进行操作，Alice 赢return true;}n -= bobRemove;// Alice 下一次移除的石头数为 Bob 上一次移除的石头数减 1aliceRemove = bobRemove - 1;if (n < aliceRemove) {// Alice 无法进行操作，Alice 输return false;}n -= aliceRemove;}
}
第四天
奇偶位数
奇偶位数https://leetcode.cn/problems/number-of-even-and-odd-bits/
给你一个 正 整数
n。用
even表示在n的二进制形式（下标从 0 开始）中值为1的偶数下标的个数。用
odd表示在n的二进制形式（下标从 0 开始）中值为1的奇数下标的个数。请注意，在数字的二进制表示中，位下标的顺序 从右到左。
返回整数数组
answer，其中answer = [even, odd]
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* evenOddBit(int n, int* returnSize) {int* ans = (int*)malloc(sizeof(int)*2);*returnSize = 2;int even = 0;int odd = 0;int num = n;int length = 0;while(num){length ++;if(num % 2 == 1){if(length % 2 == 0){odd ++;}else{even ++;}}num /= 2;}ans[0] = even;ans[1] = odd;return ans;}等差数列划分
等差数列划分https://leetcode.cn/problems/arithmetic-slices/
如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
- 例如，
[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。给你一个整数数组
nums，返回数组nums中所有为等差数组的 子数组 个数。子数组 是数组中的一个连续序列
int numberOfArithmeticSlices(int* nums, int numsSize) {if (numsSize == 1) {return 0;}int d = nums[0] - nums[1], t = 0;int ans = 0;// 因为等差数列的长度至少为 3，所以可以从 i=2 开始枚举for (int i = 2; i < numsSize; ++i) {if (nums[i - 1] - nums[i] == d) {++t;} else {d = nums[i - 1] - nums[i];t = 0;}ans += t;}return ans;
}有效的回旋镖
1037. 有效的回旋镖https://leetcode.cn/problems/valid-boomerang/
给定一个数组
points，其中points[i] = [xi, yi]表示 X-Y 平面上的一个点，如果这些点构成一个 回旋镖 则返回true。回旋镖 定义为一组三个点，这些点 各不相同 且 不在一条直线上
bool isBoomerang(int** points, int pointsSize, int* pointsColSize) {// 计算向量 (x1 - x0, y1 - y0) 和 (x2 - x0, y2 - y0) 的叉积int dx1 = points[1][0] - points[0][0];int dy1 = points[1][1] - points[0][1];int dx2 = points[2][0] - points[0][0];int dy2 = points[2][1] - points[0][1];// 判断叉积是否为 0，如果不为 0，则三点不共线，构成回旋镖return dx1 * dy2 != dx2 * dy1;}第五天
用地毯覆盖后的最少白色砖块
用地毯覆盖后的最少白色砖块https://leetcode.cn/problems/minimum-white-tiles-after-covering-with-carpets/
给你一个下标从 0 开始的 二进制 字符串
floor，它表示地板上砖块的颜色。
floor[i] = '0'表示地板上第i块砖块的颜色是 黑色 。floor[i] = '1'表示地板上第i块砖块的颜色是 白色 。同时给你
numCarpets和carpetLen。你有numCarpets条 黑色 的地毯，每一条 黑色 的地毯长度都为carpetLen块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。请你返回没被覆盖的白色砖块的 最少 数目。
int minimumWhiteTiles(char* floor, int numCarpets, int carpetLen) {int length = strlen(floor);// 创建动态规划数组int** dp = (int**)malloc((length + 1) * sizeof(int*));for (int i = 0; i <= length; i++) {dp[i] = (int*)calloc(numCarpets + 1, sizeof(int));}// 初始化动态规划数组for (int i = 1; i <= length; i++) {for (int j = 0; j <= numCarpets; j++) {// 不使用新的地毯覆盖第 i 块砖块dp[i][j] = dp[i - 1][j] + (floor[i - 1] == '1');if (j > 0) {// 使用新的地毯覆盖第 i 块砖块int prev = (i - carpetLen > 0) ? i - carpetLen : 0;dp[i][j] = (dp[i][j] < dp[prev][j - 1]) ? dp[i][j] : dp[prev][j - 1];}}}int ans = dp[length][numCarpets];// 释放动态规划数组for (int i = 0; i <= length; i++) {free(dp[i]);}free(dp);return ans;}高度检查器
高度检查器https://leetcode.cn/problems/height-checker/
学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
排序后的高度情况用整数数组
expected表示，其中expected[i]是预计排在这一行中第i位的学生的高度（下标从 0 开始）。给你一个整数数组
heights，表示 当前学生站位 的高度情况。heights[i]是这一行中第i位学生的高度（下标从 0 开始）。返回满足
heights[i] != expected[i]的 下标数量 。
int comp(const void* a,const void* b){return *(int *)a - *(int *)b;
}int heightChecker(int* heights, int heightsSize) {int nums = 0;int* arr = (int*) malloc(sizeof(int) * heightsSize);for(int i = 0;i < heightsSize;i++){arr[i] = heights[i];}qsort(arr,heightsSize,sizeof(int),comp);for(int i = 0;i < heightsSize;i++){if(heights[i] != arr[i]){nums ++;}}return nums;
}删除一个元素使数组严格递增
删除一个元素使数组严格递增https://leetcode.cn/problems/remove-one-element-to-make-the-array-strictly-increasing/
给你一个下标从 0 开始的整数数组
nums，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回true，否则返回false。如果数组本身已经是严格递增的，请你也返回true。数组
nums是 严格递增 的定义为：对于任意下标的1 <= i < nums.length都满足nums[i - 1] < nums[i]。
bool canBeIncreasing(int* nums, int numsSize) {int count = 0;for (int i = 1; i < numsSize; i++) {if (nums[i] <= nums[i - 1]) {// 出现不满足严格递增的情况，计数加 1count++;if (count > 1) {// 如果需要删除超过一个元素，直接返回 falsereturn false;}if (i > 1 && nums[i] <= nums[i - 2]) {// 如果删除前一个元素后仍然不满足严格递增，尝试修改当前元素nums[i] = nums[i - 1];}}}return true;
}第六天
统计相似字符串对的数目
统计相似字符串对的数目https://leetcode.cn/problems/count-pairs-of-similar-strings/
给你一个下标从 0 开始的字符串数组
words。如果两个字符串由相同的字符组成，则认为这两个字符串 相似 。
- 例如，
"abca"和"cba"相似，因为它们都由字符'a'、'b'、'c'组成。- 然而，
"abacba"和"bcfd"不相似，因为它们不是相同字符组成的。请你找出满足字符串
words[i]和words[j]相似的下标对(i, j)，并返回下标对的数目，其中0 <= i < j <= words.length - 1。
暴力破解
bool isCom(char* word1,char* word2){int arr[26][2];memset(arr,0,sizeof(int)*52);for(int i = 0;i < strlen(word1);i++){arr[word1[i] - 'a'][0] ++;}for(int i = 0;i < strlen(word2);i++){arr[(word2[i] - 'a')][1] ++;}for(int i = 0;i < 26;i ++){if ((arr[i][0] > 0 && arr[i][1] == 0) || (arr[i][0] == 0 && arr[i][1] > 0)) {return false;}}return true;}int similarPairs(char** words, int wordsSize) {int ans = 0;for(int i = 0;i < wordsSize;i++){for(int j = i + 1;j < wordsSize;j++){if(isCom(words[i],words[j])){ans ++;}}}return ans;
}优化解
class Solution {
public:int similarPairs(vector<string>& words) {int res = 0;unordered_map<int, int> cnt;for (const string& word : words) {int state = 0;for (char c : word) {state |= 1 << (c - 'a');}res += cnt[state];cnt[state]++;}return res;}
};在区间范围内统计奇数数目
在区间范围内统计奇数数目https://leetcode.cn/problems/count-odd-numbers-in-an-interval-range/
给你两个非负整数
low和high。请你返回low和high之间（包括二者）奇数的数目。
int sum(int n){int nums = 0;if(n % 2 == 1){nums += (n + 1)/2;}else{nums += n/2;}return nums;
}int countOdds(int low, int high) {int nums = 0;nums += (sum(high) - sum(low));if(low % 2 == 1){nums ++;}return nums;
}统计字符串中的元音子字符串
统计字符串中的元音子字符串https://leetcode.cn/problems/count-vowel-substrings-of-a-string/
子字符串 是字符串中的一个连续（非空）的字符序列。
元音子字符串 是 仅 由元音（
'a'、'e'、'i'、'o'和'u'）组成的一个子字符串，且必须包含 全部五种 元音。给你一个字符串
word，统计并返回word中 元音子字符串的数目 。
// 判断字符是否为元音字母
int isVowel(char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}// 检查子字符串是否仅由元音字母组成且包含全部五种元音字母
int isValidVowelSubstring(char* word, int start, int end) {int vowelCount[5] = {0};for (int i = start; i <= end; i++) {if (!isVowel(word[i])) {return 0;}switch (word[i]) {case 'a':vowelCount[0] = 1;break;case 'e':vowelCount[1] = 1;break;case 'i':vowelCount[2] = 1;break;case 'o':vowelCount[3] = 1;break;case 'u':vowelCount[4] = 1;break;}}for (int i = 0; i < 5; i++) {if (vowelCount[i] == 0) {return 0;}}return 1;
}// 主函数，统计元音子字符串的数量
int countVowelSubstrings(char* word) {int n = strlen(word);int count = 0;// 枚举所有可能的子字符串for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {if (isValidVowelSubstring(word, i, j)) {count++;}}}return count;
}第七天
一维数组的动态和
一维数组的动态和https://leetcode.cn/problems/running-sum-of-1d-array/
给你一个数组
nums。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i])。请返回
nums的动态和。
int* runningSum(int* nums, int numsSize, int* returnSize) {*returnSize = numsSize;for (int i = 1; i < numsSize; i++) {nums[i] += nums[i - 1];}return nums;
}每个查询的最大异或值
每个查询的最大异或值https://leetcode.cn/problems/maximum-xor-for-each-query/
给你一个 有序 数组
nums，它由n个非负整数组成，同时给你一个整数maximumBit。你需要执行以下查询n次：
- 找到一个非负整数
k < 2maximumBit，使得nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k的结果 最大化 。k是第i个查询的答案。- 从当前数组
nums删除 最后 一个元素。请你返回一个数组
answer，其中answer[i]是第i个查询的结果。
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* getMaximumXor(int* nums, int numsSize, int maximumBit, int* returnSize) {int* ans = (int*)malloc(sizeof(int) * numsSize);*returnSize = numsSize;// 计算最大可能的值 2^maximumBit - 1int maxV = (1 << maximumBit) - 1;// 计算前缀异或值int xorValue = 0;for (int i = 0; i < numsSize; i++) {xorValue ^= nums[i];}// 从后往前计算最大异或结果for (int i = 0; i < numsSize; i++) {// 计算最大异或结果ans[i] = xorValue ^ maxV;// 去掉当前元素的异或值xorValue ^= nums[numsSize - 1 - i];}return ans;
}三数之和的多种可能
三数之和的多种可能https://leetcode.cn/problems/3sum-with-multiplicity/
给定一个整数数组
arr，以及一个整数target作为目标值，返回满足i < j < k且arr[i] + arr[j] + arr[k] == target的元组i, j, k的数量。由于结果会非常大，请返回
109 + 7的模。
#define MOD 1000000007// 比较函数，用于 qsort
int compare(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}int threeSumMulti(int* arr, int arrSize, int target) {// 对数组进行排序qsort(arr, arrSize, sizeof(int), compare);long long count = 0;// 遍历数组，固定一个元素 arr[i]for (int i = 0; i < arrSize - 2; i++) {int newTarget = target - arr[i];int j = i + 1, k = arrSize - 1;// 使用双指针法在剩余元素中寻找满足条件的 arr[j] 和 arr[k]while (j < k) {int sum = arr[j] + arr[k];if (sum < newTarget) {j++;} else if (sum > newTarget) {k--;} else {// 找到满足条件的 arr[j] 和 arr[k]if (arr[j] != arr[k]) {int leftCount = 1, rightCount = 1;// 处理重复元素 arr[j]while (j + 1 < k && arr[j] == arr[j + 1]) {leftCount++;j++;}// 处理重复元素 arr[k]while (k - 1 > j && arr[k] == arr[k - 1]) {rightCount++;k--;}// 计算满足条件的元组数量count += (long long)leftCount * rightCount;count %= MOD;j++;k--;} else {// arr[j] 和 arr[k] 相等int num = k - j + 1;// 计算组合数 C(num, 2)count += (long long)num * (num - 1) / 2;count %= MOD;break;}}}}return (int)count;
}
![[实现Rpc] 客户端 | Requestor | RpcCaller的设计实现](https://i-blog.csdnimg.cn/img_convert/65b350266ec6129e1ef6e14a08824d2d.png)
