关注、星标下方公众号，和你一起成长
(相关资料图)
作者 | 梁唐
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是老梁。
很抱歉这两天真的太忙了，到晚上才有时间来更新。
我们来看下上周的LeetCode周赛，这场是LeetCode第339场，由安贤量化公司赞助。上来就是一个大槽点，居然只有第一名才有直通面试的资格……
这场两极分化有点严重，简单题非常简单，难题则非常难。T4全场只有不到100人通过……
很多人表示看到大佬们都没通过就果断弃赛了……
给你一个仅由 0和 1组成的二进制字符串 s。
如果子字符串中 所有的0都在1之前且其中 0的数量等于 1的数量，则认为 s的这个子字符串是平衡子字符串。请注意，空子字符串也视作平衡子字符串。
返回 s中最长的平衡子字符串长度。
子字符串是字符串中的一个连续字符序列。
签到题，逻辑稍微有一点棘手。有一个小trick，当1的数量大于0并且又遇到了新的0之后，要将0设置成1，而不是直接清零。
classSolution{public:intfindTheLongestBalancedSubstring(strings){intn=s.length();intret=0,zero=0,one=0;for(inti=0;izero){one=0;zero=0;continue;}ret=max(ret,min(zero,one)*2);}}returnret;}}; 给你一个整数数组 nums。请你创建一个满足以下条件的二维数组：
nums中的元素。 二维数组中的每一行都包含 不同的整数。 二维数组的行数应尽可能 少。 返回结果数组。如果存在多种答案，则返回其中任何一种。
请注意，二维数组的每一行上可以存在不同数量的元素。
同样签到题，由于子数组中不能存在相同的元素，很容易想到我们可以贪心，把相同的元素分散到不同的数组里。
通过排序可以很方便地将相同的元素聚合在一起，然后拆开分配即可。
classSolution{public:vector>findMatrix(vector&nums){vector>ret;mapmp;sort(nums.begin(),nums.end());for(autox:nums){mp[x]++;intv=mp[x]-1;if(v==ret.size())ret.push_back(vector());ret[v].push_back(x);}returnret;}}; 有两只老鼠和 n块不同类型的奶酪，每块奶酪都只能被其中一只老鼠吃掉。
下标为 i处的奶酪被吃掉的得分为：
reward1[i]。 如果第二只老鼠吃掉，则得分为 reward2[i]。 给你一个正整数数组 reward1，一个正整数数组 reward2，和一个非负整数 k。
请你返回第一只老鼠恰好吃掉 k块奶酪的情况下，最大得分为多少。
我们默认老鼠B吃掉所有奶酪，那么得到的收益总和就位reward2的总和。我们再来看看奶酪被老鼠A吃掉的情况，对于一块奶酪来说，假设A老鼠吃掉它的收益是x，B老鼠收益是y。那么它被A而不是B吃掉带来的额外收益就是x - y。很容易想到，我们可以贪心来处理，对于所有的奶酪都求出A与B之间收益的差值，再按照差值进行从大到小排序，取出最大的k个即可。
表面上看剩下的计算还是很麻烦，我们要找到前K大的差值对应的id，然后再计算对应的reward1，再求剩下的reward2。其实可以不用这么麻烦，我们一开始先求出所有B老鼠的收益。之后再加上k个差值，B老鼠的收益再加上两者的差值就刚好是A老鼠的收益。
classSolution{public:intmiceAndCheese(vector&reward1,vector&reward2,intk){intn=reward1.size();inttot=0;for(inti=0;i());for(inti=0;i 给你一个整数 n和一个在范围 [0, n - 1]以内的整数 p，它们表示一个长度为 n且下标从 0开始的数组 arr，数组中除了下标为 p处是 1以外，其他所有数都是 0。
同时给你一个整数数组 banned，它包含数组中的一些位置。banned中第 i个位置表示 arr[banned[i]] = 0，题目保证 banned[i] != p。
你可以对 arr进行 若干次操作。一次操作中，你选择大小为 k的一个 子数组，并将它 翻转。在任何一次翻转操作后，你都需要确保 arr中唯一的 1不会到达任何 banned中的位置。换句话说，arr[banned[i]]始终 保持0。
请你返回一个数组 ans，对于 [0, n - 1]之间的任意下标 i，ans[i]是将 1放到位置 i处的 最少翻转操作次数，如果无法放到位置 i处，此数为 -1。
i， ans[i]相互之间独立计算。 将一个数组中的元素 翻转指的是将数组中的值变成 相反顺序。 这题我感觉是语文题，题目读懂就不太容易。
比较容易想到解法，对于为止p来说，一次翻转能够到达的位置是确定的。假设我们先不考虑边界问题，那么一次翻转能够到达的最左侧是p-k+1，最右侧是p+k-1。并且不难发现，到达的位置是有奇偶性的。也就是说，通过翻转p只能去往奇数或者偶数的位置。我们可以来简单的证明，假设我们选取的数组最左侧刚好是p，那么翻转之后p的位置变成p+k-1。假设数组的最左侧是p-1，那么翻转之后p的位置是p+k-3。可以发现，选取的数组移动一个单位，p翻转之后的位置移动2个单位，所以不管怎么翻，奇偶性是固定的。
既然是固定的，我们可以通过p+k-1来确定。很多同学可能会想到bfs，我们每次维护一个能到达的位置，从它出发去遍历其他能通过翻转到达的位置，最后求出答案。
方法是可行的，但很遗憾，在本题的数据规模当中会超时。因为k可能很大， 导致我们能枚举的位置非常多。正是这一点拦住了绝大多数同学。
没什么比较好的办法，只能来思考优化。首先，我们可以发现，对于每个位置来说我们只会遍历一次。主要的消耗在于我们遍历了太多无效的位置。有没有办法可以减少无效位置的遍历呢？当然是有的，我们可以把所有有效的位置存放在set当中，之后通过二分的方法来查找能够到达的范围内的有效位置，这样可以过滤掉大部分遍历，快速找到结果。
我们前文给的p-k+1和p+k-1都是在没有限制的情况下，实际上我们的数组是有限制的，左侧是0，右侧是n-1。考虑上限制的话，我们最左侧的范围可能不一定是p-k+1，当p < k时，我们无法将p至于子数组的最右侧，最好情况是我们的子数组从0开始，此时p翻转之后的位置是k-p-1。同理，当n - p < k时，我们也无法将p至于子数组的最左侧，最好的情况是子数组的右侧从n-1开始，此时p翻转之后的位置是2n-p-k-1。
确定了范围之后，我们在set当中二分查找即可，思路比较难想到，但想到了之后，代码本身并不困难。算是很有意思也很有挑战的问题。
classSolution{public:vectorminReverseOperations(intn,intp,vector&banned,intk){vectordis(n,-1);dis[p]=0;if(k==1)returndis;setban;for(autox:banned)ban.insert(x);setst[2];for(inti=0;ique;que.push(p);while(!que.empty()){intu=que.front();que.pop();intl=max(u-k+1,k-u-1);intr=min(u+k-1,2*n-k-u-1);intx=(u+k-1)%2;autoit=st[x].lower_bound(l);while(it!=st[x].end()){if(*it>r)break;dis[*it]=dis[u]+1;que.push(*it);it=st[x].erase(it);}}returndis;}}; 喜欢本文的话不要忘记三连~
标签：
所刊载信息部分转载自互联网，并不代表本网赞同其观点和对其真实性负责。邮箱：5855973@qq.com
联系我们| 中国品牌网 | 沪ICP备2022005074号-18 营业执照 Copyright © 2018@. All Rights Reserved.
