資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++ 語言
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學用 C++ 實現字串中移除最少字元後組成迴文排列
問題陳述
給定一個字串 S，我們必須找出可以移除的最小字元數，從而使字串 S 的任何排列成為迴文串
示例
如果 str = “abcdba”，則我們移除 1 個字元，即‘c’或‘d’。
演算法
1. There can be two types of a palindrome, even length, and odd length palindromes 2. We can deduce the fact that an even length palindrome must have every character occurring even number of times 3.An odd palindrome must have every character occurring even number of times except one character occurring odd number of time 4. Check the frequency of every character and those characters occurring odd number of times are then counted. Then the result is total count of odd frequency characters’ minus 1
示例
#include <bits/stdc++.h>
#define MAX 26
using namespace std;
int minCharactersRemoved(string str) {
int hash[MAX] = {0};
for (int i = 0; str[i]; ++i) {
hash[str[i] - 'a']++;
}
int cnt = 0;
for (int i = 0; i < MAX; ++i) {
if (hash[i] & 1) {
++cnt;
}
}
return (cnt == 0) ? 0 : (cnt - 1);
}
int main(){
string str = "abcdba";
cout << "Minimum characters to be removed = " <<
minCharactersRemoved(str) << endl;
return 0;
}編譯並執行上述程式時，將生成以下輸出
輸出
Minimum characters to be removed = 1
更新於：2019 年 12 月 23 日
184 次檢視
廣告