代码随想录算法训练营第七天| LC454. 四数相加II、LC383. 赎金信、LC15. 三数:和、LC18. 四数:和、哈希表章节
LeetCode 454 四数相加II
题目链接:454. 四数相加II
做题情况:自己第一反应是写了个O(n4)的暴力解法,然后提交显示超时,然后由于本题出现在哈希表章节,然后想到在找最后一个数时使用哈希表,优化到了O(n3)章节,可是提交还是超时,自己自然而然也就想到可以继续优化到O(n2),可以使用两个数的相加的相反数来建立一个哈希表,从而只要两个for循环即可,具体ac代码如下:
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int res=0;
int n1=nums1.size();
int n2=nums2.size();
int n3=nums3.size();
int n4=nums4.size();
unordered_map<int,int>hash;
for(int i=0;i<n3;i ){
for(int j=0;j<n4;j )
hash[-(nums3[i] nums4[j])] =1;//两个数相加的相反数来建立一个哈希表
}
for(int i=0;i<n1;i ){
for(int j=0;j<n2;j ){
if(hash.find(nums1[i] nums2[j])!=hash.end()){
res =hash.find(nums1[i] nums2[j])->second;
}
}
}
return res;
}
};
LeetCode 383 赎金信
题目链接:383. 赎金信
做题情况:本题思路很简单,只要建立一个关于字符串magazine的unordered_map字母哈希表,然后再继续遍历字符串ransomNote的字母,看在不在哈希表中,在哈希表对应数量减1,减到0时删除这个这个k-v对(因为一个对应一个),自己独立完成具体ac代码如下:
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int>hash;
int n1=ransomNote.size();
int n2=magazine.size();
for(int i=0;i<n2;i ){
hash[magazine[i]] =1;
}
for(int i=0;i<n1;i ){
if(hash.find(ransomNote[i])==hash.end()){
return false;
}
hash[ransomNote[i]]--;
if(hash[ransomNote[i]]==0){
hash.erase(ransomNote[i]);
}
}
return true;
}
};
看完相应内容讲解后,知道本题还可以继续优化,==由于只有小写字母,故只需要建立一个长度为26的数组来记录magazine里字母出现的次数,然后再用randomNote去验证这个数组是都包含了ansomNote所需要的所有字母,这样更简单高效。==具体实现如下:
//本题目用数组进行优化的代码,注意这种代码的写法,很清晰
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26]={0};
int n1=ransomNote.size();
int n2=magazine.size();
for(int i=0;i<n2;i ){
record[magazine[i]-'a'] =1;
}
for(int i=0;i<n1;i ){
record[ransomNote[i]-'a'] -=1;
if(record[ransomNote[i]-'a']<0){
return false;
}
}
return true;
}
};
LeetCode 15 三数之和
题目链接:15. 三数之和
做题情况:自己这道题目想了好久,想用哈希解法进行求解,可以自己总是不知道咋样去重,本题要求三元组不能重复的,这是本题的难点,参考卡哥视频和代码随想录书相关部分,发现本题竟然主要考查双指针用法,大吃一惊,当然用哈希法也可以做,但是很繁琐,也不是本题的重点。哈希法代码如下:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>result;
//先排序
sort(nums.begin(),nums.end());
//找出a b c=0
//a=nums[i], b=nums[j], c=-(a b)
for(int i=0;i<nums.size();i ){
if(nums[i]>0){//注意此处的剪枝操作,排序之后如果第一个元素已经大于零,那么不可能凑成三元组
break;
}
if(i>0&&nums[i]==nums[i-1]){//三元组元素a去重
continue;
}
unordered_set<int>set;
for(int j=i 1;j<nums.size();j ){
if(j>i 2&&nums[j]==nums[j-1]&&nums[j-1]==nums[j-2]){// 三元组元素b去重
continue;
}
int c=0-(nums[i] nums[j]);
if(set.find(c)!=set.end()){
result.push_back({nums[i],nums[j],c});
set.erase(c);// 三元组元素c去重
}else{
set.insert(nums[j]);//注意此处也有c去重操作
}
}
}
return result;
}
};
双指针解法才是本题的重点,而且比哈希法高效且易懂写出代码,具体代码如下:
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>>result;
//排序
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i ){
if(nums[i]>0)break;//注意此处的剪枝操作,排序之后如果第一个元素已经大于零,那么不可能凑成三元组
// 错误去重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){
if(nums[i] nums[left] nums[right]>0)right--;
else if(nums[i] nums[left] nums[right]<0)left ;
else{
result.push_back({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;
}
};
LeetCode 18 四数之和
题目链接:18. 四数之和
做题情况:自己在独立做的时候和上题目一样,一心在往哈希表方向想,实际上这道题目用哈希表方法更繁琐和难以实现,还是和上题一样考察双指针方法,只是多加了一个for循环,也要注意这道题目和第一道题目454. 四数相加II的区别,看完卡哥视频和代码随想录书相关部分后,这道题目主要有以下几个细节:①两次剪枝处理,注意和上一题的区别 ②去重的方法 ③ 溢出情况,具体ac代码如下:
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>>result;
sort(nums.begin(),nums.end());
for(int k=0;k<nums.size();k ){//
//一级剪枝操作
if(nums[k]>target&&nums[k]>=0){
break;
}
if(k>0&&nums[k]==nums[k-1]){//对nums[k]去重
continue;
}
for(int i=k 1;i<nums.size();i ){
//二级剪枝操作
if(nums[k] nums[i]>target&&nums[k] nums[i]>=0){
break;
}
if(i>k 1&&nums[i]==nums[i-1]){//对nums[i]去重
continue;
}
int left=i 1;
int right=nums.size()-1;
while(left<right){
//注意溢出
if((long)nums[k] nums[i] nums[left] nums[right]>target){
right--;
}else if((long)nums[k] nums[i] nums[left] nums[right]<target){
left ;
}else{
result.push_back({nums[k],nums[i],nums[left],nums[right]});
对nums[left]和nums[right]去重
while(left<right&&nums[right]==nums[right-1])right--;
while(left<right&&nums[left]==nums[left 1])left ;
right--;
left ;
}
}
}
}
return result;
}
};
哈希表章节总结
具体知识点总结见卡哥总结,主要写下自己在做题目时候几个经验:①哈希表是判断某元素是否出现在集合中或者出现的次数,看到这些类似字眼就要想到哈希表 ②数组也可以作为哈希表,注意啥时候使用数组、set(集合)、map(映射)③注意本章节双指针的相关几道题目的应用,不能局限思想,思想要打开
今天自己独立做所给题目花了一个小时,ac出前两道题目,后两道题目没做出来,感觉双指针方法也用的太巧妙了,所有做下来以及写博客共花了四五小时左右
贵在坚持,加油,共勉
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfigbfk
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
excel下划线不显示怎么办
PHP中文网 06-23 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
photoshop蒙版画笔没反应怎么办
PHP中文网 06-24