给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。
登录
0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。
返回这些数字之和。题目数据保证答案是一个 32 位 整数。
示例 1：
输入：root = [1,0,1,0,1,0,1] 输出：22 解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
示例 2：
输入：root = [0] 输出：0
提示：
[1, 1000] 范围内Node.val 仅为 0 或 1 容易想到「递归」进行求解，在 DFS 过程中记录下当前的值为多少，假设遍历到当前节点 $x$ 前，记录的值为 $cur$，那么根据题意，我们需要先将 $cur$ 进行整体左移（腾出最后一位），然后将节点 $x$ 的值放置最低位来得到新的值，并继续进行递归。
递归有使用「函数返回值」和「全局变量」两种实现方式。
代码：
###Java
class Solution {
public int sumRootToLeaf(TreeNode root) {
return dfs(root, 0);
}
int dfs(TreeNode root, int cur) {
int ans = 0, ncur = (cur << 1) + root.val;
if (root.left != null) ans += dfs(root.left, ncur);
if (root.right != null) ans += dfs(root.right, ncur);
return root.left == null && root.right == null ? ncur : ans;
}
}
###Java
class Solution {
int ans = 0;
public int sumRootToLeaf(TreeNode root) {
dfs(root, 0);
return ans;
}
void dfs(TreeNode root, int cur) {
int ncur = (cur << 1) + root.val;
if (root.left != null) dfs(root.left, ncur);
if (root.right != null) dfs(root.right, ncur);
if (root.left == null && root.right == null) ans += ncur;
}
}
自然也可以使用「迭代」进行求解。
为了不引入除「队列」以外的其他数据结构，当我们可以把某个节点 $x$ 放出队列时，先将其的值修改为当前遍历路径对应的二进制数。
代码：
###Java
class Solution {
public int sumRootToLeaf(TreeNode root) {
int ans = 0;
Deque<TreeNode> d = new ArrayDeque<>();
d.addLast(root);
while (!d.isEmpty()) {
TreeNode poll = d.pollFirst();
if (poll.left != null) {
poll.left.val = (poll.val << 1) + poll.left.val;
d.addLast(poll.left);
}
if (poll.right != null) {
poll.right.val = (poll.val << 1) + poll.right.val;
d.addLast(poll.right);
}
if (poll.left == null && poll.right == null) ans += poll.val;
}
return ans;
}
}
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
思路分析：
本题最直观的思路就是直接递归遍历即可：按照访问根节点——左子树——右子树——的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。
实现步骤：
确定递归函数的参数和返回值： 因为本题需要递归遍历每个节点而且当前节点的计算用到了上次计算的结果，所以函数返回值是 计算结果值；确定终止条件： 当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接 $return$ $0$；确定单层递归的逻辑：
【图解举例】
具体代码如下：
###C++
class Solution {
public:
int traserval(TreeNode *root, int sum) {
if(root == NULL) return 0;
sum = (sum << 1) | root->val;
if(!root->left && !root->right) return sum;
int leftVal = traserval(root->left, sum);
int rightVal = traserval(root->right, sum);
return leftVal + rightVal;
}
int sumRootToLeaf(TreeNode* root) {
return traserval(root, 0);
}
};
复杂度分析：
关于二叉树后序遍历的详细说明请参考「145. 二叉树的后序遍历的官方题解」。
后序遍历的访问顺序为：左子树——右子树——根节点。我们对根节点 $\textit{root}$ 进行后序遍历：
如果节点是叶子节点，返回它对应的数字 $\textit{val}$。
如果节点是非叶子节点，返回它的左子树和右子树对应的结果之和。
###Python
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
def dfs(node: Optional[TreeNode], val: int) -> int:
if node is None:
return 0
val = (val << 1) | node.val
if node.left is None and node.right is None:
return val
return dfs(node.left, val) + dfs(node.right, val)
return dfs(root, 0)
###C++
class Solution {
public:
int dfs(TreeNode *root, int val) {
if (root == nullptr) {
return 0;
}
val = (val << 1) | root->val;
if (root->left == nullptr && root->right == nullptr) {
return val;
}
return dfs(root->left, val) + dfs(root->right, val);
}
int sumRootToLeaf(TreeNode* root) {
return dfs(root, 0);
}
};
###Java
class Solution {
public int sumRootToLeaf(TreeNode root) {
return dfs(root, 0);
}
public int dfs(TreeNode root, int val) {
if (root == null) {
return 0;
}
val = (val << 1) | root.val;
if (root.left == null && root.right == null) {
return val;
}
return dfs(root.left, val) + dfs(root.right, val);
}
}
###C#
public class Solution {
public int SumRootToLeaf(TreeNode root) {
return DFS(root, 0);
}
public int DFS(TreeNode root, int val) {
if (root == null) {
return 0;
}
val = (val << 1) | root.val;
if (root.left == null && root.right == null) {
return val;
}
return DFS(root.left, val) + DFS(root.right, val);
}
}
###C
int dfs(struct TreeNode *root, int val) {
if (root == NULL) {
return 0;
}
val = (val << 1) | root->val;
if (root->left == NULL && root->right == NULL) {
return val;
}
return dfs(root->left, val) + dfs(root->right, val);
}
int sumRootToLeaf(struct TreeNode* root){
return dfs(root, 0);
}
###JavaScript
var sumRootToLeaf = function(root) {
const dfs = (root, val) => {
if (!root) {
return 0;
}
val = (val << 1) | root.val;
if (!root.left&& !root.right) {
return val;
}
return dfs(root.left, val) + dfs(root.right, val);
}
return dfs(root, 0);
};
###go
func dfs(node *TreeNode, val int) int {
if node == nil {
return 0
}
val = val<<1 | node.Val
if node.Left == nil && node.Right == nil {
return val
}
return dfs(node.Left, val) + dfs(node.Right, val)
}
func sumRootToLeaf(root *TreeNode) int {
return dfs(root, 0)
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是节点数目。总共访问 $n$ 个节点。
空间复杂度：$O(n)$。递归栈需要 $O(n)$ 的空间。
我们用栈来模拟递归，同时使用一个 $\textit{prev}$ 指针来记录先前访问的节点。算法步骤如下：
如果节点 $\textit{root}$ 非空，我们将不断地将它及它的左节点压入栈中。
我们从栈中获取节点：
该节点的右节点为空或者等于 $\textit{prev}$，说明该节点的左子树及右子树都已经被访问，我们将它出栈。如果该节点是叶子节点，我们将它对应的数字 $\textit{val}$ 加入结果中。设置 $\textit{prev}$ 为该节点，设置 $\textit{root}$ 为空指针。
该节点的右节点非空且不等于 $\textit{prev}$，我们令 $\textit{root}$ 指向该节点的右节点。
如果 $\textit{root}$ 为空指针或者栈空，中止算法，否则重复步骤 $1$。
需要注意的是，每次出入栈都需要更新 $\textit{val}$。
###Python
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
ans = val = 0
st = []
pre = None
while root or st:
while root:
val = (val << 1) | root.val
st.append(root)
root = root.left
root = st[-1]
if root.right is None or root.right == pre:
if root.left is None and root.right is None:
ans += val
val >>= 1
st.pop()
pre = root
root = None
else:
root = root.right
return ans
###C++
class Solution {
public:
int sumRootToLeaf(TreeNode* root) {
stack<TreeNode *> st;
int val = 0, ret = 0;
TreeNode *prev = nullptr;
while (root != nullptr || !st.empty()) {
while (root != nullptr) {
val = (val << 1) | root->val;
st.push(root);
root = root->left;
}
root = st.top();
if (root->right == nullptr || root->right == prev) {
if (root->left == nullptr && root->right == nullptr) {
ret += val;
}
val >>= 1;
st.pop();
prev = root;
root = nullptr;
} else {
root = root->right;
}
}
return ret;
}
};
###Java
class Solution {
public int sumRootToLeaf(TreeNode root) {
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
int val = 0, ret = 0;
TreeNode prev = null;
while (root != null || !stack.isEmpty()) {
while (root != null) {
val = (val << 1) | root.val;
stack.push(root);
root = root.left;
}
root = stack.peek();
if (root.right == null || root.right == prev) {
if (root.left == null && root.right == null) {
ret += val;
}
val >>= 1;
stack.pop();
prev = root;
root = null;
} else {
root = root.right;
}
}
return ret;
}
}
###C#
public class Solution {
public int SumRootToLeaf(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
int val = 0, ret = 0;
TreeNode prev = null;
while (root != null || stack.Count > 0) {
while (root != null) {
val = (val << 1) | root.val;
stack.Push(root);
root = root.left;
}
root = stack.Peek();
if (root.right == null || root.right == prev) {
if (root.left == null && root.right == null) {
ret += val;
}
val >>= 1;
stack.Pop();
prev = root;
root = null;
} else {
root = root.right;
}
}
return ret;
}
}
###C
#define MAX_NODE_SIZE 1000
int sumRootToLeaf(struct TreeNode* root) {
struct TreeNode ** stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * MAX_NODE_SIZE);
int top = 0;
int val = 0, ret = 0;
struct TreeNode *prev = NULL;
while (root != NULL || top) {
while (root != NULL) {
val = (val << 1) | root->val;
stack[top++] = root;
root = root->left;
}
root = stack[top - 1];
if (root->right == NULL || root->right == prev) {
if (root->left == NULL && root->right == NULL) {
ret += val;
}
val >>= 1;
top--;
prev = root;
root = NULL;
} else {
root = root->right;
}
}
free(stack);
return ret;
}
###JavaScript
var sumRootToLeaf = function(root) {
const stack = [];
let val = 0, ret = 0;
let prev = null;
while (root || stack.length) {
while (root) {
val = (val << 1) | root.val;
stack.push(root);
root = root.left;
}
root = stack[stack.length - 1];
if (!root.right || root.right === prev) {
if (!root.left && !root.right) {
ret += val;
}
val >>= 1;
stack.pop();
prev = root;
root = null;
} else {
root = root.right;
}
}
return ret;
};
###go
func sumRootToLeaf(root *TreeNode) (ans int) {
val, st := 0, []*TreeNode{}
var pre *TreeNode
for root != nil || len(st) > 0 {
for root != nil {
val = val<<1 | root.Val
st = append(st, root)
root = root.Left
}
root = st[len(st)-1]
if root.Right == nil || root.Right == pre {
if root.Left == nil && root.Right == nil {
ans += val
}
val >>= 1
st = st[:len(st)-1]
pre = root
root = nil
} else {
root = root.Right
}
}
return
}
复杂度分析
时间复杂度：$O(n)$，其中 $n$ 是节点数目。总共访问 $n$ 个节点。
空间复杂度：$O(n)$。栈最多压入 $n$ 个节点。
给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。
示例 1：
输入：s = "00110110", k = 2 输出：true 解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。
示例 2：
输入：s = "0110", k = 1 输出：true 解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
示例 3：
输入：s = "0110", k = 2 输出：false 解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
提示：
1 <= s.length <= 5 * 105s[i] 不是'0' 就是 '1'
1 <= k <= 20暴力枚举所有长为 $k$ 的子串，保存到一个哈希集合中。
如果最终哈希集合的大小恰好等于 $2^k$，那么说明所有长为 $k$ 的二进制串都在 $s$ 中。
###py
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
st = {s[i - k: i] for i in range(k, len(s) + 1)}
return len(st) == 1 << k
###java
class Solution {
public boolean hasAllCodes(String s, int k) {
Set<String> set = new HashSet<>();
for (int i = k; i <= s.length(); i++) {
set.add(s.substring(i - k, i));
}
return set.size() == (1 << k);
}
}
###cpp
class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<string> st;
for (int i = k; i <= s.size(); i++) {
st.insert(s.substr(i - k, k));
}
return st.size() == (1 << k);
}
};
###go
func hasAllCodes(s string, k int) bool {
set := map[string]struct{}{}
for i := k; i <= len(s); i++ {
set[s[i-k:i]] = struct{}{}
}
return len(set) == 1<<k
}
把子串转成整数，保存到哈希集合或者布尔数组中。
小优化：如果循环过程中发现已经找到 $2^k$ 个不同的二进制数，可以提前返回 $\texttt{true}$。
###py
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
MASK = (1 << k) - 1
st = set() # 更快的写法见另一份代码【Python3 列表】
x = 0
for i, ch in enumerate(s):
# 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch
# &MASK 目的是去掉超出 k 的比特位
x = (x << 1 & MASK) | int(ch)
if i >= k - 1:
st.add(x)
return len(st) == 1 << k
###py
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
MASK = (1 << k) - 1
has = [False] * (1 << k)
cnt = x = 0
for i, ch in enumerate(s):
# 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch
# &MASK 目的是去掉超出 k 的比特位
x = (x << 1 & MASK) | int(ch)
if i < k - 1 or has[x]:
continue
has[x] = True
cnt += 1
if cnt == 1 << k:
return True
return False
###java
class Solution {
public boolean hasAllCodes(String s, int k) {
final int MASK = (1 << k) - 1;
boolean[] has = new boolean[1 << k];
int cnt = 0;
int x = 0;
for (int i = 0; i < s.length() && cnt < (1 << k); i++) {
char ch = s.charAt(i);
// 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch&1
// &MASK 目的是去掉超出 k 的比特位
x = (x << 1 & MASK) | (ch & 1);
if (i >= k - 1 && !has[x]) {
has[x] = true;
cnt++;
}
}
return cnt == (1 << k);
}
}
###cpp
class Solution {
public:
bool hasAllCodes(string s, int k) {
const int MASK = (1 << k) - 1;
vector<int8_t> has(1 << k);
int cnt = 0;
int x = 0;
for (int i = 0; i < s.size() && cnt < (1 << k); i++) {
// 把 s[i] 加到 x 的末尾：x 整体左移一位，然后或上 s[i]&1
// &MASK 目的是去掉超出 k 的比特位
x = (x << 1 & MASK) | (s[i] & 1);
if (i >= k - 1 && !has[x]) {
has[x] = true;
cnt++;
}
}
return cnt == (1 << k);
}
};
###go
func hasAllCodes(s string, k int) bool {
has := make([]bool, 1<<k)
cnt := 0
mask := 1<<k - 1
x := 0
for i, ch := range s {
// 把 ch 加到 x 的末尾：x 整体左移一位，然后或上 ch&1
// &mask 目的是去掉超出 k 的比特位
x = x<<1&mask | int(ch&1)
if i < k-1 || has[x] {
continue
}
has[x] = true
cnt++
if cnt == 1<<k {
return true
}
}
return false
}
欢迎关注 B站@灵茶山艾府
我们遍历字符串 $s$，并用一个哈希集合（HashSet）存储所有长度为 $k$ 的子串。在遍历完成后，只需要判断哈希集合中是否有 $2^k$ 项即可，这是因为长度为 $k$ 的二进制串的数量为 $2^k$。
注意到如果 $s$ 包含 $2^k$ 个长度为 $k$ 的二进制串，那么它的长度至少为 $2^k+k-1$。因此我们可以在遍历前判断 $s$ 是否足够长。
###C++
class Solution {
public:
bool hasAllCodes(string s, int k) {
if (s.size() < (1 << k) + k - 1) {
return false;
}
unordered_set<string> exists;
for (int i = 0; i + k <= s.size(); ++i) {
exists.insert(move(s.substr(i, k)));
}
return exists.size() == (1 << k);
}
};
###C++
class Solution {
public:
bool hasAllCodes(string s, int k) {
if (s.size() < (1 << k) + k - 1) {
return false;
}
string_view sv(s);
unordered_set<string_view> exists;
for (int i = 0; i + k <= s.size(); ++i) {
exists.insert(sv.substr(i, k));
}
return exists.size() == (1 << k);
}
};
###Python
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) < (1 << k) + k - 1:
return False
exists = set(s[i:i+k] for i in range(len(s) - k + 1))
return len(exists) == (1 << k)
###Java
class Solution {
public boolean hasAllCodes(String s, int k) {
if (s.length() < (1 << k) + k - 1) {
return false;
}
Set<String> exists = new HashSet<String>();
for (int i = 0; i + k <= s.length(); ++i) {
exists.add(s.substring(i, i + k));
}
return exists.size() == (1 << k);
}
}
###C#
public class Solution {
public bool HasAllCodes(string s, int k) {
if (s.Length < (1 << k) + k - 1) {
return false;
}
HashSet<string> exists = new HashSet<string>();
for (int i = 0; i + k <= s.Length; ++i) {
exists.Add(s.Substring(i, k));
}
return exists.Count == (1 << k);
}
}
###Go
func hasAllCodes(s string, k int) bool {
if len(s) < (1 << k) + k - 1 {
return false
}
exists := make(map[string]bool)
for i := 0; i + k <= len(s); i++ {
substring := s[i:i+k]
exists[substring] = true
}
return len(exists) == (1 << k)
}
###C
typedef struct {
char *key;
UT_hash_handle hh;
} HashItem;
HashItem *hashFindItem(HashItem **obj, char *key) {
HashItem *pEntry = NULL;
HASH_FIND_STR(*obj, key, pEntry);
return pEntry;
}
bool hashAddItem(HashItem **obj, char *key) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = strdup(key);
HASH_ADD_STR(*obj, key, pEntry);
return true;
}
void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr->key);
free(curr);
}
}
bool hasAllCodes(char* s, int k) {
int len = strlen(s);
int total = 1 << k;
if (len < total + k - 1) {
return false;
}
HashItem *exists = NULL;
for (int i = 0; i + k <= len; ++i) {
char tmp[k + 1];
strncpy(tmp, s + i, k);
tmp[k] = '\0';
hashAddItem(&exists, tmp);
}
bool ret = HASH_COUNT(exists) == (1 << k);
hashFree(&exists);
return ret;
}
###JavaScript
var hasAllCodes = function(s, k) {
if (s.length < (1 << k) + k - 1) {
return false;
}
const exists = new Set();
for (let i = 0; i + k <= s.length; ++i) {
exists.add(s.substring(i, i + k));
}
return exists.size === (1 << k);
};
###TypeScript
function hasAllCodes(s: string, k: number): boolean {
if (s.length < (1 << k) + k - 1) {
return false;
}
const exists = new Set<string>();
for (let i = 0; i + k <= s.length; ++i) {
exists.add(s.substring(i, i + k));
}
return exists.size === (1 << k);
}
###Rust
use std::collections::HashSet;
impl Solution {
pub fn has_all_codes(s: String, k: i32) -> bool {
let k = k as usize;
let total = 1 << k;
if s.len() < total + k - 1 {
return false;
}
let mut exists = HashSet::new();
for i in 0..=(s.len() - k) {
exists.insert(&s[i..i + k]);
}
exists.len() == total
}
}
复杂度分析
时间复杂度：$O(k * |s|)$，其中 $|s|$ 是字符串 $s$ 的长度。将长度为 $k$ 的字符串加入哈希集合的时间复杂度为 $O(k)$，即为计算哈希值的时间。
空间复杂度：$O(k * 2^k)$。哈希集合中最多有 $2^k$ 项，每一项是一个长度为 $k$ 的字符串。
我们可以借助滑动窗口，对方法一进行优化。
假设我们当前遍历到的长度为 $k$ 的子串为
$$
s_i, s_{i+1}, \cdots, s_{i+k-1}
$$
它的下一个子串为
$$
s_{i+1}, s_{i+2}, \cdots, s_{i+k}
$$
由于这些子串都是二进制串，我们可以将其表示成对应的十进制整数的形式，即
$$
\begin{aligned}
& \textit{num}i &= s_i * 2^{k-1} + s{i+1} * 2^{k-2} + \cdots + s_{i+k-1} * 2^0 \
& \textit{num}{i+1} &= s{i+1} * 2^{k-1} + s_{i+2} * 2^{k-2} + \cdots + s_{i+k} * 2^0 \
\end{aligned}
$$
那么我们可以将这些十进制整数作为哈希表中的项。由于每一个长度为 $k$ 的二进制串都唯一对应了一个十进制整数，因此这样做与方法一是一致的。与二进制串本身不同的是，我们可以在 $O(1)$ 的时间内通过 $\textit{num}i$ 得到 $\textit{num}{i+1}$，即：
$$
num_{i+1} = (num_{i} - s_i * 2^{k-1}) * 2 + s_{i+k}
$$
这样以来，我们在遍历 $s$ 的过程中只维护子串对应的十进制整数，而不需要对字符串进行操作，从而减少了时间复杂度。
###C++
class Solution {
public:
bool hasAllCodes(string s, int k) {
if (s.size() < (1 << k) + k - 1) {
return false;
}
int num = stoi(s.substr(0, k), nullptr, 2);
unordered_set<int> exists = {num};
for (int i = 1; i + k <= s.size(); ++i) {
num = (num - ((s[i - 1] - '0') << (k - 1))) * 2 + (s[i + k - 1] - '0');
exists.insert(num);
}
return exists.size() == (1 << k);
}
};
###Python
class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
if len(s) < (1 << k) + k - 1:
return False
num = int(s[:k], base=2)
exists = set([num])
for i in range(1, len(s) - k + 1):
num = (num - ((ord(s[i - 1]) - 48) << (k - 1))) * 2 + (ord(s[i + k - 1]) - 48)
exists.add(num)
return len(exists) == (1 << k)
###Java
class Solution {
public boolean hasAllCodes(String s, int k) {
if (s.length() < (1 << k) + k - 1) {
return false;
}
int num = Integer.parseInt(s.substring(0, k), 2);
Set<Integer> exists = new HashSet<Integer>();
exists.add(num);
for (int i = 1; i + k <= s.length(); ++i) {
num = (num - ((s.charAt(i - 1) - '0') << (k - 1))) * 2 + (s.charAt(i + k - 1) - '0');
exists.add(num);
}
return exists.size() == (1 << k);
}
}
###C#
public class Solution {
public bool HasAllCodes(string s, int k) {
if (s.Length < (1 << k) + k - 1) {
return false;
}
int num = Convert.ToInt32(s.Substring(0, k), 2);
HashSet<int> exists = new HashSet<int> { num };
for (int i = 1; i + k <= s.Length; ++i) {
num = (num - ((s[i - 1] - '0') << (k - 1))) * 2 + (s[i + k - 1] - '0');
exists.Add(num);
}
return exists.Count == (1 << k);
}
}
###Go
func hasAllCodes(s string, k int) bool {
if len(s) < (1 << k) + k - 1 {
return false
}
num := 0
for i := 0; i < k; i++ {
num = num << 1
if s[i] == '1' {
num |= 1
}
}
exists := make(map[int]bool)
exists[num] = true
for i := 1; i + k <= len(s); i++ {
num = (num - (int(s[i-1]-'0') << (k-1))) * 2 + int(s[i+k-1]-'0')
exists[num] = true
}
return len(exists) == (1 << k)
}
###C
typedef struct {
int key;
UT_hash_handle hh;
} HashItem;
HashItem *hashFindItem(HashItem **obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
return pEntry;
}
bool hashAddItem(HashItem **obj, int key) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
HASH_ADD_INT(*obj, key, pEntry);
return true;
}
void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}
bool hasAllCodes(char* s, int k) {
int len = strlen(s);
int total = 1 << k;
if (len < total + k - 1) {
return false;
}
int num = 0;
for (int i = 0; i < k; i++) {
num = (num << 1) | (s[i] - '0');
}
HashItem *exists = NULL;
hashAddItem(&exists, num);
for (int i = k; i < len; i++) {
int mask = (1 << k) - 1;
num = ((num << 1) | (s[i] - '0')) & mask;
hashAddItem(&exists, num);
}
bool ret = HASH_COUNT(exists) == total;
hashFree(&exists);
return ret;
}
###JavaScript
var hasAllCodes = function(s, k) {
if (s.length < (1 << k) + k - 1) {
return false;
}
let num = parseInt(s.substring(0, k), 2);
const exists = new Set([num]);
for (let i = 1; i + k <= s.length; ++i) {
num = (num - (parseInt(s[i - 1]) << (k - 1))) * 2 + parseInt(s[i + k - 1]);
exists.add(num);
}
return exists.size === (1 << k);
};
###TypeScript
function hasAllCodes(s: string, k: number): boolean {
if (s.length < (1 << k) + k - 1) {
return false;
}
let num = parseInt(s.substring(0, k), 2);
const exists = new Set<number>([num]);
for (let i = 1; i + k <= s.length; ++i) {
num = (num - (parseInt(s[i - 1]) << (k - 1))) * 2 + parseInt(s[i + k - 1]);
exists.add(num);
}
return exists.size === (1 << k);
}
###Rust
use std::collections::HashSet;
impl Solution {
pub fn has_all_codes(s: String, k: i32) -> bool {
let k = k as usize;
let total = 1 << k;
if s.len() < total + k - 1 {
return false;
}
let bytes = s.as_bytes();
let mut num = 0;
for i in 0..k {
num = (num << 1) | (bytes[i] - b'0') as usize;
}
let mut exists = HashSet::new();
exists.insert(num);
for i in 1..=bytes.len() - k {
let high_bit = ((bytes[i - 1] - b'0') as usize) << (k - 1);
num = (num - high_bit) << 1 | (bytes[i + k - 1] - b'0') as usize;
exists.insert(num);
}
exists.len() == total
}
}
复杂度分析
时间复杂度：$O(|s|)$，其中 $|s|$ 是字符串 $s$ 的长度。
空间复杂度：$O(2^k)$。哈希集合中最多有 $2^k$ 项，每一项是一个十进制整数。
大多数题解，都是在哈希表中存储字符串。类似如下的代码：
class Solution {
public:
bool hasAllCodes(string s, int k) {
unordered_set<string> set;
for(int i = 0; i + k <= s.size(); i ++) set.insert(s.substr(i, k));
return set.size() == (1 << k);
}
};
但其实，这样做，因为哈希表中存的是长度为 k 的子串。每次计算子串的哈希值，是需要 O(k) 的时间的。所以这个算法真正的复杂度是 O(|s| * k)
我提交的数据是这样的：
这个问题可以优化，我们可以使用滑动窗口的思想，每次把长度为 k 的子串所对应的整数计算出来。之后，每次窗口向前移动，子串最高位丢掉一个字符；最低位添加一个字符，使用 O(1) 的时间即可计算出新的数字。同时，哈希表中存储的是整型，复杂度才是真正的 O(1)。整体算法复杂度是 O(|s|)的。
class Solution {
public:
bool hasAllCodes(string s, int k) {
if(k > s.size()) return 0;
int cur = 0;
for(int i = 0; i < k - 1; i ++)
cur = 2 * cur + (s[i] == '1');
unordered_set<int> set;
for(int i = k - 1; i < s.size(); i ++){
cur = cur * 2 + (s[i] == '1');
set.insert(cur);
cur &= ~(1 << (k - 1));
}
return set.size() == (1 << k);
}
};
上面的代码在 leetcode 上测试，时间快一倍，空间消耗也更少。
最后，如果使用整型，我们就可以不再使用哈希表了，直接把数组当哈希表用，索引即是 key。这样，性能又能提升一倍。
class Solution {
public:
bool hasAllCodes(string s, int k) {
if(k > s.size()) return 0;
int cur = 0;
for(int i = 0; i < k - 1; i ++)
cur = 2 * cur + (s[i] == '1');
vector<bool> used(1 << k, false);
for(int i = k - 1; i < s.size(); i ++){
cur = cur * 2 + (s[i] == '1');
used[cur] = true;
cur &= ~(1 << (k - 1));
}
for(int e: used) if(!e) return false;
return true;
}
};
觉得有帮助请点赞哇！
以 $n = 1010010$ 为例。从右往左，我们需要计算 $1001$ 的间距 $3$，以及 $101$ 的间距 $2$：
class Solution:
def binaryGap(self, n: int) -> int:
ans = 0
n //= (n & -n) * 2 # 去掉 n 末尾的 100..0
while n > 0:
gap = (n & -n).bit_length() # n 的尾零个数加一
ans = max(ans, gap)
n >>= gap # 去掉 n 末尾的 100..0
return ans
class Solution {
public int binaryGap(int n) {
int ans = 0;
n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
while (n > 0) {
int gap = Integer.numberOfTrailingZeros(n) + 1;
ans = Math.max(ans, gap);
n >>= gap; // 去掉 n 末尾的 100..0
}
return ans;
}
}
class Solution {
public:
int binaryGap(int n) {
int ans = 0;
n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
while (n > 0) {
int gap = countr_zero((uint32_t) n) + 1;
ans = max(ans, gap);
n >>= gap; // 去掉 n 末尾的 100..0
}
return ans;
}
};
#define MAX(a, b) ((b) > (a) ? (b) : (a))
int binaryGap(int n) {
int ans = 0;
n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
while (n > 0) {
int gap = __builtin_ctz(n) + 1;
ans = MAX(ans, gap);
n >>= gap; // 去掉 n 末尾的 100..0
}
return ans;
}
func binaryGap(n int) (ans int) {
n /= n & -n * 2 // 去掉 n 末尾的 100..0
for n > 0 {
gap := bits.TrailingZeros(uint(n)) + 1
ans = max(ans, gap)
n >>= gap // 去掉 n 末尾的 100..0
}
return
}
var binaryGap = function(n) {
let ans = 0;
n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
while (n > 0) {
const gap = 32 - Math.clz32(n & -n); // n 的尾零个数加一
ans = Math.max(ans, gap);
n >>= gap; // 去掉 n 末尾的 100..0
}
return ans;
};
impl Solution {
pub fn binary_gap(mut n: i32) -> i32 {
let mut ans = 0;
n /= (n & -n) * 2; // 去掉 n 末尾的 100..0
while n > 0 {
let gap = n.trailing_zeros() + 1;
ans = ans.max(gap);
n >>= gap; // 去掉 n 末尾的 100..0
}
ans as _
}
}
见下面位运算题单的「一、基础题」。
欢迎关注 B站@灵茶山艾府
给定一个正整数 n，找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1，返回 0 。
如果只有 0 将两个 1 分隔开（可能不存在 0 ），则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如，"1001" 中的两个 1 的距离为 3 。
示例 1：
输入：n = 22 输出：2 解释：22 的二进制是 "10110" 。 在 22 的二进制表示中，有三个 1，组成两对相邻的 1 。 第一对相邻的 1 中，两个 1 之间的距离为 2 。 第二对相邻的 1 中，两个 1 之间的距离为 1 。 答案取两个距离之中最大的，也就是 2 。
示例 2：
输入：n = 8 输出：0 解释：8 的二进制是 "1000" 。 在 8 的二进制表示中没有相邻的两个 1，所以返回 0 。
示例 3：
输入：n = 5 输出：2 解释：5 的二进制是 "101" 。
提示：
1 <= n <= 109根据题意进行模拟即可，遍历 $n$ 的二进制中的每一位 $i$，同时记录上一位 $1$ 的位置 $j$，即可得到所有相邻 $1$ 的间距，所有间距取 $\max$ 即是答案。
代码：
###Java
class Solution {
public int binaryGap(int n) {
int ans = 0;
for (int i = 31, j = -1; i >= 0; i--) {
if (((n >> i) & 1) == 1) {
if (j != -1) ans = Math.max(ans, j - i);
j = i;
}
}
return ans;
}
}
今日份加餐：【面试高频题】难度 1.5/5，脑筋急转弯类模拟题 🎉🎉🎉
或是考虑加练如下「模拟」题 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 6. Z 字形变换 | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 8. 字符串转换整数 (atoi) | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 12. 整数转罗马数字 | LeetCode 题解链接 | 中等 | 🤩🤩 |
| 59. 螺旋矩阵 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 65. 有效数字 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 73. 矩阵置零 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 89. 格雷编码 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 166. 分数到小数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 260. 只出现一次的数字 III | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 414. 第三大的数 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 419. 甲板上的战舰 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 443. 压缩字符串 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 457. 环形数组是否存在循环 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 528. 按权重随机选择 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 539. 最小时间差 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 726. 原子的数量 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
思路与算法
我们可以使用一个循环从 $n$ 二进制表示的低位开始进行遍历，并找出所有的 $1$。我们用一个变量 $\textit{last}$ 记录上一个找到的 $1$ 的位置。如果当前在第 $i$ 位找到了 $1$，那么就用 $i - \textit{last}$ 更新答案，再将 $\textit{last}$ 更新为 $i$ 即可。
在循环的每一步中，我们可以使用位运算 $\texttt{n & 1}$ 获取 $n$ 的最低位，判断其是否为 $1$。在这之后，我们将 $n$ 右移一位：$\texttt{n = n >> 1}$，这样在第 $i$ 步时，$\texttt{n & 1}$ 得到的就是初始 $n$ 的第 $i$ 个二进制位。
代码
###Python
class Solution:
def binaryGap(self, n: int) -> int:
last, ans, i = -1, 0, 0
while n:
if n & 1:
if last != -1:
ans = max(ans, i - last)
last = i
n >>= 1
i += 1
return ans
###C++
class Solution {
public:
int binaryGap(int n) {
int last = -1, ans = 0;
for (int i = 0; n; ++i) {
if (n & 1) {
if (last != -1) {
ans = max(ans, i - last);
}
last = i;
}
n >>= 1;
}
return ans;
}
};
###Java
class Solution {
public int binaryGap(int n) {
int last = -1, ans = 0;
for (int i = 0; n != 0; ++i) {
if ((n & 1) == 1) {
if (last != -1) {
ans = Math.max(ans, i - last);
}
last = i;
}
n >>= 1;
}
return ans;
}
}
###C#
public class Solution {
public int BinaryGap(int n) {
int last = -1, ans = 0;
for (int i = 0; n != 0; ++i) {
if ((n & 1) == 1) {
if (last != -1) {
ans = Math.Max(ans, i - last);
}
last = i;
}
n >>= 1;
}
return ans;
}
}
###C
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int binaryGap(int n) {
int last = -1, ans = 0;
for (int i = 0; n; ++i) {
if (n & 1) {
if (last != -1) {
ans = MAX(ans, i - last);
}
last = i;
}
n >>= 1;
}
return ans;
}
###go
func binaryGap(n int) (ans int) {
for i, last := 0, -1; n > 0; i++ {
if n&1 == 1 {
if last != -1 {
ans = max(ans, i-last)
}
last = i
}
n >>= 1
}
return
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
###JavaScript
var binaryGap = function(n) {
let last = -1, ans = 0;
for (let i = 0; n != 0; ++i) {
if ((n & 1) === 1) {
if (last !== -1) {
ans = Math.max(ans, i - last);
}
last = i;
}
n >>= 1;
}
return ans;
};
复杂度分析
时间复杂度：$O(\log n)$。循环中的每一步 $n$ 会减少一半，因此需要 $O(\log n)$ 次循环。
空间复杂度：$O(1)$。
枚举 $[\textit{left},\textit{right}]$ 中的整数 $x$，计算 $x$ 二进制中的 $1$ 的个数 $c$。如果 $c$ 是质数，那么答案增加一。
由于 $[1,10^6]$ 中的二进制数至多有 $19$ 个 $1$，所以只需 $19$ 以内的质数，即
$$
2, 3, 5, 7, 11, 13, 17, 19
$$
primes = {2, 3, 5, 7, 11, 13, 17, 19}
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
ans = 0
for x in range(left, right + 1):
if x.bit_count() in primes:
ans += 1
return ans
class Solution {
private static final Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19);
public int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; x++) {
if (primes.contains(Integer.bitCount(x))) {
ans++;
}
}
return ans;
}
}
class Solution {
// 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
public:
int countPrimeSetBits(int left, int right) {
int ans = 0;
for (uint32_t x = left; x <= right; x++) {
if (ranges::contains(primes, popcount(x))) {
ans++;
}
}
return ans;
}
};
// 注：也可以用哈希集合做，由于本题质数很少，用 slice 也可以
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
func countPrimeSetBits(left, right int) (ans int) {
for x := left; x <= right; x++ {
if slices.Contains(primes, bits.OnesCount(uint(x))) {
ans++
}
}
return
}
数位 DP v2.0 模板讲解（上下界数位 DP）
对于本题，在递归边界（$i=n$）我们需要判断是否填了质数个 $1$，所以需要参数 $\textit{cnt}_1$ 表示填过的 $1$ 的个数。其余同 v2.0 模板。
primes = {2, 3, 5, 7, 11, 13, 17, 19}
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
high_s = list(map(int, bin(right)[2:])) # 避免在 dfs 中频繁调用 int()
n = len(high_s)
low_s = list(map(int, bin(left)[2:].zfill(n))) # 添加前导零，长度和 high_s 对齐
# 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
@cache # 缓存装饰器，避免重复计算 dfs（一行代码实现记忆化）
def dfs(i: int, cnt1: int, limit_low: bool, limit_high: bool) -> int:
if i == n:
return 1 if cnt1 in primes else 0
lo = low_s[i] if limit_low else 0
hi = high_s[i] if limit_high else 1
res = 0
for d in range(lo, hi + 1):
res += dfs(i + 1, cnt1 + d, limit_low and d == lo, limit_high and d == hi)
return res
return dfs(0, 0, True, True)
class Solution {
private static final Set<Integer> primes = Set.of(2, 3, 5, 7, 11, 13, 17, 19);
public int countPrimeSetBits(int left, int right) {
int n = 32 - Integer.numberOfLeadingZeros(right);
int[][] memo = new int[n][n + 1];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dfs(n - 1, 0, true, true, left, right, memo);
}
// 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
private int dfs(int i, int cnt1, boolean limitLow, boolean limitHigh, int left, int right, int[][] memo) {
if (i < 0) {
return primes.contains(cnt1) ? 1 : 0;
}
if (!limitLow && !limitHigh && memo[i][cnt1] != -1) {
return memo[i][cnt1];
}
int lo = limitLow ? left >> i & 1 : 0;
int hi = limitHigh ? right >> i & 1 : 1;
int res = 0;
for (int d = lo; d <= hi; d++) {
res += dfs(i - 1, cnt1 + d, limitLow && d == lo, limitHigh && d == hi, left, right, memo);
}
if (!limitLow && !limitHigh) {
memo[i][cnt1] = res;
}
return res;
}
}
class Solution {
// 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
public:
int countPrimeSetBits(int left, int right) {
int n = bit_width((uint32_t) right);
vector memo(n, vector<int>(n + 1, -1));
// 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
auto dfs = [&](this auto&& dfs, int i, int cnt1, bool limit_low, bool limit_high) -> int {
if (i < 0) {
return ranges::contains(primes, cnt1);
}
if (!limit_low && !limit_high && memo[i][cnt1] != -1) {
return memo[i][cnt1];
}
int lo = limit_low ? left >> i & 1 : 0;
int hi = limit_high ? right >> i & 1 : 1;
int res = 0;
for (int d = lo; d <= hi; d++) {
res += dfs(i - 1, cnt1 + d, limit_low && d == lo, limit_high && d == hi);
}
if (!limit_low && !limit_high) {
memo[i][cnt1] = res;
}
return res;
};
return dfs(n - 1, 0, true, true);
}
};
// 注：也可以用哈希集合做，由于本题质数很少，用数组也可以
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
func countPrimeSetBits(left int, right int) int {
n := bits.Len(uint(right))
memo := make([][]int, n)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
// 在 dfs 的过程中，统计二进制中的 1 的个数 cnt1
var dfs func(int, int, bool, bool) int
dfs = func(i, cnt1 int, limitLow, limitHigh bool) (res int) {
if i < 0 {
if slices.Contains(primes, cnt1) {
return 1
}
return 0
}
if !limitLow && !limitHigh {
p := &memo[i][cnt1]
if *p >= 0 {
return *p
}
defer func() { *p = res }()
}
lo := 0
if limitLow {
lo = left >> i & 1
}
hi := 1
if limitHigh {
hi = right >> i & 1
}
for d := lo; d <= hi; d++ {
res += dfs(i-1, cnt1+d, limitLow && d == lo, limitHigh && d == hi)
}
return
}
return dfs(n-1, 0, true, true)
}
primes = [2, 3, 5, 7, 11, 13, 17, 19]
class Solution:
def calc(self, high: int) -> int:
# 转换成计算 < high + 1 的合法正整数个数
# 这样转换可以方便下面的代码把 high 也算进来
high += 1
res = ones = 0
for i in range(high.bit_length() - 1, -1, -1):
if high >> i & 1 == 0:
continue
# 如果这一位填 0，那么后面可以随便填
# 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for p in primes:
k = p - ones # 剩余需要填的 1 的个数
if k > i:
break
if k >= 0:
res += comb(i, k)
# 这一位填 1，继续计算
ones += 1
return res
def countPrimeSetBits(self, left: int, right: int) -> int:
return self.calc(right) - self.calc(left - 1)
MX = 20
comb = [[0] * MX for _ in range(MX)]
for i in range(MX):
comb[i][0] = 1
for j in range(1, i + 1):
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j]
primes = [2, 3, 5, 7, 11, 13, 17, 19]
class Solution:
def calc(self, high: int) -> int:
# 转换成计算 < high + 1 的合法正整数个数
# 这样转换可以方便下面的代码把 high 也算进来
high += 1
res = ones = 0
for i in range(high.bit_length() - 1, -1, -1):
if high >> i & 1 == 0:
continue
# 如果这一位填 0，那么后面可以随便填
# 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for p in primes:
k = p - ones # 剩余需要填的 1 的个数
if k > i:
break
if k >= 0:
res += comb[i][k]
# 这一位填 1，继续计算
ones += 1
return res
def countPrimeSetBits(self, left: int, right: int) -> int:
return self.calc(right) - self.calc(left - 1)
class Solution {
private static final int MX = 20;
private static final int[][] comb = new int[MX][MX];
private static final int[] primes = {2, 3, 5, 7, 11, 13, 17, 19};
private static boolean initialized = false;
// 这样写比 static block 快
public Solution() {
if (initialized) {
return;
}
initialized = true;
// 预处理组合数
for (int i = 0; i < MX; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++) {
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
}
}
public int countPrimeSetBits(int left, int right) {
return calc(right) - calc(left - 1);
}
private int calc(int high) {
// 转换成计算 < high + 1 的合法正整数个数
// 这样转换可以方便下面的代码把 high 也算进来
high++;
int res = 0;
int ones = 0;
for (int i = 31 - Integer.numberOfLeadingZeros(high); i >= 0; i--) {
if ((high >> i & 1) == 0) {
continue;
}
// 如果这一位填 0，那么后面可以随便填
// 问题变成在 pos 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for (int p : primes) {
int k = p - ones; // 剩余需要填的 1 的个数
if (k > i) {
break;
}
if (k >= 0) {
res += comb[i][k];
}
}
ones++; // 这一位填 1，继续计算
}
return res;
}
}
constexpr int MX = 20;
int comb[MX][MX];
auto init = [] {
// 预处理组合数
for (int i = 0; i < MX; i++) {
comb[i][0] = 1;
for (int j = 1; j <= i; j++) {
comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
}
}
return 0;
}();
class Solution {
static constexpr int primes[] = {2, 3, 5, 7, 11, 13, 17, 19};
int calc(int high) {
// 转换成计算 < high + 1 的合法正整数个数
// 这样转换可以方便下面的代码把 high 也算进来
high++;
int res = 0, ones = 0;
for (int i = bit_width((uint32_t) high) - 1; i >= 0; i--) {
if ((high >> i & 1) == 0) {
continue;
}
// 如果这一位填 0，那么后面可以随便填
// 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for (int p : primes) {
int k = p - ones; // 剩余需要填的 1 的个数
if (k > i) {
break;
}
if (k >= 0) {
res += comb[i][k];
}
}
ones++; // 这一位填 1，继续计算
}
return res;
}
public:
int countPrimeSetBits(int left, int right) {
return calc(right) - calc(left - 1);
}
};
const mx = 20
var comb [mx][mx]int
var primes = []int{2, 3, 5, 7, 11, 13, 17, 19}
func init() {
// 预处理组合数
for i := range comb {
comb[i][0] = 1
for j := 1; j <= i; j++ {
comb[i][j] = comb[i-1][j-1] + comb[i-1][j]
}
}
}
func calc(high int) (res int) {
// 转换成计算 < high + 1 的合法正整数个数
// 这样转换可以方便下面的代码把 high 也算进来
high++
ones := 0
for i := bits.Len(uint(high)) - 1; i >= 0; i-- {
if high>>i&1 == 0 {
continue
}
// 如果这一位填 0，那么后面可以随便填
// 问题变成在 i 个位置中填 k 个 1 的方案数，满足 ones + k 是质数
for _, p := range primes {
k := p - ones // 剩余需要填的 1 的个数
if k > i {
break
}
if k >= 0 {
res += comb[i][k]
}
}
// 这一位填 1，继续计算
ones++
}
return res
}
func countPrimeSetBits(left, right int) int {
return calc(right) - calc(left-1)
}
不计入预处理的时间和空间。
给你两个整数 left 和 right ，在闭区间 [left, right] 范围内，统计并返回 计算置位位数为质数 的整数个数。
计算置位位数 就是二进制表示中 1 的个数。
21 的二进制表示 10101 有 3 个计算置位。
示例 1：
输入：left = 6, right = 10 输出：4 解释： 6 -> 110 (2 个计算置位，2 是质数) 7 -> 111 (3 个计算置位，3 是质数) 9 -> 1001 (2 个计算置位，2 是质数) 10-> 1010 (2 个计算置位，2 是质数) 共计 4 个计算置位为质数的数字。
示例 2：
输入：left = 10, right = 15 输出：5 解释： 10 -> 1010 (2 个计算置位, 2 是质数) 11 -> 1011 (3 个计算置位, 3 是质数) 12 -> 1100 (2 个计算置位, 2 是质数) 13 -> 1101 (3 个计算置位, 3 是质数) 14 -> 1110 (3 个计算置位, 3 是质数) 15 -> 1111 (4 个计算置位, 4 不是质数) 共计 5 个计算置位为质数的数字。
提示：
1 <= left <= right <= 1060 <= right - left <= 104利用一个 int 的二进制表示不超过 $32$，我们可以先将 $32$ 以内的质数进行打表。
从前往后处理 $[left, right]$ 中的每个数 $x$，利用 lowbit 操作统计 $x$ 共有多少位 $1$，记为 $cnt$，若 $cnt$ 为质数，则对答案进行加一操作。
代码：
###Java
class Solution {
static boolean[] hash = new boolean[40];
static {
int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
for (int x : nums) hash[x] = true;
}
public int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int i = left; i <= right; i++) {
int x = i, cnt = 0;
while (x != 0 && ++cnt >= 0) x -= (x & -x);
if (hash[cnt]) ans++;
}
return ans;
}
}
枚举 $[left, right]$ 范围内的数总是不可避免，上述解法的复杂度取决于复杂度为 $O(\log{x})$ 的 lowbit 操作。
而比 lowbit 更加优秀的统计「二进制 $1$ 的数量」的做法最早在 (题解) 191. 位1的个数 讲过，采用「分治」思路对二进制进行成组统计，复杂度为 $O(\log{\log{x}})$。
代码：
###Java
class Solution {
static boolean[] hash = new boolean[40];
static {
int[] nums = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
for (int x : nums) hash[x] = true;
}
public int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int i = left; i <= right; i++) {
int x = i;
x = (x & 0x55555555) + ((x >>> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >>> 2) & 0x33333333);
x = (x & 0x0f0f0f0f) + ((x >>> 4) & 0x0f0f0f0f);
x = (x & 0x00ff00ff) + ((x >>> 8) & 0x00ff00ff);
x = (x & 0x0000ffff) + ((x >>> 16) & 0x0000ffff);
if (hash[x]) ans++;
}
return ans;
}
}
考虑加练其他「位运算」相关内容 🍭🍭🍭
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 137. 只出现一次的数字 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 190. 颠倒二进制位 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 191. 位1的个数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 231. 2 的幂 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 338. 比特位计数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 342. 4的幂 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 461. 汉明距离 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 477. 汉明距离总和 | LeetCode 题解链接 | 简单 | 🤩🤩🤩🤩 |
| 1178. 猜字谜 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 剑指 Offer 15. 二进制中1的个数 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ ("▔□▔)/
也欢迎你 关注我 和 加入我们的「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。
所有题解已经加入 刷题指南，欢迎 star 哦 ~
我们可以枚举 $[\textit{left},\textit{right}]$ 范围内的每个整数，挨个判断是否满足题目要求。
对于每个数 $x$，我们需要解决两个问题：
###Python
class Solution:
def isPrime(self, x: int) -> bool:
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
def countPrimeSetBits(self, left: int, right: int) -> int:
return sum(self.isPrime(x.bit_count()) for x in range(left, right + 1))
###C++
class Solution {
bool isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
public:
int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; ++x) {
if (isPrime(__builtin_popcount(x))) {
++ans;
}
}
return ans;
}
};
###Java
class Solution {
public int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; ++x) {
if (isPrime(Integer.bitCount(x))) {
++ans;
}
}
return ans;
}
private boolean isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
}
###C#
public class Solution {
public int CountPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; ++x) {
if (IsPrime(BitCount(x))) {
++ans;
}
}
return ans;
}
private bool IsPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
private static int BitCount(int i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
return i & 0x3f;
}
}
###go
func isPrime(x int) bool {
if x < 2 {
return false
}
for i := 2; i*i <= x; i++ {
if x%i == 0 {
return false
}
}
return true
}
func countPrimeSetBits(left, right int) (ans int) {
for x := left; x <= right; x++ {
if isPrime(bits.OnesCount(uint(x))) {
ans++
}
}
return
}
###C
bool isPrime(int x) {
if (x < 2) {
return false;
}
for (int i = 2; i * i <= x; ++i) {
if (x % i == 0) {
return false;
}
}
return true;
}
int countPrimeSetBits(int left, int right){
int ans = 0;
for (int x = left; x <= right; ++x) {
if (isPrime(__builtin_popcount(x))) {
++ans;
}
}
return ans;
}
###JavaScript
var countPrimeSetBits = function(left, right) {
let ans = 0;
for (let x = left; x <= right; ++x) {
if (isPrime(bitCount(x))) {
++ans;
}
}
return ans;
};
const isPrime = (x) => {
if (x < 2) {
return false;
}
for (let i = 2; i * i <= x; ++i) {
if (x % i === 0) {
return false;
}
}
return true;
}
const bitCount = (x) => {
return x.toString(2).split('0').join('').length;
}
复杂度分析
时间复杂度：$O((\textit{right}-\textit{left})\sqrt{\log\textit{right}})$。二进制中 $1$ 的个数为 $O(\log\textit{right})$，判断值为 $x$ 的数是否为质数的时间为 $O(\sqrt{x})$。
空间复杂度：$O(1)$。我们只需要常数的空间保存若干变量。
注意到 $\textit{right} \le 10^6 < 2^{20}$，因此二进制中 $1$ 的个数不会超过 $19$，而不超过 $19$ 的质数只有
$$
2, 3, 5, 7, 11, 13, 17, 19
$$
我们可以用一个二进制数 $\textit{mask}=665772=10100010100010101100_{2}$ 来存储这些质数，其中 $\textit{mask}$ 二进制的从低到高的第 $i$ 位为 $1$ 表示 $i$ 是质数，为 $0$ 表示 $i$ 不是质数。
设整数 $x$ 的二进制中 $1$ 的个数为 $c$，若 $\textit{mask}$ 按位与 $2^c$ 不为 $0$，则说明 $c$ 是一个质数。
###Python
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
return sum(((1 << x.bit_count()) & 665772) != 0 for x in range(left, right + 1))
###C++
class Solution {
public:
int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; ++x) {
if ((1 << __builtin_popcount(x)) & 665772) {
++ans;
}
}
return ans;
}
};
###Java
class Solution {
public int countPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; ++x) {
if (((1 << Integer.bitCount(x)) & 665772) != 0) {
++ans;
}
}
return ans;
}
}
###C#
public class Solution {
public int CountPrimeSetBits(int left, int right) {
int ans = 0;
for (int x = left; x <= right; ++x) {
if (((1 << BitCount(x)) & 665772) != 0) {
++ans;
}
}
return ans;
}
private static int BitCount(int i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = (i + (i >> 4)) & 0x0f0f0f0f;
i = i + (i >> 8);
i = i + (i >> 16);
return i & 0x3f;
}
}
###go
func countPrimeSetBits(left, right int) (ans int) {
for x := left; x <= right; x++ {
if 1<<bits.OnesCount(uint(x))&665772 != 0 {
ans++
}
}
return
}
###C
int countPrimeSetBits(int left, int right){
int ans = 0;
for (int x = left; x <= right; ++x) {
if ((1 << __builtin_popcount(x)) & 665772) {
++ans;
}
}
return ans;
}
###JavaScript
var countPrimeSetBits = function(left, right) {
let ans = 0;
for (let x = left; x <= right; ++x) {
if (((1 << bitCount(x)) & 665772) != 0) {
++ans;
}
}
return ans;
};
const bitCount = (x) => {
return x.toString(2).split('0').join('').length;
}
复杂度分析
时间复杂度：$O(\textit{right}-\textit{left})$。
空间复杂度：$O(1)$。我们只需要常数的空间保存若干变量。
L，R 最大为 $10^6$，转换为二进制，有 20 位，故 计算置位 个数不会超过 20。即求出 20 以内的质数列表即可。Integer.bitCount(i) 函数可快速求得 i 的二进制形式中 1 的个数。class Solution {
public int countPrimeSetBits(int L, int R) {
//0-20的质数列表，prime[i]为1，则i为质数
int[] primes = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1};
int res = 0;
for (int i = L; i <= R; i++) {
int t = Integer.bitCount(i);
res += primes[t];
}
return res;
}
}
特殊的二进制字符串 是具有以下两个性质的二进制序列：
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 哦 ~
