【力扣一轮】454.四数之和 && 383.赎金信

csdn推荐

454.四数相加

代码随想录链接

力扣链接

思路

暴力解法就是4个for循环,看所有结果出现0,则计数。

更高效是怎么做?for循环减半。为什么能想到这里,注意到它的和是0,(和可以是任何数)这样就相当于两两数组为一对,看其中一对数组中的元素,在另外一对数组中是否出现了相反数。这里的一对说的是A+B或其他组合方式,(不重要,因为都是随机的)

注意题目要求,允许有重复的计算。也就是说如果一对数组中有两个-2,另一对数组中只有一个2,那么计算为0的次数为2。

所以,需要对其中一个计算一个出现次数。(这里我想的是用multi_set也行,直接count就可以。但由于底层实现为红黑树,不是直接的哈希表。所以用unordered_set其实计算速度更快)

问题

回答视频中最后的几个疑问(自己理解)

Q1:为什么会想到用哈希表?

A1:因为仍然是看其中一个元素是否存在于哈希表中,所以用哈希表会方便快捷。

Q2:用哈希表时,应该用什么哈希结构?为什么不用数组,为什么不用set?

A2:因为在存储时,不仅要存储对应的元素,也要存储元素出现的次数,所以用到map。同时,因为无法确定出现元素大小,用数组开辟空间可能会造成浪费。

伪代码

遍历其中两个数组的和值
	将所有结果及出现次数记录进map中
遍历另外两个数组的和值
	对每一个和值取反
	查看每一个和值是否出现在map中
		若出现
			则计数

代码

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<int,int> mp;
    int number = 0 ;
    for(int i = 0 ; i < nums1.size() ;i++){
        for(int j = 0 ; j < nums2.size(); j++){
            int onePlusone = nums1[i]+nums2[j];
            //如果当前元素没有存储在集合中,则将元素存储进集合中,否则次数+1
            unordered_map<int,int>::iterator result = mp.find(onePlusone);
            if(result==mp.end()){
                mp.insert(pair<int,int>(onePlusone,1));
            }else{
                result->second+=1;
            }
        }
    }
    //遍历后两个数组
    for(int i = 0 ; i < nums3.size();i++){
        for(int j = 0 ; j < nums4.size() ; j++){
            int minus = -1*(nums3[i]+nums4[j]);
            unordered_map<int,int>::iterator result = mp.find(minus);
            if(mp.find(minus)!=mp.end()){//如果为end,表示没找到
                number += result->second;
            }
        }
    }
    return number;
}

383.赎金信 思路

同样的使用哈希表。也是判断是否出现的问题。

下一个问题,应该用什么数据结构?现在只需要知道单个字母是否在另一个字符串中出现。结合之前的有效字母异位符,数组,set,map,使用数组即可。因为字母的个数是确定的。并且要存储的是magazine的字母元素。

然而以上想法截止到第二句,都没问题,需要注意的是,不是全对应。比如字符串2中有字符串1中没有的字母,此时字母表数组里面也会有元素没出现。所以判断条件需要多一点。

所以最开始我是用map来纠正,现在想想用字母表数组其实也可以。

伪代码

map版本:

初始化map
遍历'magazine'字符串
	如果map中没有字母
		添加进map中
	反之
		map中对应字母数+1
遍历'ransomNote'字符串
	如果没找到或者最后对应字母次数用完为0
		返回false
	反之
		字母对应位置次数--
返回true

字母表数组版本:

初始化字母数组
遍历'magazine'字符串
    字母数组对应次数+1
遍历'ransomNote'字符串
    字母数组对应次数-1
遍历字母数组
    其中任意字母位置小于0
    	则说明不可以,返回false
返回true

代码

map版本:

bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> mp;
        for (int i = 0; i < magazine.size(); i++) {
            unordered_map<char, int>::iterator result = mp.find(magazine[i]);
            if (result == mp.end()) {
                mp.insert(pair<char, int>(magazine[i], 1));
            } else {
                result->second++;
            }
        }
        for (int j = 0; j < ransomNote.size(); j++) {
            unordered_map<char, int>::iterator result = mp.find(ransomNote[j]);
            if (result == mp.end() || result->second ==0 ) { // 没找到
                return false;
            } else { // 找到啦
                result->second--;
            }
        }
        return true;
    }

字母表数组版本:

bool canConstruct(string ransomNote, string magazine) {
        int alpha_bet[26] = {0};
        for (int i = 0; i < magazine.size(); i++) {
            alpha_bet[magazine[i] - 'a']++;
        }
        for (int j = 0; j < ransomNote.size(); j++) {
            alpha_bet[ransomNote[j] - 'a']--;
            if (alpha_bet[ransomNote[j] - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }

文章来源:https://blog.csdn.net/weixin_44498989/article/details/139127036



微信扫描下方的二维码阅读本文

© 版权声明
THE END
喜欢就支持一下吧
点赞12 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容