这是七月集训的第日，今日的训练内容是 ****
解题报告 1.力扣970 原题链接970. 强整数
题目概述解题思路给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。
如果某一整数可以表示为 xi + yj ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。
你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。
首先找到所有的可以的 i 与 j 的最大值，然后开始枚举所有的 i 和 j ，将满足条件的和存入哈希表，然后再利用哈希表构建返回的函数。
源码剖析
int* powerfulIntegers(int x, int y, int bound, int* returnSize)
{
int max_i = log(bound)/log(x);
int max_j = log(bound)/log(y);
if (x == 1) {
max_i = 0;
}
if (y == 1) {
max_j = 0;
}
int* StrongInt = (int*)malloc((bound + 1) * sizeof(int));
memset(StrongInt,0,(bound + 1) * sizeof(int));
for (int i = 0; i <= max_i; i++) {
for (int j = 0; j <= max_j; j++) {
if (pow(x, i) + pow(y, j) <= bound) {
StrongInt[(long long)(pow(x, i) + pow(y, j))] = 1;
}
if (pow(x, i) + pow(y, j) > bound) {
break;
}
}
}
*returnSize = 0;
for (int i = 0; i < bound + 1; i++) {
*returnSize += StrongInt[i];
}
int* ans = (int*)malloc(*returnSize * sizeof(int));
int j = 0;
for (int i = 0; i < bound + 1; i++) {
if (StrongInt[i] == 1) {
ans[j] = i;
j++;
}
}
return ans;
}
2.力扣914
原题链接
914. 卡牌分组
题目概述解题思路给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
首先先将数据填入哈希表，然后再对哈希表内的非 0 数据求取最大公因数即可，这里积累一下一个新的函数，专门用来求最大公因数，在源码剖析中已经写入。
源码剖析int gcd(int a, int b){ //积累一个新的函数，递归求解最大公因数
if(b==0)return a;
else return gcd(b,a%b);
}
bool hasGroupsSizeX(int* deck, int deckSize){
int hash[10000]={0};
int i;
int ret = 0;
for(i=0;i
hash[deck[i]]++;
}
for(i=0;i<10000;++i){
if(hash[i]>0){
ret = gcd(hash[i],ret);
}
}
return ret>=2;
}
3.力扣1497
原题链接
1497. 检查数组对是否可以被 k 整除
题目概述解题思路给你一个整数数组 arr 和一个整数 k ，其中数组长度是偶数，值为 n 。
现在需要把数组恰好分成 n / 2 对，以使每对数字的和都能够被 k 整除。
如果存在这样的分法，请返回 True ；否则，返回 False 。
参考了题解，这题的核心是一种贪心的算法，将所有的数全都对所给的数 k 进行取余，那么首先就是判断不为 0 的部分，这些部分需要全部配对，举个例子，比如现在余数中有 5个1 ，而 k=5 ，那么如果我需要全部都成功配对的话，必须要剩余 5 个 4 才可以，也就是说 mod[i] 的个数与 mod[k-i] 的数量一定要是相同的，才能将这些部分全都成功配对，这样就只需要循环前 k/2 就可以了，而且不需要将 0 带上，余数为 0 代表它只需要和 0 进行配对即可。所以在统计完了上面的非 0 部分之后，在额外判断一下，余数为 0 的个数是否为偶数。
源码剖析bool canArrange(int* arr, int arrSize, int k){
int *mod = (int*)malloc(sizeof(int)*k);
memset(mod, 0, sizeof(int)*k);
for(int i = 0; i
mod[(arr[i]%k+k)%k]++;
}
for(int i = 1; i<=k/2; i++){
if(mod[i]!=mod[k-i])
return false;
}
return mod[0]%2==0;
}
4.力扣面试题 17.05. 字母与数字
原题链接
面试题 17.05. 字母与数字
题目概述解题思路给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
先暂做记录。
源码剖析暑期编程PK赛 得CSDN机械键盘等精美礼品！
