Daily LeetCode – day0142 1703. Minimum Adjacent Swaps for K Consecutive Ones

import java.util.ArrayList;

// 1703. Minimum Adjacent Swaps for K Consecutive Ones
class Solution {
    public int minMoves(int[] nums, int k) {
        ArrayList<Integer> ones = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == 1) {
                ones.add(i);
            }
        }
        int sum = 0;
        int mid = k / 2;
        for (int i = 0; i < k; ++i) {
            sum += Math.abs(ones.get(i) - ones.get(mid));
        }
        int ans = sum;
        for (int i = 0; k + i < ones.size(); ++i) {
            mid = k / 2 + i;
            sum -= Math.abs(ones.get(mid) - ones.get(i));
            sum += Math.abs(ones.get(k + i) - ones.get(mid + 1));
            sum += (ones.get(mid + 1) - ones.get(mid)) * (k / 2);
            sum -= (ones.get(mid + 1) - ones.get(mid)) * (k - 1 - k / 2);
            ans = Math.min(ans, sum);
        }
        int offset = 0;
        for (int i = 1; i < k; ++i) {
            offset += (i - 1) / 2 + 1;
        }
        return ans - offset;
    }
}
学习笔记:
这是一道超级困难的题目,要O(n)的复杂度才可以过。
而且做的时候没有一点思绪,能想到的也都是暴力的解法。
上了YouTube看到了Huifeng Guan的解法后才理解。
但是当中还需要分析奇偶情况分开解,着实让人想吐。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注