欢迎光临散文网 会员登陆 & 注册

Leetcode Hash table 哈希表【代码随想录Part 3.1】

2023-07-17 20:27 作者:Poyo_a  | 我要投稿


终于来到了day6,尊嘟很不容易坚持下来

【242. 有效的字母异位词】

输入: s = "anagram", t = "nagaram"输出: true

【个人第一次读题的感受】: 就是判断各个字母出现的次数是不是一样的,但是毫无头绪。

咱们就逆向工程一下,学习别人如何用hash table来解决:

               由于只由a~z 26个字母,ASCII码为连续的。

  1. 声明一个数组,用来记录字符串s里字符出现的次数。具体做法是:ASCII是连续的数值,所以字符a映射下标为0,以此类推,z的下标为25.

  2. 再遍历 字符串s的时候,只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可,并不需要记住字符a的ASCII,只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数,统计出来了。最后利用for循环来消除出现过的。如果最后record有不为0的部分,那么就是false




还要数组,计算机真是麻烦


【技术总结】:这道题目想不出来其实是对哈希表不熟悉。其实哈希表就是一个连连看找对应的过程。其中数据规模较小的话,使用数组来记录数据。

其次,通过对字符串的元素依次访问求出“偏移量”存进record里面。

最后就是,利用访问t字符串以及偏移量去访问元素,减去访问过的。

如果是相同的字符串,那么它们应该是 0.true


还有3个题,但是太苦手了。明天再解决两个题8


Leetcode Hash table 哈希表【代码随想录Part 3.1】的评论 (共 条)

分享到微博请遵守国家法律