資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學用C語言程式列印字元排列成迴文串的 位置。
給定一個長度為n的字串str。列印字串中每個元素的位置，以便它可以形成一個迴文串，否則在螢幕上列印訊息“No palindrome”。
什麼是迴文串？
迴文串是一個單詞或字元序列，從反向或向後讀與從向前讀相同，例如MADAM、racecar。
要查詢一個序列或一個單詞是否是迴文串，我們通常將一個單詞的反向儲存在一個單獨的字串中，然後比較兩者，如果它們相同，則給定的單詞或序列是迴文串。但是在這個問題中，我們必須列印排列以使單詞或序列成為迴文串。
例如，有一個字串str = “tinni”，那麼它可以是intni或nitin，所以我們必須返回其中一個序列的排列作為索引，從1開始，結果可以是2 3 1 4 5或3 2 1 5 4中的一個。
上述問題需要如下所示的示例解決方案：
示例
Input: string str = “baa” Output: 2 1 3 Input: string str = “tinni” Output: 2 3 1 4 5
演算法
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
示例
#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'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;
}輸出
如果我們執行上面的程式，它將生成以下輸出：
2 3 1 4 5
更新於：2019年8月22日
168 次瀏覽
廣告