資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中最大偶長迴文排列子串
問題陳述
給定一個字串，任務是找到可以排列成迴文的最長子串。
示例
如果輸入字串 = “5432112356”，則答案為 6，因為最長的迴文子串是 “321123”，其長度為 6
演算法
- 如果子串的長度是奇數，則它不能被考慮在最終解中。
- 如果子串的長度是偶數，則只有當子串中每個字元出現的次數都是偶數時，它才可能是解，這可以使用字典計數來完成。我們檢查每個字元是否出現偶數次。如果是，則將其包含為可能的解之一。然後，我們透過在字串中包含下一個字元來形成下一個子串，這可以透過簡單地遞增結束位置來完成，並遞迴檢查是否可以形成滿足給定條件且長度更大的子串，並返回所有可能解的最大值。
示例
#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> countt;
bool isPalindromePossible(unordered_map<int, int> &countt) {
for (auto key : countt) {
if (key.second & 1) {
return false;
}
return true;
}
int getMaxPalindrome(string str, unordered_map<int, int> &countt, int start, int end) {
if (end == str.length()) {
if ((end - start) % 2 == 0)
if (isPalindromePossible(countt))
return end - start;
return 0;
} else {
if ((end - start) % 2 == 0) {
if (isPalindromePossible(countt)) {
countt[str[end]]++;
return max(end - start, getMaxPalindrome(str, countt, start, end + 1));
} else {
countt[str[end]]++;
return getMaxPalindrome(str, countt, start, end + 1);
}
} else {
countt[str[end]]++;
unordered_map<int, int>
c(countt.begin(), countt.end());
int length = getMaxPalindrome(str, c, start, end + 1);
countt[str[end]]--;
countt[str[start]]--;
return max(length, getMaxPalindrome(str, countt, start + 1, end));
}
}
}
int main(int argc, char const *argv[]) {
string str = "5432112356";
int start = 0, end = 0;
cout << "Maximum palindrome length = " << getMaxPalindrome(str, countt, start, end) << endl;
return 0;
}輸出
編譯並執行上述程式後，將生成以下輸出：
Maximum palindrome length = 6
更新於：2020年1月10日
109 次瀏覽
廣告