이진 문자열의 모든 순열을 생성하여 얻은 다양한 숫자

문제 설명

길이가 N인 이진 문자열 str이 주어졌습니다. 이 문자열의 모든 순열을 찾아서 이를 10진수 값으로 변환하고 모든 고유한 10진수 값을 반환해야 합니다.

예

들어가세요

으아아아

출력

으아아아

지침

"1"의 모든 순열은 "1"입니다. 따라서 "1"과 관련된 십진수 값은 1과 같습니다.

들어가세요

으아아아

출력

으아아아

지침

'10'의 배열은 '01'과 '10'뿐입니다. 이는 각각 1과 2에 해당합니다.

들어가세요

으아아아

출력

으아아아

지침

"101"의 가능한 모든 순열은 "110", "101", "110", "011", "101" 및 "011"입니다. 이를 십진수로 변환하면 3, 5, 6개의 고유한 십진수를 얻습니다. 숫자.

방법 1

첫 번째 방법에서는 역추적을 사용하여 이진 문자열의 모든 순열을 가져옵니다. 그 후, 이진 순열을 십진수 값으로 변환하고 이 세트를 사용하여 고유한 십진수 값을 선택합니다. pow() 메소드와 for 루프를 사용하여 10진수를 2진수로 변환합니다.

알고리즘

• 1단계 - "getDecimalPermutations()" 함수를 정의하여 결과 10진수 값을 가져옵니다.

• 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() 함수에서 10진수 변수를 0 값으로 초기화합니다.

• 4.2단계 - for 루프를 사용하여 끝부터 시작하는 이진 문자열을 반복하고 '(num[i] - '0') * pow(2, j )'를 추가하여 십진수 값으로 변환합니다.

• 4.3단계 - 십진수 값을 반환합니다.

• 5단계 - "getDecimalPermutations" 함수에 bToD() 함수에서 반환된 10진수 값을 삽입합니다.

• 6단계 - 고유한 소수 값을 포함하는 세트의 모든 값을 인쇄합니다.

예

으아아아

출력

으아아아

• 시간 복잡도 - O(n!). "getBinaryPermutations()" 함수의 시간 복잡도는 "n!"입니다. 모든 순열을 찾기 위해 역추적을 사용하기 때문입니다. bToD() 함수의 시간 복잡도는 O(n)입니다.

• 공간 복잡성 - O(n!). 각 문자열에는 목록에 저장되는 n!순열이 있습니다.

방법 2

이 방법에서는 역추적 방법 대신 C++의 next_permutation() 함수를 사용하여 이진 문자열 순열을 생성합니다. 추가적으로 2진수를 10진수로 변환하는 방법을 변경했습니다.

알고리즘

• 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단계 - 문자열의 다음 순열이 존재하면 true를 반환하므로 do-while 루프 조건에서 next_permutation() 메서드를 사용합니다.

• 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() 方法。

第二种方法的代码更清晰，但需要更多的时间和复杂性。

위 내용은 이진 문자열의 모든 순열을 생성하여 얻은 다양한 숫자의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!