資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究給定字串的最大權重轉換（C++）
問題陳述
給定一個僅由 A 和 B 組成的字串。我們可以透過切換任何字元將給定字串轉換為另一個字串。因此，給定字串的許多轉換都是可能的。任務是找到最大權重轉換的權重。
字串的權重使用以下公式計算：
Weight of string = Weight of total pairs + weight of single characters - Total number of toggles.
只有當兩個連續字元不同時，才將它們視為一對。
單個對（兩個字元都不同）的權重 = 4
單個字元的權重 = 1
如果輸入字串為 - "AA"，則輸出將為 3 -
給定字串的轉換是 "AA"、"AB"、"BA" 和 "BB"。
最大權重轉換是 "AB" 或 "BA"。權重為“一對 - 一次切換”= 4-1 = 3。
演算法
1. If (n == 1) maxWeight(str[0..n-1]) = 1 2. Else If str[0] != str[1] maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 4 + getMaxRec(str[2..n-1]) 3. Elses maxWeight(str[0..n-1]) = Max (1 + maxWeight(str[1..n-1]), 3 + getMaxRec(str[2..n-1])
示例
#include<bits/stdc++.h>
using namespace std;
int getMaxRec(string &str, int i, int n, int lookup[]){
if (i >= n) {
return 0;
}
if (lookup[i] != -1) {
return lookup[i];
}
int ans = 1 + getMaxRec(str, i + 1, n, lookup);
if (i + 1 < n) {
if (str[i] != str[i+1]) {
ans = max(4 + getMaxRec(str, i + 2, n, lookup), ans);
} else {
ans = max(3 + getMaxRec(str, i + 2, n, lookup), ans);
}
}
return lookup[i] = ans;
}
int getMaxWeight(string str){
int n = str.length();
int lookup[n];
memset(lookup, -1, sizeof lookup);
return getMaxRec(str, 0, str.length(), lookup);
}
int main(){
string str = "AA";
cout << "Result = " << getMaxWeight(str) << endl;
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出：
Result = 3
更新於： 2020年2月10日
369 次檢視
廣告