資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學生成二進位制字串所有排列組合後獲得的不同數字
問題陳述
給定長度為 N 的二進位制字串 str。我們需要找到字串的所有排列組合，將它們轉換為十進位制值，並返回所有唯一的十進位制值。
示例
輸入
str = ‘1’
輸出
[1]
解釋
‘1’的所有排列組合只有‘1’。因此，與‘1’相關的十進位制值為1。
輸入
str = ‘10’
輸出
[1, 2]
解釋
‘10’的排列組合只有‘01’和‘10’，分別相當於1和2。
輸入
‘101’
輸出
[3, 5, 6]
解釋
‘101’的所有可能的排列組合是‘110’，‘101’，‘110’，‘011’，‘101’和‘011’，如果我們將它們轉換為十進位制數，我們將得到3、5和6這三個唯一的十進位制數。
方法一
在第一種方法中，我們將使用回溯法來獲得二進位制字串的所有排列組合。之後，我們將二進位制排列組合轉換為十進位制值，並使用集合來選擇唯一的十進位制值。我們將使用pow()方法和for迴圈將十進位制轉換為二進位制。
演算法
步驟1 − 定義`getDecimalPermutations()`函式以獲取結果十進位制值。
步驟2 − 執行`getBinaryPermutations()`函式以獲取字串的所有二進位制排列組合。同時，將字串、左索引、右索引和排列向量作為引數傳遞。
步驟2.1 − 在`getBinaryPermutations()`函式中，如果左索引和右索引相等，則將結果字串推入排列列表。
步驟2.2 − 如果左索引和右索引不相等，則使用for迴圈迭代字串從左索引到右索引。
步驟2.3 − 在for迴圈中交換第i個字元和左索引處的字元。
步驟2.4 − 再次呼叫`getBinaryPermutations`函式，並將相同的引數和`left + 1`索引作為引數。
步驟2.5 − 為回溯目的交換第i個索引和左索引處的字元。
步驟3 − 建立一個名為`allDecimals`的集合。之後，迭代二進位制字串的所有排列組合。
步驟4 − 呼叫bToD()函式將二進位制轉換為十進位制。
步驟4.1 − 在bToD()函式中，將十進位制變數初始化為0值。
步驟4.2 − 使用for迴圈從末尾迭代二進位制字串，並將`(num[i] - '0') * pow(2, j)`新增到十進位制值。
步驟4.3 − 返回十進位制值。
步驟5 − 在`getDecimalPermutations`函式中，插入bToD()函式返回的十進位制值。
步驟6 − 列印集合的所有值，這些值將包含唯一的十進位制值。
示例
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Function to convert binary to decimal
int bToD(string num){
int decimal = 0;
for (int i = num.size() - 1, j = 0; i >= 0; i--, j++){
decimal += (num[i] - '0') * pow(2, j);
}
return decimal;
}
// Function to get all permutations of a binary string
void getBinaryPermutations(string str, int left, int right, vector<string> &permutations){
// Base case
if (left == right){
// push_back() function is used to push elements into a vector from the back
permutations.push_back(str);
} else {
// Permutations made
for (int i = left; i <= right; i++){
// Swapping done
swap(str[left], str[i]);
// Recursion called for next index (left + 1)
getBinaryPermutations(str, left + 1, right, permutations);
// Backtrack
swap(str[left], str[i]);
}
}
}
void getDecimalPermutations(string str){
vector<string> permutations;
getBinaryPermutations(str, 0, str.length() - 1, permutations);
set<int> allDecimals;
for (const auto &p : permutations){
allDecimals.insert(bToD(p));
}
cout << "All decimal numbers which we can achieve using permutations are " << endl;
for (const auto &d : allDecimals){
cout << d << " ";
}
}
int main(){
string bString = "101";
getDecimalPermutations(bString);
return 0;
}
輸出
All decimal numbers which we can achieve using permutations are 3 5 6
時間複雜度 − O(n!)。`getBinaryPermutations()`函式的時間複雜度為`n!`，因為我們使用回溯法來查詢所有排列組合。bToD()函式的時間複雜度為O(n)。
空間複雜度 − O(n!)。每個字串都有n!個排列組合，我們將其儲存在列表中。
方法二
在這種方法中，我們將使用C++的`next_permutation()`函式來生成二進位制字串的排列組合，而不是回溯法。我們還改變了將二進位制轉換為十進位制的方法。
演算法
步驟1 − 定義`allNumbers`集合。
步驟2 − 使用`sort()`方法對二進位制字串進行排序。
步驟3 − 使用do-while迴圈迭代字串的每個排列組合。
步驟4 − 在do-while迴圈中，透過傳遞字串作為引數來呼叫bToD()函式，以將二進位制轉換為十進位制數。
步驟4.1 − 在bToD()函式中，定義`currentBase`變數並將其初始化為1。
步驟4.2 − 使用for迴圈，從最後一個索引迭代字串。
步驟4.3 − 在for迴圈中，如果當前字元等於‘1’，我們需要將`currentBase`值新增到`decimal_number`。
步驟4.4 − 將`currentBase`乘以2。
步驟5 − 將十進位制數插入`allNumber`集合。
步驟6 − 在do-while迴圈的條件中使用`next_permutation()`方法，因為它在字串的下一個排列組合存在時返回true。
步驟7 − 列印新增到`allNumbers`中的所有數字，以獲取與給定二進位制字串的所有排列組合相關的唯一十進位制數。
示例
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
int bToD(string num){
int decimal_number = 0;
// Initializing base value to 1, and it increases by power of 2 in each iteration
int currentBase = 1;
for (int i = num.length() - 1; i >= 0; i--){
if (num[i] == '1'){
decimal_number += currentBase;
}
currentBase = currentBase * 2;
}
return decimal_number;
}
void getDecimalPermutations(string str){
// create set
set<int> allNumbers;
// sort the string
sort(str.begin(), str.end());
do {
// convert binary string to decimal
int result = bToD(str);
// insert the decimal number to set
allNumbers.insert(result);
// get the next permutation
} while (next_permutation(str.begin(), str.end()));
//Print all distinct decimal numbers
cout << "All decimal numbers which we can achieve using permutations are " << endl;
for (auto num : allNumbers)
cout << num << " ";
cout << endl;
}
int main(){
string bString = "101";
getDecimalPermutations(bString);
return 0;
}
輸出
All decimal numbers which we can achieve using permutations are 3 5 6
時間複雜度 − O(n*n!)。在這裡，`next_permutations()`需要O(n)時間來查詢一個排列組合，而我們正在查詢總共n!個排列組合。
空間複雜度 − O(n!)，因為我們將所有排列組合儲存在列表中。
結論
我們學習了不同的方法來獲得透過給定二進位制字串的所有排列組合獲得的唯一十進位制值。在第一種方法中，我們使用了回溯法；在第二種方法中，我們使用了`next_permutation()`方法。
第二種方法的程式碼更清晰，但它需要更多的時間和複雜度。
瀏覽量：322
