登录
每日一题-交替位二进制数🟢
2026年2月18日 00:00
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
示例 1：
输入：n = 5 输出：true 解释：5 的二进制表示是：101
示例 2：
输入：n = 7 输出：false 解释：7 的二进制表示是：111.
示例 3：
输入：n = 11 输出：false 解释：11 的二进制表示是：1011.
提示：
1 <= n <= 231 - 1
普通视图
今天 — 2026年2月18日LeetCode 每日一题题解
【宫水三叶】位运算应用题
2022年3月28日 07:06
遍历
根据题意，对 $n$ 的每一位进行遍历检查。
代码：
###Java
class Solution {
public boolean hasAlternatingBits(int n) {
int cur = -1;
while (n != 0) {
int u = n & 1;
if ((cur ^ u) == 0) return false;
cur = u; n >>= 1;
}
return true;
}
}
- 时间复杂度：$O(\log{n})$
- 空间复杂度：$O(1)$
位运算
另外一种更为巧妙的方式是利用交替位二进制数性质。
当给定值 $n$ 为交替位二进制数时，将 $n$ 右移一位得到的值 $m$ 仍为交替位二进制数，且与原数 $n$ 错开一位，两者异或能够得到形如 $0000...1111$ 的结果 $x$，此时对 $x$ 执行加法（进位操作）能够得到形如 $0000...10000$ 的结果，将该结果与 $x$ 执行按位与后能够得到全 $0$ 结果。
代码：
###Java
class Solution {
public boolean hasAlternatingBits(int n) {
int x = n ^ (n >> 1);
return (x & (x + 1)) == 0;
}
}
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
同类型加餐
今日份加餐：经典「状态压缩 + 位运算」入门题 🎉🎉
或是考虑加练如下「位运算」题目 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 137. 只出现一次的数字 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 190. 颠倒二进制位 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 191. 位1的个数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 260. 只出现一次的数字 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 405. 数字转换为十六进制数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 461. 汉明距离 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 477. 汉明距离总和 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 526. 优美的排列 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
交替位二进制数
2022年3月26日 09:47
方法一：模拟
思路
从最低位至最高位，我们用对 $2$ 取模再除以 $2$ 的方法，依次求出输入的二进制表示的每一位，并与前一位进行比较。如果相同，则不符合条件；如果每次比较都不相同，则符合条件。
代码
###Python
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
prev = 2
while n:
cur = n % 2
if cur == prev:
return False
prev = cur
n //= 2
return True
###Java
class Solution {
public boolean hasAlternatingBits(int n) {
int prev = 2;
while (n != 0) {
int cur = n % 2;
if (cur == prev) {
return false;
}
prev = cur;
n /= 2;
}
return true;
}
}
###C#
public class Solution {
public bool HasAlternatingBits(int n) {
int prev = 2;
while (n != 0) {
int cur = n % 2;
if (cur == prev) {
return false;
}
prev = cur;
n /= 2;
}
return true;
}
}
###C++
class Solution {
public:
bool hasAlternatingBits(int n) {
int prev = 2;
while (n != 0) {
int cur = n % 2;
if (cur == prev) {
return false;
}
prev = cur;
n /= 2;
}
return true;
}
};
###C
bool hasAlternatingBits(int n) {
int prev = 2;
while (n != 0) {
int cur = n % 2;
if (cur == prev) {
return false;
}
prev = cur;
n /= 2;
}
return true;
}
###go
func hasAlternatingBits(n int) bool {
for pre := 2; n != 0; n /= 2 {
cur := n % 2
if cur == pre {
return false
}
pre = cur
}
return true
}
###JavaScript
var hasAlternatingBits = function(n) {
let prev = 2;
while (n !== 0) {
const cur = n % 2;
if (cur === prev) {
return false;
}
prev = cur;
n = Math.floor(n / 2);
}
return true;
};
复杂度分析
-
时间复杂度：$O(\log n)$。输入 $n$ 的二进制表示最多有 $O(\log n)$ 位。
-
空间复杂度：$O(1)$。使用了常数空间来存储中间变量。
方法二：位运算
思路
对输入 $n$ 的二进制表示右移一位后，得到的数字再与 $n$ 按位异或得到 $a$。当且仅当输入 $n$ 为交替位二进制数时，$a$ 的二进制表示全为 $1$（不包括前导 $0$）。这里进行简单证明：当 $a$ 的某一位为 $1$ 时，当且仅当 $n$ 的对应位和其前一位相异。当 $a$ 的每一位为 $1$ 时，当且仅当 $n$ 的所有相邻位相异，即 $n$ 为交替位二进制数。
将 $a$ 与 $a + 1$ 按位与，当且仅当 $a$ 的二进制表示全为 $1$ 时，结果为 $0$。这里进行简单证明：当且仅当 $a$ 的二进制表示全为 $1$ 时，$a + 1$ 可以进位，并将原最高位置为 $0$，按位与的结果为 $0$。否则，不会产生进位，两个最高位都为 $1$，相与结果不为 $0$。
结合上述两步，可以判断输入是否为交替位二进制数。
代码
###Python
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
a = n ^ (n >> 1)
return a & (a + 1) == 0
###Java
class Solution {
public boolean hasAlternatingBits(int n) {
int a = n ^ (n >> 1);
return (a & (a + 1)) == 0;
}
}
###C#
public class Solution {
public bool HasAlternatingBits(int n) {
int a = n ^ (n >> 1);
return (a & (a + 1)) == 0;
}
}
###C++
class Solution {
public:
bool hasAlternatingBits(int n) {
long a = n ^ (n >> 1);
return (a & (a + 1)) == 0;
}
};
###C
bool hasAlternatingBits(int n) {
long a = n ^ (n >> 1);
return (a & (a + 1)) == 0;
}
###go
func hasAlternatingBits(n int) bool {
a := n ^ n>>1
return a&(a+1) == 0
}
###JavaScript
var hasAlternatingBits = function(n) {
const a = n ^ (n >> 1);
return (a & (a + 1)) === 0;
};
复杂度分析
-
时间复杂度：$O(1)$。仅使用了常数时间来计算。
-
空间复杂度：$O(1)$。使用了常数空间来存储中间变量。
python3 位运算
2019年9月2日 15:53
将n右移一位异或n，检查结果是否全为1。
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
tmp = n^(n>>1)
return tmp&(tmp+1) == 0
昨天 — 2026年2月17日LeetCode 每日一题题解
简单题，简单做（Python/Java/C++/Go）
2026年2月17日 07:29
枚举小时 $h=0,1,2,\ldots,11$ 以及分钟 $m=0,1,2,\ldots,59$。如果 $h$ 二进制中的 $1$ 的个数加上 $m$ 二进制中的 $1$ 的个数恰好等于 $\textit{turnedOn}$，那么把 $h:m$ 添加到答案中。
注意如果 $m$ 是个位数，需要添加一个前导零。
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
ans = []
for h in range(12):
for m in range(60):
if h.bit_count() + m.bit_count() == turnedOn:
ans.append(f"{h}:{m:02d}")
return ans
class Solution {
public List<String> readBinaryWatch(int turnedOn) {
List<String> ans = new ArrayList<>();
for (int h = 0; h < 12; h++) {
for (int m = 0; m < 60; m++) {
if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
ans.add(String.format("%d:%02d", h, m));
}
}
}
return ans;
}
}
class Solution {
public:
vector<string> readBinaryWatch(int turnedOn) {
vector<string> ans;
char s[6];
for (uint8_t h = 0; h < 12; h++) {
for (uint8_t m = 0; m < 60; m++) {
if (popcount(h) + popcount(m) == turnedOn) {
sprintf(s, "%d:%02d", h, m);
ans.emplace_back(s);
}
}
}
return ans;
}
};
func readBinaryWatch(turnedOn int) (ans []string) {
for h := range 12 {
for m := range 60 {
if bits.OnesCount8(uint8(h))+bits.OnesCount8(uint8(m)) == turnedOn {
ans = append(ans, fmt.Sprintf("%d:%02d", h, m))
}
}
}
return
}
复杂度分析
- 时间复杂度：$\mathcal{O}(1)$。
- 空间复杂度：$\mathcal{O}(1)$。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
每日一题-二进制手表🟢
2026年2月17日 00:00
二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。每个 LED 代表一个 0 或 1，最低位在右侧。
- 例如，下面的二进制手表读取
"4:51"。
给你一个整数 turnedOn ，表示当前亮着的 LED 的数量，返回二进制手表可以表示的所有可能时间。你可以 按任意顺序 返回答案。
小时不会以零开头：
- 例如，
"01:00"是无效的时间，正确的写法应该是"1:00"。
分钟必须由两位数组成，可能会以零开头：
- 例如，
"10:2"是无效的时间，正确的写法应该是"10:02"。
示例 1：
输入：turnedOn = 1 输出：["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
示例 2：
输入：turnedOn = 9 输出：[]
提示：
0 <= turnedOn <= 10
401. 二进制手表，回溯，Java0ms
2021年3月12日 12:12
401. 二进制手表
思路
简单提一句，回溯就是纯暴力枚举，配合剪枝食用风味更佳
- 总体思路
- 在10个灯中选num个灯点亮，如果选择的灯所组成的时间已不合理（小时超过11，分钟超过59）就进行剪枝
- 也就是从0到10先选一个灯亮，再选当前灯的后面的灯亮，再选后面的灯的后面的灯亮，一直到num个灯点满
- 具体思路
- 为了方便计算，分别设置了小时数组和分钟数组
- 递归的四个参数分别代表：剩余需要点亮的灯数量，从索引index开始往后点亮灯，当前小时数，当前分钟数
- 每次进入递归后，先判断当前小时数和分钟数是否符合要求，不符合直接return
- for循环枚举点亮灯的情况，从index枚举到10，每次枚举，
- 减少一个需要点亮的灯数量num - 1
- 从当前已点亮的灯后面选取下一个要点亮的灯 i + 1
- 在hour中增加当前点亮灯的小时数，
如果i大于3，当前灯是分钟灯而不是小时灯，则加上0个小时 - 在minute中增加当前点亮灯的分钟数，
如果i没有大于3，当前灯是小时灯而不是分钟灯，则加上0分钟
- 当剩余需要点亮的灯数量为0的时候，已枚举完一种情况，根据题目要求的格式加到res列表中
- 返回res
代码
class Solution:
def readBinaryWatch(self, num: int) -> List[str]:
hours = [1, 2, 4, 8, 0, 0, 0, 0, 0, 0]
minutes = [0, 0, 0, 0, 1, 2, 4, 8, 16, 32]
res = []
def backtrack(num, index, hour, minute):
if hour > 11 or minute > 59:
return
if num == 0:
res.append('%d:%02d' % (hour, minute))
return
for i in range(index, 10):
backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i])
backtrack(num, 0, 0, 0)
return res
class Solution {
int[] hours = new int[]{1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
int[] minutes = new int[]{0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
List<String> res = new ArrayList<>();
public List<String> readBinaryWatch(int num) {
backtrack(num, 0, 0, 0);
return res;
}
public void backtrack(int num, int index, int hour, int minute){
if(hour > 11 || minute > 59)
return;
if(num == 0){
StringBuilder sb = new StringBuilder();
sb.append(hour).append(':');
if (minute < 10) {
sb.append('0');
}
sb.append(minute);
res.add(sb.toString());
return;
}
for(int i = index; i < 10; i++){
backtrack(num - 1, i + 1, hour + hours[i], minute + minutes[i]);
}
}
}
复杂度分析
- 时间复杂度：$O(C^{num}_{10})$ 从10个选num个，实际比这个低因为剪枝了
- 空间复杂度：$O(num)$
C++总结了回溯问题类型 带你搞懂回溯算法(搜索篇)
2020年5月4日 02:03
在上一篇题解中，我总结了回溯算法的三种类型，以及什么时候用回溯算法，怎么写回溯算法，如果没看过的，强烈建议先看：C++ 总结了回溯问题类型 带你搞懂回溯算法(大量例题)
这一节，我们就来解析“搜索”类型的回溯问题。
为什么要单独分出一种“搜索”类型？
其实，“搜索”类型的题解中都能看到“子集”、“排列”类型题目的影子，只要你搞懂前面两种类型问题的本质，就很容易联想到了。“搜索”类型的问题最难的就是把问题抽象化！！大多数比赛或者面试题中不会直接出现“子集、排列、组合”等字眼，更不会直接让去求，而是通过某些包装，借助某个情景，让你一下子摸不着头脑，看不出应该使用哪种解法，本题就是最好的说明
解题步骤：
1.读懂题意，把题目尽可能抽象成“子集、排列、组合”类型问题
本题的题目总结而言就是：有十盏灯，我分别给他编号0-9，号码0-3代表小时，号码4-9代表分钟，然后每盏灯又代表着不同数字，如下图
(灯泡中的红色数字,其实就是二进制转换，题目中的图也有标)
然后从10盏灯中挑选n盏打开，问你有多少种组合，返回这些组合代表的时间。这样一翻译，是不是有点“组合”类型问题的味道了？说白了就是：从n个数里面挑选k个，返回组合。如果你能形成这种抽象思想，那么你就成功一大半了。
2.回溯六步走
- ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要
- ②根据题意，确立结束条件**
- ③找准选择列表(与函数参数相关),与第一步紧密关联
- ④判断是否需要剪枝**
- ⑤作出选择，递归调用，进入下一层
- ⑥撤销选择
3.开始解题
①递归树，这里用动画演示。假设n=2，即选两盏灯亮
<,,,,,,,,,,,,>
我们接下来思考，回溯函数需要什么哪些参数，来表示当前状态。首先灯是越来越少的，所以需要一个参数num,表示剩余可亮的灯数，直到num等于0就应该结束；然后还需要参数start，来指示当前可选择的灯的开始位置，比如n=2我选了7号灯,然后剩下的一盏灯，只能选8号或9号，你不可能回去选0-6号，因为会导致重复，这个问题在“子集、组合”类型问题中说过，详细请看顶部的文章；最后还需要一个time参数，来表示当前状态的时间。算法签名如下
###cpp
unordered_map<int,int> hash={{0,1},{1,2},{2,4},{3,8},{4,1},{5,2},{6,4},{7,8},{8,16},{9,32}};//用一个hash表映射，灯对应的数字
void backtrack(int num,int start,pair<int,int>& time)//我用stl中的pair结构来统一管理小时和分钟，代码比较简洁，你也可以把他们拆成两个参数，hour和minute
②根据题意，确立结束条件
这个上面提到过了，当num=0就是没有灯可以点亮了，就应该return，加入结果集
###cpp
if(num==0)
{
if(time.first>11||time.second>59)//判断合法性,注意题目要求
return;
string temp_hour=to_string(time.first);
string temp_minute=to_string(time.second);
if(temp_minute.size()==1)//如果minute只有一位要补0，注意题目要求
temp_minute.insert(0,"0");
res.push_back(temp_hour+":"+temp_minute);//构造格式
return;
}
③找准选择列表
从参数start标识的位置开始，到最后一盏灯，都是可选的
###cpp
for(int i=start;i<10;i++)
{
}
④判断是否需要剪枝
当hour>11或minute>59的时候，无论还有没有灯可以点亮，都不用再继续递归下去，因为后面只会越增越多，应该剪枝
###cpp
for(int i=start;i<10;i++)
{
if(time.first>11||time.second>59)
continue;
}
⑤作出选择，递归调用，进入下一层
###cpp
for(int i=start;i<10;i++)
{
if(time.first>11||time.second>59)
continue;
pair<int,int>store=time;//保存状态,用于回溯时，恢复当前状态
if(i<4)//对小时数进行操作
time.first+=hash[i];
else//对分钟数进行操作
time.second+=hash[i];
backtrack(num-1,i+1,time);//进入下一层，注意下一层的start是i+1，即从当前灯的下一盏开始
⑥撤销选择
整体代码如下
###cpp
vector<string>res;
unordered_map<int,int> hash={{0,1},{1,2},{2,4},{3,8},{4,1},{5,2},{6,4},{7,8},{8,16},{9,32}};
void backtrack(int num,int start,pair<int,int>& time)
{
if(num==0)
{
if(time.first>11||time.second>59)//判断合法性
return;
string temp_hour=to_string(time.first);
string temp_minute=to_string(time.second);
if(temp_minute.size()==1)//如果minute只有一位要补0
temp_minute.insert(0,"0");
res.push_back(temp_hour+":"+temp_minute);//构造格式
return;
}
for(int i=start;i<10;i++)
{
if(time.first>11||time.second>59)
continue;
pair<int,int>store=time;//保存状态
if(i<4)
time.first+=hash[i];
else
time.second+=hash[i];
backtrack(num-1,i+1,time);//进入下一层，注意下一层的start是i+1，即从当前灯的下一盏开始
time=store;//恢复状态
}
}
vector<string> readBinaryWatch(int num) {
pair<int,int>time(0,0);//初始化时间为0:00
backtrack(num,0,time);
return res;
}
C++：简简单单的几行代码解决问题
2019年6月29日 20:09
class Solution {
public:
vector<string> readBinaryWatch(int num) {
vector<string> res;
//直接遍历 0:00 -> 12:00 每个时间有多少1
for (int i = 0; i < 12; i++) {
for (int j = 0; j < 60; j++) {
if (count1(i) + count1(j) == num) {
res.push_back(to_string(i)+":"+
(j < 10 ? "0"+to_string(j) : to_string(j)));
}
}
}
return res;
}
//计算二进制中1的个数
int count1(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
};
昨天以前LeetCode 每日一题题解
每日一题-颠倒二进制位🟢
2026年2月16日 00:00
颠倒给定的 32 位有符号整数的二进制位。
示例 1：
输入：n = 43261596
输出：964176192
解释：
| 整数 | 二进制 |
|---|---|
| 43261596 | 00000010100101000001111010011100 |
| 964176192 | 00111001011110000010100101000000 |
示例 2：
输入：n = 2147483644
输出：1073741822
解释：
| 整数 | 二进制 |
|---|---|
| 2147483644 | 01111111111111111111111111111100 |
| 1073741822 | 00111111111111111111111111111110 |
提示：
0 <= n <= 231 - 2-
n为偶数
进阶: 如果多次调用这个函数，你将如何优化你的算法？
O(1) 位运算分治，原理讲解（Python/Java/C++/Go）
2026年2月12日 09:58
以反转一个 $8$ 位整数为例。
为方便阅读，我把这个数字记作 $12345678$。目标是得到 $87654321$。
用分治思考，反转 $12345678$ 可以分成如下三步：
- 递归反转左半 $1234$，得到 $4321$。
- 递归反转右半 $5678$，得到 $8765$。
- 交换 $4321$ 和 $8765$，得到 $87654321$。
反转 $1234$ 可以拆分为反转 $12$ 和 $34$，反转 $5678$ 可以拆分为反转 $56$ 和 $78$。
对于 $12$ 这种长为 $2$ 的情况，交换 $1$ 和 $2$ 即可完成反转。
你可能会问：这样做，算法能更快吗？
利用位运算「并行计算」的特点，我们可以高效地实现上述过程。
去掉递归的「递」，直接看「归」的过程（自底向上）。
递归的最底层是反转 $12$，反转 $34$，反转 $56$，反转 $78$。利用位运算，这些反转可以同时完成：
$$
\begin{array}{c}
\text{12345678} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{分离}} \
\text{1\phantom{2}3\phantom{4}5\phantom{6}7\phantom{8}} \
\text{\phantom{1}2\phantom{3}4\phantom{5}6\phantom{7}8} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{移位}} \
\text{\phantom{2}1\phantom{2}3\phantom{4}5\phantom{6}7} \
\text{2\phantom{3}4\phantom{5}6\phantom{7}8\phantom{7}} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{合并}} \
\text{21436587} \
\end{array}
$$
然后两个两个交换：
$$
\begin{array}{c}
\text{21436587} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{分离}} \
\text{21\phantom{11}65\phantom{11}} \
\text{\phantom{11}43\phantom{11}87} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{移位}} \
\text{\phantom{11}21\phantom{11}65} \
\text{43\phantom{11}87\phantom{11}} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{合并}} \
\text{43218765} \
\end{array}
$$
然后四个四个交换：
$$
\begin{array}{c}
\text{43218765} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{分离}} \
\text{4321\phantom{1111}} \
\text{\phantom{1111}8765} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{移位}} \
\text{\phantom{1111}4321} \
\text{8765\phantom{1111}} \
\left\downarrow \rule{0pt}{1.5em} \right. \rlap{\text{合并}} \
\text{87654321} \
\end{array}
$$
依此类推。
对于 $32$ 位整数，还需要执行八个八个交换，最后把高低 $16$ 位交换。
m0 = 0x55555555 # 01010101 ...
m1 = 0x33333333 # 00110011 ...
m2 = 0x0f0f0f0f # 00001111 ...
m3 = 0x00ff00ff # 00000000111111110000000011111111
m4 = 0x0000ffff # 00000000000000001111111111111111
class Solution:
def reverseBits(self, n: int) -> int:
n = n>>1&m0 | (n&m0)<<1 # 交换相邻位
n = n>>2&m1 | (n&m1)<<2 # 两个两个交换
n = n>>4&m2 | (n&m2)<<4 # 四个四个交换
n = n>>8&m3 | (n&m3)<<8 # 八个八个交换
return n>>16 | (n&m4)<<16 # 交换高低 16 位
class Solution {
private static final int m0 = 0x55555555; // 01010101 ...
private static final int m1 = 0x33333333; // 00110011 ...
private static final int m2 = 0x0f0f0f0f; // 00001111 ...
private static final int m3 = 0x00ff00ff; // 00000000111111110000000011111111
public int reverseBits(int n) {
n = n>>>1&m0 | (n&m0)<<1; // 交换相邻位
n = n>>>2&m1 | (n&m1)<<2; // 两个两个交换
n = n>>>4&m2 | (n&m2)<<4; // 四个四个交换
n = n>>>8&m3 | (n&m3)<<8; // 八个八个交换
return n>>>16 | n<<16; // 交换高低 16 位
}
}
class Solution {
static constexpr uint32_t m0 = 0x55555555; // 01010101 ...
static constexpr uint32_t m1 = 0x33333333; // 00110011 ...
static constexpr uint32_t m2 = 0x0f0f0f0f; // 00001111 ...
static constexpr uint32_t m3 = 0x00ff00ff; // 00000000111111110000000011111111
uint32_t reverseBits32(uint32_t n) {
n = n>>1&m0 | (n&m0)<<1; // 交换相邻位
n = n>>2&m1 | (n&m1)<<2; // 两个两个交换
n = n>>4&m2 | (n&m2)<<4; // 四个四个交换
n = n>>8&m3 | (n&m3)<<8; // 八个八个交换
return n>>16 | n<<16; // 交换高低 16 位
}
public:
int reverseBits(int n) {
return reverseBits32(n);
}
};
const m0 = 0x55555555 // 01010101 ...
const m1 = 0x33333333 // 00110011 ...
const m2 = 0x0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff // 00000000111111110000000011111111
const m4 = 0x0000ffff // 00000000000000001111111111111111
func reverseBits(n int) int {
n = n>>1&m0 | n&m0<<1 // 交换相邻位
n = n>>2&m1 | n&m1<<2 // 两个两个交换
n = n>>4&m2 | n&m2<<4 // 四个四个交换
n = n>>8&m3 | n&m3<<8 // 八个八个交换
return n>>16 | n&m4<<16 // 交换高低 16 位
}
复杂度分析
- 时间复杂度：$\mathcal{O}(1)$。无论输入的是 $0$ 还是 $2^{31}-2$，计算量没有任何区别。更精细地说，时间复杂度是 $\mathcal{O}(\log W)$，其中 $W=32$ 是位宽。
- 空间复杂度：$\mathcal{O}(1)$。
附：库函数写法
class Solution:
def reverseBits(self, n: int) -> int:
# 没有 O(1) 的库函数，只能用字符串转换代替
# 032b 中的 b 表示转成二进制串，032 表示补前导零到长度等于 32
return int(f'{n:032b}'[::-1], 2)
class Solution:
def reverseBits(self, n: int) -> int:
# 没有 O(1) 的库函数，只能用字符串转换代替
return int(bin(n)[2:].zfill(32)[::-1], 2)
class Solution {
public int reverseBits(int n) {
return Integer.reverse(n);
}
}
class Solution {
public:
int reverseBits(int n) {
return __builtin_bitreverse32(n);
}
};
func reverseBits(n int) int {
return int(bits.Reverse32(uint32(n)))
}
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
【负雪明烛】「循环」与「分治」解法
2021年3月29日 09:59
各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 64 天。今天力扣上的每日一题是「190. 颠倒二进制位」。
解题思路
今天的题目是要求将一个数字，把其二进制翻转，求得到的另外一个二进制数。
方法一：循环
这是最容易想到的方法了，每次把 res 左移，把 $n$ 的二进制末尾数字，拼接到结果 res 的末尾。然后把 $n$ 右移。
举一个 8 位的二进制进行说明：
| i | n | res |
|---|---|---|
| - | 11001001 | - |
| 0 | 1100100 | 1 |
| 1 | 110010 | 10 |
| 2 | 11001 | 100 |
| 3 | 1100 | 1001 |
| 4 | 110 | 10010 |
| 5 | 11 | 100100 |
| 6 | 1 | 1001001 |
| 8 | - | 10010011 |
代码如下：
###Python
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
res = 0
for i in range(32):
res = (res << 1) | (n & 1)
n >>= 1
return res
###C++
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; ++i) {
res = (res << 1) | (n & 1);
n >>= 1;
}
return res;
}
};
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
方法二：分而治之
有另外一种不使用循环的做法，类似于归并排序。
其思想是分而治之，把数字分为两半，然后交换这两半的顺序；然后把前后两个半段都再分成两半，交换内部顺序……直至最后交换顺序的时候，交换的数字只有 1 位。
以一个 8 位的二进制数字为例：
代码如下：
###Python
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
n = (n >> 16) | (n << 16);
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
return n;
###C++
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
n = (n >> 16) | (n << 16);
n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);
return n;
}
};
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
刷题心得
位运算还是很有意思的。
参考资料：
OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。
祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！
颠倒二进制位
2021年3月28日 17:13
方法一：逐位颠倒
思路
将 $n$ 视作一个长为 $32$ 的二进制串，从低位往高位枚举 $n$ 的每一位，将其倒序添加到翻转结果 $\textit{rev}$ 中。
代码实现中，每枚举一位就将 $n$ 右移一位，这样当前 $n$ 的最低位就是我们要枚举的比特位。当 $n$ 为 $0$ 时即可结束循环。
需要注意的是，在某些语言（如 $\texttt{Java}$）中，没有无符号整数类型，因此对 $n$ 的右移操作应使用逻辑右移。
代码
###C++
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;
for (int i = 0; i < 32 && n > 0; ++i) {
rev |= (n & 1) << (31 - i);
n >>= 1;
}
return rev;
}
};
###Java
public class Solution {
public int reverseBits(int n) {
int rev = 0;
for (int i = 0; i < 32 && n != 0; ++i) {
rev |= (n & 1) << (31 - i);
n >>>= 1;
}
return rev;
}
}
###Go
func reverseBits(n uint32) (rev uint32) {
for i := 0; i < 32 && n > 0; i++ {
rev |= n & 1 << (31 - i)
n >>= 1
}
return
}
###JavaScript
var reverseBits = function(n) {
let rev = 0;
for (let i = 0; i < 32 && n > 0; ++i) {
rev |= (n & 1) << (31 - i);
n >>>= 1;
}
return rev >>> 0;
};
###C
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;
for (int i = 0; i < 32 && n > 0; ++i) {
rev |= (n & 1) << (31 - i);
n >>= 1;
}
return rev;
}
###Python
class Solution:
def reverseBits(self, n: int) -> int:
rev = 0
for i in range(32):
if n == 0:
break
rev |= (n & 1) << (31 - i)
n >>= 1
return rev
###C#
public class Solution {
public int ReverseBits(int n) {
int rev = 0;
for (int i = 0; i < 32 && n != 0; ++i) {
rev |= (n & 1) << (31 - i);
n = (int)((uint)n >> 1);
}
return rev;
}
}
###TypeScript
function reverseBits(n: number): number {
let rev = 0;
for (let i = 0; i < 32 && n !== 0; ++i) {
rev |= (n & 1) << (31 - i);
n >>>= 1;
}
return rev >>> 0;
}
###Rust
impl Solution {
pub fn reverse_bits(n: i32) -> i32 {
let mut x = n;
let mut rev = 0;
for i in 0..32 {
if x == 0 {
break;
}
rev |= (x & 1) << (31 - i);
x >>= 1;
}
rev
}
}
复杂度分析
-
时间复杂度：$O(\log n)$。
-
空间复杂度：$O(1)$。
方法二：位运算分治
思路
若要翻转一个二进制串，可以将其均分成左右两部分，对每部分递归执行翻转操作，然后将左半部分拼在右半部分的后面，即完成了翻转。
由于左右两部分的计算方式是相似的，利用位掩码和位移运算，我们可以自底向上地完成这一分治流程。
{:width="60%"}
对于递归的最底层，我们需要交换所有奇偶位：
- 取出所有奇数位和偶数位；
- 将奇数位移到偶数位上，偶数位移到奇数位上。
类似地，对于倒数第二层，每两位分一组，按组号取出所有奇数组和偶数组，然后将奇数组移到偶数组上，偶数组移到奇数组上。以此类推。
需要注意的是，在某些语言（如 $\texttt{Java}$）中，没有无符号整数类型，因此对 $n$ 的右移操作应使用逻辑右移。
代码
###C++
class Solution {
private:
const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111
public:
uint32_t reverseBits(uint32_t n) {
n = n >> 1 & M1 | (n & M1) << 1;
n = n >> 2 & M2 | (n & M2) << 2;
n = n >> 4 & M4 | (n & M4) << 4;
n = n >> 8 & M8 | (n & M8) << 8;
return n >> 16 | n << 16;
}
};
###Java
public class Solution {
private static final int M1 = 0x55555555; // 01010101010101010101010101010101
private static final int M2 = 0x33333333; // 00110011001100110011001100110011
private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111
public int reverseBits(int n) {
n = n >>> 1 & M1 | (n & M1) << 1;
n = n >>> 2 & M2 | (n & M2) << 2;
n = n >>> 4 & M4 | (n & M4) << 4;
n = n >>> 8 & M8 | (n & M8) << 8;
return n >>> 16 | n << 16;
}
}
###Go
const (
m1 = 0x55555555 // 01010101010101010101010101010101
m2 = 0x33333333 // 00110011001100110011001100110011
m4 = 0x0f0f0f0f // 00001111000011110000111100001111
m8 = 0x00ff00ff // 00000000111111110000000011111111
)
func reverseBits(n uint32) uint32 {
n = n>>1&m1 | n&m1<<1
n = n>>2&m2 | n&m2<<2
n = n>>4&m4 | n&m4<<4
n = n>>8&m8 | n&m8<<8
return n>>16 | n<<16
}
###JavaScript
var reverseBits = function(n) {
const M1 = 0x55555555; // 01010101010101010101010101010101
const M2 = 0x33333333; // 00110011001100110011001100110011
const M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
const M8 = 0x00ff00ff; // 00000000111111110000000011111111
n = n >>> 1 & M1 | (n & M1) << 1;
n = n >>> 2 & M2 | (n & M2) << 2;
n = n >>> 4 & M4 | (n & M4) << 4;
n = n >>> 8 & M8 | (n & M8) << 8;
return (n >>> 16 | n << 16) >>> 0;
};
###C
const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111
uint32_t reverseBits(uint32_t n) {
n = n >> 1 & M1 | (n & M1) << 1;
n = n >> 2 & M2 | (n & M2) << 2;
n = n >> 4 & M4 | (n & M4) << 4;
n = n >> 8 & M8 | (n & M8) << 8;
return n >> 16 | n << 16;
}
###Python
class Solution:
def reverseBits(self, n: int) -> int:
M1 = 0x55555555 # 01010101010101010101010101010101
M2 = 0x33333333 # 00110011001100110011001100110011
M4 = 0x0f0f0f0f # 00001111000011110000111100001111
M8 = 0x00ff00ff # 00000000111111110000000011111111
n = n & 0xFFFFFFFF
n = (n >> 1 & M1) | ((n & M1) << 1)
n = (n >> 2 & M2) | ((n & M2) << 2)
n = (n >> 4 & M4) | ((n & M4) << 4)
n = (n >> 8 & M8) | ((n & M8) << 8)
return ((n >> 16) | (n << 16)) & 0xFFFFFFFF
###C#
public class Solution {
private const int M1 = 0x55555555; // 01010101010101010101010101010101
private const int M2 = 0x33333333; // 00110011001100110011001100110011
private const int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
private const int M8 = 0x00ff00ff; // 00000000111111110000000011111111
public int ReverseBits(int n) {
int result = n;
result = ((int)((uint)result >> 1) & M1) | ((result & M1) << 1);
result = ((int)((uint)result >> 2) & M2) | ((result & M2) << 2);
result = ((int)((uint)result >> 4) & M4) | ((result & M4) << 4);
result = ((int)((uint)result >> 8) & M8) | ((result & M8) << 8);
return (int)((uint)result >> 16) | (result << 16);
}
}
###TypeScript
function reverseBits(n: number): number {
const M1 = 0x55555555; // 01010101010101010101010101010101
const M2 = 0x33333333; // 00110011001100110011001100110011
const M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
const M8 = 0x00ff00ff; // 00000000111111110000000011111111
let result: number = n;
result = ((result >>> 1) & M1) | ((result & M1) << 1);
result = ((result >>> 2) & M2) | ((result & M2) << 2);
result = ((result >>> 4) & M4) | ((result & M4) << 4);
result = ((result >>> 8) & M8) | ((result & M8) << 8);
return ((result >>> 16) | (result << 16)) >>> 0;
}
###Rust
impl Solution {
pub fn reverse_bits(x: i32) -> i32 {
const M1: u32 = 0x55555555; // 01010101010101010101010101010101
const M2: u32 = 0x33333333; // 00110011001100110011001100110011
const M4: u32 = 0x0f0f0f0f; // 00001111000011110000111100001111
const M8: u32 = 0x00ff00ff; // 00000000111111110000000011111111
let mut n = x as u32;
n = (n >> 1 & M1) | (n & M1) << 1;
n = (n >> 2 & M2) | (n & M2) << 2;
n = (n >> 4 & M4) | (n & M4) << 4;
n = (n >> 8 & M8) | (n & M8) << 8;
(n >> 16 | n << 16) as i32
}
}
复杂度分析
-
时间复杂度：$O(1)$。
-
空间复杂度：$O(1)$。
每日一题-二进制求和🟢
2026年2月15日 00:00
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
提示：
1 <= a.length, b.length <= 104-
a和b仅由字符'0'或'1'组成 - 字符串如果不是
"0"，就不含前导零
模拟加法计算过程（Python/Java/C++/C/Go/JS/Rust）
2026年2月5日 09:42
二进制的加法怎么算？
和十进制的加法一样，从低到高（从右往左）计算。
示例 1 是 $11+1$，计算过程如下：
- 计算最低位，$1+1=10$，所以答案的最低位填 $0$，进位是 $1$。
- 计算下一位，$a$ 中的 $1$ 和进位的 $1$ 相加，$1+1=10$，所以答案的下一位填 $0$，进位是 $1$。现在答案是 $00$。
- 虽然 $a$ 和 $b$ 都遍历完了，但计算并未结束。还剩下进位 $1$，填入答案的下一位（从低到高第三位）。最终答案为 $100$。
由此可见，需要在计算过程中维护进位值 $\textit{carry}$，每次计算
$$
\textit{sum} = a\ 这一位的值 + b\ 这一位的值 + \textit{carry}
$$
然后答案这一位填 $\textit{sum}\bmod 2$，进位更新为 $\left\lfloor\dfrac{\textit{sum}}{2}\right\rfloor$。例如 $\textit{sum} = 10$，那么答案这一位填 $0$，进位更新为 $1$。
写法一
把计算结果插在答案的末尾，最后把答案反转。
###py
class Solution:
def addBinary(self, a: str, b: str) -> str:
ans = []
i = len(a) - 1 # 从右往左遍历 a 和 b
j = len(b) - 1
carry = 0 # 保存进位
while i >= 0 or j >= 0 or carry:
x = int(a[i]) if i >= 0 else 0
y = int(b[j]) if j >= 0 else 0
s = x + y + carry # 计算这一位的加法
# 例如 s = 10，把 '0' 填入答案，把 carry 置为 1
ans.append(str(s % 2))
carry = s // 2
i -= 1
j -= 1
return ''.join(reversed(ans))
###java
class Solution {
public String addBinary(String a, String b) {
StringBuilder ans = new StringBuilder();
int i = a.length() - 1; // 从右往左遍历 a 和 b
int j = b.length() - 1;
int carry = 0; // 保存进位
while (i >= 0 || j >= 0 || carry > 0) {
int x = i >= 0 ? a.charAt(i) - '0' : 0;
int y = j >= 0 ? b.charAt(j) - '0' : 0;
int sum = x + y + carry; // 计算这一位的加法
// 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
ans.append(sum % 2);
carry = sum / 2;
i--;
j--;
}
return ans.reverse().toString();
}
}
###cpp
class Solution {
public:
string addBinary(string a, string b) {
string ans;
int i = a.size() - 1; // 从右往左遍历 a 和 b
int j = b.size() - 1;
int carry = 0; // 保存进位
while (i >= 0 || j >= 0 || carry) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int sum = x + y + carry; // 计算这一位的加法
// 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
ans += sum % 2 + '0';
carry = sum / 2;
i--;
j--;
}
ranges::reverse(ans);
return ans;
}
};
###c
#define MAX(a, b) ((b) > (a) ? (b) : (a))
char* addBinary(char* a, char* b) {
int n = strlen(a);
int m = strlen(b);
char* ans = malloc((MAX(n, m) + 2) * sizeof(char));
int k = 0;
int i = n - 1; // 从右往左遍历 a 和 b
int j = m - 1;
int carry = 0; // 保存进位
while (i >= 0 || j >= 0 || carry) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int sum = x + y + carry; // 计算这一位的加法
// 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
ans[k++] = sum % 2 + '0';
carry = sum / 2;
i--;
j--;
}
// 反转 ans
for (int l = 0, r = k - 1; l < r; l++, r--) {
char tmp = ans[l];
ans[l] = ans[r];
ans[r] = tmp;
}
ans[k] = '\0';
return ans;
}
###go
func addBinary(a, b string) string {
ans := []byte{}
i := len(a) - 1 // 从右往左遍历 a 和 b
j := len(b) - 1
carry := byte(0) // 保存进位
for i >= 0 || j >= 0 || carry > 0 {
// 计算这一位的加法
sum := carry
if i >= 0 {
sum += a[i] - '0'
}
if j >= 0 {
sum += b[j] - '0'
}
// 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
ans = append(ans, sum%2+'0')
carry = sum / 2
i--
j--
}
slices.Reverse(ans)
return string(ans)
}
###js
var addBinary = function(a, b) {
const ans = [];
let i = a.length - 1; // 从右往左遍历 a 和 b
let j = b.length - 1;
let carry = 0; // 保存进位
while (i >= 0 || j >= 0 || carry) {
const x = i >= 0 ? Number(a[i]) : 0;
const y = j >= 0 ? Number(b[j]) : 0;
const sum = x + y + carry; // 计算这一位的加法
// 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
ans.push(String(sum % 2));
carry = Math.floor(sum / 2);
i--;
j--;
}
return ans.reverse().join('');
};
###rust
impl Solution {
pub fn add_binary(a: String, b: String) -> String {
let a = a.as_bytes();
let b = b.as_bytes();
let mut ans = vec![];
let mut i = a.len() as isize - 1; // 从右往左遍历 a 和 b
let mut j = b.len() as isize - 1;
let mut carry = 0; // 保存进位
while i >= 0 || j >= 0 || carry > 0 {
let x = if i >= 0 { a[i as usize] - b'0' } else { 0 };
let y = if j >= 0 { b[j as usize] - b'0' } else { 0 };
let sum = x + y + carry; // 计算这一位的加法
// 例如 sum = 10，把 '0' 填入答案，把 carry 置为 1
ans.push(sum % 2 + b'0');
carry = sum / 2;
i -= 1;
j -= 1;
}
ans.reverse();
unsafe { String::from_utf8_unchecked(ans) }
}
}
写法二
直接填入答案，不反转。
###py
class Solution:
def addBinary(self, a: str, b: str) -> str:
# 保证 len(a) >= len(b)，简化后续代码逻辑
if len(a) < len(b):
a, b = b, a
n, m = len(a), len(b)
ans = [0] * (n + 1)
carry = 0 # 保存进位
for i in range(n - 1, -1, -1):
j = m - (n - i)
y = int(b[j]) if j >= 0 else 0
s = int(a[i]) + y + carry
ans[i + 1] = str(s % 2)
carry = s // 2
ans[0] = str(carry)
return ''.join(ans[carry ^ 1:]) # 如果 carry == 0 则去掉 ans[0]
###java
class Solution {
public String addBinary(String a, String b) {
// 保证 a.length() >= b.length()，简化后续代码逻辑
if (a.length() < b.length()) {
return addBinary(b, a);
}
int n = a.length();
int m = b.length();
char[] ans = new char[n + 1];
int carry = 0; // 保存进位
for (int i = n - 1, j = m - 1; i >= 0; i--, j--) {
int x = a.charAt(i) - '0';
int y = j >= 0 ? b.charAt(j) - '0' : 0;
int sum = x + y + carry;
ans[i + 1] = (char) (sum % 2 + '0');
carry = sum / 2;
}
ans[0] = (char) (carry + '0');
// 如果 carry == 0 则去掉 ans[0]
return new String(ans, carry ^ 1, n + carry);
}
}
###cpp
class Solution {
public:
string addBinary(string a, string b) {
// 保证 a.size() >= b.size()，简化后续代码逻辑
if (a.size() < b.size()) {
swap(a, b);
}
int n = a.size(), m = b.size();
string ans(n + 1, 0);
int carry = 0; // 保存进位
for (int i = n - 1, j = m - 1; i >= 0; i--, j--) {
int x = a[i] - '0';
int y = j >= 0 ? b[j] - '0' : 0;
int sum = x + y + carry;
ans[i + 1] = sum % 2 + '0';
carry = sum / 2;
}
if (carry) {
ans[0] = '1';
} else {
ans.erase(ans.begin());
}
return ans;
}
};
###c
#define MAX(a, b) ((b) > (a) ? (b) : (a))
char* addBinary(char* a, char* b) {
int n = strlen(a);
int m = strlen(b);
char* ans = malloc((MAX(n, m) + 2) * sizeof(char));
ans[MAX(n, m) + 1] = '\0';
int carry = 0; // 保存进位
for (int i = n - 1, j = m - 1; i >= 0 || j >= 0; i--, j--) {
int x = i >= 0 ? a[i] - '0' : 0;
int y = j >= 0 ? b[j] - '0' : 0;
int sum = x + y + carry;
ans[MAX(i, j) + 1] = sum % 2 + '0';
carry = sum / 2;
}
ans[0] = carry + '0';
// 如果 carry == 0 则去掉 ans[0]
return ans + (carry ^ 1);
}
###go
func addBinary(a, b string) string {
// 保证 len(a) >= len(b)，简化后续代码逻辑
if len(a) < len(b) {
a, b = b, a
}
n, m := len(a), len(b)
ans := make([]byte, n+1)
carry := byte(0) // 保存进位
for i := n - 1; i >= 0; i-- {
sum := a[i] - '0' + carry
if j := m - (n - i); j >= 0 {
sum += b[j] - '0'
}
ans[i+1] = sum%2 + '0'
carry = sum / 2
}
ans[0] = carry + '0'
// 如果 carry == 0 则去掉 ans[0]
return string(ans[carry^1:])
}
###js
var addBinary = function(a, b) {
// 保证 a.length >= b.length，简化后续代码逻辑
if (a.length < b.length) {
[a, b] = [b, a];
}
const n = a.length;
const m = b.length;
const ans = Array(n + 1);
let carry = 0; // 保存进位
for (let i = n - 1, j = m - 1; i >= 0; i--, j--) {
const x = Number(a[i]);
const y = j >= 0 ? Number(b[j]) : 0;
const sum = x + y + carry;
ans[i + 1] = String(sum % 2);
carry = Math.floor(sum / 2);
}
if (carry) {
ans[0] = '1';
} else {
ans.shift();
}
return ans.join('');
};
###rust
impl Solution {
pub fn add_binary(a: String, b: String) -> String {
// 保证 a.len() >= b.len()，简化后续代码逻辑
if a.len() < b.len() {
return Self::add_binary(b, a);
}
let a = a.as_bytes();
let b = b.as_bytes();
let n = a.len();
let m = b.len();
let mut ans = vec![0; n + 1];
let mut carry = 0; // 保存进位
for i in (0..n).rev() {
let x = a[i] - b'0';
let y = if n - i <= m { b[m - (n - i)] - b'0' } else { 0 };
let sum = x + y + carry;
ans[i + 1] = sum % 2 + b'0';
carry = sum / 2;
}
if carry > 0 {
ans[0] = b'1';
} else {
ans.remove(0);
}
unsafe { String::from_utf8_unchecked(ans) }
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(\max(n,m))$，其中 $n$ 是 $a$ 的长度，$m$ 是 $b$ 的长度。
- 空间复杂度：$\mathcal{O}(\max(n,m))$。
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
二进制求和
2020年6月22日 21:41
题目分析
考虑一个最朴素的方法：先将 $a$ 和 $b$ 转化成十进制数，求和后再转化为二进制数。利用 Python 和 Java 自带的高精度运算，我们可以很简单地写出这个程序：
###python
class Solution:
def addBinary(self, a, b) -> str:
return '{0:b}'.format(int(a, 2) + int(b, 2))
###Java
class Solution {
public String addBinary(String a, String b) {
return Integer.toBinaryString(
Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
);
}
}
如果 $a$ 的位数是 $n$，$b$ 的位数为 $m$，这个算法的渐进时间复杂度为 $O(n + m)$。但是这里非常简单的实现基于 Python 和 Java 本身的高精度功能，在其他的语言中可能并不适用，并且在 Java 中：
- 如果字符串超过 $33$ 位，不能转化为
Integer - 如果字符串超过 $65$ 位，不能转化为
Long - 如果字符串超过 $500000001$ 位，不能转化为
BigInteger
因此，为了适用于长度较大的字符串计算，我们应该使用更加健壮的算法。
方法一：模拟
思路和算法
我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。
具体的，我们可以取 $n = \max{ |a|, |b| }$，循环 $n$ 次，从最低位开始遍历。我们使用一个变量 $\textit{carry}$ 表示上一个位置的进位，初始值为 $0$。记当前位置对其的两个位为 $a_i$ 和 $b_i$，则每一位的答案为 $(\textit{carry} + a_i + b_i) \bmod{2}$，下一位的进位为 $\lfloor \frac{\textit{carry} + a_i + b_i}{2} \rfloor$。重复上述步骤，直到数字 $a$ 和 $b$ 的每一位计算完毕。最后如果 $\textit{carry}$ 的最高位不为 $0$，则将最高位添加到计算结果的末尾。
注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。当然你也可以直接把 $a$ 和 $b$ 中短的那一个补 $0$ 直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。
代码
###Java
class Solution {
public String addBinary(String a, String b) {
StringBuffer ans = new StringBuffer();
int n = Math.max(a.length(), b.length()), carry = 0;
for (int i = 0; i < n; ++i) {
carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
ans.append((char) (carry % 2 + '0'));
carry /= 2;
}
if (carry > 0) {
ans.append('1');
}
ans.reverse();
return ans.toString();
}
}
###C++
class Solution {
public:
string addBinary(string a, string b) {
string ans;
reverse(a.begin(), a.end());
reverse(b.begin(), b.end());
int n = max(a.size(), b.size()), carry = 0;
for (size_t i = 0; i < n; ++i) {
carry += i < a.size() ? (a.at(i) == '1') : 0;
carry += i < b.size() ? (b.at(i) == '1') : 0;
ans.push_back((carry % 2) ? '1' : '0');
carry /= 2;
}
if (carry) {
ans.push_back('1');
}
reverse(ans.begin(), ans.end());
return ans;
}
};
###Go
func addBinary(a string, b string) string {
ans := ""
carry := 0
lenA, lenB := len(a), len(b)
n := max(lenA, lenB)
for i := 0; i < n; i++ {
if i < lenA {
carry += int(a[lenA-i-1] - '0')
}
if i < lenB {
carry += int(b[lenB-i-1] - '0')
}
ans = strconv.Itoa(carry%2) + ans
carry /= 2
}
if carry > 0 {
ans = "1" + ans
}
return ans
}
###C
void reserve(char* s) {
int len = strlen(s);
for (int i = 0; i < len / 2; i++) {
char t = s[i];
s[i] = s[len - i - 1], s[len - i - 1] = t;
}
}
char* addBinary(char* a, char* b) {
reserve(a);
reserve(b);
int len_a = strlen(a), len_b = strlen(b);
int n = fmax(len_a, len_b), carry = 0, len = 0;
char* ans = (char*)malloc(sizeof(char) * (n + 2));
for (int i = 0; i < n; ++i) {
carry += i < len_a ? (a[i] == '1') : 0;
carry += i < len_b ? (b[i] == '1') : 0;
ans[len++] = carry % 2 + '0';
carry /= 2;
}
if (carry) {
ans[len++] = '1';
}
ans[len] = '\0';
reserve(ans);
return ans;
}
###Python
class Solution:
def addBinary(self, a: str, b: str) -> str:
ans = []
a = a[::-1]
b = b[::-1]
n = max(len(a), len(b))
carry = 0
for i in range(n):
carry += int(a[i]) if i < len(a) else 0
carry += int(b[i]) if i < len(b) else 0
ans.append(str(carry % 2))
carry //= 2
if carry:
ans.append('1')
return ''.join(ans)[::-1]
###C#
public class Solution {
public string AddBinary(string a, string b) {
char[] aArr = a.ToCharArray();
char[] bArr = b.ToCharArray();
Array.Reverse(aArr);
Array.Reverse(bArr);
int n = Math.Max(a.Length, b.Length);
int carry = 0;
List<char> ans = new List<char>();
for (int i = 0; i < n; i++) {
carry += i < aArr.Length ? (aArr[i] == '1' ? 1 : 0) : 0;
carry += i < bArr.Length ? (bArr[i] == '1' ? 1 : 0) : 0;
ans.Add((carry % 2) == 1 ? '1' : '0');
carry /= 2;
}
if (carry > 0) {
ans.Add('1');
}
ans.Reverse();
return new string(ans.ToArray());
}
}
###JavaScript
var addBinary = function(a, b) {
let ans = [];
a = a.split('').reverse().join('');
b = b.split('').reverse().join('');
const n = Math.max(a.length, b.length);
let carry = 0;
for (let i = 0; i < n; i++) {
carry += i < a.length ? parseInt(a[i]) : 0;
carry += i < b.length ? parseInt(b[i]) : 0;
ans.push((carry % 2).toString());
carry = Math.floor(carry / 2);
}
if (carry) {
ans.push('1');
}
return ans.reverse().join('');
};
###TypeScript
function addBinary(a: string, b: string): string {
let ans: string[] = [];
a = a.split('').reverse().join('');
b = b.split('').reverse().join('');
const n = Math.max(a.length, b.length);
let carry = 0;
for (let i = 0; i < n; i++) {
carry += i < a.length ? parseInt(a[i]) : 0;
carry += i < b.length ? parseInt(b[i]) : 0;
ans.push((carry % 2).toString());
carry = Math.floor(carry / 2);
}
if (carry) {
ans.push('1');
}
return ans.reverse().join('');
}
###Rust
impl Solution {
pub fn add_binary(a: String, b: String) -> String {
let mut a_chars: Vec<char> = a.chars().collect();
let mut b_chars: Vec<char> = b.chars().collect();
a_chars.reverse();
b_chars.reverse();
let n = a_chars.len().max(b_chars.len());
let mut carry = 0;
let mut ans = Vec::new();
for i in 0..n {
carry += if i < a_chars.len() { if a_chars[i] == '1' { 1 } else { 0 } } else { 0 };
carry += if i < b_chars.len() { if b_chars[i] == '1' { 1 } else { 0 } } else { 0 };
ans.push(if carry % 2 == 1 { '1' } else { '0' });
carry /= 2;
}
if carry > 0 {
ans.push('1');
}
ans.reverse();
ans.into_iter().collect()
}
}
复杂度分析
假设 $n = \max{ |a|, |b| }$。
- 时间复杂度：$O(n)$，这里的时间复杂度来源于顺序遍历 $a$ 和 $b$。
- 空间复杂度：$O(1)$，除去答案所占用的空间，这里使用了常数个临时变量。
方法二：位运算
思路和算法
如果不允许使用加减乘除，则可以使用位运算替代上述运算中的一些加减乘除的操作。
如果不了解位运算，可以先了解位运算并尝试练习以下题目：
我们可以设计这样的算法来计算：
- 把 $a$ 和 $b$ 转换成整型数字 $x$ 和 $y$，在接下来的过程中，$x$ 保存结果，$y$ 保存进位。
- 当进位不为 $0$ 时
- 计算当前 $x$ 和 $y$ 的无进位相加结果：
answer = x ^ y - 计算当前 $x$ 和 $y$ 的进位：
carry = (x & y) << 1 - 完成本次循环，更新
x = answer，y = carry
- 计算当前 $x$ 和 $y$ 的无进位相加结果：
- 返回 $x$ 的二进制形式
为什么这个方法是可行的呢？在第一轮计算中，answer 的最后一位是 $x$ 和 $y$ 相加之后的结果，carry 的倒数第二位是 $x$ 和 $y$ 最后一位相加的进位。接着每一轮中，由于 carry 是由 $x$ 和 $y$ 按位与并且左移得到的，那么最后会补零，所以在下面计算的过程中后面的数位不受影响，而每一轮都可以得到一个低 $i$ 位的答案和它向低 $i + 1$ 位的进位，也就模拟了加法的过程。
代码
###Java
import java.math.BigInteger;
class Solution {
public String addBinary(String a, String b) {
BigInteger x = new BigInteger(a, 2);
BigInteger y = new BigInteger(b, 2);
while (!y.equals(BigInteger.ZERO)) {
BigInteger answer = x.xor(y);
BigInteger carry = x.and(y).shiftLeft(1);
x = answer;
y = carry;
}
return x.toString(2);
}
}
###C++
class Solution {
public:
string addBinary(string a, string b) {
string result = "";
int i = a.length() - 1, j = b.length() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) {
sum += a[i--] - '0';
}
if (j >= 0) {
sum += b[j--] - '0';
}
result = char(sum % 2 + '0') + result;
carry = sum / 2;
}
return result;
}
};
###Go
func addBinary(a string, b string) string {
if a == "" {
return b
}
if b == "" {
return a
}
x := new(big.Int)
x.SetString(a, 2)
y := new(big.Int)
y.SetString(b, 2)
zero := new(big.Int)
for y.Cmp(zero) != 0 {
answer := new(big.Int)
answer.Xor(x, y)
carry := new(big.Int)
carry.And(x, y)
carry.Lsh(carry, 1)
x.Set(answer)
y.Set(carry)
}
return x.Text(2)
}
###C
char* addBinary(char* a, char* b) {
int len_a = strlen(a);
int len_b = strlen(b);
int max_len = (len_a > len_b ? len_a : len_b) + 2;
char* result = (char*)malloc(max_len * sizeof(char));
if (!result) {
return NULL;
}
int i = len_a - 1, j = len_b - 1;
int carry = 0;
int k = max_len - 2;
result[max_len - 1] = '\0';
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) {
sum += a[i--] - '0';
}
if (j >= 0) {
sum += b[j--] - '0';
}
result[k--] = (sum % 2) + '0';
carry = sum / 2;
}
if (k >= 0) {
char* final_result = result + k + 1;
char* dup = strdup(final_result);
free(result);
return dup;
}
return result;
}
###Python
class Solution:
def addBinary(self, a, b) -> str:
x, y = int(a, 2), int(b, 2)
while y:
answer = x ^ y
carry = (x & y) << 1
x, y = answer, carry
return bin(x)[2:]
###C#
public class Solution {
public string AddBinary(string a, string b) {
if (string.IsNullOrEmpty(a)) {
return b;
}
if (string.IsNullOrEmpty(b)) {
return a;
}
BigInteger x = BigInteger.Parse("0" + a, System.Globalization.NumberStyles.AllowBinarySpecifier);
BigInteger y = BigInteger.Parse("0" + b, System.Globalization.NumberStyles.AllowBinarySpecifier);
while (y != 0) {
BigInteger answer = x ^ y;
BigInteger carry = (x & y) << 1;
x = answer;
y = carry;
}
if (x == 0) {
return "0";
}
string result = "";
while (x > 0) {
result = (x % 2).ToString() + result;
x /= 2;
}
return result;
}
}
###JavaScript
var addBinary = function(a, b) {
let x = BigInt('0b' + a);
let y = BigInt('0b' + b);
while (y !== 0n) {
let answer = x ^ y;
let carry = (x & y) << 1n;
x = answer;
y = carry;
}
return x.toString(2);
};
###TypeScript
function addBinary(a: string, b: string): string {
let x = BigInt('0b' + a);
let y = BigInt('0b' + b);
while (y !== 0n) {
let answer = x ^ y;
let carry = (x & y) << 1n;
x = answer;
y = carry;
}
return x.toString(2);
}
###Rust
impl Solution {
pub fn add_binary(a: String, b: String) -> String {
let a_chars: Vec<char> = a.chars().collect();
let b_chars: Vec<char> = b.chars().collect();
let mut i = a_chars.len() as i32 - 1;
let mut j = b_chars.len() as i32 - 1;
let mut carry = 0;
let mut result = Vec::new();
while i >= 0 || j >= 0 || carry > 0 {
let mut sum = carry;
if i >= 0 {
sum += a_chars[i as usize].to_digit(2).unwrap_or(0);
i -= 1;
}
if j >= 0 {
sum += b_chars[j as usize].to_digit(2).unwrap_or(0);
j -= 1;
}
result.push(char::from_digit(sum % 2, 10).unwrap());
carry = sum / 2;
}
result.iter().rev().collect()
}
}
复杂度分析
- 时间复杂度：$O(|a| + |b| + X \cdot \max ({|a| + |b|}))$，字符串转化成数字需要的时间代价为 $O(|a| + |b|)$，计算的时间代价为 $O(\max { |a|, |b| })$，$X$ 为位运算所需的时间，因为这里用到了高精度计算，所以位运算的时间不一定为 $O(1)$。
- 空间复杂度：这里使用了 $x$ 和 $y$ 来保存 $a$ 和 $b$ 的整数形式，如果用 Python 实现，这里用到了 Python 的高精度功能，实际的空间代价是 $O(|a| + |b|)$。
画解算法：67. 二进制求和
2019年6月19日 10:11
解题思路
整体思路是将两个字符串较短的用 $0$ 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。
本题解中大致思路与上述一致，但由于字符串操作原因，不确定最后的结果是否会多出一位进位，所以会有 2 种处理方式：
- 第一种，在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转
- 第二种，按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位
时间复杂度：$O(n)$
代码
###Java
class Solution {
public String addBinary(String a, String b) {
StringBuilder ans = new StringBuilder();
int ca = 0;
for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
int sum = ca;
sum += i >= 0 ? a.charAt(i) - '0' : 0;
sum += j >= 0 ? b.charAt(j) - '0' : 0;
ans.append(sum % 2);
ca = sum / 2;
}
ans.append(ca == 1 ? ca : "");
return ans.reverse().toString();
}
}
###JavaScript
/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {
let ans = "";
let ca = 0;
for(let i = a.length - 1, j = b.length - 1;i >= 0 || j >= 0; i--, j--) {
let sum = ca;
sum += i >= 0 ? parseInt(a[i]) : 0;
sum += j >= 0 ? parseInt(b[j]) : 0;
ans += sum % 2;
ca = Math.floor(sum / 2);
}
ans += ca == 1 ? ca : "";
return ans.split('').reverse().join('');
};
画解
<,,>
想看大鹏画解更多高频面试题，欢迎阅读大鹏的 LeetBook：《画解剑指 Offer 》，O(∩_∩)O
BFS 模拟 + 优化（Python/Java/C++/C/Go/JS/Rust）
2026年2月14日 08:37
类似 102. 二叉树的层序遍历，用一个 BFS 模拟香槟溢出流程：第一层溢出的香槟流到第二层，第二层溢出的香槟流到第三层，依此类推。
具体地：
- 处理第一层到第二层，从 $(0,0)$ 溢出的香槟流到 $(1,0)$ 和 $(1,1)$。设溢出的香槟量为 $x$，那么 $(1,0)$ 和 $(1,1)$ 的香槟量都增加 $\dfrac{x}{2}$。
- 处理第二层到第三层，从 $(1,0)$ 溢出的香槟流到 $(2,0)$ 和 $(2,1)$，从 $(1,1)$ 溢出的香槟流到 $(2,1)$ 和 $(2,2)$。
- 依此类推。一般地，从 $(i,j)$ 溢出的香槟流到 $(i+1,j)$ 和 $(i+1,j+1)$。设溢出的香槟量为 $x$，那么下一层的 $j$ 和 $j+1$ 的香槟量都增加 $\dfrac{x}{2}$。用一个数组保存下一层每个玻璃杯的香槟量。
优化前
###py
class Solution:
def champagneTower(self, poured: int, queryRow: int, queryGlass: int) -> float:
cur = [float(poured)]
for i in range(1, queryRow + 1):
nxt = [0.0] * (i + 1)
for j, x in enumerate(cur):
if x > 1: # 溢出到下一层
nxt[j] += (x - 1) / 2
nxt[j + 1] += (x - 1) / 2
cur = nxt
return min(cur[queryGlass], 1.0) # 如果溢出，容量是 1
###java
class Solution {
public double champagneTower(int poured, int queryRow, int queryGlass) {
double[] cur = new double[]{(double) poured};
for (int i = 1; i <= queryRow; i++) {
double[] nxt = new double[i + 1];
for (int j = 0; j < cur.length; j++) {
double x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
cur = nxt;
}
return Math.min(cur[queryGlass], 1); // 如果溢出，容量是 1
}
}
###cpp
class Solution {
public:
double champagneTower(int poured, int queryRow, int queryGlass) {
vector<double> cur = {1.0 * poured};
for (int i = 1; i <= queryRow; i++) {
vector<double> nxt(i + 1);
for (int j = 0; j < cur.size(); j++) {
double x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
cur = move(nxt);
}
return min(cur[queryGlass], 1.0); // 如果溢出，容量是 1
}
};
###c
#define MIN(a, b) ((b) < (a) ? (b) : (a))
double champagneTower(int poured, int queryRow, int queryGlass) {
double* cur = malloc(sizeof(double));
cur[0] = poured;
int curSize = 1;
for (int i = 1; i <= queryRow; i++) {
double* nxt = calloc(i + 1, sizeof(double));
for (int j = 0; j < curSize; j++) {
double x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
free(cur);
cur = nxt;
curSize = i + 1;
}
double ans = MIN(cur[queryGlass], 1); // 如果溢出，容量是 1
free(cur);
return ans;
}
###go
func champagneTower(poured, queryRow, queryGlass int) float64 {
cur := []float64{float64(poured)}
for i := 1; i <= queryRow; i++ {
nxt := make([]float64, i+1)
for j, x := range cur {
if x > 1 { // 溢出到下一层
nxt[j] += (x - 1) / 2
nxt[j+1] += (x - 1) / 2
}
}
cur = nxt
}
return min(cur[queryGlass], 1) // 如果溢出，容量是 1
}
###js
var champagneTower = function(poured, queryRow, queryGlass) {
let cur = [poured];
for (let i = 1; i <= queryRow; i++) {
const nxt = Array(i + 1).fill(0);
for (let j = 0; j < cur.length; j++) {
const x = cur[j] - 1;
if (x > 0) { // 溢出到下一层
nxt[j] += x / 2;
nxt[j + 1] += x / 2;
}
}
cur = nxt;
}
return Math.min(cur[queryGlass], 1); // 如果溢出，容量是 1
};
###rust
impl Solution {
pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
let mut cur = vec![poured as f64];
for i in 1..=query_row as usize {
let mut nxt = vec![0.0; i + 1];
for (j, x) in cur.into_iter().enumerate() {
if x > 1.0 { // 溢出到下一层
nxt[j] += (x - 1.0) / 2.0;
nxt[j + 1] += (x - 1.0) / 2.0;
}
}
cur = nxt;
}
cur[query_glass as usize].min(1.0) // 如果溢出，容量是 1
}
}
优化
无需使用两个数组，可以像 0-1 背包那样，在同一个数组上修改。
###py
class Solution:
def champagneTower(self, poured: int, queryRow: int, queryGlass: int) -> float:
f = [0.0] * (queryRow + 1)
f[0] = float(poured)
for i in range(queryRow):
for j in range(i, -1, -1):
x = f[j] - 1
if x > 0:
f[j + 1] += x / 2
f[j] = x / 2
else:
f[j] = 0.0
return min(f[queryGlass], 1.0) # 如果溢出，容量是 1
###java
class Solution {
public double champagneTower(int poured, int queryRow, int queryGlass) {
double[] f = new double[queryRow + 1];
f[0] = poured;
for (int i = 0; i < queryRow; i++) {
for (int j = i; j >= 0; j--) {
double x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
return Math.min(f[queryGlass], 1); // 如果溢出，容量是 1
}
}
###cpp
class Solution {
public:
double champagneTower(int poured, int queryRow, int queryGlass) {
vector<double> f(queryRow + 1);
f[0] = poured;
for (int i = 0; i < queryRow; i++) {
for (int j = i; j >= 0; j--) {
double x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
return min(f[queryGlass], 1.0); // 如果溢出，容量是 1
}
};
###c
#define MIN(a, b) ((b) < (a) ? (b) : (a))
double champagneTower(int poured, int queryRow, int queryGlass) {
double* f = calloc(queryRow + 1, sizeof(double));
f[0] = poured;
for (int i = 0; i < queryRow; i++) {
for (int j = i; j >= 0; j--) {
double x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
double ans = MIN(f[queryGlass], 1); // 如果溢出，容量是 1
free(f);
return ans;
}
###go
func champagneTower(poured, queryRow, queryGlass int) float64 {
f := make([]float64, queryRow+1)
f[0] = float64(poured)
for i := range queryRow {
for j := i; j >= 0; j-- {
x := f[j] - 1
if x > 0 {
f[j+1] += x / 2
f[j] = x / 2
} else {
f[j] = 0
}
}
}
return min(f[queryGlass], 1) // 如果溢出，容量是 1
}
###js
var champagneTower = function(poured, queryRow, queryGlass) {
const f = Array(queryRow + 1).fill(0);
f[0] = poured;
for (let i = 0; i < queryRow; i++) {
for (let j = i; j >= 0; j--) {
const x = f[j] - 1;
if (x > 0) {
f[j + 1] += x / 2;
f[j] = x / 2;
} else {
f[j] = 0;
}
}
}
return Math.min(f[queryGlass], 1); // 如果溢出，容量是 1
};
###rust
impl Solution {
pub fn champagne_tower(poured: i32, query_row: i32, query_glass: i32) -> f64 {
let query_row = query_row as usize;
let mut f = vec![0.0; query_row + 1];
f[0] = poured as f64;
for i in 0..query_row {
for j in (0..=i).rev() {
let x = f[j] - 1.0;
if x > 0.0 {
f[j + 1] += x / 2.0;
f[j] = x / 2.0;
} else {
f[j] = 0.0;
}
}
}
f[query_glass as usize].min(1.0) // 如果溢出，容量是 1
}
}
复杂度分析
- 时间复杂度：$\mathcal{O}(\textit{queryRow}^2)$。
- 空间复杂度：$\mathcal{O}(\textit{queryRow})$。
相似题目
分类题单
- 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
- 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
- 单调栈（基础/矩形面积/贡献法/最小字典序）
- 网格图（DFS/BFS/综合应用）
- 位运算（基础/性质/拆位/试填/恒等式/思维）
- 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
- 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
- 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
- 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
- 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
- 链表、树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA）
- 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）
欢迎关注 B站@灵茶山艾府
每日一题-香槟塔🟡
2026年2月14日 00:00
我们把玻璃杯摆成金字塔的形状，其中 第一层 有 1 个玻璃杯， 第二层 有 2 个，依次类推到第 100 层，每个玻璃杯将盛有香槟。
从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。（当最底层的玻璃杯满了，香槟会流到地板上）
例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。在倒三杯香槟后，第二层的香槟满了 - 此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯盛放了一半的香槟，他两边的玻璃杯各自盛放了四分之一的香槟，如下图所示。
现在当倾倒了非负整数杯香槟后，返回第 i 行 j 个玻璃杯所盛放的香槟占玻璃杯容积的比例（ i 和 j 都从0开始）。
示例 1: 输入: poured(倾倒香槟总杯数) = 1, query_glass(杯子的位置数) = 1, query_row(行数) = 1 输出: 0.00000 解释: 我们在顶层（下标是（0，0））倒了一杯香槟后，没有溢出，因此所有在顶层以下的玻璃杯都是空的。 示例 2: 输入: poured(倾倒香槟总杯数) = 2, query_glass(杯子的位置数) = 1, query_row(行数) = 1 输出: 0.50000 解释: 我们在顶层（下标是（0，0）倒了两杯香槟后，有一杯量的香槟将从顶层溢出，位于（1，0）的玻璃杯和（1，1）的玻璃杯平分了这一杯香槟，所以每个玻璃杯有一半的香槟。
示例 3:
输入: poured = 100000009, query_row = 33, query_glass = 17 输出: 1.00000
提示:
0 <= poured <= 1090 <= query_glass <= query_row < 100
