문자열의 문자 수가 인접한 문자 수보다 많도록 문자열을 배열합니다.

문자열 조작은 다양한 문제 해결 시나리오에서 매우 중요합니다. 주어진 문자열의 순열은 인접한 문자 수보다 더 많은 문자 수를 최적화하기 위해 발견되었습니다. 이것은 가능한 한 많은 인접한 문자 쌍을 생성하기 위해 문자열의 문자를 재배열해야 하는 흥미로운 퍼즐입니다. 왼쪽은 오른쪽의 문자보다 작습니다. p>

방법

최대 문자 수가 바로 인접한 문자 수보다 큰 문자열 순열을 해결하는 방법에는 여러 가지가 있습니다.

방법 1 − 역추적 및 가지치기 −

방법 2 - 동적 프로그래밍 -

방법 3 - 힙 알고리즘-

방법 4 - 가지치기를 통한 사전 순서 -

방법 1: 역추적 및 가지치기

• 역추적 알고리즘을 사용하여 문자열의 모든 순열을 생성합니다.

• 각 단계에서 현재 배열에 지금까지 발견된 최대값보다 더 많은 문자가 이웃 문자보다 많은지 확인하세요.

• 그렇지 않다면 불필요한 계산을 피하기 위해 가지를 일찍 잘라내고 역추적하세요.

문법

으아악

• 인접 문자보다 최대 문자 수를 더 많이 저장하세요

으아악

• 최종 배열 저장

으아악

• 인접한 문자보다 큰 문자 수를 세어보세요

으아악

• 업데이트 결과

으아악

• 다음 문자 선택

으아악

• 다음 위치로 역추적

으아악

• 선택 취소

으아악

• 역추적 프로세스 시작

으아악

• 사용된 문자 추적

으아악

알고리즘

1단계 - 빈 문자열로 max_permutation을 시작합니다.

• 보조 함수 역추적(현재_순열, 남은_문자)을 정의해야 합니다.

2단계 - 남은_문자수 문자열이 비어 있는 경우 -

• 현재 순열의 길이가 가장 큰 순열의 길이보다 긴 경우 max_permutation을 current_permutation으로 설정하세요.

• 반품.

3단계 - 반복하면서 나머지 각 문자를 반복합니다. c -

• new_permutation을 생성하려면 current_permutation에 c를 추가하세요.

• new_permutation의 길이가 1보다 크고 마지막 문자가 이전 문자보다 길지 않은 경우 이 반복을 건너뜁니다.

• remaining_characters에서 c를 가져와 새로운 new_remaining을 생성합니다.

• 반복 호출 추적(new_permutation, new_remaining).

4단계 - 입력 텍스트를 남은_문자로, 빈 문자열을 현재_순열로 사용하여 역추적 함수를 호출합니다.

5단계 - 출력 max_permutation을 제공합니다.

예 1

이 프로그램은 먼저 입력 문자열 "abcd"를 오름차순으로 정렬하여 작동합니다. 그런 다음 가능한 각 순열은 이전 문자보다 큰 문자만 고려하여 기준을 충족하지 않는 반복 순열을 방지하는 역추적 기능을 사용하여 생성됩니다. 또한 isValidPermutation 함수는 각 문자를 이전 문자와 비교하여 평가하고 이전 문자와 같거나 작은 경우 false를 반환합니다.

결과적으로 이 의도적인 프로세스는 각 문자의 최대 수가 인접한 문자보다 높은 모든 유효한 순열을 생성합니다. 개별 요구 사항에 맞게 주어진 입력 문자열, 코드 및 논리를 자유롭게 추가로 사용자 정의할 수 있습니다.

으아악

출력

으아악

방법 2: 동적 프로그래밍

• 동적 프로그래밍을 사용하여 문자열 순열을 점진적으로 생성합니다.

• 빈 접두사로 시작하여 가능한 모든 위치를 고려하고 반복적으로 문자를 추가하세요.

• 현재 접두사의 문자 수를 인접한 문자보다 크게 유지하세요.

• 개수가 지금까지 발견된 최대값 아래로 떨어진 가지를 정리합니다.

문법

으아악

• 동적 프로그래밍 루프

으아악

• 현재 문자가 인접한 문자보다 큰지 확인하세요

으아악

• 그렇다면 개수를 1

늘립니다.

으아악

• 그렇지 않으면 카운트가 똑같습니다

으아악

• dp 배열에서 최대 개수 찾기

으아악

알고리즘

1단계 - 문자열을 입력으로 받아들이고 지정된 기준을 충족하는 가장 긴 문자열의 순열을 반환하는 maxPerm(str)이라는 함수를 만듭니다.

2단계 - 먼저 길이가 n인 배열(dp라고 함)을 초기화합니다. 여기서 n은 입력 문자열 str의 길이와 같습니다. i 위치에서 끝나는 최대 순열 문자열은 각 요소 dp[i]에 저장됩니다.

3단계 - dp[0]을 문자열 str의 첫 번째 문자로 초기화합니다.

4단계 - 인덱스 1부터 n-1 -까지 str

문자를 반복합니다.

• 初始化一个空字符串curr来存储当前最大排列字符串。

• 对于索引 i 处的每个字符，将其与索引 i-1 处的前一个字符进行比较。

• 如果 str[i] 大于 str[i-1]，将 str[i] 添加到 curr 中。

• 否则，将 str[i-1] 追加到 curr 中。

• 使用 dp[i-1] 和 curr 之间的最大值更新 dp[i]。

第5步 - 循环完成后，最大排列字符串将存储在dp[n-1]中。

第 6 步 - 返回 dp[n-1] 作为结果。

Example 2

的中文翻译为：

示例2

在此示例中，输入字符串被硬编码为“abcbdb”。 findMaxPermutation 函数使用动态编程来计算每个索引处大于其相邻字符的最大字符数。然后，它通过回溯表来重建具有最大计数的字符串。生成的最大排列在 main 函数中打印。

#include <iostream>
#include <string>
#include <vector>

std::string findMaxPermutation(const std::string& str) {
   int n = str.length();
    
   // make a table to store the maximum count of characters
   // larger than their adjacent characters
   std::vector<std::vector<int>> dp(n, std::vector<int>(2, 0));

   // Initialize the table for the base case
   dp[0][0] = 0; // Count when str[0] is not included
   dp[0][1] = 1; // Count when str[0] is included
    
   // Calculate the maximum count for each index
   for (int i = 1; i < n; i++) {
      // When str[i] is not involved, the count is the maximum
      // when str[i-1] is included or not 
      dp[i][0] = std::max(dp[i-1][0], dp[i-1][1]);
        
      // When str[i] is involved, the count is the count when
      // str[i-1] is not included plus 1
      dp[i][1] = dp[i-1][0] + 1;
   }
    
   // The more count will be the largest of the last two values
   int maxCount = std::max(dp[n-1][0], dp[n-1][1]);

   // Reconstruct the string with the maximum count
   std::string maxPerm;
   int i = n - 1;
   int count = maxCount;
    
   // Start from the end and check which character to include
   while (i >= 0) {
      if ((dp[i][0] == count - 1 && dp[i][1] == count) || (dp[i][0] == count && dp[i][1] == count)) {
         maxPerm = str[i] + maxPerm;
         count--;
      }
      i--;
   }
   return maxPerm;
}
int main() {
   std::string str = "abcbdb";
   std::string maxPerm = findMaxPermutation(str);
    
   std::cout << "String: " << str << std::endl;
   std::cout << "Max Permutation: " << maxPerm << std::endl;
    
   return 0;
}

输出

String: abcbdb
Max Permutation: bbb

方法三：堆算法

• 实现Heap算法，高效地生成字符串的所有排列。

• 生成每个排列后，计算大于其相邻字符的字符数量。

• 保持追踪到目前为止找到的最大计数，并根据需要进行更新。

语法

function generatePermutations(string):
   n = length(string)
   characters = array of n elements initialized with string's characters

   generatePermutationsHelper(n, characters)

function generatePermutationsHelper(n, characters):
   if n = 1:
      checkAndPrintPermutation(characters)
   else:
   for i = 0 to n-1:
      generatePermutationsHelper(n-1, characters)
            
   if n is even:
      swap characters[i] and characters[n-1]
   else:
      swap characters [0] and characters[n-1]

算法

第一步 - 已经初始化了一个数组，用于存储输入字符串的字符。

第 2 步 - 继续创建一个函数，并将其命名为“generatePermutations”，带有两个参数 - 一个最终变量“size”，用于确定数组的大小，以及一个名为“arr”的数组，其中包含字符串字符。

步骤 3 - 如果大小为 1，则通过将数组中的字符组合在一起，直到最大字符数超过连续字符数，打印当前排列。

步骤 4 - 如果不是，则函数返回。为了从索引 0 到 'size - 1' 迭代数组，我们使用一个名为 'i' 的变量。

第 5 步 - 在此迭代中，我们进一步迭代参数大小 - 1 和错误的generatePermutations 函数。

第 6 步 - 如果 size 恰好是奇数，则我们将数组中索引 0 处的元素替换为索引“size - 1”处的元素。

第 7 步 - 类似地，如果 size 结果是偶数，我们将数组中索引“i”处的元素替换为索引“size - 1”。

步骤8 - 最后，我们使用初始数组大小和数组本身作为参数调用"generatePermutations"函数。

示例 1

以下的C++示例使用Heap's算法创建字符串的排列，并识别出在其相邻字符上具有最大字符数的排列 −

为了说明问题，在这个例子中使用"abcd"作为输入字符串。可以修改变量来使用不同的输入字符串。如果排列满足具有比其邻居更多字符的要求，则找到isValidPermutation函数是否有效。generatePermutations函数使用堆栈方法来跟踪具有最多字符的排列，以便它可以生成输入字符串的每个可能的排列。主函数将最大数量和排列本身作为输出打印。

#include <iostream>
#include <algorithm>
using namespace std;

// Function to check if the permutation satisfies the condition
bool isValidPermutation(const string& perm) {
   int n = perm.length();
   for (int i = 0; i < n - 1; i++) {
      if (abs(perm[i] - perm[i + 1]) <= 1)
         return false;
   }
   return true;
}

// Function to swap two characters in a string
void swapChar(char& a, char& b) {
   char temp = a;
   a = b;
   b = temp;
}

// Heap's Algorithm for generating permutations
void generatePermutations(string& str, int n, int& maxCount, string& maxPerm, int idx = 0) {
   if (idx == n - 1) {
      if (isValidPermutation(str)) {
         int count = count_if(str.begin(), str.end(), [](char c) {
            return isalpha(c) && c >= 'A' && c <= 'Z';
         });
         if (count > maxCount) {
            maxCount = count;
            maxPerm = str;
         }
      }
      return;
   }

   for (int i = idx; i < n; i++) {
      swapChar(str[idx], str[i]);
      generatePermutations(str, n, maxCount, maxPerm, idx + 1);
      swapChar(str[idx], str[i]);
   }
}

int main() {
   string str = "abcd";
   int n = str.length();
   int maxCount = 0;
   string maxPerm;

   generatePermutations(str, n, maxCount, maxPerm);

   if (maxCount == 0) {
      cout << "No valid permutation found." << endl;
   } else {
      cout << "Maximum number of characters greater than adjacent characters: " << maxCount << endl;
      cout << "Permutation with the maximum count: " << maxPerm << endl;
   }
   return 0;
}

输出

No valid permutation found.

方法4：字典序排序与剪枝

• 按字典顺序对字符串的字符进行排序。

• 生成排序字符串的排列。

• 在每一步中，检查当前排列是否满足最大字符数大于其相邻字符的条件。

• 如果不是这样，请跳过具有相似前缀的剩余排列，以避免不必要的计算。

语法

• 生成字符串所有排列的函数

function generatePermutations(string):

• TODO：排列生成的实现

• 检查字符是否大于其相邻字符的函数

function isGreaterAdjacent(char1, char2):

• TODO：比较逻辑的实现

• 找到具有大于相邻字符的最大数量的排列的函数

function findMaxAdjacentPermutation(string):

• 生成字符串的所有排列

permutations = generatePermutations(string)

• 初始化变量

max_permutation = ""
max_count = 0

• 遍历每个排列

for permutation in permutations:
   count = 0

• 迭代排列中的每个字符（不包括最后一个字符）

for i from 0 to length(permutation) - 2:
   char1 = permutation[i]
   char2 = permutation[i + 1]

• 检查当前字符是否大于其相邻字符

if isGreaterAdjacent(char1, char2):
   count = count + 1

• 检查当前排列的计数是否大于先前的最大值

if count > max_count:
   max_permutation = permutation
   max_count = count

• 返回具有最大计数的排列

return max_permutation

算法

第一步 - 从输入字符串开始。

第 2 步 - 按字典顺序对字符串进行排序以获得初始排列。

第 3 步 - 将变量 maxCount 初始化为 0，以跟踪大于相邻字符的最大字符数。

第 4 步 - 初始化变量 maxPermutation 以存储最大计数的排列。

第 5 步 - 当有下一个排列时 -

• 将变量 count 初始化为 0，以跟踪当前大于相邻字符的字符数。

• 对于当前排列中的每个字符 -

  • 检查当前字符是否大于其前一个字符和后一个字符（如果存在）。

  • 如果满足条件，则将计数增加 1。

• 如果计数大于最大计数（maxCount）-

  • 将maxCount更新为当前计数。

  • 将 maxPermutation 更新为当前排列。

步骤 6 - 将 maxPermutation 作为结果返回。

示例 1

对于此示例，为简单起见，让我们考虑固定字符串“abcde”。

在这个例子中，countAdjacentGreater函数统计字符串中相邻字符大于其前一个字符的数量。findMaxPermutation函数生成输入字符串的所有排列，并检查每个排列，找出具有最大数量相邻字符大于的那个。

主要函数初始化输入字符串"abcde"和跟踪最大计数和最大排列的变量。它调用findMaxPermutation函数来找到最大排列。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int countAdjacentGreater(const string& str) {
   int count = 0;
   for (int i = 0; i < str.length() - 1; i++) {
      if (str[i] < str[i + 1]) {
         count++;
      }
   }
   return count;
}

void findMaxPermutation(string& str, int& maxCount, string& maxPerm) {
   sort(str.begin(), str.end());
    
   do {
      int count = countAdjacentGreater(str);
      if (count > maxCount) {
         maxCount = count;
         maxPerm = str;
      }
   } while (next_permutation(str.begin(), str.end()));
}

int main() {
   string str = "abcde";
   int maxCount = 0;
   string maxPerm;

   findMaxPermutation(str, maxCount, maxPerm);

   cout << "String with the maximum number of characters greater than its adjacent characters: " << maxPerm << endl;
   cout << "Count of adjacent characters greater in the maximum permutation: " << maxCount << endl;

   return 0;
}

输出

String with the maximum number of characters greater than its adjacent characters: abcde
Count of adjacent characters greater in the maximum permutation: 4

结论

总之，找到最大字符数大于相邻字符的字符串的排列问题是字符串操作中的一个有趣的挑战。通过分析给定的字符串并有策略地重新排列其字符，可以实现所需的排列。这个问题凸显了在使用字符串和排列时仔细检查和创造性思维的重要性。

위 내용은 문자열의 문자 수가 인접한 문자 수보다 많도록 문자열을 배열합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!