特殊的二进制字符串 是具有以下两个性质的二进制序列：
登录
0 的数量与 1 的数量相等。1 的数量要大于等于 0 的数量。给定一个特殊的二进制字符串 s。
一次移动操作包括选择字符串 s 中的两个连续的、非空的、特殊子串，并交换它们。两个字符串是连续的，如果第一个字符串的最后一个字符与第二个字符串的第一个字符的索引相差正好为 1。
返回在字符串上应用任意次操作后可能得到的字典序最大的字符串。
示例 1:
输入: S = "11011000" 输出: "11100100" 解释: 将子串 "10" （在 s[1] 出现） 和 "1100" （在 s[3] 出现）进行交换。 这是在进行若干次操作后按字典序排列最大的结果。
示例 2：
输入：s = "10" 输出："10"
提示：
1 <= s.length <= 50s[i] 为 '0' 或 '1'。s 是一个特殊的二进制字符串。我们可以定义每个字符的得分：字符 1 得分为 $1$ 分，字符 0 得分为 $-1$ 分。
根据题目对「特殊字符串」的定义可知，给定字符串 s 的总得分为 $0$，且任意前缀串不会出现得分为负数的情况。
考虑将 s 进行划分为多个足够小特殊字符串 item（足够小的含义为每个 item 无法再进行划分），每个 item 的总得分为 $0$。根据 s 定义，必然可恰好划分为多个 item。
每次操作可以将相邻特殊字符串进行交换，于是问题转换为将 s 进行重排，求其重排后字典序最大的方案。
首先可以证明一个合法 item 必然满足 1...0 的形式，可通过「反证法」进行进行证明：定义了 item 总得分为 $0$，且长度不为 $0$，因此必然有 1 有 0。若第一位字符为 0，则必然能够从第一位字符作为起点，找到一个得分为负数的子串，这与 s 本身的定义冲突（s 中不存在得分为负数的前缀串）；若最后一位为 1，根据 item 总得分为 $0$，可知当前 item 去掉最后一位后得分为负，也与 s 本身定义冲突（s 中不存在得分为负数的前缀串）。
因此可将构造分两步进行：
item 进行重排，使其调整为字典序最大item 之间的位置进行重排，使其整体字典序最大由于题目没有规定重排后的性质，为第一步调整和第二步调整的保持相对独立，我们只能对 item 中的 1...0 中的非边缘部分进行调整（递归处理子串部分）。
假设所有 item 均被处理后，考虑如何进行重排能够使得最终方案字典序最大。
若有两个 item，分别为 a 和 b，我们可以根据拼接结果 ab 和 ba 的字典序大小来决定将谁放在前面。
这样根据「排序比较逻辑」需要证明在集合上具有「全序关系」:
我们使用符号 $@$ 来代指我们的「排序」逻辑：
2.1 完全性
具有完全性是指从集合 items 中任意取出两个元素 $a$ 和 $b$，必然满足 $a @ b$、$b @ a$ 和 $a#b$ 三者之一。
这点其实不需要额外证明，因为由 $a$ 和 $b$ 拼接的字符串 $ab$ 和 $ba$ 所在「字典序大小关系中」要么完全相等，要么具有明确的字典序大小关系，导致 $a$ 必须排在前面或者后面。
2.2 反对称性
具有反对称性是指由 $a@b$ 和 $b@a$ 能够推导出 $a#b$。
$a@b$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值大。
$b@a$ 说明字符串 $ab$ 的字典序大小数值要比字符串 $ba$ 字典序大小数值小。
这样，基于「字典序本身满足全序关系」和「数学上的 $a \geqslant b$ 和 $a \leqslant b$ 可推导出 $a = b$」。
得证 $a@b$ 和 $b@a$ 能够推导出 $a#b$。
2.3 传递性
具有传递性是指由 $a@b$ 和 $b@c$ 能够推导出 $a@c$。
我们可以利用「两个等长的拼接字符串，字典序大小关系与数值大小关系一致」这一性质来证明，因为字符串 $ac$ 和 $ca$ 必然是等长的。
接下来，让我们从「自定义排序逻辑」出发，换个思路来证明 $a@c$：
然后我们只需要证明在不同的 $i$ $j$ 关系之间（共三种情况），$a@c$ 恒成立即可：
综上，我们证明了无论在何种情况下，只要有 $a@b$ 和 $b@c$ 的话，那么 $a@c$ 恒成立。
我们之所以能这样证明「传递性」，本质是利用了自定义排序逻辑中「对于确定任意元素 $a$ 和 $b$ 之间的排序关系只依赖于 $a$ 和 $b$ 的第一个不同元素之间的大小关系」这一性质。
最终，我们证明了该「排序比较逻辑」必然能排序出字典序最大的方案。
代码：
###Java
class Solution {
public String makeLargestSpecial(String s) {
if (s.length() == 0) return s;
List<String> list = new ArrayList<>();
char[] cs = s.toCharArray();
for (int i = 0, j = 0, k = 0; i < cs.length; i++) {
k += cs[i] == '1' ? 1 : -1;
if (k == 0) {
list.add("1" + makeLargestSpecial(s.substring(j + 1, i)) + "0");
j = i + 1;
}
}
Collections.sort(list, (a, b)->(b + a).compareTo(a + b));
StringBuilder sb = new StringBuilder();
for (String str : list) sb.append(str);
return sb.toString();
}
}
###TypeScript
function makeLargestSpecial(s: string): string {
const list = new Array<string>()
for (let i = 0, j = 0, k = 0; i < s.length; i++) {
k += s[i] == '1' ? 1 : -1
if (k == 0) {
list.push('1' + makeLargestSpecial(s.substring(j + 1, i)) + '0')
j = i + 1
}
}
list.sort((a, b)=>(b + a).localeCompare(a + b));
return [...list].join("")
};
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
我们可以把特殊的二进制序列看作"有效的括号"，1代表左括号，0代表右括号。
比如："11011000"可以看作"(()(()))"。
两个连续且非空的特殊的子串，然后将它们交换，代表着交换两个相邻的两个有效括号。
我们可以将题进行如下划分，把每一个有效的括号匹配都看作一部分，然后进行排序，内部也进行排序处理，例如：
代码如下
###java
public String makeLargestSpecial(String s) {
if (s.length() == 0) {
return "";
}
List<String> list = new ArrayList<>();
int count = 0, last = 0;
for (int i = 0, cur = 0; i < s.length(); i++, cur++) {
if (s.charAt(i) == '1') {
count++;
} else {
count--;
}
//一组有效的括号匹配 去掉括号进行 内部排序
if (count == 0) {
String str = "1" + makeLargestSpecial(s.substring(last + 1, cur)) + "0";
list.add(str);
last = cur + 1;
}
}
//进行排序，根据冒泡排序，交换两个相邻的元素进行排序，总能让内部的括号由大到小排列
list.sort(Comparator.reverseOrder());
//拼成完整的字符串
StringBuilder sb = new StringBuilder();
for (String str : list) {
sb.append(str);
}
return sb.toString();
}
写题解不易，如果对您有帮助，记得关注 + 点赞 + 收藏呦！！！
每天都会更新每日一题题解，大家加油！！
相信好多人看到题目中 “特殊的二进制序列” 的定义就懵逼了，这到底是什么鬼？
所以题目最难的地方就是 “不说人话”。其实只要想到这种定义就是 “有效的括号字符串” 就容易许多了，“1” 代表 “(”，“0” 代表 “)”。
再看题目中 “操作” 的定义：首先选择 S 的两个 连续 且非空的 特殊 的子串，然后将它们交换。
翻译过来就是：选择 S 中的两个 相邻 的 有效的括号字符串，然后交换即可。
现在再来解决问题。首先分析 “有效的括号字符串” 的性质。
根据上面的规则，我们可以 递归地 将二进制序列对应的 “括号字符串” 分解。以序列 “110011100110110000” 为例：
我们容易想到一种 递归地 解题思路。
###python
class Solution:
def makeLargestSpecial(self, s: str) -> str:
cur, last = 0, 0
ret = []
for i in range(len(s)):
cur += 1 if s[i] == '1' else -1
if cur == 0:
ret.append('1' + self.makeLargestSpecial(s[last + 1 : i]) + '0')
last = i + 1
return ''.join(sorted(ret, reverse=True))
###c++
class Solution {
public:
string makeLargestSpecial(string s) {
vector<string> v;
for(int i = 0, cur = 0, last = 0; i < s.size(); ++i) {
(s[i] == '1')? cur++ : cur--;
if(cur == 0) {
v.push_back("1");
v.back() += makeLargestSpecial(s.substr(last + 1, i - last - 1)) + '0';
last = i + 1;
}
}
sort(v.begin(), v.end(), greater<string>());
string res;
for(auto& r : v) {
res += r;
}
return res;
}
};
给定一个字符串 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 为偶数
进阶: 如果多次调用这个函数，你将如何优化你的算法？
