leetcode-每日一题1217. 玩筹码(贪心+位运算)

简介: 判断元素的奇偶性,把奇数下标记录在odd 元素里

760ccad0d3e141fdbb7e881181d3b042.png


题目链接https://leetcode.cn/problems/minimum-cost-to-move-chips-to-the-same-position/


思路


直接想法


这题要求得到移动到同一格子的最小成本,跳两格的成本是0,跳一格的成本是1,所以我们需要尽量跳两格,发现刚好可以分成下标奇偶两列的棋子,可以把奇偶两列的棋子都移动到相邻的点上(移动到1和2上),此时我们只需要对比移动那块的棋子成本最低即可


算法


  • 遍历棋子下标 position 数组

。判断元素的奇偶性,把奇数下标记录在odd 元素里

  • 对比奇数格子上的棋子和偶数格子上的棋子的数量,返回两者最小值 即可


代码示例


func minCostToMoveChips(position []int) int {
    odd := 0
    for _, v := range position {
        if v & 1 == 1{
            odd++
        }
    }
    //len(position) - odd表示偶数格子的数量
    if odd > len(position) - odd {
        return len(position) - odd
    }
    return odd
}

4efed84b87fd4c90addc2283afe3a8a4.png


复杂度分析


  • 时间复杂度:O(n) 其中n表示数组长度,遍历数组需要花费O(n)的时间
  • 空间复杂度:O(1) 没有申请额外空间
目录
相关文章
|
6月前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
6月前
|
Java 程序员
【Leetcode 程序员面试金典 05.01】插入 —— 位运算
位运算问题,只需要把 N 的 i 到 j 位都置 0 后再和 M 左移 i 位的结果进行按位或即可
|
5月前
|
算法 索引
力扣随机一题 位运算/滑动窗口/数组
力扣随机一题 位运算/滑动窗口/数组
40 0
|
算法 C语言 C++
【位运算问题】Leetcode 136、137、260问题详解及代码实现
此外,任意一个数异或0都为他本身 (这从二进制编码来理解也很好理解,0的二进制编码全为0,任意一个数与其异或不同的就是若干位的1)
88 0
|
存储 算法 JavaScript
📖位运算在力扣算法问题的妙用
📖位运算在力扣算法问题的妙用
110 1
📖位运算在力扣算法问题的妙用
|
编译器 API C语言
力扣面试题17.04 - 消失的数字【求和相减 + 异或位运算 + 哈希表】
三种方法巧解力扣面试题17.04 - 消失的数字,你值得拥有
143 0
力扣面试题17.04 - 消失的数字【求和相减 + 异或位运算 + 哈希表】
|
机器学习/深度学习 算法
《LeetCode》位运算详解
《LeetCode》位运算详解
184 0
《LeetCode》位运算详解
|
缓存 Java 程序员
|
算法 C++ Python
经典位运算算法模板-附LeetCode剑指 Offer 56 - I. 数组中数字出现的次数-题解-python && C++源代码
经典位运算算法模板-附LeetCode剑指 Offer 56 - I. 数组中数字出现的次数-题解-python && C++源代码
|
C++ Python
LeetCode每日一题题解:693. 交替位二进制数-题解-python && C++源代码-经典位运算
LeetCode每日一题题解:693. 交替位二进制数-题解-python && C++源代码-经典位运算