关注、星标下方公众号，和你一起成长

作者 | 梁唐

(资料图片)

出品 | 公众号：Coder梁（ID：Coder_LT）

大家好，我是梁唐。

不好意思昨天有点事情晚更了一天，我们照惯例来看看上周末的LeetCode周赛。

本次周赛是LeetCode第331场，本场仍然是LeetCode学习福利场。本场比赛的赛题质量不错，不涉及到高深的算法，更多的考验思维以及对于题意的理解。即使是初学者也能得到很好的锻炼。

老梁春节期间休息了一个月，现在再做题也有思维笨拙的感受。思维能力和肌肉一样，需要时长锻炼，大家不要懈怠呀。

从数量最多的堆取走礼物

给你一个整数数组 gifts，表示各堆礼物的数量。每一秒，你需要执行以下操作：

选择礼物数量最多的那一堆。 如果不止一堆都符合礼物数量最多，从中选择任一堆即可。 选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。

返回在 k秒后剩下的礼物数量。

题解

签到题，暴力也一样能通过。

也可以使用优先队列优化，将复杂度降低到 。

classSolution{public:longlongpickGifts(vector&gifts,intk){longlongsm=0;for(inti=0;i());gifts[0]=sqrt(gifts[0]);}for(auto&x:gifts)sm+=x;returnsm;}};

统计范围内的元音字符串数

给你一个下标从 0开始的字符串数组 words以及一个二维整数数组 queries。

每个查询 queries[i] = [li, ri]会要求我们统计在 words中下标在 li到 ri范围内（包含这两个值）并且以元音开头和结尾的字符串的数目。

返回一个整数数组，其中数组的第 i个元素对应第 i个查询的答案。

注意：元音字母是 "a"、"e"、"i"、"o"和 "u"。

题解

前缀和模板题，我们判断一下每个字符串是否符合题意，然后维护一个前缀和用来查询即可。

classSolution{public:vectorvowelStrings(vector&words,vector>&queries){intn=words.size();vectorsm(n+2,0);setv{"a","e","i","o","u"};for(inti=0;iret;for(auto&vt:queries){intl=vt[0],r=vt[1]+1;ret.push_back(sm[r]-sm[l]);}returnret;}};

打家劫舍 IV

沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。

由于相邻的房屋装有相互连通的防盗系统，所以小偷 不会窃取相邻的房屋。

小偷的 窃取能力定义为他在窃取过程中能从单间房屋中窃取的 最大金额。

给你一个整数数组 nums表示每间房屋存放的现金金额。形式上，从左起第 i间房屋中放有 nums[i]美元。

另给你一个整数数组 k，表示窃贼将会窃取的 最少房屋数。小偷总能窃取至少 k间房屋。

返回小偷的 最小窃取能力

题解

如果范围小的话，不难想到背包问题。本题当中k和n都比较大，直接dp的复杂度太大不能接受。

但除此之外又想不到什么好的办法，很多人到这里就卡住了。既然正面推导走不通，我们可以逆向思维。不方便直接求解，可以从反面思考，枚举答案来进行验证。

沿着这条线展开，可以想到小偷的偷窃能力和能够覆盖的房间数量之间是呈正比的。那么我们可以二分小偷的偷窃能力，也就是二分答案，然后来反向计算最多能覆盖的房间数，来验证是否能够满足题目要求。

由于题目限制了覆盖的房间不能相邻，所以我们要使用dp的思想，分别维护当前房间要不要覆盖两个状态。当我们移动到下一个房间时，我们可以通过上一个房间是否覆盖来求解得到当前状态的值。假设d1表示上一个房间覆盖能覆盖的最大房间数，d2表示不覆盖时最多覆盖的房间数。nd1表示当前房间覆盖对应的房间数，nd2表示当前房间不覆盖对应的房间数。

那么我们可以得到这么几条状态转移：

ifm>=x:#小偷能力值大于等于当前房间nd1=d2+1#上一个房间没覆盖，当前房间覆盖nd2=max(d1,d2)#从上一个房间取最大值else:nd1=0#当前房间不能覆盖，所以是0nd2=max(d1,d2)

我们在二分法当中结合状态转移，就可以搞定了。我个人感觉比较大的阻碍是比较难逆向思考想到二分答案。

classSolution{public:intminCapability(vector&nums,intk){intn=nums.size();intl=0,r=0;for(autox:nums)r=max(r,x);while(l+1>1;intd1=0,d2=0;for(autox:nums){if(m>=x){intnd2=max(d2,d1);intnd1=d2+1;d1=nd1;d2=nd2;}else{intnd2=max(d1,d2);intnd1=0;d1=nd1;d2=nd2;}}if(max(d1,d2)>=k)r=m;elsel=m;}returnr;}};

重排水果

你有两个果篮，每个果篮中有 n个水果。给你两个下标从 0开始的整数数组 basket1和 basket2，用以表示两个果篮中每个水果的成本。

你希望两个果篮相等。为此，可以根据需要多次执行下述操作：

选中两个下标 i和 j，并交换 basket1中的第 i个水果和 basket2中的第 j个水果。 交换的成本是 min(basket1i,basket2j)。

根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1。

题解

这题前半部分比较简单，很容易想到我们可以把两个篮子里的所有水果统计在一起，将每种水果的数量除以2，就是最终每个果篮的情况。如果出现某一种水果数量是奇数，那么则说明无解，返回-1。

得到了最终情况之后，我们再和当前果篮里的水果进行比对，对比下来多余的水果就是需要交换出去的。到这里都很简单，我们只需要把需要交换出去的排序，选取值最小一半进行累加即可。因为只有两个果篮，所以每一个水果要交换去的目标是确定的。按照贪心的思路，一定是交换对面果篮中数值最大的那个，交换的成本就是当前水果的值（因为当前水果是排序之后值最小的一个，一定小于对面被交换的水果）。

但是这里面有一个trick，就是两个水果交换还有第二种可能。就是借助于全局值最小的水果进行。我们假设全局值最小的水果是M，需要交换的两个水果是A和B。如果AB直接交换，那么成本是min(A, B)。如果借助M，那么则是M分别和AB交换，成本是min(A, M) + min(B, M)，由于M是全局最小的水果，所以化简之后，代价是2M。

只要考虑上这种情况，本题就基本没有难度了。

classSolution{public:longlongminCost(vector&bk1,vector&bk2){maptot,t1,t2;intmini=0x3f3f3f3f;for(autox:bk1)tot[x]++,t1[x]++,mini=min(mini,x);for(autox:bk2)tot[x]++,t2[x]++,mini=min(mini,x);for(auto&it:tot)if(it.second%2)return-1;vectorvt;for(auto&it:t1){intk=it.first;intm=tot[k]/2;if(it.second>m){it.second-=m;for(inti=0;im){it.second-=m;for(inti=0;i

喜欢本文的话不要忘记三连~