企业网站建设 总结工业设计公司官网

企业网站建设 总结,工业设计公司官网,番禺网站建设系统,酷站哈希表简介 什么是 hash 表#xff1f;hash表就是存储数据的容器 作用#xff1a;快速查找某个元素 什么时候使用hash表#xff1f;频繁查找某个数时#xff0c;可以使用 hash 表 如何使用hash表#xff1f;1.使用hash表容器#xff1b;2.使用数组模拟简易hash表 什么时候…哈希表简介什么是 hash 表hash表就是存储数据的容器作用快速查找某个元素什么时候使用hash表频繁查找某个数时可以使用 hash 表如何使用hash表1.使用hash表容器2.使用数组模拟简易hash表什么时候使用数组模拟hash表1. 字符串中的字符2. 数据范围小算法题目题目11. 两数之和 - 力扣LeetCode题目分析给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。题目示例示例 1输入nums [2,7,11,15], target 9输出[0,1]解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2输入nums [3,2,4], target 6输出[1,2]示例 3输入nums [3,3], target 6输出[0,1]提示2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案算法原理解法1暴力枚举第一种遍历的方式先固定其中一个数依次与后面的数相加是否等于 target第二种遍历的方式先固定其中一个数依次与前面的一个数相加是否等于 target代码实现class Solution { public: vectorint twoSum(vectorint nums, int target) { for(int i 0; i nums.size(); i) { for(int j 0; j i; j) { if(nums[i] nums[j] target) { return {j, i}; } } } return { }; } };解法2使用 hash 表为什么暴力解法这么慢呢因为固定一个数之后需要在前面找一个等于 target – x 的数如固定7就需要在前面找到一个等于 target-x9-72 的数。从前向后找太慢了查找一个数可以使用hash 表。将固定的数的前面的数加入到 hash 表中固定的数改变之前将该数加入到 hash 表中。hash 表需要结合第二种遍历的方法一起使用。为什么使用第一种遍历方法hash 表就不管用了呢使用第二种遍历方法需要先将所有的元素加入到 hash 表中之后固定一个数的时候再去 hash 表中找 target – x 的数。但是如果 nums 中存在元素2而 target 4呢将所有的元素加入到 hash 表中当固定的数为2时在 hash 表中找为2的数能否被找到可以但是满足题目要求吗不能使用两次同一个下标的元素不满足。因此对于这样的情况需要判断一些边界情况太麻烦了。代码实现class Solution { public: vectorint twoSum(vectorint nums, int target) { // 创建一个hash表 存的是元素和对应元素的下标 unordered_mapint, inthash(nums.size()); // 遍历nums数组 for(int i 0; i nums.size(); i) { int val target - nums[i]; // 如果存在 target-nums[i],则直接返回 if(hash.count(val)) { return {hash[val], i}; } // 如果不存在加入hash表 hash[nums[i]] i; } return {}; } };题目2面试题 01.02. 判定是否互为字符重排 - 力扣LeetCode题目分析给定两个由小写字母组成的字符串s1和s2请编写一个程序确定其中一个字符串的字符重新排列后能否变成另一个字符串。题目示例示例 1输入:s1 abc, s2 bca输出:true示例 2输入:s1 abc, s2 bad输出:false算法原理如果一个字符串是另一个字符串重排列后的结果它们会有一个相同的特点字母出现的次数都相等。因此只需要统计字符串 s1 中每个字母出现的次数s2 中每个字母出现的次数在比较对应字母出现的次数是否相等。统计每个字母出现的次数使用hash表。可以使用数组模拟实现 hash 表为什么可以因为题目说了字符串全是小写字母构成数据范围小。创建两个 hash 表遍历两个字符串分别将字符加入 hash 表最后比较两个hash表是否相等。当然还可以在此基础进行优化只使用一个 hash 表遍历一个字符串将该字符串中的字母加入到 hash 表中其次遍历另一个字符串将遍历到的字符在 hash 表中减去如果最终 hash 表中的元素个数为0说明满足题目要求。如果某个字符出现的次数为负数那么要么这个字符是多余的要么是 hash 表中没有的也说明了不满足题目要求。其次可以做一些小优化如果一个字符串是另一个字符串重排列后的结果那么这两个字符串的长度一定相等若两个字符串的长度不相等那么根本就不需要进行下一步操作。代码实现class Solution { public: bool CheckPermutation(string s1, string s2) { if(s1.length() ! s2.length()) { return false; } // 使用数组模拟hash表 int hash[26] { 0 }; // 加入hash表 for(auto ch : s1) { hash[ch - a]; } for(auto ch : s2) { hash[ch - a]--; // 如果出现负数直接返回false if(hash[ch - a] 0) { return false; } } return true; } };题目3217. 存在重复元素 - 力扣LeetCode题目分析给你一个整数数组nums。如果任一值在数组中出现至少两次返回true如果数组中每个元素互不相同返回false。题目示例示例 1输入nums [1,2,3,1]输出true解释元素 1 在下标 0 和 3 出现。示例 2输入nums [1,2,3,4]输出false解释所有元素都不同。示例 3输入nums [1,1,1,3,3,4,3,2,4,2]输出true算法原理使用《两数之和》题目的思想固定一个数在这个数的前面找是否出现相同的元素。解法hash 表class Solution { public: bool containsDuplicate(vectorint nums) { // 创建hash表,由于不需要存下标因此使用set unordered_setint hash; // 遍历nums数组 for(int i 0; i nums.size(); i) { // 如果hash表中存在nums[i]直接返回true if(hash.count(nums[i])) { return true; } // 如果hash表中不存在nums[i]加入hash表 hash.insert(nums[i]); } // 出循环了说明不存在重复的元素返回false return false; } };题目4219. 存在重复元素 II - 力扣LeetCode题目分析给你一个整数数组nums和一个整数k判断数组中是否存在两个不同的索引i和j满足nums[i] nums[j]且abs(i - j) k。如果存在返回true否则返回false。题目示例示例 1输入nums [1,2,3,1], k 3输出true示例 2输入nums [1,0,1,1], k1输出true示例 3输入nums [1,2,3,1,2,3], k2输出false算法原理这道题与《存在重复元素I》解法相似只不过在判断是否存在重复元素时需要判断两个重复元素的下标之差是否小于等于k。因此创建的 hash 表中需要存两个元素元素和元素对应的下标。固定一个数看该数前面是否存在相同的元素如果存在还需比较这两个相同的数的下标查是否等于 k如果小于相等返回 true。如果不相等加入 hash 表中这样会将相同的元素给覆盖掉如此还能找到最终结果吗当然可以代码实现class Solution { public: bool containsNearbyDuplicate(vectorint nums, int k) { // 创建hash表 unordered_mapint, int hash; // 遍历nums数组 for(int i 0; i nums.size(); i) { int val nums[i]; // 如果hash表中存在等于val的元素且对应元素的下标相减小于等于k直接返回true if(hash.count(val) i - hash[val] k) { return true;} // 如果hash表中不存在等于val的元素或者对应元素的下标相减不小于等于k加入到hash表中 hash[val] i; } return false; } };题目549. 字母异位词分组 - 力扣LeetCode题目分析给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。题目示例示例 1:输入:strs [eat, tea, tan, ate, nat, bat]输出:[[bat],[nat,tan],[ate,eat,tea]]解释在 strs 中没有字符串可以通过重新排列来形成bat。字符串nat和tan是字母异位词因为它们可以重新排列以形成彼此。字符串ateeat和tea是字母异位词因为它们可以重新排列以形成彼此。示例 2:输入:strs []输出:[[]]示例 3:输入:strs [a]输出:[[a]]提示1 strs.length 1040 strs[i].length 100strs[i]仅包含小写字母算法原理解法hash表首先需要判断两个字符是否是字母异位词如果使用 hash 表来统计两个字符串的字母出现的次数是否相等会有点麻烦。可以使用排序两个字符串排序之后如果相等那么这两个字符串就是字母异位词。接下来考虑如何分组如何将字母异位词分成一组这就体现出泛型编程的强大之处了hash的参数类型为 string和 vectorstring。最终遍历一遍 hash 表将 hash 表中的 value 值提取出来。代码实现class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { // 创建一个hash表 unordered_mapstring, vectorstring hash; // 根据字符串排好序的结果进行分组 for(string str : strs) { // 将字符串排好序,不要对str操作 string tmp str; sort(tmp.begin(), tmp.end()); // 若排序后字符串相等,则进入同一个字符串数组 // hash[tmp]的类型是vectorstring,可以调用push_back函数 hash[tmp].push_back(str); } // 返回值 vectorvectorstring ret; // 遍历hash表 for(auto [k, v] : hash) { ret.push_back(v); } return ret; } };知识回顾深入浅出哈希表-CSDN博客深入理解STL关联容器map/multimap与set/multiset全解析-CSDN博客