这三道题是同一套知识的三次升级串起来看会有种原来如此的感觉。一、一张图看清三者的关系┌─────────────────────────────────────┐ │ 共同终点数一个二进制数里有几个 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那是数值。
