数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告