数据结构
网络
关系型数据库管理系统 (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
