给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。
重复出现（不同位置）的子串也要统计它们出现的次数。
示例 1：
输入：s = "00110011" 输出：6 解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。 注意，一些重复出现的子串（不同位置）要统计它们出现的次数。 另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。
示例 2：
输入：s = "10101" 输出：4 解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。
提示：
登录1 <= s.length <= 105s[i] 为 '0' 或 '1'
题意：子串必须形如 $\underbrace{\texttt{0}\cdots \texttt{0}}{k\ 个\ \texttt{0}}\underbrace{\texttt{1}\cdots \texttt{1}}{k\ 个\ \texttt{1}}$ 或者 $\underbrace{\texttt{1}\cdots \texttt{1}}{k\ 个\ \texttt{1}}\underbrace{\texttt{0}\cdots \texttt{0}}{k\ 个\ \texttt{0}}$。只能有一段 $\texttt{0}$ 和一段 $\texttt{1}$，不能是 $\texttt{00111}$（两段长度不等）或者 $\texttt{010}$（超过两段）等。
例如 $s = \texttt{001110000}$，按照连续相同字符，分成三组 $\texttt{00},\texttt{111},\texttt{0000}$。
一般地，遍历 $s$，按照连续相同字符分组，计算每一组的长度。设当前这组的长度为 $\textit{cur}$，上一组的长度为 $\textit{pre}$，那么当前这组和上一组，能得到 $\min(\textit{pre},\textit{cur})$ 个合法子串，加到答案中。
###py
class Solution:
def countBinarySubstrings(self, s: str) -> int:
n = len(s)
pre = cur = ans = 0
for i in range(n):
cur += 1
if i == n - 1 or s[i] != s[i + 1]:
# 遍历到了这一组的末尾
ans += min(pre, cur)
pre = cur
cur = 0
return ans
###java
class Solution {
public int countBinarySubstrings(String S) {
char[] s = S.toCharArray();
int n = s.length;
int pre = 0;
int cur = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
cur++;
if (i == n - 1 || s[i] != s[i + 1]) {
// 遍历到了这一组的末尾
ans += Math.min(pre, cur);
pre = cur;
cur = 0;
}
}
return ans;
}
}
###cpp
class Solution {
public:
int countBinarySubstrings(string s) {
int n = s.size();
int pre = 0, cur = 0, ans = 0;
for (int i = 0; i < n; i++) {
cur++;
if (i == n - 1 || s[i] != s[i + 1]) {
// 遍历到了这一组的末尾
ans += min(pre, cur);
pre = cur;
cur = 0;
}
}
return ans;
}
};
###c
#define MIN(a, b) ((b) < (a) ? (b) : (a))
int countBinarySubstrings(char* s) {
int pre = 0, cur = 0, ans = 0;
for (int i = 0; s[i]; i++) {
cur++;
if (s[i] != s[i + 1]) {
// 遍历到了这一组的末尾
ans += MIN(pre, cur);
pre = cur;
cur = 0;
}
}
return ans;
}
###go
func countBinarySubstrings(s string) (ans int) {
n := len(s)
pre, cur := 0, 0
for i := range n {
cur++
if i == n-1 || s[i] != s[i+1] {
// 遍历到了这一组的末尾
ans += min(pre, cur)
pre = cur
cur = 0
}
}
return
}
###js
var countBinarySubstrings = function(s) {
const n = s.length;
let pre = 0, cur = 0, ans = 0;
for (let i = 0; i < n; i++) {
cur++;
if (i === n - 1 || s[i] !== s[i + 1]) {
// 遍历到了这一组的末尾
ans += Math.min(pre, cur);
pre = cur;
cur = 0;
}
}
return ans;
};
###rust
impl Solution {
pub fn count_binary_substrings(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut pre = 0;
let mut cur = 0;
let mut ans = 0;
for i in 0..n {
cur += 1;
if i == n - 1 || s[i] != s[i + 1] {
// 遍历到了这一组的末尾
ans += pre.min(cur);
pre = cur;
cur = 0;
}
}
ans
}
}
见下面双指针题单的「六、分组循环」。
欢迎关注 B站@灵茶山艾府
000111 来说，符合要求的子串是 000111 0011 01
000111 的数据，就可以用来统计答案0/1 后面是连续 1/0 的数据0/1 的个数和后面 1/0 的个数min(cnt_pre, cnt_cur)
11101 来说，当我们遍历到最后的 1 时，1110 就是一段可以用来统计答案的数据01 则是另一段可以用来统计答案的数据<
,
>
class Solution {
public:
int countBinarySubstrings(string s) {
int ans = 0;
char last = '-';
int cnt_pre = 0;
int cnt_cur = 0;
s += '-';
for (auto c : s) {
if (last != c) {
last = c;
ans += min(cnt_pre, cnt_cur);
cnt_pre = cnt_cur;
cnt_cur = 0;
}
cnt_cur++;
}
return ans;
}
};
感谢您的观看，如果感觉还不错就点个赞吧，关注我的 力扣个人主页 ，欢迎热烈的交流！
思路与算法
我们可以将字符串 $s$ 按照 $0$ 和 $1$ 的连续段分组，存在 $\textit{counts}$ 数组中，例如 $s = 00111011$，可以得到这样的 $\textit{counts}$ 数组：$\textit{counts} = {2, 3, 1, 2}$。
这里 $\textit{counts}$ 数组中两个相邻的数一定代表的是两种不同的字符。假设 $\textit{counts}$ 数组中两个相邻的数字为 $u$ 或者 $v$，它们对应着 $u$ 个 $0$ 和 $v$ 个 $1$，或者 $u$ 个 $1$ 和 $v$ 个 $0$。它们能组成的满足条件的子串数目为 $\min { u, v }$，即一对相邻的数字对答案的贡献。
我们只要遍历所有相邻的数对，求它们的贡献总和，即可得到答案。
不难得到这样的实现：
###C++
class Solution {
public:
int countBinarySubstrings(string s) {
vector<int> counts;
int ptr = 0, n = s.size();
while (ptr < n) {
char c = s[ptr];
int count = 0;
while (ptr < n && s[ptr] == c) {
++ptr;
++count;
}
counts.push_back(count);
}
int ans = 0;
for (int i = 1; i < counts.size(); ++i) {
ans += min(counts[i], counts[i - 1]);
}
return ans;
}
};
###Java
class Solution {
public int countBinarySubstrings(String s) {
List<Integer> counts = new ArrayList<Integer>();
int ptr = 0, n = s.length();
while (ptr < n) {
char c = s.charAt(ptr);
int count = 0;
while (ptr < n && s.charAt(ptr) == c) {
++ptr;
++count;
}
counts.add(count);
}
int ans = 0;
for (int i = 1; i < counts.size(); ++i) {
ans += Math.min(counts.get(i), counts.get(i - 1));
}
return ans;
}
}
###JavaScript
var countBinarySubstrings = function(s) {
const counts = [];
let ptr = 0, n = s.length;
while (ptr < n) {
const c = s.charAt(ptr);
let count = 0;
while (ptr < n && s.charAt(ptr) === c) {
++ptr;
++count;
}
counts.push(count);
}
let ans = 0;
for (let i = 1; i < counts.length; ++i) {
ans += Math.min(counts[i], counts[i - 1]);
}
return ans;
};
###Go
func countBinarySubstrings(s string) int {
counts := []int{}
ptr, n := 0, len(s)
for ptr < n {
c := s[ptr]
count := 0
for ptr < n && s[ptr] == c {
ptr++
count++
}
counts = append(counts, count)
}
ans := 0
for i := 1; i < len(counts); i++ {
ans += min(counts[i], counts[i-1])
}
return ans
}
###C
int countBinarySubstrings(char* s) {
int n = strlen(s);
int counts[n], counts_len = 0;
memset(counts, 0, sizeof(counts));
int ptr = 0;
while (ptr < n) {
char c = s[ptr];
int count = 0;
while (ptr < n && s[ptr] == c) {
++ptr;
++count;
}
counts[counts_len++] = count;
}
int ans = 0;
for (int i = 1; i < counts_len; ++i) {
ans += fmin(counts[i], counts[i - 1]);
}
return ans;
}
###Python
class Solution:
def countBinarySubstrings(self, s: str) -> int:
counts = []
ptr, n = 0, len(s)
while ptr < n:
c = s[ptr]
count = 0
while ptr < n and s[ptr] == c:
ptr += 1
count += 1
counts.append(count)
ans = 0
for i in range(1, len(counts)):
ans += min(counts[i], counts[i - 1])
return ans
###C#
public class Solution {
public int CountBinarySubstrings(string s) {
List<int> counts = new List<int>();
int ptr = 0, n = s.Length;
while (ptr < n) {
char c = s[ptr];
int count = 0;
while (ptr < n && s[ptr] == c) {
ptr++;
count++;
}
counts.Add(count);
}
int ans = 0;
for (int i = 1; i < counts.Count; i++) {
ans += Math.Min(counts[i], counts[i - 1]);
}
return ans;
}
}
###TypeScript
function countBinarySubstrings(s: string): number {
const counts: number[] = [];
let ptr = 0, n = s.length;
while (ptr < n) {
const c = s[ptr];
let count = 0;
while (ptr < n && s[ptr] === c) {
ptr++;
count++;
}
counts.push(count);
}
let ans = 0;
for (let i = 1; i < counts.length; i++) {
ans += Math.min(counts[i], counts[i - 1]);
}
return ans;
}
###Rust
impl Solution {
pub fn count_binary_substrings(s: String) -> i32 {
let mut counts = Vec::new();
let bytes = s.as_bytes();
let n = bytes.len();
let mut ptr = 0;
while ptr < n {
let c = bytes[ptr];
let mut count = 0;
while ptr < n && bytes[ptr] == c {
ptr += 1;
count += 1;
}
counts.push(count);
}
let mut ans = 0;
for i in 1..counts.len() {
ans += counts[i].min(counts[i - 1]);
}
ans
}
}
这个实现的时间复杂度和空间复杂度都是 $O(n)$。
对于某一个位置 $i$，其实我们只关心 $i - 1$ 位置的 $\textit{counts}$ 值是多少，所以可以用一个 $\textit{last}$ 变量来维护当前位置的前一个位置，这样可以省去一个 $\textit{counts}$ 数组的空间。
代码
###C++
class Solution {
public:
int countBinarySubstrings(string s) {
int ptr = 0, n = s.size(), last = 0, ans = 0;
while (ptr < n) {
char c = s[ptr];
int count = 0;
while (ptr < n && s[ptr] == c) {
++ptr;
++count;
}
ans += min(count, last);
last = count;
}
return ans;
}
};
###Java
class Solution {
public int countBinarySubstrings(String s) {
int ptr = 0, n = s.length(), last = 0, ans = 0;
while (ptr < n) {
char c = s.charAt(ptr);
int count = 0;
while (ptr < n && s.charAt(ptr) == c) {
++ptr;
++count;
}
ans += Math.min(count, last);
last = count;
}
return ans;
}
}
###JavaScript
var countBinarySubstrings = function(s) {
let ptr = 0, n = s.length, last = 0, ans = 0;
while (ptr < n) {
const c = s.charAt(ptr);
let count = 0;
while (ptr < n && s.charAt(ptr) === c) {
++ptr;
++count;
}
ans += Math.min(count, last);
last = count;
}
return ans;
};
###Go
func countBinarySubstrings(s string) int {
var ptr, last, ans int
n := len(s)
for ptr < n {
c := s[ptr]
count := 0
for ptr < n && s[ptr] == c {
ptr++
count++
}
ans += min(count, last)
last = count
}
return ans
}
###C
int countBinarySubstrings(char* s) {
int ptr = 0, n = strlen(s), last = 0, ans = 0;
while (ptr < n) {
char c = s[ptr];
int count = 0;
while (ptr < n && s[ptr] == c) {
++ptr;
++count;
}
ans += fmin(count, last);
last = count;
}
return ans;
}
###Python
class Solution:
def countBinarySubstrings(self, s: str) -> int:
ptr, n = 0, len(s)
last, ans = 0, 0
while ptr < n:
c = s[ptr]
count = 0
while ptr < n and s[ptr] == c:
ptr += 1
count += 1
ans += min(count, last)
last = count
return ans
###C#
public class Solution {
public int CountBinarySubstrings(string s) {
int ptr = 0, n = s.Length;
int last = 0, ans = 0;
while (ptr < n) {
char c = s[ptr];
int count = 0;
while (ptr < n && s[ptr] == c) {
ptr++;
count++;
}
ans += Math.Min(count, last);
last = count;
}
return ans;
}
}
###TypeScript
function countBinarySubstrings(s: string): number {
let ptr = 0, n = s.length;
let last = 0, ans = 0;
while (ptr < n) {
const c = s[ptr];
let count = 0;
while (ptr < n && s[ptr] === c) {
ptr++;
count++;
}
ans += Math.min(count, last);
last = count;
}
return ans;
}
###Rust
impl Solution {
pub fn count_binary_substrings(s: String) -> i32 {
let bytes = s.as_bytes();
let n = bytes.len();
let mut ptr = 0;
let mut last = 0;
let mut ans = 0;
while ptr < n {
let c = bytes[ptr];
let mut count = 0;
while ptr < n && bytes[ptr] == c {
ptr += 1;
count += 1;
}
ans += count.min(last);
last = count;
}
ans
}
}
复杂度分析
为了做到 $\mathcal{O}(1)$ 时间，我们需要快速判断所有相邻比特位是否都不同。
如何判断不同？用哪个位运算最合适？
用异或运算最合适。对于单个比特的异或，如果两个数不同，那么结果是 $1$；如果两个数相同，那么结果是 $0$。
如何对所有相邻比特位做异或运算？
例如 $n = 10101$，可以把 $n$ 右移一位，得到 $01010$，再与 $10101$ 做异或运算，计算的就是相邻比特位的异或值了。
如果异或结果全为 $1$，就说明所有相邻比特位都不同。
如何判断一个二进制数全为 $1$？
这相当于判断二进制数加一后，是否为 231. 2 的幂。
设 $x$ 为 (n >> 1) ^ n，如果 (x + 1) & x 等于 $0$，那么说明 $x$ 全为 $1$。
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
x = (n >> 1) ^ n
return (x + 1) & x == 0
class Solution {
public boolean hasAlternatingBits(int n) {
int x = (n >> 1) ^ n;
return ((x + 1) & x) == 0;
}
}
class Solution {
public:
bool hasAlternatingBits(int n) {
uint32_t x = (n >> 1) ^ n;
return ((x + 1) & x) == 0;
}
};
bool hasAlternatingBits(int n) {
uint32_t x = (n >> 1) ^ n;
return ((x + 1) & x) == 0;
}
func hasAlternatingBits(n int) bool {
x := n>>1 ^ n
return (x+1)&x == 0
}
var hasAlternatingBits = function(n) {
const x = (n >> 1) ^ n;
return ((x + 1) & x) === 0;
};
impl Solution {
pub fn has_alternating_bits(n: i32) -> bool {
let x = (n >> 1) ^ n;
(x + 1) & x == 0
}
}
见下面位运算题单的「一、基础题」。
欢迎关注 B站@灵茶山艾府
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
示例 1：
输入：n = 5 输出：true 解释：5 的二进制表示是：101
示例 2：
输入：n = 7 输出：false 解释：7 的二进制表示是：111.
示例 3：
输入：n = 11 输出：false 解释：11 的二进制表示是：1011.
提示：
1 <= n <= 231 - 1根据题意，对 $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;
}
}
另外一种更为巧妙的方式是利用交替位二进制数性质。
当给定值 $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;
}
}
今日份加餐：经典「状态压缩 + 位运算」入门题 🎉🎉
或是考虑加练如下「位运算」题目 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 137. 只出现一次的数字 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 190. 颠倒二进制位 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 191. 位1的个数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 260. 只出现一次的数字 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 405. 数字转换为十六进制数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 461. 汉明距离 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 477. 汉明距离总和 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 526. 优美的排列 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
思路
从最低位至最高位，我们用对 $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)$。使用了常数空间来存储中间变量。
将n右移一位异或n，检查结果是否全为1。
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
tmp = n^(n>>1)
return tmp&(tmp+1) == 0
枚举小时 $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
}
欢迎关注 B站@灵茶山艾府
二进制手表顶部有 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" ，就不含前导零