关注、星标下方公众号，和你一起成长
作者 | 梁唐
(资料图片仅供参考)
出品 | 公众号：Coder梁（ID：Coder_LT）
大家好，我是老梁。
原本这篇文章应该昨天出的，但是昨天实在是太忙了，所以延后了一天，非常抱歉。
昨天这场比赛由FNZ赞助，并且前100名可以获得简历内推机会，已经很久没有看到这么多简历内推的机会了。有点久违的感动……
这一场比赛的难度不小，最后一题比以往的都要难。评论区的大佬们也表示太难了……
K 件物品的最大和
袋子中装有一些物品，每个物品上都标记着数字 1、0或 -1。
给你四个非负整数 numOnes、numZeros、numNegOnes和 k。
袋子最初包含：
numOnes件标记为 1的物品。 numZeroes件标记为 0的物品。 numNegOnes件标记为 -1的物品。 现计划从这些物品中恰好选出 k件物品。返回所有可行方案中，物品上所标记数字之和的最大值。
题解
要使得最后的数字之和最大，肯定是优先拿1和0，最后拿-1，分情况讨论即可。
classSolution{public:intkItemsWithMaximumSum(intnumOnes,intnumZeros,intnumNegOnes,intk){if(numOnes>=k)returnk;if(numOnes+numZeros>=k)returnnumOnes;returnnumOnes-(k-numOnes-numZeros);}};质数减法运算
给你一个下标从 0开始的整数数组 nums，数组长度为 n。
你可以执行无限次下述运算：
选择一个之前未选过的下标i，并选择一个 严格小于nums[i]的质数 p，从 nums[i]中减去 p。 如果你能通过上述运算使得 nums成为严格递增数组，则返回 true；否则返回 false。
严格递增数组中的每个元素都严格大于其前面的元素。
题解
数字范围比较小，可以直接暴力枚举。
首先使用筛法选出1000以内的所有质数，然后再进行暴力枚举。要使得数组严格递增的可能性最大，我们可以从后往前，从较大的数开始，尽量以较小的代价满足递增。靠后的数字越大，前面的数字要减去的值就越小，留下的空间也就越大。也是一道简单的贪心问题。
classSolution{public:boolprimeSubOperation(vector&nums){vectorpri;intes[1010];memset(es,0,sizeofes);//筛法筛质数for(inti=2;i<=1000;i++){if(es[i])continue;pri.push_back(i);for(intj=i+i;j<=1000;j+=i)es[j]=1;}for(inti=nums.size()-2;i>-1;i--){intl=nums[i+1];if(nums[i]nums[i])break;//如果满足小于nums[i+1]，则满足条件if(nums[i]>p&&nums[i]-p 使数组元素全部相等的最少操作次数
给你一个正整数数组 nums。
同时给你一个长度为 m的整数数组 queries。第 i个查询中，你需要将 nums中所有元素变成 queries[i]。你可以执行以下操作 任意次：
1。 请你返回一个长度为 m的数组 answer，其中 answer[i]是将 nums中所有元素变成 queries[i]的 最少操作次数。
注意，每次查询后，数组变回最开始的值。
题解
本题的题意非常简单，难点在于数据量比较大。一共有n个请求，如果采用暴力的方法来求解的话，每次请求需要计算n次，那么复杂度为 。
有没有什么办法可以不用枚举就能计算出结果呢？
比较容易想到，由于我们要计算操作次数的总和，那么元素的顺序不会影响结果，那么我们可以对原数组进行排序。对于每次请求q来说，数组中可能有一些数字小于它，剩下的大于它。由于我们已经对原数组进行了排序，那么可以根据q将原数组分成左右两个部分。左边的部分小于q，右边的部分大于q。
我们假设小于q的数字是k个，那么大于q的数字就是n-k个。对于小于q的部分，它的操作次数总和为 。大于q的部分总的操作次数为 。
对于这个求和的部分我们可以使用前缀和来维护，这样的话可以在 的复杂度内求出总和。剩下的问题就是求这个k，很明显，由于数组有序，我们可以使用二分法来查找。
classSolution{public:vectorminOperations(vector&nums,vector&queries){vectorret;sort(nums.begin(),nums.end());longlongsm[nums.size()+2];memset(sm,0,sizeofsm);//维护前缀和intn=nums.size();for(inti=0;i 收集树中金币
给你一个 n个节点的无向无根树，节点编号从 0到 n - 1。给你整数 n和一个长度为 n - 1的二维整数数组 edges，其中 edges[i] = [ai, bi]表示树中节点 ai和 bi之间有一条边。再给你一个长度为 n的数组 coins，其中 coins[i]可能为 0也可能为 1，1表示节点 i处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
收集距离当前节点距离为2以内的所有金币，或者 移动到树中一个相邻节点。 你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。
题解
这道题非常难，比赛的时候只有一百多人通过。
我们先来分析一下难点，首先一个难点在于数据范围比较大。虽然节点的数量最多只有 ，但我们不仅要考虑数当中的路径，还需要在树中进行遍历，另外这棵树的形态其实也是不确定的，我们可以以任何节点为根节点。
这一切都不确定就显得比较困难了，我一开始也是直接蒙了，完全不知道从何下手。后来看了大佬的题解之后才恍然大悟，题目看起来困难不要紧，我们有没有办法来降低难度呢？
比如我们可以缩小树的规模，由于本题的目的是搜集所有树上的金币，那么对于没有金币的节点我们就没有必要访问了，尤其是非中间节点，其实也就是叶子节点，以及根节点只有一个孩子的情况。并且进一步发散，如果一棵子树上都没有金币，那么整个子树也完全没必要访问。我们可以直接从树上删掉，避免之后访问到。
其次，没有金币的子树删除之后，考虑金币的获取。由于可以拾取距离2以内的金币，所以我们只需要考虑距离叶子节点大于等于2的节点。我们可以记录下每个节点距离叶子节点的距离，由于叶子节点一定有金币，没有金币的节点都被删除了。所以这些距离叶子节点2及以上节点都是要访问到的，由于这是一棵树，两点之间的最短路径只有一条，也是确定的。所以我们没必要去关心具体的路径是怎样的，凡是连接两个节点距离都大于等于2的边都必然需要经过，而且由于最后要回到出发点，所以必然会经过两次。
到这里，就只剩下了一个问题，就是我们怎么计算每个点距离叶子结点的距离呢？我们可以使用拓扑排序，利用节点的度数。叶子结点的特点就是它的度数只有1，我们把叶子节点以及和相关的边去除之后，新的度数为1的点，就是距离叶子节点为1的点。以此类推，我们就可以计算出所有点和叶子结点的距离。包括之前没有金币的子树删除，同样可以利用拓扑排序来搞定。
虽然从最后的代码来看，本题不算非常复杂，但是中间有太多需要推导的结论了，一步一步思考下来得到正解并不容易。
classSolution{public:intcollectTheCoins(vector&coins,vector>&edges){intn=coins.size();vectorgraph[n+10];intdeg[n+10],stamp[n+10];memset(deg,0,sizeofdeg);memset(stamp,0,sizeofstamp);//建图for(auto&vt:edges){intu=vt[0],v=vt[1];graph[u].push_back(v);graph[v].push_back(u);deg[u]++;deg[v]++;}dequeque;//找出所有度数为1，且没有金币的叶子结点for(inti=0;i=2&&stamp[u]>=2)ret+=2;}returnret;}}; 喜欢本文的话不要忘记三连~
检察官担任法治副校长有了“指挥棒”
全国首份《家庭教育令》来了！督促家长“依法带娃”
俄军装甲车辆将具备隐身能力