第 217 场周赛

本文主要是介绍第 217 场周赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这次就做出第一题，第一题太简单就不写了，最后一题，等后面补上。
我还是太菜了，打完比赛之后写个记录的博客，为了督促自己坚持这一件事情，同时把当时错的思路和对别人写的方法的理解做个记录，方便以后回顾，多回顾帮助吸收为自己的知识。

1673. 找出最具竞争力的子序列

比赛时超时了，我记得以前有道题也是同样的意思，就是每次先留后–k个数，从前面的数中选出最小的，然后再从这个最小的值后一位开始，留–k个数，再选最小的依次类推，但是这么写超时了，比赛中没想出来用stack怎么改下面的方法。

class Solution {public int[] mostCompetitive(int[] nums, int k) {int len = nums.length;int[] res = new int[k];for(int i=0;i<k;i++){res[i] =Integer.MAX_VALUE;}int start = 0;int p=0;while(start<=len-k && k>0){int newStart = start;for(int cur = start;cur<=len-k;cur++){if(res[p]>nums[cur]){res[p] = nums[cur];newStart = cur;}    }// System.out.println("newStart:"+newStart+" res[p]:"+res[p]);start = newStart+1;k--;p++;}return res;}
}

赛后看题解，重新做了这道题

class Solution {public int[] mostCompetitive(int[] nums, int k) {Stack<Integer> stack = new Stack<Integer>();stack.add(-1);int len = nums.length;for(int i=0;i<len;i++){while(nums[i]<stack.peek() && (k+1-stack.size()<len-i)){stack.pop();}if(stack.size()<k+1){stack.add(nums[i]);}}int[] ret = new int[k];while(k>0){ret[--k] = stack.pop();}return ret;}
}

1674. 使数组互补的最少操作次数

差分数组

这题理解了半天，看了好多题解，大致意思是两数之和的取值范围分为几段，
1<sum<min+1:需要改变两次
min+1<=sum<min+max:需要改变一次
min+max=sum：不需要改变
min+max+1<=sum<=max+limit:只需要改变一次
max+limit+1<=sum<=limit*2：需要改变两次

所以如果sum选在
1、1~Min(nums) 那就是 2nums.length次操作数（最差的情况）
2、然后从2向右发展，遍历数组中的每个元素，如果（min+1<=sum<min+max）就在2的基础上-1；到min+max再-1；到min+max+1再+1；依次类推
3、这样遍历之后就2~2limit，看选哪个值时改变的次数最小。

我也不知道有没有解释清楚，我也是看了题解想了很久才想明白。。

class Solution {public int minMoves(int[] nums, int limit) {int[] diff = new int[2*limit+2];int len = nums.length;for(int i=0;i<len/2;i++) {int min = Math.min(nums[i], nums[len-1-i]);int max = Math.max(nums[i], nums[len-1-i]);diff[1]+=2;diff[min+1]-=1;diff[min+max]-=1;diff[min+max+1]+=1;diff[max+limit+1]+=1;diff[2*limit+1]-=2;}int ans = len;int sum=diff[1];for(int i=2;i<=limit*2;i++) {sum+=diff[i];ans = ans>sum?sum:ans;}return ans;}
}

这篇关于第 217 场周赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---