中国建设银行建银购网站,金堂企业网站建设,住建局哪个科室最吃香,国外域名注册公司算法刷题-哈希表
242. 有效的字母异位词
给定两个字符串 *s* 和 *t* #xff0c;编写一个函数来判断 *t* 是否是 *s* 的字母异位词。
**注意#xff1a;**若 *s* 和 *t* 中每个字符出现的次数都相同#xff0c;则称 *s* 和 *t* 互为字母异位词。
思路
用一个哈希表来记…算法刷题-哈希表
242. 有效的字母异位词
给定两个字符串 *s* 和 *t* 编写一个函数来判断 *t* 是否是 *s* 的字母异位词。
**注意**若 *s* 和 *t* 中每个字符出现的次数都相同则称 *s* 和 *t* 互为字母异位词。
思路
用一个哈希表来记录第一个字符串每个字符出现的次数然后遍历第二个字符串减去他的字母出现的次数
最后如果哈希表每个值都是0说明符合题意
代码 bool isAnagram(string s, string t) {mapchar,int m;for(char c:s) m[c];for(char c:t) m[c]--;for(auto [x,y]:m) {if(y!0) return false;}return true;}349. 两个数组的交集
给定两个数组 nums1 和 nums2 返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
思路
用一个set记录第一个数组出现了哪些元素然后再开一个set记录两个数组都出现的元素即可
代码 vectorint intersection(vectorint nums1, vectorint nums2) {vectorint res;setint s,s2;for(int x:nums1) s.insert(x);for(int x:nums2){if(s.count(x)) s2.insert(x);} for(int x:s2) res.push_back(x);return res;}202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为
对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是 无限循环 但始终变不到 1。如果这个过程 结果为 1那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true 不是则返回 false 。
思路
写一个函数f来计算每次变化后的结果
用一个哈希表来存n能变到哪些数字如果第二次变到哈希表里的数字说明有循环退出即可
代码 int f(int n){int x0;while(n) x(n%10)*(n%10),n/10;return x;}bool isHappy(int n) {setint s;while(1){if(n1) return 1;if(s.count(n)) return 0;s.insert(n);nf(n);}}1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
思路
用一个哈希表记录每个数字出现的位置
再遍历一次数组如果nums[i]-target在哈希表中存在说明找到了直接返回
代码 vectorint twoSum(vectorint nums, int target) {mapint,int m;int nnums.size();for(int i0;in;i) m[nums[i]]i;for(int i0;in;i){int jm[target-nums[i]];if(j!0j!i) return {i,j};}return {0,0};}454. 四数相加 II
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
思路
先将nums1和nums2所有可能得到的值的组合存到哈希表中
在遍历nums3和nums4判断0-nums3[i]-nums4[j]在不在哈希表中
时间复杂度为 O ( n 2 ) O(n^2) O(n2)
代码 int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {mapint,int m;for(int x:nums1)for(int y:nums2)m[xy];int res0;for(int x:nums3)for(int y:nums4)if(m[0-x-y]!0)resm[0-x-y];return res;}383. 赎金信
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以返回 true 否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
思路
将第二个字符串的每个字符出现的次数存入到哈希表中
在遍历第一个字符串对应出现的次数减去
最后判断是否有出现次数0的字母说明不符合题意
代码 bool canConstruct(string ransomNote, string magazine) {mapchar,int m;for(char c:magazine) m[c];for(char c:ransomNote) m[c]--;for(auto [x,y]:m) if(y0) return false;return true;}15. 三数之和
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
**注意**答案中不可以包含重复的三元组。
思路
先对数据进行排序然后遍历一次数组双指针不断缩小范围
代码 vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());vectorvectorint res;int nnums.size();for(int k0;kn-2;k){if(nums[k]0) break;if(k0nums[k]nums[k-1]) continue;int ik1,jn-1;while(ij){int sumnums[k]nums[i]nums[j];if(sum0)while(ij nums[i]nums[i]);else if(sum0) while(ij nums[j] nums[--j]);else{res.push_back({nums[i],nums[j],nums[k]});while(ijnums[i]nums[i]);while(ijnums[j]nums[--j]);}}}return res;}18. 四数之和
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。
思路
和三数之和一样双指针算法。
代码 vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorint res;int nnums.size();for(int k0;kn;k){if(nums[k]targetnums[k]0) break;if(k0 nums[k]nums[k-1] ) continue;for(int ik1;in;i){if(ik1 nums[i]nums[i-1]) continue;int li1,rn-1;while(lr){long long sum(long long)nums[k]nums[i]nums[l]nums[r];if(sumtarget) r--;else if(sumtarget) l;else {res.push_back({nums[k],nums[i],nums[l],nums[r]});while(lr nums[l]nums[l1])l;while(lr nums[r]nums[r-1]) r--;r--,l;}}}}return res;}
