上陸アルゴリズムI LeetCode Weekly Contest 217解題報告

No.1最も裕福な顧客の資産総量
問題を解く構想.
サブ配列和の最大値を求める.Java 8以降のstreamを使って一言で済ませることができます.
コードディスプレイ

classSolution{

    publicintmaximumWealth(int[][] accounts){

        return Arrays.stream(accounts).

                map(i -> Arrays.stream(i).sum()).

                max(Integer::compareTo).get();

    }

}

No.2最も競争力のある都のサブシーケンスを見つけ出す
問題を解く構想.
すなわち、kの長いの辞書順が最も小さいサブシーケンスが見つかる.欲張るたびに最小の数を取ればいい.
しかし、グローバル範囲の最小数を取ることはできない、例えば、1回目の取りでは、[0,n-k]の下付き範囲で最小を取るしかない、取った最小値の下付きをxと仮定すると、2回目の取りは[x,n-k+1]の下付き範囲で最小を取るべきである.
優先キューを使用して完了することができる.
コードディスプレイ

class Number {

    int num;

    int idx;

    public Number(int num, int idx) {

        this.num = num;

        this.idx = idx;

    }

}

public int[] mostCompetitive(int[] nums, int k) {

    //           ,            

    PriorityQueue heap = new PriorityQueue<>((a, b) -> a.num == b.num ? a.idx - b.idx : a.num - b.num);

    // idx         

    int idx;

    for (idx = 0; idx <= nums.length - k; idx++) {

        heap.add(new Number(nums[idx], idx));

    }

    int[] res = new int[k];

    int latestIdx = -1;

    for (int i = 0; i < k; i++) {

        Number num = heap.poll();

        //    latestIdx        

        while (num.idx < latestIdx) {

            num = heap.poll();

        }

        //         [x, n - k + i]      

        res[i] = num.num;

        latestIdx = num.idx;

        //      ,           

        for (; idx <= nums.length - k + i + 1 && idx < nums.length; idx++) {

            heap.add(new Number(nums[idx], idx));

        }

    }

    return res;

}

}
No.3配列を補完する最小オペランド
問題を解く構想.
コアは依然として列挙である:列挙の最終的な和はいくらであるか.前処理のデータによって、各グループの数をこの和にするには、何個の数字を変更する必要があるかを迅速に計算する.
コードディスプレイ

class Solution {

    public int minMoves(int[] nums, int limit) {

        int halfLen = nums.length / 2;

        //      ,       

        int[] smallPart = new int[halfLen];

        int[] bigPart = new int[halfLen];

        for (int i = 0, j = nums.length - 1; i < j; i++, j--) {

            smallPart[i] = Math.min(nums[i], nums[j]);

            bigPart[i] = Math.max(nums[i], nums[j]);

        }

        //         

        int[] smallCntPreSum = new int[limit + 1];

        int[] bigCntPreSum = new int[limit + 1];

        for (int i = 0; i < halfLen; i++) {

            smallCntPreSum[smallPart[i]]++;

            bigCntPreSum[bigPart[i]]++;

        }

        for (int i = 1; i <= limit; i++) {

            smallCntPreSum[i] += smallCntPreSum[i - 1];

            bigCntPreSum[i] += bigCntPreSum[i - 1];

        }

        //          

        int[] sumCnt = new int[limit * 2 + 1];

        for (int i = 0; i < halfLen; i++) {

            sumCnt[smallPart[i] + bigPart[i]]++;

        }

        int res = nums.length;

        for (int sum = 2; sum <= limit + limit; ++sum) {

            //       sum  ,      tot   

            int tot = halfLen - sumCnt[sum];

            if (sum <= limit)

                tot += halfLen - smallCntPreSum[sum - 1];

            else

                tot += bigCntPreSum[sum - limit - 1];

            res = Math.min(res, tot);

        }

        return res;

    }

}

No.4配列の最小オフセット
問題を解く構想.
各数には一定の変化範囲があり、例えば5は5または10にしかならず、8は1、2、4、8になることができる.
双方向の変化は扱いにくいので、まず各数をその最大値の形式にすることができます:偶数は変わらず、奇数は2を掛けることができます.
次に、最大値と最小値の差を最小にするために、いくつかの数を縮小する必要があります.
私たちが縮小する必要があるのは最大値です.最大値を縮小してこそ結果に影響を与えるからです.したがって、最大値を縮小するだけでよい.
コードディスプレイ

class Solution {

    public int minimumDeviation(int[] nums) {

        TreeSet set = new TreeSet<>();

        for (int num : nums) {

            set.add(num % 2 == 0 ? num : num * 2);

        }

        int res = set.last() - set.first();

        while (res > 0 && set.last() % 2 == 0) {

            int max = set.last();

            set.remove(max);

            set.add(max / 2);

            res = Math.min(res, set.last() - set.first());

        }

        return res;

    }

}