배열된 문자 위치를 회문이 되도록 인쇄하는 C 프로그램-C++-php.cn

배열된 문자 위치를 회문이 되도록 인쇄하는 C 프로그램

PHPz

풀어 주다： 2023-09-03 11:25:13

앞으로

555명이 탐색했습니다.

배열된 문자 위치를 회문이 되도록 인쇄하는 C 프로그램

길이가 n인 문자열 str을 제공합니다. 회문을 형성할 수 있도록 문자열의 각 요소 위치를 인쇄하고, 그렇지 않으면 "회문 없음"이라는 메시지를 화면에 인쇄합니다.

회문이란 무엇인가요?

Palindrome은 MADAM, racecar와 같이 역방향 또는 역방향에서 읽은 문자 순서와 정방향에서 읽는 문자 순서가 동일한 단어입니다.

순서 또는 단어가 회문인지 확인하려면 일반적으로 단어의 반대 부분을 별도의 문자열에 저장하고 둘을 비교하여 동일하면 주어진 단어 또는 순서가 회문입니다. 하지만 이 문제에서는 회문의 단어나 시퀀스를 형성하기 위해 순열을 인쇄해야 합니다.

마찬가지로 문자열 str = "tinni"가 있으면 intni 또는 nitin이 될 수 있으므로 1부터 시작하는 인덱스로 반환해야 하며 결과의 순열 순서는 2 3 1 4 5 또는 3 2 1 5가 될 수 있습니다. 4 둘 중 하나.

위 문제에는 아래 예제와 같은 솔루션이 필요합니다. -

Example

Input: string str = &ldquo;baa&rdquo;
Output: 2 1 3
Input: string str = &ldquo;tinni&rdquo;
Output: 2 3 1 4 5

로그인 후 복사

Algorithm

void printPalindromePos(string &str)
START
STEP 1: DECLARE vector<int> pos[MAX]
STEP 2: DECLARE AND ASSIGN n WITH LENGTH OF str
STEP 3: LOOP FOR i = 0 AND i < n AND i++
   pos[str[i]].push_back(i+1)
END LOOP
STEP 4: SET oddCount = 0
STEP 5: DECLARE oddChar
STEP 6: LOOP FOR i=0 AND i<MAX AND i++
   IF pos[i].size() % 2 != 0 THEN,
      INCREMENT oddCount BY 1
      SET oddChar AS i
   END IF
END FOR
STEP 7: IF oddCount > 1 THEN,
   PRINT "NO PALINDROME"
STEP 8: LOOP FOR i=0 AND i<MAX AND i++
   DECRLARE mid = pos[i].size()/2
   LOOP FOR j=0 AND j<mid AND j++
      PRINT pos[i][j]
   END LOOP
END LOOP
STEP 9: IF oddCount > 0 THEN,
   DECLARE AND SET last = pos[oddChar].size() - 1
   PRINT pos[oddChar][last]
   SET pos[oddChar].pop_back();
END IF
STEP 10: LOOP FOR i=MAX-1 AND i>=0 AND i--
   DECLARE AND SET count = pos[i].size()
   LOOP FOR j=count/2 AND j<count AND j++
      PRINT pos[i][j]
STOP

로그인 후 복사

Example

#include <bits/stdc++.h>
using namespace std;
// Giving the maximum characters
const int MAX = 256;
void printPalindromePos(string &str){
   //Inserting all positions of characters in the given string.
   vector<int> pos[MAX];
   int n = str.length();
   for (int i = 0; i < n; i++)
      pos[str[i]].push_back(i+1);
      /* find the number of odd elements.Takes O(n) */
   int oddCount = 0;
   char oddChar;
   for (int i=0; i<MAX; i++) {
      if (pos[i].size() % 2 != 0) {
         oddCount++;
         oddChar = i;
      }
   }
   /* Palindrome can&#39;t contain more than 1 odd characters */
   if (oddCount > 1)
      cout << "NO PALINDROME";
   /* Print positions in first half of palindrome */
   for (int i=0; i<MAX; i++){
      int mid = pos[i].size()/2;
      for (int j=0; j<mid; j++)
         cout << pos[i][j] << " ";
   }
   // Consider one instance odd character
   if (oddCount > 0){
      int last = pos[oddChar].size() - 1;
      cout << pos[oddChar][last] << " ";
      pos[oddChar].pop_back();
   }
   /* Print positions in second half of palindrome */
   for (int i=MAX-1; i>=0; i--){
      int count = pos[i].size();
      for (int j=count/2; j<count; j++)
      cout << pos[i][j] << " ";
   }
}
int main(){
   string s = "tinni";
   printPalindromePos(s);
   return 0;
}

로그인 후 복사