在刷题的时候你会发现,对于数组和字符串的题目,经常会用到哈希表这个知识点。那么什么是哈希表,或者说哈希表的定义又是啥,如果你去网上查,会有很多关于哈希表的定义,这里我们不再阐述哈希表的定义。
哈希表来解决问题的时候,一般选择以下三种数据结构。
- 数组
set集合map映射
本篇先说数组:通过数组来使用哈希表的知识,也就可以说是哈希数组,什么哈希数组?
举个例子:给定一个数组A,根据数组A来解决一个问题。
为解决问题,我们 新建一个数组B,把数组A的值作为数组B的索引,数组B就是哈希数组。
通俗的讲,哈希数组就是把一个数组的值作为自己的索引,这个数组就是哈希数组,后续对哈希数组进行什么操作,根据题意进行模拟就行。
什么时候使用哈希表这个知识点呢,大多数情况下,当题目中出现重复元素的时候,就应该考虑是否可以使用哈希表来解决问题。
例题:出现频率最高的字母。
这道例题很好的诠释了哈希表的基本概念,以及如何通过数组这个数据结构来使用哈希表的知识,并解决问题。
题目描述
给定一个只包含小写字母的字符串,统计字符串中每个字母出现的频率,并找出出现频率最高的字母,如果最高频率的字母有多个,输出字典序靠前的那个字母。
输入描述
包含多组测试数据,每组测试数据占一行。
输出描述
有多组输出,每组输出占一行。
输入示例
2 abcdeef aabbccddeeff输出示例
e a例题中,给出一个字符串,要求统计出现频率最高的字符。
思路:如果把每个字符的总数都记录下来,再进行比较,那么总数最大的就是我们所求的,如果存在多个出现次数相同的字符,那就输出英文字母表中靠前的就可以,那么怎么记录每个字符出现的次数,并且能把字符和出现的次数对应上呢,这就用到哈希表的知识点。
方法:新建一个数组res,数组长度26,数组索引为0,1,2,···,25,我们让0代表a,1代表b,以此类推,25代表z,res[0]的值就代表a出现的次数,res[1]的值就代表b出现的次数,如果a的次数和b的次数相同,那就输出a,到此问题就解决。
上面我们提到,哈希数组就是把一个数组的值作为自己的索引,这里是字符串,把字符串转换成数组就可以,道理都是一样的,例如:str = [a,b,c,d,e],对于res来说,res的索引为0,1,2,···,这里0对应a,1对应b,这里有一种对应关系,这不就是把str的值当成res的索引。
如果还不能理解,把题意换一下,求一个整数数组中,数字出现次数最多的数字,数组元素仅包含0~9,即ans=[0,3,4,2,1],同理,res的索引为0,1,2等,这里的0,1,2就是ans的值,只不过相比上面的str,ans是直接将数组值作为res的索引,str是间接的将数组值作为res的索引。
以下是完整Java代码:
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); for (int i = 0; i < n; i++) { String input = scanner.next(); char mostFrequentChar = findMostFrequentChar(input); // 调用方法获取字符 System.out.println(mostFrequentChar); } scanner.close(); } // 找到最大频次字符的方法 public static char findMostFrequentChar(String input) { int[] frequency = new int[26]; for (char c : input.toCharArray()) { frequency[c - 'a']++; } char mostFrequentChar = 'a'; int maxFrequency = frequency[0]; for (int i = 1; i < 26; i++) { if (frequency[i] > maxFrequency) { maxFrequency = frequency[i]; mostFrequentChar = (char) ('a' + i); } } return mostFrequentChar; } }如果给出的例题不好理解,请参考如下例题;力扣:面试题 01.01.判定字符是否唯一。
题目要求
实现一个算法,确定一个字符串s的所有字符是否全都不同。
示例 1:
输入:s= "leetcode"输出:false示例 2:
输入:s= "abc"输出:true限制:
0 <= len(s) <= 100s[i]仅包含小写字母
解题思路和方法是一样的,不再阐述,以下是C语言完整代码:
bool isUnique(char* astr){ int *result = (int *)calloc(26,sizeof(int)); int len = strlen(astr); int i; for(i=0;i<len;i++){ result[astr[i] - 97] = result[astr[i] - 97] + 1; } for(i=0;i<26;i++){ if(result[i] > 1){ return false; } } return true; }附:以上内容中,第一道例题和例题代码均来自卡码网,若有侵权,将第一时间内删除。其余内容为自己撰写,若有错误,将在第一时间进行修改。