算法日常刷题笔记（2）

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

第一天

找到初始输入字符串

找到初始输入字符串 Ihttps://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;
}