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