資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
