数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究打印范围为 1 到 n 内具有交替模式位的数字
交替位模式意味着在数字中交替位置放置 0 和 1，即没有两个 0 或 1 放在一起。例如，10 的二进制表示形式为 (1010)2，它具有交替位模式，因为 0 和 1 相互隔开。
问题陈述
给定一个整数 N。找到 1 到 N 范围内所有位模式交替的整数。
示例 1
Input: 10
Output: 1, 2, 5, 10
解释
$\mathrm{(1)_{10} = (1)_2, (2)_{10} = (10)_2, (5)_{10} = (101)_2, (10)_{10} = (1010)_2}$
示例 2
Input: 31
Output: 1, 2, 5, 10, 21
解释
$\mathrm{(1)_{10} = (1)_2, (2)_{10} = (10)_2, (5)_{10} = (101)_2, (10)_{10} = (1010)_2, (21)_{10} = (10101)_2}$
方法 1：检查交替模式
解决此问题的朴素方法是检查 1 到 n 范围内的每个数字，查看其位模式是否交替。
这可以通过以下方式完成：
为了检查一个数字是否具有交替位模式，我们可以使用 AND 操作的真值表来检查连续位是否不同。
伪代码 -
procedure checkAltPattern (num)
temp = num
count = 0
while (temp)
count = count +1
num = num >> 1
end while
for i = 0 to count - 2
iTh = num >> i
i2Th = num >> (i + 2)
if ((iTh & 1) != (i2Th & 1))
ans = FALSE
end if
end for
ans = TRUE
end procedure
procedure numbers (num)
ans []
for i = 1 to num
if checkAltPattern = TRUE
ans.add(i)
end if
end for
end procedure
示例
在以下程序中，我们检查 1 到 N 范围内的每个数字，查看它们是否具有交替位模式，方法是检查在每个交替位置是否存在相同的位。
#include <bits/stdc++.h>
using namespace std;
// Function to check if the number has alternate pattern
bool checkAltPattern(int num){
int temp = num, count = 0;
// Counting total bits of the number by using the right shift operator
while (temp) {
count++;
// Right shift of a number shift all the bits one position right
temp >>= 1;
}
// For every alternate position checking if bits are same
for (int i = 0; i < (count - 1); i++) {
int iTh = num >> i, i2Th = num >> (i + 2);
// iTh & 1 gives the bit at ith position
// i2Th &N1 gives the bit at (i+2)th position
// If both bits are not same then bits pattern is not alternate
if ((iTh & 1) != (i2Th & 1)) {
return false;
}
}
return true;
}
vector<int> numbers(int num){
// Initializing an array to add numbers with alternate bit pattern
vector<int> ans;
for (int i = 1; i <= num; i++){
if (checkAltPattern(i)){
ans.push_back(i);
}
}
return ans;
}
int main(){
int N = 50;
cout << "Numbers in range 1 to " << N << " having alternate bit pattern : ";
vector<int> res = numbers(N);
for (int i = 0; i < res.size(); i++){
cout << res[i] << " ";
}
return 0;
}
输出
Numbers in range 1 to 50 having alternate bit pattern : 1 2 5 10 21 42
时间复杂度 - O(nlogn)，因为对于每个数字，我们都会检查交替模式，这需要 O(logn) 时间，因为 logn 是表示该数字的位数。因此，总时间为 O(logn + logn + … n 次) = O(nlogn)
空间复杂度 - O(1)，因为没有使用额外的空间。
方法 2：从 1 生成数字
解决此问题的优化且更好的方法是从第一个具有交替模式的数字开始，然后连续交替地添加 0 和 1。
要向右侧添加 0，请使用左移运算符。
要向右侧添加 1，请先进行左移，然后使用 XOR 运算符添加 1。
伪代码 -
procedure addZero (pass)
pass = pass << 1
ans = pass
end procedure
procedure addOne (pass)
pass = pass << 1
pass = pass ^ 1
ans = pass
end procedure
procedure numbers (N)
ans []
int num = 1
ans.add (num)
while (1)
num = addZero (num)
if (num > N)
break
else
ans.add (num)
end if
num = addOne (num)
if (num > N)
break
else
ans.add (num)
end if
end while
end procedure
示例
在以下程序中，addZero() 函数在 LSB 位置添加 0，addOne() 函数在 LSB 位置添加 1。
#include <bits/stdc++.h>
using namespace std;
int addZero(int pass){
// Left shift puts 0 at LSB position
pass = pass << 1;
return pass;
}
int addOne(int pass){
// Left shift puts 0 at LSB position
pass = pass << 1;
// XOR with 1 sets the LSB position
pass = pass ^ 1;
return pass;
}
vector<int> numbers(int N){
// Initializing an array to add numbers with alternate bit pattern
vector<int> ans;
// First number with alternate bit pattern is 1
int num = 1;
ans.push_back(num);
while (1) {
num = addZero(num);
// If on adding 0, num is greater than N then leave loop
if (num > N) {
break;
}
else{
ans.push_back(num);
}
num = addOne(num);
// If on adding 1, num is greater than N then leave loop
if (num > N){
break;
}
else{
ans.push_back(num);
}
}
return ans;
}
int main(){
int N = 50;
cout << "Numbers in range 1 to " << N << " having alternate bit pattern : ";
vector<int> res = numbers(N);
for (int i = 0; i < res.size(); i++){
cout << res[i] << " ";
}
return 0;
}
输出
Numbers in range 1 to 50 having alternate bit pattern : 1 2 5 10 21 42
时间复杂度 - O(logn)
空间复杂度 - O(1)
结论
总之，为了找到具有交替位模式的数字，优化的方案是从 1 开始生成数字本身，通过左移然后设置和取消设置 LSB 位置。这种方法是最优化和最优的。
91 次查看
