資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告