青岛网站建设哪个好,外贸网络推广怎么做,乡镇网站个人做可以不,淄博哪里做网站本专栏内容为#xff1a;算法学习专栏#xff0c;分为优选算法专栏#xff0c;贪心算法专栏#xff0c;动态规划专栏以及递归#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习#xff0c;你可以了解并掌握算法。 #x1f493;博主csdn个人主页#xff1a;小… 本专栏内容为算法学习专栏分为优选算法专栏贪心算法专栏动态规划专栏以及递归搜索与回溯算法专栏四部分。 通过本专栏的深入学习你可以了解并掌握算法。 博主csdn个人主页小小unicorn ⏩专栏分类算法从入门到精通 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 专题十 哈希表简介什么时候用哈希表怎么用哈希表 面试题 01.02. 判定是否互为字符重排算法原理 存在重复元素算法原理 存在重复元素 II算法原理 字母异位词分组算法原理 哈希表简介
在介绍本专题前我们先介绍一下什么是哈希表
哈希表就是一个容器它的用途就是可以快速查找元素它的时间复杂度是O(1)级别空间复杂度就是O(N也就是用空间换时间。
什么时候用哈希表
介绍了什么是哈希表那么什么时候可以用哈希表 记住一点当我们要频繁的进行查找某一个数的时候这时候我们就可以考虑用哈希表。当然提到查找也不要忘了我们之前学过的二分算法也可用来查找元素。
怎么用哈希表
提到怎么用通常情况下容器里面的哈希表我们可以直接拿来用其次就是我们可以用一个数组来模拟哈希表。 通常会用在两个场景一是在处理字符串中的字符的时候我们可以用数组来建议模拟哈希表方便做到快速查找。 其次当数据量很小的时候我们也可以直接考虑用数组来模拟哈希表。
面试题 01.02. 判定是否互为字符重排
题目来源Leetcode面试题 01.02. 判定是否互为字符重排 给定两个由小写字母组成的字符串 s1 和 s2请编写一个程序确定其中一个字符串的字符重新排列后能否变成另一个字符串。
算法原理
在判断字符重不重排首先我们要先判断这两个字符串的长度是否一致长度都不一致肯定无法重排。
判断两个字符串能否构成重排最暴力就是直接仍在两个哈希表里然后判断这两个哈希表是否相等但是这样太麻烦了。 我们可以进行优化用数组模拟哈希表因为全都是小写字母那么我们直接开一个大小为26的一个字符数组。
遍历第一个数组碰到一个字母就对应然后遍历第二个数组碰到对应字符数组中字母相同就对应–。同时判断数组下标如果说下标0了那就说明该字符在第一个数组中就不存在不能构成重排。
代码实现
class Solution
{
public:bool CheckPermutation(string s1, string s2) {int ns1.size(),ms2.size();if(n!m)return false;char hash[26];//遍历第一个数组for(auto S1:s1){hash[S1-a];}//遍历第二个数组for(auto S2:s2){hash[S2-a]--;if(hash[S2-a]0)return false;}return true;}
};存在重复元素
题目来源Leetcode217存在重复元素 给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 返回 true 如果数组中每个元素互不相同返回 false 。
算法原理
解法用哈希表 固定1位置看1位置前面有没用相同元素没有就继续向后移动看2位置前面有没有相同元素没有就继续向后移动依次内推。
代码实现
class Solution
{
public:bool containsDuplicate(vectorint nums) {unordered_setint hash;for(auto x:nums){//存在相同元素if(hash.count(x))return true;elsehash.insert(x);}return false;}
};存在重复元素 II
题目来源Leetcode219存在重复元素 II 给你一个整数数组 nums 和一个整数 k 判断数组中是否存在两个 不同的索引 i 和 j 满足 nums[i] nums[j] 且 abs(i - j) k 。如果存在返回 true 否则返回 false 。
算法原理
本题跟上一题的思路基本一样但是本题要保证两个相同元素的下标差的绝对值要小于K。 哈希表里面第一个存nums[i]用来判断有没有重复元素第二个存对应的下标。因为要判断下标关系是否符合要求。跟第一题私立基本一样固定一个数看前面有没有重复元素。 没有就向右移动。
代码实现
class Solution
{
public:bool containsNearbyDuplicate(vectorint nums, int k) {unordered_mapint,int hash;for(int i0;inums.size();i){if(hash.count(nums[i])){if(i-hash[nums[i]]k)return true;}//找不到把当前下标插入到哈希表里面hash[nums[i]]i;}return false;}
};字母异位词分组
题目来源49.字母异位词分组 给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 算法原理
先把题目例子分析一遍可以将例子进行分组。 最后把每个组输出即可。
那么如何判断两个字符串是否是字母异位词呢 这里我们可以排序我们将字符串排完序如果可以字母异位那么他们排完序后的ASLL码值肯定都是一样的。
2.如何进行分组 这里我们就要合理用我们的哈希表。 我们将key定义为string,将val定义为字符串数组。 遍历字符串数组遍历第一个字符排序然后看在不在哈希表不在就加入到key和val然后遍历第二个字符串排完序看跟哈希表里面key匹不匹配匹配就加入到val循环此过程遍历完整个字符串数组后把哈希表里面的val全部取出来即可。
代码实现
class Solution
{
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring,vectorstring hash;//1.把所有的异位字母词分组for(auto s:strs){string tmps;sort(tmp.begin(),tmp.end());hash[tmp].push_back(s);}//2.提取结果vectorvectorstring ret;for(auto [x,y]: hash){ret.push_back(y);}return ret;}
};
