1217. Play with Chips

yPhantom 2019年10月14日 27次浏览

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

  • Move the i-th chip by 2 units to the left or to the right with a cost of 0.
  • Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

Example 1:

Input: chips = [1,2,3]
Output: 1
Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

Example 2:

Input: chips = [2,2,2,3,3]
Output: 2
Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.

Constraints:

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

Solution

这道题是这次考试唯一快速又准确的做出来的题目了emoji people:sweat

说一下思考过程。首先题目中的两个条件,一个chip左右移动两步则cost为0,左右移动一步cost为1,当时脑袋立刻就想到那把所有的chip都按两步移动进行简化一下,相当于小学学的表达式化简了。

然后看了一下例子,又在纸上画了画,发现这样移动之后就只有相邻的两个的位置了,每个位置上的数的个数分别是chip的奇数值和偶数值。因此有如下代码:

class Solution {
    public int minCostToMoveChips(int[] chips) {
        int oddCount = 0;
        int evenCount = 0;
        for(int chip: chips) {
            if (chip % 2 == 1) {
                oddCount++;
            } else {
                evenCount++;
            }
        }
        return Math.min(oddCount, evenCount);
    }
}