2023-07-29：给你一个由数字组成的字符串 s，返回 s 中独特子字符串数量。
其中的每一个数字出现的频率都相同。
答案2023-07-29：
大体步骤如下：
1.初始化变量base为固定值1000000007，用于计算哈希码。
2.创建一个空的哈希集合set，用于存储独特子字符串的哈希码。
3.创建一个长度为10的整数数组cnts，用于记录数字出现的频率。
4.循环遍历字符串s的每个字符，使用变量l来表示当前子字符串的起始位置。
5.在循环开始时，将数组cnts的所有元素初始化为0。
6.初始化哈希码hashCode为0。
7.初始化变量curVal、maxCnt、maxKinds和allKinds为0，分别表示当前数字值、最大频率、最大频率的数字种类数和所有数字种类数。
8.开始内层循环，依次遍历从l位置开始的子字符串的每个字符，使用变量r表示当前字符的索引。
9.将当前字符转换为整数curVal，同时计算哈希码hashCode，基于base的乘法运算，并加上curVal+1。
10.将cnts[curVal]加1表示当前数字curVal的频率增加了一次。
11.如果cnts[curVal]等于1，说明新出现了一种数字，将allKinds加1，表示所有数字的种类数增加了一种。
12.如果cnts[curVal]大于maxCnt，表示当前数字的频率超过了之前的最大频率，将maxCnt更新为cnts[curVal]，并将maxKinds重置为1，表示找到一种新的最大频率数字。
13.如果cnts[curVal]等于maxCnt，表示当前数字的频率和最大频率相同，将maxKinds加1，表示累计的最大频率数字种类数增加了一种。
14.若maxKinds等于allKinds，表示当前子字符串中每种数字都出现了最大频率次数，将当前子字符串的哈希码hashCode添加到集合set中。
15.循环结束后，更新l的值，进入下一个子字符串的计算。
16.返回集合set的大小，即独特子字符串的数量。
17.在main函数中，定义字符串s为"11223"，调用equalDigitFrequency函数计算结果，并打印输出。
时间复杂度：
该算法的时间复杂度为O(N^2)，其中N是字符串s的长度。外层循环遍历字符串s的每个字符，内层循环遍历以每个字符为起始位置的子字符串。因此，总的时间复杂度可以近似为N*(N+1)/2，即O(N^2)。
空间复杂度：
该算法的空间复杂度为O(1)，因为除了常数个变量之外，没有额外使用大量的空间。集合set的空间取决于独特子字符串的数量，但最坏情况下独特子字符串的数量是固定的，最多只有10个数字种类。因此，可以看作是常数级的空间复杂度，即O(1)。
go完整代码如下：
packagemain
import(
"fmt"
"strconv"
)
funcequalDigitFrequency(sstring)int{
base:=int64(1000000007)
set:=make(map[int64]bool)
cnts:=make([]int,10)
forl:=0;lfori:=0;i<10;i++{
cnts[i]=0
}
hashCode:=int64(0)
curVal,maxCnt,maxKinds,allKinds:=0,0,0,0
forr:=l;rcurVal,_=strconv.Atoi(string(s[r]))
hashCode=hashCode*base+int64(curVal+1)
cnts[curVal]++
ifcnts[curVal]==1{
allKinds++
}
ifcnts[curVal]>maxCnt{
maxCnt=cnts[curVal]
maxKinds=1
}elseifcnts[curVal]==maxCnt{
maxKinds++
}
ifmaxKinds==allKinds{
set[hashCode]=true
}
}
}
returnlen(set)
}
funcmain(){
s:="11223"
result:=equalDigitFrequency(s)
fmt.Println(result)
}
rust完整代码如下：
usestd::collections::HashSet;
fnequal_digit_frequency(s:&str)->usize{
letbase:i64=1_000_000_007;
letmutset:HashSet=HashSet::new();
letmutcnts:[i64;10];
letss=s.as_bytes();
forlin0..ss.len(){
cnts=[0;10];
letmuthash_code=0;
letmutcur_val;
let(mutmax_cnt,mutmax_kinds,mutall_kinds)=(0,0,0);
letmutr=l;
whilercur_val=ss[r]asi64-'0'asi64;
hash_code=(hash_codeasi64).wrapping_mul(baseasi64)+cur_val+1;
cnts[cur_valasusize]+=1;
ifcnts[cur_valasusize]==1{
all_kinds+=1;
}
ifcnts[cur_valasusize]>max_cnt{
max_cnt=cnts[cur_valasusize];
max_kinds=1;
}elseifcnts[cur_valasusize]==max_cnt{
max_kinds+=1;
}
ifmax_kinds==all_kinds{
set.insert(hash_code);
}
r+=1;
}
}
set.len()
}
fnmain(){
lets="11223";
letresult=equal_digit_frequency(s);
println!("{}",result);
}
c++完整代码如下：
#include
#include
#include
intequalDigitFrequency(std::strings){
constlonglongbase=1000000007;
std::unordered_setset;
std::vectorcnts(10,0);
for(intl=0;lstd::fill(cnts.begin(),cnts.end(),0);
longlonghashCode=0;
intcurVal,maxCnt=0,maxKinds=0,allKinds=0;
for(intr=l;rcurVal=s[r]-'0';
hashCode=hashCode*base+curVal+1;
cnts[curVal]++;
if(cnts[curVal]==1){
allKinds++;
}
if(cnts[curVal]>maxCnt){
maxCnt=cnts[curVal];
maxKinds=1;
}
elseif(cnts[curVal]==maxCnt){
maxKinds++;
}
if(maxKinds==allKinds){
set.insert(hashCode);
}
}
}
returnset.size();
}
intmain(){
std::strings="11223";
intresult=equalDigitFrequency(s);
std::cout<
return0;
}
c完整代码如下：
#include
#include
#defineBASE1000000007
#defineMAX_DIGITS10
intequalDigitFrequency(char*s){
unsignedlonglongset[MAX_DIGITS]={0};
intcnts[MAX_DIGITS]={0};
intsetSize=0;
for(intl=0;s[l]!='\0';l++){
for(inti=0;icnts[i]=0;
}
unsignedlonglonghashCode=0;
intcurVal,maxCnt=0,maxKinds=0,allKinds=0;
for(intr=l;s[r]!='\0';r++){
curVal=s[r]-'0';
hashCode=hashCode*BASE+curVal+1;
cnts[curVal]++;
if(cnts[curVal]==1){
allKinds++;
}
if(cnts[curVal]>maxCnt){
maxCnt=cnts[curVal];
maxKinds=1;
}
elseif(cnts[curVal]==maxCnt){
maxKinds++;
}
if(maxKinds==allKinds){
boolexists=false;
for(inti=0;iif(set[i]==hashCode){
exists=true;
break;
}
}
if(!exists){
set[setSize++]=hashCode;
}
}
}
}
returnsetSize;
}
intmain(){
chars[]="11223";
intresult=equalDigitFrequency(s);
printf("%d\n",result);
return0;
}
热门跟贴