leetcode-1785-构成特定和需要添加的最少元素-创新互联

给你一个整数数组nums,和两个整数limitgoal。数组nums有一条重要属性:abs(nums[i])<= limit

创新互联公司-专业网站定制、快速模板网站建设、高性价比惠民网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式惠民网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖惠民地区。费用合理售后完善,十余年实体公司更值得信赖。

返回使数组元素总和等于goal所需要向数组中添加的 最少元素数量 ,添加元素 不应改变 数组中abs(nums[i])<= limit这一属性。

注意,如果x >= 0,那么abs(x)等于x;否则,等于-x

示例 1:

输入:nums = [1,-1,1], limit = 3, goal = -4
输出:2
解释:可以将 -2 和 -3 添加到数组中,数组的元素总和变为 1 - 1 + 1 - 2 - 3 = -4 。

示例 2:

输入:nums = [1,-10,9,1], limit = 100, goal = 0
输出:1

提示:

  • 1<= nums.length<= 10^5
  • 1<= limit<= 10^6
  • -limit<= nums[i]<= limit
  • -10^9<= goal<= 10^9

分析:

看到这道题,第一反应就是把nums中的数加起来,然后用加起来的值和goal的差值除以limit即可得到结果。

class Solution {public:
    int minElements(vector& nums, int limit, int goal) {int addnum = 0;
        for(auto num : nums)
            addnum += num;
        int gapnum = goal - addnum;
        return (abs(gapnum) - 1)/abs(limit) + 1;
    }
};

很遗憾只能满足65 / 77 个通过测试用例。原因在于后面的测试用例中nums的和非常大,超出了int所能表示的范围,因此我们还要考虑其他的方式。

为了防止超出范围,我想到了一个方法:

在nums求和的过程中,想办法让和的绝对值小于limit,我们可以通过给这个和加上或者减去limit来实现这个效果,并分别记录加上和减去的次数,这个次数在后面是可以相互抵消的。

依照这个思路可得到如下代码:

class Solution {public:
    int minElements(vector& nums, int limit, int goal) {int addnum = 0;//nums的和(其中加上和减去了多个limit)
        int minustimes = 0;//减limit次数
        int plustimes = 0;//加limit次数
        for(auto num : nums){addnum += num;
            if(addnum >= limit){//过大则减
                addnum -= limit;
                ++minustimes;
            }
            if(addnum<= -limit){//过小则加
                addnum += limit;
                ++plustimes;
            }
        }
        int gapnum = goal - addnum;//goal与addnum的差值
        if(gapnum == 0)//正好为0时,可直接返回差值
            return abs(minustimes - plustimes);
        int remaintimes = (abs(gapnum) - 1)/abs(limit) + 1;//加减limit后还需limit的个数
        int totaltimes = 0;//总次数
        if(gapnum >0){//gapnum大于0时,remaintimes为加的次数
            totaltimes = abs(remaintimes + plustimes - minustimes);
        }else{//gapnum小于0时,remaintimes为减的次数
            totaltimes = abs(remaintimes + minustimes - plustimes);
        }
        return totaltimes;
    }
};

执行用时:88 ms, 在所有 C++ 提交中击败了92.20%的用户

内存消耗:71.6 MB, 在所有 C++ 提交中击败了78.72%的用户

通过测试用例:77 / 77

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


分享名称:leetcode-1785-构成特定和需要添加的最少元素-创新互联
文章来源:http://pwwzsj.com/article/coedjg.html