题目链接： Leetcode Weekly Contest 217

写在前面：

1、1672. Richest Customer Wealth

难度：Easy

题目大意：

给一个二维数组，求每一行的和，输出最大的和。

思路：

签到题，按照题目的要求做就行了。

代码

class Solution {
    public int maximumWealth(int[][] accounts) {
        int maxMoney=0;
        for(int i=0;i<accounts.length;i++){
            int amount=0;
            for(int j=0;j<accounts[i].length;j++){
                amount+=accounts[i][j];
            }
            if(amount>maxMoney){
                maxMoney=amount;
            }
        }
        return maxMoney;
    }
}

 

2、1673. Find the Most Competitive Subsequence

难度：Medium

题目大意：

输入一个整型数组nums[ ]和一个整数k，从nums[ ]中删去一些数剩下k个数，要求使得剩下的k个数从高位到地位尽可能地小,高位的优先级比地位高。如{1,2，3}优于{1,3,2} 。

思路：

参考高赞回答，将数组元素依次入栈，保证数组元素原来的相对顺序，如果发现一个数比栈顶元素小，并且检查弹出该元素后还能填满大小为k的栈，将该元素弹出。栈的大小小于k，则将数组元素入栈。

代码

class Solution {
    public int[] mostCompetitive(int[] nums, int k) {
        int[] res=new int[k];
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<nums.length;i++){
            while(!stack.isEmpty()&&nums[i]<stack.peek()&&stack.size()-1+nums.length-i>=k){
                //stack.size()-1stack表示移去顶部元素后剩下元素的数量
                //nums.length-i表示从下标i开始nums一共还有多少个元素
                stack.pop();
            }
            if(stack.size()<k){
                stack.push(nums[i]);
            }
        }
        for(int i=k-1;i>=0;i--){
            res[i]=stack.pop();
        }
        return res;
    }
}


 

3、1674. Minimum Moves to Make Array Complementary

难度：Medium

题目大意：

如果一个数组nums满足nums[i]+nums[n-1-i]都等于同一个数，则称这个数组是互补的，n为数组长度。给出一个数组，每次操作能将一个数变为[1，limit]之间的任何数，求至少经过多少次操作能将该数组编程互补数组。

思路：

参考高赞回答。
遍历所有的nums[i]+nums[n-1-i]，求当target=nums[i]+nums[n-1-i]时需要多少次操作，任何求所有情况中的最小值即可。这道题本质是数学题，用了“差分数组”这种数据结构。

代码

class Solution {
    public int minMoves(int[] nums, int limit) {
        int n=nums.length;
        int[] diff=new int[2*limit*2];
        int l,r;
        for(int i=0;i<n/2;i++){
            int A=nums[i],B=nums[n-1-i];
            l=2;
            r=2*limit;
            diff[l]+=2;
            diff[r+1]-=2;
            l=1+Math.min(A,B);
            r=limit+Math.max(A,B);
            diff[l]+=-1;
            diff[r+1]-=-1;
            l=A+B;
            r=A+B;
            diff[l]+=-1;
            diff[r+1]-=-1;
        }
        int res=n,sum=0;
        for(int i=2;i<=2*limit;i++){
            sum+=diff[i];
            if(sum<res){
                res=sum;
            }
        }
        return res;
    }
}
 

4、1675. Minimize Deviation in Array

难度：Hard

题目大意：

给出一个数组，可以将任何一个奇数翻倍，也可以将任何一个偶数减半，操作次数不限，求经过任意次操作后，数组最大值与最小值的最小差是多少。

思路

参考高赞回答 ，先把所有的数扩大到它们能达到的最大值，即将所有的奇数翻倍，然后将所有数存入TreeSet中。每次计算取出TreeSet中最大的数，如果是偶数，则减半，如果是奇数，说明最大值与最小值的差距已经无法再缩小,退出循环，每次都更新数组最大值与最小值之差。

代码

class Solution {
    public int minimumDeviation(int[] nums) {
        TreeSet<Integer> set=new TreeSet<>();
        for(int a:nums){//先把每个数在可及的范围内扩到最大
            if(a%2==1){
                a*=2;
            }
            set.add(a);
        }
        int deviation=set.last()-set.first();
        while(true){
            int val=set.last();
            int diff=val-set.first();
            deviation=Math.min(deviation,diff);
            if(val%2==0){
                set.remove(val);
                set.add(val/2);
            }
            else{
                break;//无法再缩小
            }
        }
        return set.last()-set.first();
    }
}