网站建设精准精细快速,制作网站404页面,中企动力z邮局登录,网站seo诊断优化分析该怎么做文章目录 前言LeetCode、338. 比特位计数【中等#xff0c;位运算】题目链接与分类思路位运算移位处理前缀思想实现 资料获取 前言
博主介绍#xff1a;✌目前全网粉丝2W#xff0c;csdn博客专家、Java领域优质创作者#xff0c;博客之星、阿里云平台优质作者、专注于Java… 文章目录 前言LeetCode、338. 比特位计数【中等位运算】题目链接与分类思路位运算移位处理前缀思想实现 资料获取 前言
博主介绍✌目前全网粉丝2Wcsdn博客专家、Java领域优质创作者博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引博客目录索引(持续更新)
视频平台b站-Coder长路 LeetCode、338. 比特位计数【中等位运算】
题目链接与分类
题目链接LeetCode、338. 比特位计数
分类基础算法/位运算 思路
位运算移位处理
思路暴力来对所有数字的二进制位来进行模拟计算。
复杂度分析时间复杂度O(n.logn)空间复杂度O(n)
class Solution {//10万数据量public int[] countBits(int n) {int[] res new int[n 1];for (int i 0; i n; i ) {int count 0;int num i;while (num ! 0) {if (num % 2 1) count ;num num 1;}res[i] count;}return res;}
}前缀思想实现
思路二叉树来保存1-n左子树使用0、右子树使用1左边表示1右边表示x21。 复杂度分析时间复杂度O(n)空间复杂度O(n)
class Solution {// 主函数计算 0 到 n 的每个数字的二进制表示中包含的 1 的个数public int[] countBits(int n) {int[] res new int[n 1]; // 初始化结果数组// 从数字1开始进行深度优先搜索dfs(1, n, 1, res);return res;}// 深度优先搜索函数private void dfs(int num, int max, int cnt, int[] res) {if (num max) { // 如果当前数字大于给定的最大值结束递归return;}res[num] cnt; // 更新结果数组记录当前数字的二进制表示中包含的1的个数// 递归调用左子树和右子树dfs(num 1, max, cnt, res); // 左子树1的个数不变dfs((num 1) 1, max, cnt 1, res); // 右子树1的个数加1}
}资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅在下方专栏
长路-文章目录汇总算法、后端Java、前端、运维技术导航博主所有博客导航索引汇总开源项目Studio-Vue—校园工作室管理系统(含前后台SpringBootVue)博主个人独立项目包含详细部署上线视频已开源学习与生活-专栏可以了解博主的学习历程算法专栏算法收录
更多博客与资料可查看获取联系方式文末获取开发资源及更多资源博客获取 整理者长路 时间2024.2.13
