二进制手表顶部有 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简单提一句，回溯就是纯暴力枚举，配合剪枝食用风味更佳
如果i大于3，当前灯是分钟灯而不是小时灯，则加上0个小时
如果i没有大于3，当前灯是小时灯而不是分钟灯，则加上0分钟
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]);
}
}
}
复杂度分析
在上一篇题解中，我总结了回溯算法的三种类型，以及什么时候用回溯算法，怎么写回溯算法，如果没看过的，强烈建议先看：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;
}
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;
}
};
颠倒给定的 32 位有符号整数的二进制位。
示例 1：
输入：n = 43261596
输出：964176192
解释：
| 整数 | 二进制 |
|---|---|
| 43261596 | 00000010100101000001111010011100 |
| 964176192 | 00111001011110000010100101000000 |
示例 2：
输入：n = 2147483644
输出：1073741822
解释：
| 整数 | 二进制 |
|---|---|
| 2147483644 | 01111111111111111111111111111100 |
| 1073741822 | 00111111111111111111111111111110 |
提示：
0 <= n <= 231 - 2n 为偶数
进阶: 如果多次调用这个函数，你将如何优化你的算法？
以反转一个 $8$ 位整数为例。
为方便阅读，我把这个数字记作 $12345678$。目标是得到 $87654321$。
用分治思考，反转 $12345678$ 可以分成如下三步：
反转 $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 位
}
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)))
}
欢迎关注 B站@灵茶山艾府
各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 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;
}
};
有另外一种不使用循环的做法，类似于归并排序。
其思想是分而治之，把数字分为两半，然后交换这两半的顺序；然后把前后两个半段都再分成两半，交换内部顺序……直至最后交换顺序的时候，交换的数字只有 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;
}
};
位运算还是很有意思的。
参考资料：
OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。
祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！
思路
将 $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)$。
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
示例 1：
输入:a = "11", b = "1" 输出："100"
示例 2：
输入：a = "1010", b = "1011" 输出："10101"
提示：
1 <= a.length, b.length <= 104a 和 b 仅由字符 '0' 或 '1' 组成"0" ，就不含前导零二进制的加法怎么算？
和十进制的加法一样，从低到高（从右往左）计算。
示例 1 是 $11+1$，计算过程如下：
由此可见，需要在计算过程中维护进位值 $\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) }
}
}
欢迎关注 B站@灵茶山艾府
考虑一个最朴素的方法：先将 $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 中：
Integer
Long
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| }$。
思路和算法
如果不允许使用加减乘除，则可以使用位运算替代上述运算中的一些加减乘除的操作。
如果不了解位运算，可以先了解位运算并尝试练习以下题目：
我们可以设计这样的算法来计算：
answer = x ^ y
carry = (x & y) << 1
x = answer，y = carry
为什么这个方法是可行的呢？在第一轮计算中，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()
}
}
复杂度分析
整体思路是将两个字符串较短的用 $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
类似 102. 二叉树的层序遍历，用一个 BFS 模拟香槟溢出流程：第一层溢出的香槟流到第二层，第二层溢出的香槟流到第三层，依此类推。
具体地：
###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
}
}
欢迎关注 B站@灵茶山艾府
我们把玻璃杯摆成金字塔的形状，其中 第一层 有 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我们创建一个二维数组dp[i][j]，其中，i表示行号，j表示酒杯编号。
根据题目描述，我们可以知道，针对于第row行第column列（dp[row][column]）的这个酒杯，有机会能够注入到它的“上层”酒杯只会是dp[row-1][column-1]和dp[row-1][column]，那么这里是“有机会”，因为只有这两个酒杯都满了（减1）的情况下，才会注入到dp[row][column]这个酒杯中，所以，我们可以得到状态转移方程为：
dp[row][column] = Math.max(dp[row-1][column-1]-1, 0)/2 + Math.max(dp[row-1][column]-1, 0)/2。
那么我们从第一行开始计算，逐一可以计算出每一行中每一个酒杯的容量，那么题目的结果就显而易见了。具体操作，如下图所示：
由于题目只需要获取第query_row行的第query_glass编号的酒杯容量，那么我们其实只需要关注第query_row行的酒杯容量即可，所以，用一维数组dp[]来保存最新计算的那个行中每个酒杯的容量。
计算方式与上面的解法相似，此处就不赘述了。
###java
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[][] dp = new double[query_row + 2][query_row + 2];
dp[1][1] = poured; // 为了方式越界，下标（0,0）的酒杯我们存放在dp[1][1]的位置上
for (int row = 2; row <= query_row + 1; row++) {
for (int column = 1; column <= row; column++) {
dp[row][column] = Math.max(dp[row - 1][column - 1] - 1, 0) / 2 + Math.max(dp[row - 1][column] - 1, 0) / 2;
}
}
return Math.min(dp[query_row + 1][query_glass + 1], 1);
}
}
###java
class Solution {
public double champagneTower(int poured, int query_row, int query_glass) {
double[] dp = new double[query_glass + 2]; // 第i层中每个glass的容量
dp[0] = poured; // 第0层的第0个编号酒杯倾倒香槟容量
int row = 0;
while (row < query_row) { // 获取第query_row行，只需要遍历到第query_row减1行即可。
for (int glass = Math.min(row, query_glass); glass >= 0; glass--) {
double overflow = Math.max(dp[glass] - 1, 0) / 2.0;
dp[glass] = overflow; // 覆盖掉旧值
dp[glass + 1] += overflow; // 由于是倒序遍历，所以对于dp[glass + 1]要执行“+=”操作
}
row++; // 计算下一行
}
return Math.min(dp[query_glass], 1); // 如果倾倒香槟容量大于1，则只返回1.
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」
为了方便，我们令 poured 为 k，query_row 和 query_glass 分别为 $n$ 和 $m$。
定义 $f[i][j]$ 为第 $i$ 行第 $j$ 列杯子所经过的水的流量（而不是最终剩余的水量）。
起始我们有 $f[0][0] = k$，最终答案为 $\min(f[n][m], 1)$。
不失一般性考虑 $f[i][j]$ 能够更新哪些状态：显然当 $f[i][j]$ 不足 $1$ 的时候，不会有水从杯子里溢出，即 $f[i][j]$ 将不能更新其他状态；当 $f[i][j]$ 大于 $1$ 时，将会有 $f[i][j] - 1$ 的水会等量留到下一行的杯子里，所流向的杯子分别是「第 $i + 1$ 行第 $j$ 列的杯子」和「第 $i + 1$ 行第 $j + 1$ 列的杯子」，增加流量均为 $\frac{f[i][j] - 1}{2}$，即有 $f[i + 1][j] += \frac{f[i][j] - 1}{2}$ 和 $f[i + 1][j + 1] += \frac{f[i][j] - 1}{2}$。
代码：
###Java
class Solution {
public double champagneTower(int k, int n, int m) {
double[][] f = new double[n + 10][n + 10];
f[0][0] = k;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= i; j++) {
if (f[i][j] <= 1) continue;
f[i + 1][j] += (f[i][j] - 1) / 2;
f[i + 1][j + 1] += (f[i][j] - 1) / 2;
}
}
return Math.min(f[n][m], 1);
}
}
###TypeScript
function champagneTower(k: number, n: number, m: number): number {
const f = new Array<Array<number>>()
for (let i = 0; i < n + 10; i++) f.push(new Array<number>(n + 10).fill(0))
f[0][0] = k
for (let i = 0; i <= n; i++) {
for (let j = 0; j <= i; j++) {
if (f[i][j] <= 1) continue
f[i + 1][j] += (f[i][j] - 1) / 2
f[i + 1][j + 1] += (f[i][j] - 1) / 2
}
}
return Math.min(f[n][m], 1)
}
###Python3
class Solution:
def champagneTower(self, k: int, n: int, m: int) -> float:
f = [[0] * (n + 10) for _ in range(n + 10)]
f[0][0] = k
for i in range(n + 1):
for j in range(i + 1):
if f[i][j] <= 1:
continue
f[i + 1][j] += (f[i][j] - 1) / 2
f[i + 1][j + 1] += (f[i][j] - 1) / 2
return min(f[n][m], 1)
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
给你一个只包含字符 'a'、'b' 和 'c' 的字符串 s。
如果一个 子串 中所有 不同 字符出现的次数都 相同，则称该子串为 平衡 子串。
请返回 s 的 最长平衡子串 的 长度 。
子串 是字符串中连续的、非空 的字符序列。
示例 1：
输入： s = "abbac"
输出： 4
解释：
最长的平衡子串是 "abba"，因为不同字符 'a' 和 'b' 都恰好出现了 2 次。
示例 2：
输入： s = "aabcc"
输出： 3
解释：
最长的平衡子串是 "abc"，因为不同字符 'a'、'b' 和 'c' 都恰好出现了 1 次。
示例 3：
输入： s = "aba"
输出： 2
解释：
最长的平衡子串之一是 "ab"，因为不同字符 'a' 和 'b' 都恰好出现了 1 次。另一个最长的平衡子串是 "ba"。
提示：
1 <= s.length <= 105s 仅包含字符 'a'、'b' 和 'c'。先考虑简单一点的问题：如果只有字母 a 和 b 怎么做？
这是一个经典的用前缀和维护的题目。假设平衡子串的下标范围是 $[l, r]$，设 $a_i$ 表示字母 a 在长度为 $i$ 的前缀里的出现次数，$b_i$ 表示字母 b 在长度为 $i$ 的前缀里的出现次数，则
$$
a_r - a_{l - 1} = b_r - b_{l - 1}
$$
移项得
$$
a_r - b_r = a_{l - 1} - b_{l - 1}
$$
因此，类似于 leetcode 974. 和可被 K 整除的子数组，我们枚举子串的右端点 $r$，并找到 $\Delta = (a_i - b_i)$ 的值与 $r$ 相同的最小下标 $l$，则以 $r$ 为右端点的平衡子串的最大长度就是 $(r - l)$。我们可以把 $\Delta$ 的值放入哈希表，并对每个 $\Delta$ 维护最小的下标。
回到当前问题，现在增加了一个字母 c，我们能不能用类似的方法做呢？设 $c_i$ 表示字母 c 在长度为 $i$ 的前缀里的出现次数，我们继续分析一下平衡子串的条件
$$
\begin{matrix}
a_r - a_{l - 1} = b_r - b_{l - 1} \
b_r - b_{l - 1} = c_r - c_{l - 1} \
\end{matrix}
$$
移项得
$$
\begin{matrix}
a_r - b_r = a_{l - 1} - b_{l - 1} \
b_r - c_r = b_{l - 1} - c_{l - 1} \
\end{matrix}
$$
因此，我们仍然可以用相同的做法求出平衡子串的最大长度，只不过哈希表的 key 不是一个整数 $(a_i - b_i)$，而是一个数对 $(a_i - b_i, b_i - c_i)$。
复杂度 $\mathcal{O}(n)$（认为字符集大小是常数）。
其实，这个做法也可以推广到任意字符集，复杂度 $\mathcal{O}(n|\Sigma| \times 2^{|\Sigma|})$，其中 $|\Sigma|$ 是字符集大小。有兴趣的读者可以试着做一下本题强化版 CF GYM100584D - Balanced strings，链接就不附了，怕扣子又把我帖子搞没了。
class Solution {
public:
int longestBalanced(string s) {
int n = s.size(), ans = 0;
// 子串只包含一个字母的情况
auto calc1 = [&]() {
int cnt = 0;
for (int i = 0; i < n; i++) {
if (i == 0 || s[i] == s[i - 1]) cnt++;
else cnt = 1;
ans = max(ans, cnt);
}
};
// 子串只包含两个字母的情况
auto calc2 = [&](char a, char b) {
unordered_map<int, int> mp;
mp[0] = -1;
// x 表示 a_i - b_i 的值
int x = 0;
for(int i = 0; i < n; i++) {
if (s[i] == a) x++;
else if (s[i] == b) x--;
else {
// 遇到不在子串里的字符，截断
mp.clear();
x = 0;
}
if (mp.count(x)) ans = max(ans, i - mp[x]);
else mp[x] = i;
}
};
// 子串包含三个字母的情况
auto calc3 = [&]() {
unordered_map<long long, int> mp;
mp[0] = -1;
// x 表示 a_i - b_i 的值
// y 表示 b_i - c_i 的值
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
if (s[i] == 'a') x++;
else if (s[i] == 'b') x--, y++;
else y--;
// c++ 的 unordered_map 不支持用 pair 作为 key
// 所以只能把数对映射成一个整数
// 当然也可以直接用 map，用 pair 作为 key
// 只是复杂度会乘上一个 log
long long key = 10LL * x * n + y;
if (mp.count(key)) ans = max(ans, i - mp[key]);
else mp[key] = i;
}
};
calc1();
calc2('a', 'b');
calc2('a', 'c');
calc2('b', 'c');
calc3();
return ans;
}
};
读者首先需要掌握用前缀和 + 哈希表的方式，求特定子数组数量或最大长度的方法。读者可以学习 灵神题单 - 常用数据结构 的“前缀和与哈希表”一节。
如果读者掌握了这一技巧，那么至少可以解答只包含 a 和 b 的情况。若此时仍然不会做本题，需要加强从特殊到一般的拓展能力。一般来说可以先考虑一个简化的问题怎么做（例如图上问题先想一下树上怎么做，树上问题先想一下链上怎么做，二维矩阵问题先想一下一维序列怎么做），这只能在大量的练习中慢慢习得。
