文章目录
知识讲解
??字符计数法的方法和原理都很简单，原理就是对ASCLL码的引用。
使用方法：
例如我们要统计一个字符串里，小写字母出现的个数
int count(char *s){
int Hash[26] = { 0 };
int n = strlen(s);
for(int i = 0; i < n; i++){
Hash[s[i] - 'a']++;
}
}
通过下标来(0~25)表示26个小写字母(a ~ z)。
课后习题
1. 判定字符是否唯一
题目链接：
面试题 01.01. 判定字符是否唯一
这道题我们只需用数组统计每个字母的出现次数，找出只出现过一次的字母即可。
代码如下：
bool isUnique(char* astr){
int Hash[26] = { 0 };
int n = strlen(astr);
for(int i = 0; i < n; i++){
if(astr[i] >= 'a'){
Hash[astr[i]- 'a']++;
}
else{
Hash[astr[i]- 'A']++;
}
}
for(int i = 0; i < 26; i++){
if(Hash[i] > 1){
return false;
}
}
return true;
}
这种写法可以过力扣上的全部例子，但是有一种特殊情况不行
所以正确的写法应该如下：
bool isUnique(char* astr){
int Hash[256] = { 0 };
int n = strlen(astr);
for(int i = 0; i < n; i++){
Hash[astr[i]]++;
}
for(int i = 0; i < 256; i++){
if(Hash[i] > 1){
return false;
}
}
return true;
}
2. 第一个只出现一次的字符
题目链接：
剑指 Offer 50. 第一个只出现一次的字符
思路分析：
??由于我们字符串中只有小写字母，所以我们只需考虑小写的情况即可。
代码如下：
char firstUniqChar(char* s){
int Hash[26] = { 0 };
int n = strlen(s);
for(int i = 0; i < n; i++){
Hash[s[i] - 'a']++;
}
for(int i = 0; i < n; i++){
if(Hash[s[i] - 'a'] == 1){
return s[i];
}
}
return ' ';
}
3. 赎金信
题目链接：
383. 赎金信
思路分析：
??这道题其实就是让我们判断是否能用magazine中的字符来表示ransomNota中的字符，所以我们只需要统计两个字符串中的字符类型与个数，然后进行比较，如果ransomNota中有的magazine中都有，则返回true；
代码如下：
bool canConstruct(char * ransomNote, char * magazine){
int n1 = strlen(ransomNote);
int n2 = strlen(magazine);
int arr1[26] = { 0 };
int arr2[26] = { 0 };
for (int i = 0; i < n1; i++){
arr1[ransomNote[i] - 'a']++;
}
for (int i = 0; i < n2; i++){
arr2[magazine[i] - 'a']++;
}
for (int i = 0; i < 26; i++){
if (arr2[i] < arr1[i]){
return false;
}
}
return true;
}
4. 宝石与石头
题目链接：
771. 宝石与石头
思路分析：
??这道题很简单，我们只需要将 j 中出现的字母用下标对应的方法记录下来，然后再遍历字符串 s，计算s中有多少个属于 j 中的字母。
代码如下：
int numJewelsInStones(char * jewels, char * stones){
int num = 0;
int n = strlen(jewels);
int Hash[123] = { 0 };
//标记宝石
for(int i = 0; i < n; i++){
Hash[jewels[i]]++;
}
int m = strlen(stones);
for(int i = 0; i < m; i++){
//判断是否是宝石
if(Hash[stones[i]] > 0){
num++;
}
}
return num;
}
5. 判定是否互为字符重排
题目链接：
面试题 01.02. 判定是否互为字符重排
思路分析：
??这道题和之前的方法都一样，用数组将s1和s2两个字符串的字符都记录下来，如果它们的字符种类和数目都相同，则s2可以通过重新排序得到s1。
代码如下：
bool CheckPermutation(char* s1, char* s2){
int n1 = strlen(s1);
int n2 = strlen(s2);
//判断特殊情况
if(n1 != n2){
return false;
}
int Hash1[123] = { 0 };
int Hash2[123] = { 0 };
for(int i = 0; i < n1; i++){
//分别记录s1和s2的字符及个数
Hash1[s1[i]]++;
Hash2[s2[i]]++;
}
for(int i = 0; i < 123; i++){
//判断字符数量是否相同
if(Hash1[i] != Hash2[i]){
return false;
}
}
return true;
}
6. 检查是否所有字符出现次数相同
1941. 检查是否所有字符出现次数相同
思路分析：
??我们还是用数组的方式对字符串中的字符进行计算，并同时用一个变量记录其中某个字符的数量，然后再拿数组中的数据与其进行比较是否相同，如果出现不同的字符的数量则直接返回false。
代码如下：
bool areOccurrencesEqual(char * s){
int arr[26] = { 0 };
int len = strlen(s);
int n = 0;
for(int i = 0; i < len; i++){
//计算每种字符的数量
arr[s[i] - 'a']++;
//记录某一个字符的数量
n = arr[s[i] - 'a'];
}
for(int i = 0; i < 26; i++){
//为0则说明没出现该字符，直接跳过
if(arr[i] == 0){
continue;
}
else if(arr[i] != n){
return false;
}
}
return true;
}
7. 242. 有效的字母异位词
题目链接：
242. 有效的字母异位词
这道题和判断是否为字符重排这道题的做法是一样的。
代码如下：
bool isAnagram(char * s, char * t){
int n1 = strlen(s);
int n2 = strlen(t);
if(n1 != n2){
return false;
}
int arr1[26] = { 0 };
int arr2[26] = { 0 };
for (int i = 0; i < n1; i++){
arr1[s[i] - 'a']++;
arr2[t[i] - 'a']++;
}
for (int i = 0; i < 26; i++){
if (arr2[i] != arr1[i]){
return false;
}
}
return true;
}
8. 有效的变位词
题目链接：
剑指 Offer II 032. 有效的变位词
这道题和上面那道是相似的，就是多了一个条件：若 s 和 t 中每个字符出现的次数都相同且字符顺序不完全相同，则称 s 和 t 互为变位词（字母异位词）。
所以我们还需判断两个字符串是否为相同的字符串。
代码如下：
bool isAnagram(char * s, char * t){
int n1 = strlen(s);
int n2 = strlen(t);
if(n1 != n2){
return false;
}
int arr1[26] = { 0 };
int arr2[26] = { 0 };
int flag = 1;
for (int i = 0; i < n1; i++){
if(s[i] != t[i]){//判断是否有不相同的串
flag = 0;
}
arr1[s[i] - 'a']++;
arr2[t[i] - 'a']++;
}
if(flag){
return false;
}
for (int i = 0; i < 26; i++){
if (arr2[i] != arr1[i]){
return false;
}
}
return true;
}
9. 判断句子是否为全字母句
题目链接：
1832. 判断句子是否为全字母句
思路分析：
??题目要求是判断所给的句子是否为全字母句，而全字母句就是所有字母都至少出现过一次的句子，所以我们只需用数组记录句子中出现的字母，然后再遍历数组。
代码如下：
bool checkIfPangram(char * sentence){
int n = strlen(sentence);
//长度小于26的句子一定不是全字母句
if(n < 26){
return false;
}
int Hash[26] = { 0 };
for(int i = 0; i < n; i++){
Hash[sentence[i] - 'a']++;
}
for(int i = 0; i < 26; i++){
if(Hash[i] == 0){
return false;
}
}
return true;
}
10. 数组中第 K 个独一无二的字符串
题目链接：
2053. 数组中第 K 个独一无二的字符串
这道题稍微有一点点难度
思路分析：
??我的解法还是比较暴力的
- 首先我们需要定义一个数组dp用来记录所有只出现过一次的数组的位置。
- 然后我们遍历所有的字符串，用strcmp进行比较，将重复出现的串用数组dp标记为0.
- 最后我们遍历数组dp，找到第k个未被标记的下标，然后将该下标对应的串返回即可，如果没有则返回""
代码如下：
int dp[1001];
char * kthDistinct(char ** arr, int arrSize, int k){
//初始化数组
memset(dp, 1, sizeof(dp));
//遍历所有数组，并将重复出现的串标记为0
for(int i = 0; i < arrSize; i++){
//如果dp[i] == 0说明以及比较过了
if(dp[i] == 0){
continue;
}
for(int j = 0; j < arrSize; j++){
if(dp[j] == 0)continue;
if(i == j)continue;
if(strcmp(arr[i], arr[j]) == 0){
dp[i] = 0;
dp[j] = 0;
}
}
}
for(int i = 0; i < arrSize; i++){
if(dp[i]){
k--;
}
if(!k){
return arr[i];
}
}
return "";
}
