Day 7 | 454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和

发布时间:2024年01月18日

454.四数相加II

先贴我的代码;

int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int res = 0;
        unordered_map<int,int> box12;
        unordered_map<int,int> box34;
        for(int a : nums1){
            for(int b : nums2){
                box12[a+b]++;
            }
        }
        for(int a : nums3){
            for(int b : nums4){
                box34[a+b]++;
            }
        }
        for(auto iter = box12.begin(); iter != box12.end(); iter++){
            int val = iter->first;
            auto iter34 = box34.find(-val);
            if(iter34 != box34.end()) res += iter->second * iter34->second;
        }
        return res;

做题心得:

? ? ? ? 我选择直接将12 和 34 俩个数组中的数进行相加并存进map,value 表示当前俩个数组能够组成 key 值有多少种不同的排列组合。

? ? ? ? 关键点,我最后遍历map的时候,返回的值是 res += iter12 * iter34,这是因为我直接把整个数组都计算过了,那么相乘就是其总共存在的当前对应值的解数量。

? ? ? ? 这里还有一个点需要注意:

? ? ? ? 需要注意 set? 和 map 的取值区别:

std::set

std::set 中的元素是键,因为它是一个集合,不包含重复元素。当使用?find?等方法在 std::set 中查找元素时,返回的迭代器指向的是元素本身。所以,你需要通过 * 操作符解引用迭代器来获取元素的值。

std::map:

std::map 中的元素是键值对,因此迭代器指向的是一个包含键值对的对象。你可以通过 -> 操作符来访问键值对中的成员,其中 first 是键,second 是值。

对于 std::map,迭代器的 -> 操作符已经被重载,允许你直接访问键值对的成员,而不需要显式地使用 * 操作符。这是因为 std::map 的迭代器是一个类对象,其 -> 操作符被定义为返回指向值部分的引用,这使得语法更加直观。它的迭代器直接提供了方便的访问方式,而不需要额外的解引用。


383. 赎金信

先贴我的代码:

bool canConstruct(string ransomNote, string magazine) {
        int box[26] = {0};
        if(ransomNote.size() > magazine.size()) return false;
        for(char c : magazine){
            box[c - 'a']++;
        }
        for(char c : ransomNote){
            box[c -'a']--;
            if(box[c-'a'] < 0) return false;
        }
        return true;
    }

解题心得:

? ? ? ? 对于这种问题,就是开辟一个数组空间,存放26个字母出现的次数,再用另外一个字符串里的字符去做对应的加加减减,而在此题中,如果信中的字符在杂志中没有或者用完了,那么对应的值肯定会小于0,通过这一点来判断是否有问题。

15. 三数之和

? ? ? ?先贴代码:

vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int l, r;
        sort(nums.begin(),nums.end());
        if(nums.size() == 0 || nums[0] > 0) return res;
        for(int i = 0; i < nums.size()-2; i++){
            if( i > 0 && nums[i] == nums[i-1]) continue;
            l = i + 1;
            r = nums.size()-1;
            while(l < r){
                if(nums[i] + nums[l] + nums[r] > 0) r--;
                else if(nums[i] + nums[l] + nums[r] < 0) l++;
                else{
                    vector<int> val;
                    val.push_back(nums[i]);
                    val.push_back(nums[l]);
                    val.push_back(nums[r]);
                    res.push_back(val);
                    // res.push_back(vector<int>{nums[i],nums[l],nums[r]});
                    while(l < r && nums[l] == nums[l+1]) l++;
                    while(l < r && nums[r] == nums[r-1]) r--;

                    l++;
                    r--;
                }
            }
        }
        return res;

写题心得:

? ? ? ? 如何减枝,首先是当排完序后第一个值大于0,那肯定不会后面相加会得到 0;

? ? ? ? 排完序后,最外层 i 的循环,需要过滤掉与上一个 i-1 想同的值,因为 i-1 的答案一定是 i 所构成的答案的子集。

? ? ? ? 后面就没啥好说的了,记得在找到答案后,先对单边各自收缩,只要相等就收缩,直到不相同,还要对双边进行收缩。这里是为什么呢?假设不双边收缩只收缩一边,那么根本不可能会形成 == 0 的情况,因为等于 0 所对应的值已经收进答案中,并且重复的已经去除掉了,所以要想找下一个答案,肯定是俩边双向收缩。

? ? ? ? 还要关注一点就是如果 vector<vector<int>> 直接push元素,可以这么写:

? ? ? ? res。push_back(vector<int> {a,b,c,d...e}) 这么写更简洁。

  vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> res;
        int l, r;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size(); i++){ // 这里原先写的 nums.size()-3
            if(nums[i] > target && nums[i] >= 0) break;
            if(i > 0 && nums[i-1] == nums[i]) continue;
            for(int k = i + 1; k < nums.size(); k++){
                if((nums[i] + nums[k]) > target && (nums[i] + nums[k]) >= 0) break;
                if(k > i+1 && nums[k] == nums[k-1]) continue;
                l = k+1, r = nums.size() - 1;
                while( l < r){
                    if((long)nums[i] + nums[k] + nums[l] + nums[r] > target) r--;
                    else if((long)nums[i] + nums[k] + nums[l] + nums[r] < target) l++;
                    else{
                        res.push_back(vector<int>{nums[i],nums[k],nums[l],nums[r]});
                        while(l < r && nums[l] == nums[l+1]) l++;
                        while(l < r && nums[r] == nums[r-1]) r--;

                        l++;
                        r--;
                    }
                }
            }
        }
        return res;
    }

解题心得:

? ? ? ? 不知道有没有人跟我一样,会追求代码一步都不要走错,所以在最开始遍历 i 以及 k 里面,我都给 nums.size() -3 和 -2,以至于使得代码不会做无用功,但是我没考虑到,Nums也有可能是空数组,如果我直接对空数组进行操作,导致的后果就是会有负数,会导致堆数据异常!!

(这边又细想了一下,如果 i 很极端遍历到最后一个元素,那么 k = i + 1 就会遍历超过此数组,但是并没有报错,是因为取值是合法的,再加上 k? < nums1.size()这个约束,则不可能执行下去,而我直接 Nums.size()-3则是非法操作,因为当size为0的时候,进行函数运算则不可能执行会导致报错)

? ? ? ? 其次减枝的时候要考虑负数的情况,因为不是为 0 。如果单纯的使得 nums【开头】 > target,则没考虑 target <?0 的情况,。

? ? ? ? 以及最后要扩充到 long ,不然会溢出。

关于 Nums.size() -3 合法性也可以按照下面的修改

if(nums.size() < 4) return res;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size()-3; i++){ // 这里原先写的 nums.size()-3
            if(nums[i] > target && nums[i] >= 0) break;
            if(i > 0 && nums[i-1] == nums[i]) continue;
            for(int k = i + 1; k < nums.size()-2; k++){

只要先确认 nums的size > 4,那么下面关于 i 和 k 的范围取值 nums.size()就不会操作非法地址。

文章来源:https://blog.csdn.net/weixin_54143009/article/details/135647955
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。