问题陈述
我们给定了长度为 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 个唯一的十进制数。
方法 1
在第一种方法中，我们将使用回溯来获取二进制字符串的所有排列。之后，我们将二进制排列转换为十进制值，并使用该集合选择唯一的十进制值。我们将使用 pow() 方法和 for 循环将十进制转换为二进制。
算法
第 1 步 – 定义“getDecimalPermutations()”函数以获取结果十进制值。
第 2 步 – 执行“getBinaryPermutations()”函数以获取字符串的所有二进制排列。另外，还传递字符串、左右索引和排列向量作为参数。
步骤 2.1 – 在“getBinaryPermutations()”函数中，如果左右索引相等，则将结果字符串推送到排列列表中。
步骤 2.2 – 如果左右索引不相等，则使用 for 循环从左索引到右索引迭代字符串。
步骤 2.3 – 在 for 循环中交换第 i 个索引和左侧索引处的字符。
步骤 2.4 – 再次使用与参数相同的参数和“left + 1”索引调用“getBinaryPermutations”函数。
步骤 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 #include using namespace std;// Function to convert binary to decimalint 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 stringvoid getBinaryPermutations(string str, int left, int right, vector &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 permutations; getBinaryPermutations(str, 0, str.length() - 1, permutations); set allDecimals; for (const auto &p : permutations){ allDecimals.insert(bToD(p)); } cout 输出
All decimal numbers which we can achieve using permutations are 3 5 6
登录后复制
时间复杂度 - O(n!)。 “getBinaryPermutations()”函数的时间复杂度是“n！”，因为我们使用回溯来查找所有排列。 bToD() 函数的时间复杂度为 O(n)。
空间复杂度 - O(n!)。每个字符串都有 n!我们存储在列表中的排列。
方法2
在这种方法中，我们将使用 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 #include #include 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 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 3 5 6
登录后复制
时间复杂度 - O(n*n!)。这里，next_permutations() 需要 O(n) 时间来找到一个排列，并且我们正在找到总共 n！排列。
空间复杂度 - O(n!)，因为我们将所有排列存储在列表中。
结论
我们学习了不同的方法来获取通过给定二进制字符串的所有排列获得的唯一十进制值。在第一种方法中，我们使用了回溯；在第二种方法中，我们使用了 next_permutation() 方法。
第二种方法的代码更清晰，但需要更多的时间和复杂性。
以上就是通过生成二进制字符串的所有排列获得的不同数字的详细内容，更多请关注【创想鸟】其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。
发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583832.html
