Java教程

[题解]《算法零基础100讲》(第24讲) 字符串算法(四) - 字符计数法

本文主要是介绍[题解]《算法零基础100讲》(第24讲) 字符串算法(四) - 字符计数法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 知识讲解
  • 课后习题
    • 1. 判定字符是否唯一
    • 2. 第一个只出现一次的字符
    • 3. 赎金信
    • 4. 宝石与石头
    • 5. 判定是否互为字符重排
    • 6. 检查是否所有字符出现次数相同
    • 7. 242. 有效的字母异位词
    • 8. 有效的变位词
    • 9. 判断句子是否为全字母句
    • 10. 数组中第 K 个独一无二的字符串

知识讲解

  字符计数法的方法和原理都很简单,原理就是对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 个独一无二的字符串
这道题稍微有一点点难度
思路分析:
  我的解法还是比较暴力的

  1. 首先我们需要定义一个数组dp用来记录所有只出现过一次的数组的位置。
  2. 然后我们遍历所有的字符串,用strcmp进行比较,将重复出现的串用数组dp标记为0.
  3. 最后我们遍历数组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 "";
}

在这里插入图片描述

这篇关于[题解]《算法零基础100讲》(第24讲) 字符串算法(四) - 字符计数法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!