Day05: 计数法（C语言）
前言 如果你想学好算法和数据结构，请跟随他的脚步： 英雄哪里出来.
大家一起学习，一起打卡，一起成长。
目录
模板题目列表1748.唯一元素的和387.字符串中的第一个唯一字符1941. 检查是否所有字符出现次数相同448. 找到所有数组中消失的数字1512. 好数对的数目1711. 大餐计数
模板
如果题目是有关次数的问题，例如查找出只出现多少次的数字或字符，就可以用这个方法。
#define CAPACITY 100 //题目给出的最大范围
void FindValue(int* nums, int numsSize)
{
if (NULL == nums) //1
return;
int map[CAPACITY] = { 0 }; //2
//3
for (int i = 0; i < numsSize; ++i)
{
map[nums[i]]++;
}
//4 解决方案（题目要求）
}
判空申请一个用来计数的数组，范围太大可以动态申请遍历一遍，主要是统计次数
接下来的几个题目，基本都是按照这个方式来做的
题目列表
1748.唯一元素的和
链接: 唯一元素的和
#define CAPACITY 101
int sumOfUnique(int* nums, int numsSize)
{
if (NULL == nums) //1判空
return 0;
//2.根据题意给出的范围，申请一个计数的数组
//并初始化为0
int count[CAPACITY] = {0};
int ans = 0;
//3.计数
for (int i = 0; i < numsSize; ++i)
{
count[nums[i]]++;
}
//4.据题目要求写方案
for (int i = 0; i < CAPACITY; ++i)
{
if (count[i] == 1)
{
ans += i;
}
}
return ans;
}
387.字符串中的第一个唯一字符
链接: 字符串中的第一个唯一字符
#define CAPACITY 27
int firstUniqChar(char * s)
{
//和上面的解题步骤一样
if (NULL == s) //1
return -1;
int nums[CAPACITY] = {0}; //2
int len = strlen(s);
for (int i = 0; i < len; ++i) //3
{
nums[s[i] - 'a']++;
}
for (int i = 0; i < len; ++i) //4
{
if (nums[s[i] - 'a'] == 1)
{
return i;
}
}
return -1;
}
1941. 检查是否所有字符出现次数相同
链接: 1941. 检查是否所有字符出现次数相同.
#define CAPACITY 26
bool areOccurrencesEqual(char * s)
{
if (NULL == s)
return false;
int map[CAPACITY] = {0};
int count = 0;
for (int i = 0; i < strlen(s); ++i)
{
map[s[i] - 'a']++;
}
for (int i = 0; i < CAPACITY; ++i)
{
if (map[i] != 0 && map[i] != map[s[0] - 'a'])
{
return false;
}
}
return true;
}
448. 找到所有数组中消失的数字
链接: 448. 找到所有数组中消失的数字.
这个题比较特殊，第一是范围较大，可以采用动态申请空间，第二是要返回一个数组，申请动态数组，并根据题目要求返回这个数组的大小
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize)
{
*returnSize = 0;
if (NULL == nums)
return NULL;
//申请动态空间
int* map = (int*)malloc(sizeof(int) * (numsSize + 1));
memset(map, 0, sizeof(int) * (numsSize + 1));
//申请要返回的空间
int* ans = (int*)malloc(sizeof(int) * (numsSize + 1));
for (int i = 0; i < numsSize; ++i)
{
map[nums[i]]++;
}
for (int i = 1; i < numsSize + 1; ++i)
{
if (map[i] == 0)
{
ans[(*returnSize)++] = i;
}
}
free(map);
return ans;
}
1512. 好数对的数目
链接: 1512. 好数对的数目
暴力法 双重循环，根据题目要求来记数
int numIdenticalPairs(int* nums, int numsSize)
{
if (nums == NULL)
return -1;
int count = 0;
for (int i = 0; i < numsSize - 1; ++i)
{
for (int j = i + 1; j < numsSize; ++j)
{
if (nums[i] == nums[j])
{
count++;
}
}
}
return count;
}
哈希表
#define CAPACITY 101
int numIdenticalPairs(int* nums, int numsSize)
{
int map[CAPACITY] = {0};
int ans = 0;
for(int i = 0; i < numsSize; i++)
{
map[nums[i]]++;
ans += map[nums[i]] - 1;
}
return ans;
}
1711. 大餐计数
链接: 1711. 大餐计数
大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
题目示例：
输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。
范围：
题目说出，两道不同餐品组合是2的幂，那反过来想，对每个元素，枚举出它和另一个数的所有和sum，即所有2的幂。那另一个数就是等于 other = sum - num
int map[(1<<21) + 1]; //根据题目要求写范围
int countPairs(int* deliciousness, int deliciousnessSize)
{
if (NULL == deliciousness)
return 0;
memset (map, 0, sizeof(map));
int sum = 0; //用来保存2的幂
int ans = 0; //返回的答案
for(int i = 0; i < deliciousnessSize; ++i)
{
for(sum = 1; sum <= (1<<21); sum *= 2)
{
int other = sum - deliciousness[i];
if (other < 0)
{
continue;
}
ans += map[other];
ans %= 1000000007;
}
map[deliciousness[i]]++;
}
return ans;
}
方法来源 个人感觉这个方法比官方答案更好理解
链接： 英雄哪里出来《算法零基础100讲》.