数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 C++ 中查找具有给定权重的子字符串
在这个问题中，我们给定一个字符串 str 和一个整数 pow。我们的任务是查找具有给定权重的子字符串。
我们需要返回权重等于 pow 的子字符串。
字符串的权重是其字符权重的总和。
字符的权重：a -> 1，b -> 2，c -> 3，...
让我们举个例子来理解这个问题，
Input : string = "programming" power = 49 Output : 'pro'
说明 -
Power of matrix : pro, power(p) = 16 power(p) = 18 power(p) = 15 Total = 16 + 18 + 15 = 49
解决方案方法
解决该问题的一个简单方法是使用嵌套循环。我们将遍历字符串，并使用内部循环查找子字符串。对于每个子字符串，我们将计算其权重。然后检查它是否等于“pow”，如果是则返回 true，否则返回 false。
解决该问题的有效方法是使用 map 存储权重。我们将计算子字符串的权重并将其存储在 map 中。检查 map 中是否存在一个值可以使权重等于所需的权重。如果是，则返回true。当遍历字符串的所有字符并且没有找到匹配权重的值时，返回false。
算法
步骤 1 - 遍历字符串并找到权重 (currPow)。
步骤 2 - 检查值 (currPow - pow) 是否存在于 map 中。
步骤 2.1 - 如果存在，则打印 -> 子字符串。
步骤 3 - 将 currPow 的值插入到 map 中。
步骤 4 - 如果遍历了字符串的所有字符，则打印 -> “不可能”。
示例
程序说明解决方案的工作原理
#include <bits/stdc++.h>
using namespace std;
void findSubStringWithPower(string str, int power) {
int i;
unordered_map<int , int > powerSS;
int currPower = 0;
int N = str.length();
for (i = 0; i < N; i++) {
currPower = currPower + (str[i] - 'a' + 1);
if (currPower == power) {
cout<<"Substring : "<<str.substr((0), i+1)<<" has power "<<power;
return;
}
if (powerSS.find(currPower - power) != powerSS.end()) {
cout<<"Substring from index "<<str.substr((powerSS[currPower-power] + 1),(i - (powerSS[currPower - power] + 1)) + 1);
cout<<" has power "<<power; return;
}
powerSS[currPower] = i;
}
cout<<"No substring found!";
}
int main() {
string str = "programming";
int power = 49;
findSubStringWithPower(str, power);
return 0;
}输出
Substring : pro has power 49
更新于： 2022年1月25日
194 次查看
广告