資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究檢查二進位制字串中字元不等的索引對能否透過交換字元對使字串變成迴文
問題陳述
給定字串str和二進位制字串B。兩個字串的長度都等於N。我們需要檢查是否可以透過多次交換字串str中任何一對索引的字元（字串B中對應索引的字元不相等）來使字串str成為迴文。
示例
輸入
str = ‘AAS’ B = ‘101’
輸出
‘YES’
解釋
我們可以交換str[1]和str[2]，因為B[1]和B[2]不相等。最終字串可以是'ASA'。
輸入
str = ‘AASS’ B = ‘1111’
輸出
‘No’
解釋
由於字串B不包含不相等的字元，因此無法使字串成為迴文。
輸入
str = ‘AASSBV’ B = ‘111100’
輸出
‘No’
解釋
由於字元頻率不匹配，無法使字串str成為迴文。
方法一
在第一種方法中，我們將檢查是否可以使用字串str的所有字元構成任何迴文字串。如果是，我們可以檢查是否可以透過交換字串B中字元不相等的索引對的字元來使字串成為迴文。否則，我們返回false。
演算法
步驟1 - 執行utility()函式，該函式根據給定條件字串是否可以透過交換字元變成迴文來返回布林值。
步驟2 - 定義canBePalindromic()函式來檢查是否可以使用str的字元構成任何迴文字串。
步驟2.1 - 建立一個map來儲存每個字元及其在字串str中的頻率。使用for迴圈迭代字串並計算字元頻率。
步驟2.2 - 統計具有偶數和奇數頻率的字元數量。
步驟2.3 - 使用set獲取字串的唯一字元總數。
步驟2.4 - 如果字串長度為奇數且只有一個字元具有奇數頻率，則返回true。
步驟2.5 - 如果字串長度為偶數，所有字元的頻率都為偶數，且0個字元的頻率為奇數，則返回true。
步驟2.6 - 返回false。
步驟3 - 如果字串不能構成迴文，則返回false。
步驟4 - 如果字串B包含多個'1'和'0'，則返回true；否則，返回false。
示例
#include <bits/stdc++.h>
using namespace std;
// function to check if the string can be palindromic
bool canBePalindromic(string str){
//Creating the map to store the frequency of each character
map<char, int> charMap;
// store the frequency of each character of string Str
for (int i = 0; i < str.length(); i++) {
charMap[str[i]] += 1;
}
// to store the count of even and odd frequent characters
int even = 0, odd = 0;
// iterate through the map
for (auto e : charMap) {
//If frequency is odd, increment odd count; else, increment even count
if (e.second % 2 == 1) {
odd++;
} else {
even++;
}
}
// set to store unique characters of string Str
unordered_set<char> set;
//Insert all characters of string Str in set
for (int i = 0; i < str.size(); i++){
set.insert(str[i]);
}
// if the string length is odd and only one character has an odd frequency, return true
if (str.size() % 2 == 1 && even == set.size() - 1 && odd == 1){
return true;
}
// If the string length is even and all characters have even frequency, return true
if (str.size() % 2 == 0 && even == set.size() && odd == 0){
return true;
}
// else return false
return false;
}
// function to check if the string can be palindromic by swapping characters according to string B
bool utility(string S, string B){
// If string S cannot be palindromic, return false.
if (canBePalindromic(S) == false){
return false;
} else{
// if at least one '1' and '0' is present in string B, string S can be palindromic
int one = 0, zero = 0;
for (int i = 0; i < B.size(); i++) {
// If the current character is '0.'
if (B[i] == '0'){
zero++;
} else {
one++;
}
}
// return true if at least one '1' and '0' is present in the string B
if (one >= 1 && zero >= 1){
return true;
} else {
return false;
}
}
}
int main(){
string S = "NANA";
string B = "0001";
bool result = utility(S, B);
if (result)
cout << "Yes";
else
cout << "No";
return 0;
}
輸出
Yes
時間複雜度 - O(NlogN)，因為我們使用for迴圈迭代字串，並且set的insert()方法需要(logN)時間。
空間複雜度 - O(K)，其中K是唯一字元的總數。
方法二
在這種方法中，我們將使用陣列來儲存字元的頻率，而不是map。
演算法
步驟1 - 建立一個長度為26的'charFrequancy'陣列並初始化為零。
步驟2 - 統計字串B中1和0的總數。
步驟3 - 更新陣列中每個字元的頻率。
步驟4 - 如果字串長度為偶數且奇數頻率不為零，則返回false。
步驟5 - 如果字串長度為奇數且奇數頻率大於1，則返回false。
步驟6 - 如果字串中同時存在1和0，則返回true。
步驟7 - 返回false。
示例
#include <bits/stdc++.h>
using namespace std;
// function to check if the given string can be converted to a palindrome
bool utility(string str, string B){
// array to store character counts in str
int charFrequancy[26] = {0};
int ones = 0, zeros = 0, odd_fre = 0;
// count ones and zeros
for (char ch : B) {
if (ch == '1')
ones++;
if (ch == '0')
zeros++;
}
// store counts of characters
for (char ch : str){
charFrequancy[ch - 'A']++;
}
// check total character with odd frequency
for (int i = 0; i < 26; i++){
if (charFrequancy[i] % 2 == 1)
odd_fre++;
}
if (str.length() % 2 == 0 && odd_fre != 0)
return false;
if (str.length() % 2 == 1 && odd_fre > 1)
return false;
if (ones > 0 && zeros > 0)
return true;
return false;
}
int main(){
string S = "NBCNB";
string B = "01010";
if (utility(S, B)){
cout << "Yes";
} else {
cout << "No";
}
return 0;
}
輸出
Yes
時間複雜度 - O(N)，因為我們使用for迴圈迭代字串。
空間複雜度 - O(1)，因為我們始終使用長度為26的陣列。
結論
我們學習了兩種方法來檢查字串是否可以根據給定條件透過交換字元變成迴文。第一種方法使用set和map，第二種方法只使用陣列來儲存資料。第二種方法優於第一種方法，因為insert()方法需要O(logn)時間將資料插入set，而陣列需要O(1)時間。
209 次瀏覽
