LeetCode: 1217.Play With Chips(玩筹码)

灰太狼 2023-07-04 15:47 8阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k）][LeetCode_560. Subarray Sum Equals K_k]**

--------------------

**文章目录：**

题目描述：

java实现方式1：

python实现方式1：

java实现方式2：

python实现方式2：

源码地址：

--------------------

### 题目描述： ###

数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。

你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：

将第 i 个筹码向左或者右移动 2 个单位，代价为 0。  
将第 i 个筹码向左或者右移动 1 个单位，代价为 1。  
最开始的时候，同一位置上也可能放着两个或者更多的筹码。

返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

示例 1：

输入：chips = [1,2,3]
    输出：1
    解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。

示例 2：

输入：chips = [2,2,2,3,3]
    输出：2
    解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。

提示：

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

--------------------

### java实现方式1： ###

/**
         * 摆筹码
         *
         * @param chips 筹码下标
         * @return 最小距离
         */
        public int minCostToMoveChips(int[] chips) {
            int step = 0;
            for (int chip : chips) {
                if (chip % 2 == 1) {
                    step++;
                }
            }
            return Math.min(step, chips.length - step);
        }

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### python实现方式1： ###

def min_cost_to_move_chips(chips: List[int]) -> int:
        '''
            摆筹码代价最小
        Args:
            chips: 数组
        Returns:
            摆筹码
        '''
        step = 0
        for num in chips:
            if num % 2 == 1:
                step += 1
        return min(step, len(chips) - step)

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### java实现方式2： ###

/**
         * 摆筹码 (要么摆到奇数位置，要么摆到偶数位置，最后取最小值)
         *
         * @param chips 筹码下标
         * @return 最小距离
         */
        public int minCostToMoveChips2(int[] chips) {
            int step1 = 0;
            int step2 = 0;
            for (int chip : chips) {
                if (chip % 2 == 1) {
                    step1++;
                } else {
                    step2++;
                }
            }
            return Math.min(step1, step2);
        }

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### python实现方式2： ###

def min_cost_to_move_chips2(chips: List[int]) -> int:
        '''
            摆筹码代价最小
        Args:
            chips: 数组
        Returns:
            摆筹码
        '''
        step1, step2 = 0, 0
        for num in chips:
            if num % 2 == 1:
                step1 += 1
            else:
                step2 += 1
        return min(step1, step2)

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### 源码地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode