位运算，leetcode191，461，338-北京尧图网络

这三道题是同一套知识的三次升级串起来看会有种原来如此的感觉。一、一张图看清三者的关系┌─────────────────────────────────────┐ │ 共同终点数一个二进制数里有几个 1 │ └─────────────────────────────────────┘ ↑ ┌─────────────────┼─────────────────┐ │ │ │ 【191】【461】【338】数一个数数两数差异数所有数 │ │ │ 直接数先异或再数用DP批量数 │ │ │ O(k) 一发入魂多一步 x^y 复用前面算好的一句话概括差异题号题目数什么关键动作复杂度191位 1 的个数数一个数里的 1直接n(n-1)O(k)461汉明距离数两数差异的位数先x^y标记差异再数O(k)338比特位计数数0~n 所有数里的 1DP 复用已算结果O(n)k 1 的个数或不同位的个数不是数的大小。二、第一层191 —— 掌握数 1这个基本动作它教你的是工具本身。public int hammingWeight(int n) { int cnt 0; while (n ! 0) { n n - 1; // 抹掉最右侧的 1 cnt; } return cnt; }核心机制你之前已经吃透了n-1借位会自动跳过最右那串 0一击命中最近的 1之后恰好只让那一个 1 消失。有几个 1 就循环几次中间的 0 全部跳过。这一层必须真正理解的是为什么它比逐位判断快——n 8 (00001000只有1个1) n(n-1) 法: 1 次逐位判断法: 32 次快 32 倍的来源就是跳过 0的能力。三、第二层461 —— 学会把新问题转化成旧问题它教你的是转化的思路。汉明距离定义是两数二进制位不同的位置数。乍看是个新概念但异或一步就把它打回原形x 0001 y 0100 x^y 0101 ← 每个 1 恰好标记一个不同的位置异或的规则是不同为 1所以x^y里的 1天然就是不同的位置。于是数两数有几位不同 ≡ 数x^y里有几个 1 ≡ 191 题public int hammingDistance(int x, int y) { int n x ^ y; // 转化新题 → 旧题 int cnt 0; while (n ! 0) { n n-1; cnt; } // 完全照搬 191 return cnt; }这一层的思维模式拿到新题先想能不能化归到已解决的问题。异或就是那座桥。四、第三层338 —— 当数 1要做很多次时如何批量化它教你的是复用DP。338 要求对0~n每一个数都算出 1 的个数。最简单的想法是对每个数调 191 的解法——能过但复杂度 O(n log n)题目要求 O(n)。关键洞察i(i-1)和i1都会得到一个比 i 小的数而这个更小的数的答案已经算过了// 思路A用 i(i-1) 复用直接复用你笔记里的操作 ans[i] ans[i (i-1)] 1; // 抹掉最右的11的个数少1 // 思路B用 i1 复用更推荐更好理解 ans[i] ans[i 1] (i 1); // 砍掉末位加上末位的贡献这一层的思维模式重复计算时找更小的子问题已算好的答案。因为i(i-1) i且i1 i从小到大扫一遍查表时答案必然已在数组里。五、三层之间的递进关系层次题新增能力思维升级基础191会数 1掌握一个高效的原子操作转化461会异或标记新问题 → 旧问题批量338会 DP 复用重复计算 → 查表底层工具从头到尾没变过一直是这四个n (n-1) // 抹掉最右的 1 ← 数 1 的核心 n -n // 提取最右的 1 n x // 搬数据 / 砍末位 1 x // 造掩码变的只是怎么组织这些工具。六、三题共同的三个坑这三题踩的坑高度重合记住一次管三题while (n ! 0)不能写成n 0负数如-132 个 1会被n 0直接判死返回 0正确答案 32。必须用! 0。和要分清左补符号位负数补 1左补 0。涉及无符号视角或遍历所有位时用才语义正确。191/461 的逐位解法尤其要注意。计数单位要统一338 里ans[i]存的是个数所以右边两项也必须是个数——这就是为什么是ans[i1]查表拿个数而不是i1那是数值。

位运算，leetcode191，461，338

相关推荐

MLP二次创作meme：哀叹主题的情感表达与创作技巧

DNF 70版本私服搭建全攻略：从环境配置到特色玩法实现

CATIA V5改版后CAM工序断开怎么办？3D InterOp跨版本关联方案**

更多资讯

从10类实体到21个BIO标签：BERT微调中文NER对齐实战

GitLab、Bitbucket与GitPuk代码管理平台深度对比

Git代码暂存机制详解与应用实践

MagicDraw SysML中文教程：MBSE建模学习路径与工程落地

Agentic Web与ANP协议：下一代互联网的智能体协作架构

IDEA中Tomcat多项目部署实战与优化

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？