admin 管理员组

文章数量: 887006

哈希表通俗解释，leetcode

本人转码小白，刚刚学习到哈希表。欢迎各位大佬批评指正。

算法思想来自博客代码随想录。(不是打广告啊，自学实在需要一些参考)

浅聊一下哈希表：

哈希表：又叫散列表，用来快速判断一个元素是否出现在集合里。(数组就是一个哈希表)

哈希函数：将一个某个数据成员，映射成一个数，并将其放在哈希表中。

举个人话的例子：

水果店里苹果单价2.5元，香蕉单价3.1元，菠萝...,如何快速查到某种水果的单价?这时需要用到哈希函数。

先用哈希函数进行映射：

然后，放到一个哈希表(数组)中，over。

方法比较：

传统找单价方法：输入苹果，遍历所有水果，找到苹果，输出2.5.      O(n)

哈希方法：输入苹果，输出映射001，找到001索引对应的2.5。         O(1)

哈希碰撞：学到了再聊....

1.题目描述：

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

字母异位词：每个字符出现字数相同。比如s = "aee" ，t = "eae"

2.题解思路：

1.定义一个长度为26的数组(哈希表)

2.把字符串中的'a','b','c'...'z'分别映射到0,1,2....25。(即数组的索引上)

3.s中的字母每出现一次，数组索引对应的值加1。

   t中的字母每出现一次，数组索引对应的值减1。

4.遍历结束后，如果数组中的元素全是0，证明s和t为字母异位词。

举例子：假设 s = "aee" ，t = "eae"

3.本地实现

#include<iostream>
#include<string>
using namespace std;class Solution
{
public:bool isAnagram(string s, string t){int hash[26] = { 0 };//创建一个长度为26的，全是0的数组，作为哈希表//遍历s，把字母a、b、c....转化成数字0、1、2.....。哈希函数的思想for (int i = 0; i < s.size(); i++){hash[s[i] - 'a']++;  //一种映射方法，保证'a'对应的是0。每出现一次，增加1}//遍历tfor (int i = 0; i < t.size(); i++){hash[t[i] - 'a']--;  //每出现一次，减少1}//遍历一边hash表，如果全是0，两字符串为字母异位for (int i = 0; i < (sizeof(hash) / sizeof(hash[0])); i++){if (hash[i] != 0) return false;//一旦表内有不为1，返回false}return true;//表内全是0，返回true}
};int main()
{string s = "abc",t = "bca";Solution solution;cout << solution.isAnagram(s, t) << endl;system("pause");return 0;
}

码字不易，谢谢访问。

本文标签： 哈希表通俗解释，leetcode

版权声明：本文标题：哈希表通俗解释，leetcode 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732361508h1535347.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。