关于后端:1217-玩筹码-简单贪心运用题

这是 LeetCode 上的 1217. 玩筹码 ，难度为简略。

Tag :「贪婪」、「枚举」

有 n 个筹码。第 $i$ 个筹码的地位是 position[i]。

咱们须要把所有筹码移到同一个地位。在一步中，咱们能够将第 $i$ 个筹码的地位从 $position[i]$ 扭转为:

position[i] + 2 或 position[i] - 2，此时 cost = 0
position[i] + 1 或 position[i] - 1，此时 cost = 1

返回将所有筹码挪动到同一地位上所须要的最小代价。

示例 1：

输出：position = [1,2,3]

输入：1

解释：第一步: 将地位 3 的筹码挪动到地位 1，老本为 0。第二步: 将地位 2 的筹码挪动到地位 1，老本 = 1。总成本是 1。

示例 2：

输出：position = [2,2,2,3,3]

输入：2

解释：咱们能够把地位 3 的两个筹码移到地位 2。每一步的老本为 1。总成本 = 2。

示例 3:

输出：position = [1,1000000000]

输入：1

提醒：

$1 <= chips.length <= 100$
$1 <= chips[i] <= 10^9$

假如挪动的指标地位是 $a$，以后所在位置是 $b$，将小球从 $b$ 挪动到 $a$ 的老本取决于两地位间隔的「奇偶性」，间隔为偶数时老本固定为 $0$，间隔为奇数时老本固定为 $1$。

同时咱们能够通过「分状况探讨」来证实，所有小球挪动到一个全新地位（起始没有小球的地位），后果不会变好，假如所抉择的最终（全新）地位为 $t$：

假如抉择的地位 $t$ 导致所有数到地位 $t$ 间隔均为偶数，此时总成本为 $0$，同时可知所有数的地位奇偶性雷同，此时抉择所有数中的任意一个的地位，同样可得总成本为 $0$ 的后果，因而选全新的地位不会让后果变好；
假如抉择的地位 $t$ 导致所有数到地位 $t$ 间隔均为奇数，此时总成本为 $n$，同时可知所有数的地位奇偶性雷同，此时抉择所有数中的任意一个的地位，可得总成本为 $0$ 的后果，因而选全新的地位会让后果变差；
假如抉择的地位 $t$ 导致所有数到地位 $t$ 间隔奇数后果为 $c1$，偶数后果为 $c2$，可知 $n = c1 + c2$，同时咱们通过调整 $t$ 的奇偶性来确保 $c1 <= c2$。此时总的老本为 $c1$，同时可知所有与 $t$ 间隔为奇数的数所在位置奇偶性雷同，所有与 $t$ 间隔为偶数的数所在位置奇偶性也雷同，此时将 $t$ 调整为与 $t$ 奇偶性雷同的原有数的地位，同样可能失去总成本为 $c1$ 的后果，因而选全新的地位不会让后果变好。

综上，咱们能够枚举所有已有的地位为指标地位，并通过奇偶性统计其余地位到指标地位的老本，在所有已有地位中取最小的总成本即是答案。

代码：

class Solution {public int minCostToMoveChips(int[] ps) {
        int n = ps.length, ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {int a = ps[i], cur = 0;
            for (int j = 0; j < n; j++) {int b = ps[j];
                cur += Math.abs(a - b) % 2;
            }
            ans = Math.min(ans, cur);
        }
        return ans;
    }
}

工夫复杂度：$O(n^2)$
空间复杂度：$O(1)$

更进一步，咱们能够发现要使得「总的挪动老本最优」的指标地位有无数个，只有指标地位的奇偶性不变，即可确保总成本不变。

因而咱们能够省去枚举具体位置的操作，转而统计原有数的奇偶地位个数，假如偶数地位有 $a$ 个，奇数地位有 $b$ 个，最终目标地位选为偶数的老本为 $b$，最终目标地位选为奇数的老本为 $a$，即两者中的最小值即是答案。

代码：

class Solution {public int minCostToMoveChips(int[] ps) {
        int n = ps.length, a = 0;
        for (int i : ps) a += i % 2;
        return Math.min(a, n - a);
    }
}

工夫复杂度：$O(n)$
空间复杂度：$O(1)$

这是咱们「刷穿 LeetCode」系列文章的第 No.1217 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

本文由 mdnice 多平台公布

关于后端:1217-玩筹码-简单贪心运用题

题目形容

贪婪 + 枚举指标地位

贪婪 + 统计奇偶性

最初