leetcode2859-计算K置位下标对应元素的和

题目链接

2859. 计算 K 置位下标对应元素的和 - 力扣(LeetCode)

解题思路

  1. 枚举nums的每一个下标i;
  2. 统计i的二进制数的1的个数;
  3. 累加满足bit_count(i) == k的nums[i];

难点,如何统计二进制中1的个数?


例题

2859. 计算 K 置位下标对应元素的和 - 力扣(LeetCode)

位运算

我们可以通过位运算:

  • 通过&i:获取最低位的值;
  • 通过>>i:每次右移一位来更新最低位

这样的复杂度为O(C),C为数字的数据类型的位数。

位运算优化

我们可以用 n = n & (n - 1)代替n = n >> 1进行n的更新。这样做的好处是什么?

可以看到每一次 n = n & (n - 1)都会把当前n的最低为1一处掉,直到最后所有1都被消除,n变成0。

这样的时间复杂度为O(K),K为数字中的1的个数。

class Solution:
    def hammingWeight(self, n: int) -> int:
        c = 0
        while n != 0:
            n &= (n-1)
            c += 1
        return  c
        

综上

解题代码

class Solution:
    def sumIndicesWithKSetBits(self, nums: List[int], k: int) -> int:
        #统计位1的个数
        def bit_count(num:int) -> int:
            c = 0
            while num > 0:
                num &= num - 1
                c += 1
            return  c
        sum_ = 0
        #枚举每一个下标,如果下标位置等于k,累计对应的数值
        for i,num in enumerate(nums):
            if bit_count(i) == k:
                sum_ += num
        return sum_

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/347231.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

postgresql12表膨胀解决(不锁表)

查看所有数据库占用磁盘空间 SELECTpg_database.datname AS "数据库名称",pg_size_pretty(pg_database_size(pg_database.datname)) AS "磁盘占用空间" FROMpg_database;发现有个数据库占用空间过大 查询库中所有表占用空间 SELECTtable_name,pg_size_…

固态硬盘优化设置

目录 前言: 关闭Windows Search 禁用系统保护(不建议) 不建议禁用系统保护原因 关闭碎片整理 提升固态硬盘速度 开启TRIM 合理使用固态硬盘的容量 正确关机 关闭开机自启 前言: 电脑配备固态硬盘就能一劳永逸吗&#…

字符金字塔(C语言刷题)

个人博客主页:https://blog.csdn.net/2301_79293429?typeblog 专栏:https://blog.csdn.net/2301_79293429/category_12545690.html 题目描述 请打印输出一个字符金字塔,字符金字塔的特征请参考样例 输入描述: 输入一个字母,保…

动态规划-96.不同的二叉搜索树

给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种? 思路 二叉搜索树特性:左子树的节点全部小于根节点,右子树的节点全部大于根节点 n3,则1,2,3轮流当根节点。 当1为根节点时&am…

一个前端搬砖“专家“的2023年度总结

23年年中的时候,我跟领导进行了一次沟通,讨论了下我后面应该在哪些地方深入。最后我就记得领导那句:缺少总结。 我发现我好像确实缺少总结,我平时会把遇到的问题,感觉值得记录的写在csdn里面,但是都只是问…

大数据信用查询系统能查到什么呢?

在金融助贷行业,大数据有叫大数据信用或者网贷大数据,在申贷的时候,想必大多数人都有听说过,很多人因为大数据不良的原因申贷被拒过,那大数据信用查询系统能查到什么呢?本文就简单为大家总结几点大数据信用查询的内容…

建议码住!2023年全球16大AI聊天工具汇总来啦

2023值得载入史册。这一年,全世界的AI技术迎来了重大突破,并从多个角度影响和改变了我们的生活和工作。 AI可以和你聊天、为你提供专业的法律建议、快速查找资料,还能帮助你制作视频、设计图片、制做PPT,甚至能够写代码、写小说、…

执行ping命令时提示ping: sendmsg: Operation not permitted

查看日志发现出现了大量的table full, dropping packet记录, 后上网查看资料发现是因为当前会话数已经满了,因此出现丢包现象。 这里需要说一下nf_conntrack nf_conntrack(在老版本的 Linux 内核中叫 ip_conntrack)是一个内核模块,用于跟踪一…

1005. K 次取反后最大化的数组和 - 力扣(LeetCode)

题目描述 给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。) 以这种方式修改数组后,返回数组可…

Oracal学习

Oracle是什么 是甲骨文公司的一款支持事务且吞吐量高的数据库特点: (1)支持多用户、大事务量的事务处理 (2)数据安全性和完整性控制 (3)支持分布式数据处理 (4)可移植性…

深度学习中RGB影像图的直方图均衡化python代码and对图片中指定部分做基于掩模的特定区域直方图均衡化

深度学习很重要的预处理步骤 就是需要对做直方图均衡化 其中主要分成灰度图以及RGB图的直方图均衡化 这俩的方法和代码不同 想要去看具体原理的朋友可以查看下面这篇博客的内容 写的很详细颜色直方图均衡化(https://www.cnblogs.com/wancy/p/17668345.html) 我们这个场景中会用…

Git 入门精讲

我们为什么要学习git? 就当下的发展而言,只要你从事开发就一定会接触git。作为最强大的分布式版本控制器,git 与 svn 有着本质上的区别。 Git是一种分布式版本控制系统,每个开发者都可以在本地维护完整的代码库,可以离…

04 经典的OSPF

思维导图的方式回顾OSPF 什么是OSPF?为什么需要OSPF? - 华为 (huawei.com) 1 ospf 领行学习思维导图 1.1 ospf 的工作过程 建立领据表同步数据库计算路由表1.2 ospf 的状态

C++ 红黑树

目录 一、红黑树的概念和性质 二、实现红黑树 1、节点定义构造 2、插入 3、左单旋&右单旋 4、中序遍历 5、检查平衡 6、获取树的高度 7、查找 8、析构 测试 完整版 一、红黑树的概念和性质 红黑树,是一种二叉搜索树,但在每个结点上增加一…

数据恢复与硬盘修理

第1篇 数据恢复与硬盘修理基础 本篇包括第1章,主要介绍数据恢复的发展现状、硬盘维修的基本知识以及一些基本工具的使用。 第1章 基础知识 1.1 数据恢复技术的发展和研究现状 目前国内的数据恢复服务市场处于一个极不规范的状态。虽然大部分数据恢复服务提供商是…

Linux CentOs7 安装Mysql(5.7和8.0版本)密码修改 超详细教程

CSDN 成就一亿技术人! 今天出一期Centos下安装Mysql(详细教程)包括数据库密码跳过修改 CSDN 成就一亿技术人! 目录 1.获取安装包 2.安装程序 安装下载的rpm包 查看安装包 修改5.7版本(重要) 安装M…

如何生成漂亮的静态文档说明页

分享:如何生成漂亮的静态文档说明页 最近经常被问 https://t.itmuch.com/doc.html 文档页是怎么制作的,考虑到步骤略复杂,写篇手记总结下吧。 TIPS https://t.itmuch.com/doc.html 是个人在慕课网视频《 面向未来微服务:Spring Cloud Alibab…

二叉树堆的应用实例分析:堆排序 | TOP-K问题

📷 江池俊: 个人主页 🔥个人专栏: ✅数据结构冒险记 ✅C语言进阶之路 🌅 有航道的人,再渺小也不会迷途。 文章目录 前言一、堆排序1.1 排序思想1.2 堆排序过程(图解)1.3 堆排序代…

C++ 数论相关题目(欧拉函数、筛法求欧拉函数)

1、欧拉函数 给定 n 个正整数 ai ,请你求出每个数的欧拉函数。 欧拉函数的定义 1∼N 中与 N 互质的数的个数被称为欧拉函数,记为 ϕ(N) 。 若在算数基本定理中,Npa11pa22…pamm ,则: ϕ(N) Np1−1p1p2−1p2…pm−1p…

【数学建模】插值与拟合

文章目录 插值插值方法用Python解决插值问题 拟合最小二乘拟合数据拟合的Python实现 适用情况 处理由试验、测量得到的大量数据或一些过于复杂而不便于计算的函数表达式时,构造一个简单函数作为要考察数据或复杂函数的近似 定义 给定一组数据,需要确定满…