資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中統計具有精確 k 個不同字元的子字串數量
給定一個僅包含小寫字母的字串 str[] 和一個整數 k。目標是找到 str 的所有可能的子字串中，具有恰好 k 個不同元素的子字串的數量。
例如
輸入
str= ”pqr” k=2
輸出
Count of number of substrings with exactly k distinct characters are: 2
解釋
The substrings having exactly 2 distinct elements are: “pq”, “qr”.
輸入
str= ”stristr” k=4
輸出
Count of number of substrings with exactly k distinct characters are: 10
解釋
The substrings having exactly 2 distinct elements are: “stri”, “tris”, “rist”, “istr”, “stris”, “trist”, “ristr”, “strist”, “tristr”, “stristr”.
下面程式中使用的方案如下 −
在這種方法中，我們將使用一個數組 array[26] 來儲存字串 str 中英文字母的頻率。現在使用兩個 for 迴圈遍歷 str，如果對於子字串，每個字元只出現一次，則遞增唯一字元的數量，在該子字串的末尾，如果該數量等於 k，則根據給定條件遞增子字串的數量。
將字串 str 作為輸入。
獲取一個具有正值的整數 k。
函式 substring_k(string str, int length, int k) 獲取 str 和 k 並返回具有恰好 k 個不同字元的子字串的數量。
將初始計數設定為 0。
獲取頻率陣列 array[26]。
使用兩個 for 迴圈從 i=0 到 i<length 和 j=i 到 j<length 遍歷 str。
將 temp 作為子字串 str[i 到 j] 中唯一元素的數量。
如果 array[str[j] - 'a'] == 0，則表示此字元 str[j] 在此子字串中第一次出現。因此，遞增 temp。
現在使用 array[str[j] - 'a']++ 遞增當前字元的數量。
如果 temp 等於 k，則遞增計數。
如果 temp 大於 k，則停止進一步計算並中斷迴圈。
在所有迴圈結束時，返回計數作為結果。
示例
#include<bits/stdc++.h>
using namespace std;
int substring_k(string str, int length, int k){
int count = 0;
int array[26];
for (int i = 0; i < length; i++){
int temp = 0;
memset(array, 0, sizeof(array));
for (int j = i; j < length; j++){
if(array[str[j] − 'a'] == 0){
temp++;
}
array[str[j] − 'a']++;
if (temp == k){
count++;
}
if(temp > k){
break;
}
}
}
return count;
}
int main(){
string str = "abc";
int length = str.length();
int k = 1;
cout<<"Count of number of substrings with exactly k distinct characters are: "<<substring_k(str, length, k);
return 0;
}輸出
如果我們執行上述程式碼，它將生成以下輸出：
Count of number of substrings with exactly k distinct characters are: 3
更新於: 2021年1月5日
1K+ 次瀏覽
廣告