目录
零、写在前面
????????今天是打卡的第31天，今天的难度还行。知识点在：
一、主要知识点
? ? ? ? 1.hash降维
比英雄哥的代码改进了亿点点，就是不用每次都重设hash数组，考虑到c+1，那么b的可选项多了一个，枚举这一个多选项加入hash表就可以了。直接复杂度从O(n^3)变成了O(n^2)。
int countQuadruplets(int* nums, int n){ int a, b, c, d; int hash[201]; int sum = 0; memset(hash, 0, sizeof(hash)); for(c = 2; c < n; ++c) { b = c - 1; //本次b新加了一个可选项 for(a = b - 1; a >= 0; a--) hash[ nums[a] + nums[b] ]++; for(d = c+1; d < n; ++d) if( nums[d] - nums[c] >= 0 ) sum += hash[ nums[d] - nums[c] ]; } return sum; }
二、课后习题?
1385. 两个数组间的距离值
1385. 两个数组间的距离值
https://leetcode-cn.com/problems/find-the-distance-value-between-two-arrays/
题目描述
给你两个整数数组?arr1?，?arr2?和一个整数?d?，请你返回两个数组之间的?距离值?。
「距离值」?定义为符合此距离要求的元素数目：对于元素?arr1[i]?，不存在任何元素?arr2[j]?满足 |arr1[i]-arr2[j]| <= d 。
思路
先将arr2进行排序，然后在判断arr1元素符不符合要求的时候使用双指针，可以将复杂度降低。
int cmp(int *a,int *b){
return *a > *b;
}
int findTheDistanceValue(int* arr1, int arr1Size, int* arr2, int arr2Size, int d){
qsort(arr2,arr2Size,sizeof(int),cmp);
int ans = 0;
for(int i = 0;i < arr1Size;i++){
int low = 0,high = arr2Size - 1;
while(low < high){ //找到最接近arr[i]的两个数字
int mid = (low + high) / 2;
if(arr2[mid] > arr1[i]) high = mid;
else low = mid + 1;
}
if((low < 1 ||abs(arr1[i] - arr2[low - 1]) > d) && (low > arr2Size -1||abs(arr1[i] - arr2[low]) > d)) ans++;//判断
}
return ans;
}1291. 顺次数
1291. 顺次数https://leetcode-cn.com/problems/sequential-digits/
题目描述
我们定义「顺次数」为：每一位上的数字都比前一位上的数字大 1 的整数。
请你返回由?[low, high]?范围内所有顺次数组成的 有序 列表（从小到大排序）。
思路
这道题把，打表！打表yyds！
int cmp(int *a,int *b){return *a > *b;}
int* sequentialDigits(int low, int high, int* returnSize){
int *ans = malloc(sizeof(int)*45);*returnSize = 0;
int f[46],fsize= 0;
for(int i = 1;i <= 9;i++){//生成所有的顺次数
int temp = 0;
for(int j = i;j <= 9;j++){
temp *= 10;
temp += j;
f[fsize++] = temp;
}
}
qsort(f,fsize,sizeof(int),cmp);//排序
for(int i = 0;i < 45;i++)
if(f[i] >= low && f[i] <= high) ans[(*returnSize)++] = f[i];
return ans;
}2048. 下一个更大的数值平衡数
2048. 下一个更大的数值平衡数https://leetcode-cn.com/problems/next-greater-numerically-balanced-number/
题目描述
如果整数??x 满足：对于每个数位?d ，这个数位?恰好 在 x 中出现 d 次。那么整数 x 就是一个 数值平衡数 。
给你一个整数 n ，请你返回 严格大于 n 的 最小数值平衡数 。
思路
这题就暴力枚举，枚举所有大于n的元素，判断是否满足条件。
bool isBalanced(int num){ //判断是否满足条件
int hash[10] = {0};
while(num){
hash[num % 10] ++;
num /= 10;
}
for(int i = 0;i < 10;i++){
if(hash[i] != 0 && hash[i] != i) return false;
}
return true;
}
int nextBeautifulNumber(int n){
while(1){
n++;
if(isBalanced(n)) return n;
}
return -1;
}
349. 两个数组的交集
349. 两个数组的交集https://leetcode-cn.com/problems/intersection-of-two-arrays/
题目描述
给定两个数组，编写一个函数来计算它们的交集。
思路
排序之后双指针。你们看得懂的。
int cmp(int* a, int* b) {return *a - *b;}
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
qsort(nums1, nums1Size, sizeof(int), cmp);
qsort(nums2, nums2Size, sizeof(int), cmp);
*returnSize = 0;
int low = 0, high = 0;
int* ans = malloc(sizeof(int) * (nums1Size > nums2Size ? nums1Size :nums2Size));
//申请两个中较短的数组长度就好了
while (low < nums1Size && high < nums2Size) {
if (nums1[low] == nums2[high]) {
//去重插入
if (!(*returnSize) || nums1[low] != ans[(*returnSize) - 1])
ans[(*returnSize)++] = nums1[low];
low++;
high++;
}
else if (nums1[low] < nums2[high]) {
low++;
}
else high++;
}
return ans;
}349. 两个数组的交集
349. 两个数组的交集https://leetcode-cn.com/problems/intersection-of-two-arrays/
题目描述
给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：
nums[a] + nums[b] + nums[c] == nums[d] ，且
a < b < c < d
思路
就是例题。其实就是固定c之后把a+b的值固定为hash表，同时更新hash表将复杂度降到O(n^2)。
int countQuadruplets(int* nums, int n){
int a, b, c, d;
int hash[201];
int sum = 0;
memset(hash, 0, sizeof(hash));//初始化hash
for(c = 2; c < n; ++c) {
b = c - 1; //本次b新加了一个可选项
for(a = b - 1; a >= 0; a--)
hash[ nums[a] + nums[b] ]++;
for(d = c+1; d < n; ++d)
if( nums[d] - nums[c] >= 0 )
sum += hash[ nums[d] - nums[c] ];
}
return sum;
}
1566. 重复至少 K 次且长度为 M 的模式
题目描述
给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续 重复多次但 不重叠 。 模式由其长度和重复次数定义。
如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回??false 。
思路
这个其实因为连续出现k次且不重叠，就可以按照取模来运算了。
bool containsPattern(int* arr, int arrSize, int m, int k){
for(int i = 0;i <= arrSize - m *k;++i){
int temp;
for(temp = 0;temp < m * k;++temp){
if(arr[i+temp] != arr[i + temp%m]) break;//重复出现k次的判断
}
if(temp == m*k) return true;
}
return false;
}2025. 分割数组的最多方案数
2025. 分割数组的最多方案数https://leetcode-cn.com/problems/maximum-number-of-ways-to-partition-an-array/
题目描述
给你一个下标从 0?开始且长度为 n?的整数数组?nums?。分割?数组 nums?的方案数定义为符合以下两个条件的 pivot?数目：
1 <= pivot < n
nums[0] + nums[1] + ... + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + ... + nums[n - 1]
同时给你一个整数?k?。你可以将?nums?中?一个?元素变为?k?或?不改变?数组。请你返回在 至多?改变一个元素的前提下，最多?有多少种方法 分割?nums?使得上述两个条件都满足。
思路
这个题也算是空间换时间了。我一共用了三个hash表，其中一个维护的是所有的前缀和，两个用于维护i左边和右边的分割差。
我们可以发现 如果修改的是分割位置的左边的值 那么就有之前的差 左 - 右 = d
若修改的是分割位置的右边的值 那么就有之前的差 左 - 右 = -d
其中d = nums[i] - k 就是改变造成了多大的改变。
然后就是用两个是为了分别去判断两边的值。避免发生影响。
int cha1[200010];
int cha2[200010];
int waysToPartition(int* nums, int numsSize, int k){
long long temp[numsSize];
temp[0] = nums[0];
for(int i = 1;i < numsSize;i++) temp[i] = temp[i-1] + nums[i];//求前缀和
int ans = 0;
for(int i = 0;i < numsSize;i++){ //hash初始化用到什么初始化什么
int d = nums[i] - k;
if(d <=100000 && d>=-100000){
cha1[d + 100000] = 0;
cha1[100000 - d] = 0;
cha2[d + 100000] = 0;
cha2[100000 - d] = 0;
}
}
for(int i = 0;i < numsSize - 1;i++){//第一次判断 顺带更新cha1 cha1表示更改值右边的hash表
long long d = 2*temp[i] - temp[numsSize - 1];
if(d <=100000 && d>=-100000) cha1[d+100000]++;
if(d == 0) ans++;
}
for(int i = 0;i < numsSize;i++){
if(i){//更新hash表 i更改会造成cha1 和cha2 的改变
int k = 2*temp[i - 1] - temp[numsSize - 1];
if(k <=100000 && k>=-100000) {cha1[k+100000]--;cha2[k+100000]++;}
}
int now = 0,d = nums[i] - k;
if(d <=100000 && d>=-100000){//根据公式进行判断
now += cha1[d + 100000];
now += cha2[100000 - d];
}
if(now > ans) ans = now;
}
return ans;
}写在最后
今天题不多，并且今天的复习效果也还不错，接下来的两周，都会保存这样的节奏，题解是不会断更的，希望各位看官都能满意。感谢大家的关注！