資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中統計每個字元最多出現 k 次的子字串
給定一個字串 str。目標是計算 str 中每個字元最多出現 k 次的子字串的數量。例如，如果輸入是“abc”且 k=1，則子字串將是“a”、“b”、“c”、“ab”、“bc”、“abc”。
讓我們透過示例來理解。
輸入 − str=”abaefgf”
輸出 − 首尾字元相同的子字串數量為 9
解釋 − 子字串將是
“a”, “b”, “a”, “e” ,”f”, “g”, “f”, “aba”, “fgf”. Total 9.
輸入 − str=”abcdef”
輸出 − 首尾字元相同的子字串數量為：6
解釋 − 子字串將是 -
“a” , “b” , “c”, “d”, “e” ,”f”. Total 6
下面程式中使用的方法如下
解決給定問題的方法可能有多種，例如樸素方法和高效方法。因此，讓我們首先看看樸素方法。我們將把每個長度的子字串傳遞給函式 check()。如果該子字串以相同的字元開頭和結尾，則遞增計數。
取字串 str。計算長度為 str.size()。
函式 check(string str) 獲取子字串 str 並檢查其首尾字元是否相同。( str[0]==str[length-1] )。如果為真，則返回 1。
函式 check_Start_End(string str, int length) 以 str 及其長度作為輸入，並返回 str 中以相同字元開頭和結尾的子字串的數量。
將初始計數設為 0。
使用兩個 for 迴圈遍歷 str。從 i=0 到 i<length，內部迴圈 j=1 到 j=length-1。
我們將使用 substr(i,j) 獲取所有長度的子字串。將每個子字串傳遞給 check()。如果它返回 1，則遞增計數。
在兩個 for 迴圈結束時，count 將包含 str 中以相同字元開頭和結尾的子字串的數量。
返回 count 作為所需結果。
示例
#include <bits/stdc++.h>
using namespace std;
int count_k(string str, int len, int k){
int count = 0;
int arr[26];
for (int i = 0; i < len; i++){
memset(arr, 0, sizeof(arr));
for (int j = i; j < len; j++){
arr[str[j] - 'a']++;
if (arr[str[j] - 'a'] <= k)
{ count++; }
else
{ break; }
}
}
return count;
}
int main(){
string str = "bbddehj";
int k = 1;
int length = str.length();
cout<<"Count of substrings with each character occurring at most k times are: "<<count_k(str,
length, k);
return 0;
}輸出
如果我們執行上述程式碼，它將生成以下輸出 -
Count of substrings with each character occurring at most k times are: 14
更新於: 2020-12-01
258 次瀏覽
廣告