网站面试通知表格怎么做,考试报名费悦生活建设银行网站,大一做家教的网站,可以用手机做网站吗一#xff1a;哈希表
一般哈希表都是用来快速判断一个元素是否出现集合里。
直白来讲其实数组就是一张哈希表#xff0c;哈希表中关键码就是数组的索引下标#xff0c;然后通过下标直接访问数组中的元素。
1.两数之和
题目链接#xff1a;. - 力扣#xff08;LeetCode…一哈希表
一般哈希表都是用来快速判断一个元素是否出现集合里。
直白来讲其实数组就是一张哈希表哈希表中关键码就是数组的索引下标然后通过下标直接访问数组中的元素。
1.两数之和
题目链接. - 力扣LeetCode
// 哈希表
class Solution {
public:vectorint twoSum(vectorint nums, int target) {std::unordered_map int, int map;for(int i 0; i nums.size(); i){auto iter map.find(target - nums[i]);if(iter ! map.end()){return {iter-second, i};}else{map.insert(pairint, int(nums[i], i));}}return {};}
};
本题其实有四个重点
为什么会想到用哈希表 本题呢我就需要一个集合来存放我们遍历过的元素然后在遍历数组的时候去询问这个集合某元素是否遍历过也就是 是否出现在这个集合。那么我们就应该想到使用哈希法了。 哈希表为什么用map 这道题目中并不需要key有序选择std::unordered_map 效率更高 本题map是用来存什么的 map目的用来存放我们访问过的元素因为遍历数组的时候需要记录我们之前遍历过哪些元素和对应的下标这样才能找到与当前元素相匹配的也就是相加等于target map中的key和value用来存什么的 这道题 我们需要 给出一个元素判断这个元素是否出现过如果出现过返回这个元素的下标。 那么判断元素是否出现这个元素就要作为key所以数组中的元素作为key有key对应的就是valuevalue用来存下标。 所以 map中的存储结构为 {key数据元素value数组元素对应的下标}。 2. 字母异位词分组 class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {mapstring, int myhash;vectorvectorstring myAns;int cint 0;for(int i 0; istrs.size(); i){string temString strs[i];sort(temString.begin(), temString.end());auto iter myhash.find(temString);if(iter myhash.end()){myAns.push_back(vectorstring());myAns.back().push_back(strs[i]);myhash[temString]cint;cint ;}else{int index myhash[temString];myAns[index].push_back(strs[i]);}}return myAns;}
}; 3.最长连续序列 class Solution {
public:int longestConsecutive(vectorint nums) {unordered_setint myset;for(const int num : nums){myset.insert(num);}int longestStreak 0;for(const int num : myset){if(myset.count(num-1) 0){int currentNum num;int currentStreak 1;while(myset.count(currentNum 1)){currentNum currentNum 1;currentStreak currentStreak 1; }longestStreak max(longestStreak, currentStreak);}}return longestStreak;}
}; 二双指针
1.移动零 // 使用双指针左指针指向当前已经处理好的序列的尾部右指针指向待处理序列的头部。
// 右指针不断向右移动每次右指针指向非零数则将左右指针对应的数交换同时左指针右移
class Solution {
public:void moveZeroes(vectorint nums) {int n nums.size(), left 0, right 0;while (right n) {if (nums[right]) {swap(nums[left], nums[right]);left;}right;}}
};思路通过右指针来遍历数组左指针始终指向处理好的序列的尾部。 2.盛最多水的容器 /* 算法流程
1.初始化 双指针 i , j 分列水槽左右两端
2.循环收窄 直至双指针相遇时跳出a.更新面积最大值 resb.选定两板高度中的短板向中间收窄一格
3.返回值 返回面积最大值 res 即可 */class Solution {
public:int maxArea(vectorint height) {int i 0, j height.size() - 1, res 0;while(i j) {res height[i] height[j] ? max(res, (j - i) * height[i]): max(res, (j - i) * height[j--]); }return res;}
};3.三数之和 class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());// 找出a b c 0// a nums[i], b nums[left], c nums[right]for (int i 0; i nums.size(); i) {// 排序之后如果第一个元素已经大于零那么无论如何组合都不可能凑成三元组直接返回结果就可以了if (nums[i] 0) {return result;}// 错误去重a方法将会漏掉-1,-1,2 这种情况/*if (nums[i] nums[i 1]) {continue;}*/// 正确去重a方法if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.size() - 1;while (right left) {// 去重复逻辑如果放在这里000 的情况可能直接导致 rightleft 了从而漏掉了 0,0,0 这种三元组/*while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;*/if (nums[i] nums[left] nums[right] 0) right--;else if (nums[i] nums[left] nums[right] 0) left;else {result.push_back(vectorint{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;// 找到答案时双指针同时收缩right--;left;}}}return result;}
}; 思路 首先将数组排序然后有一层for循环i从下标0的地方开始同时定一个下标left 定义在i1的位置上定义下标right 在数组结尾的位置上。 依然还是在数组中找到 abc 使得a b c 0我们这里相当于 a nums[i]b nums[left]c nums[right]。 接下来如何移动left 和right呢 如果nums[i] nums[left] nums[right] 0 就说明 此时三数之和大了因为数组是排序后了所以right下标就应该向左移动这样才能让三数之和小一些。 如果 nums[i] nums[left] nums[right] 0 说明 此时 三数之和小了left 就向右移动才能让三数之和大一些直到left与right相遇为止。
