共计 1929 个字符，预计需要花费 5 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 1217. 玩筹码 ，难度为 简略。
Tag :「贪婪」、「枚举」
有 n 个筹码。第 $i$ 个筹码的地位是 position[i]。
咱们须要把所有筹码移到同一个地位。在一步中，咱们能够将第 $i$ 个筹码的地位从 $position[i]$ 扭转为:
position[i] + 2 或 position[i] - 2，此时cost = 0position[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 多平台公布
