2023-07-29：給你一個(gè)由數(shù)字組成的字符串 s，返回 s 中獨(dú)特子字符串?dāng)?shù)量。 其中的每一
2023-07-29：給你一個(gè)由數(shù)字組成的字符串 s，返回 s 中獨(dú)特子字符串?dāng)?shù)量。
其中的每一個(gè)數(shù)字出現(xiàn)的頻率都相同。
答案2023-07-29：
大體步驟如下：
1.初始化變量base為固定值1000000007，用于計(jì)算哈希碼。
2.創(chuàng)建一個(gè)空的哈希集合set，用于存儲(chǔ)獨(dú)特子字符串的哈希碼。
3.創(chuàng)建一個(gè)長(zhǎng)度為10的整數(shù)數(shù)組cnts，用于記錄數(shù)字出現(xiàn)的頻率。
4.循環(huán)遍歷字符串s的每個(gè)字符，使用變量l來(lái)表示當(dāng)前子字符串的起始位置。
5.在循環(huán)開(kāi)始時(shí)，將數(shù)組cnts的所有元素初始化為0。
6.初始化哈希碼hashCode為0。
7.初始化變量curVal、maxCnt、maxKinds和allKinds為0，分別表示當(dāng)前數(shù)字值、最大頻率、最大頻率的數(shù)字種類數(shù)和所有數(shù)字種類數(shù)。
8.開(kāi)始內(nèi)層循環(huán)，依次遍歷從l位置開(kāi)始的子字符串的每個(gè)字符，使用變量r表示當(dāng)前字符的索引。
9.將當(dāng)前字符轉(zhuǎn)換為整數(shù)curVal，同時(shí)計(jì)算哈希碼hashCode，基于base的乘法運(yùn)算，并加上curVal+1。
10.將cnts[curVal]加1表示當(dāng)前數(shù)字curVal的頻率增加了一次。
11.如果cnts[curVal]等于1，說(shuō)明新出現(xiàn)了一種數(shù)字，將allKinds加1，表示所有數(shù)字的種類數(shù)增加了一種。
12.如果cnts[curVal]大于maxCnt，表示當(dāng)前數(shù)字的頻率超過(guò)了之前的最大頻率，將maxCnt更新為cnts[curVal]，并將maxKinds重置為1，表示找到一種新的最大頻率數(shù)字。
13.如果cnts[curVal]等于maxCnt，表示當(dāng)前數(shù)字的頻率和最大頻率相同，將maxKinds加1，表示累計(jì)的最大頻率數(shù)字種類數(shù)增加了一種。
14.若maxKinds等于allKinds，表示當(dāng)前子字符串中每種數(shù)字都出現(xiàn)了最大頻率次數(shù)，將當(dāng)前子字符串的哈希碼hashCode添加到集合set中。
15.循環(huán)結(jié)束后，更新l的值，進(jìn)入下一個(gè)子字符串的計(jì)算。
16.返回集合set的大小，即獨(dú)特子字符串的數(shù)量。
17.在main函數(shù)中，定義字符串s為"11223"，調(diào)用equalDigitFrequency函數(shù)計(jì)算結(jié)果，并打印輸出。
時(shí)間復(fù)雜度：
該算法的時(shí)間復(fù)雜度為O(N^2)，其中N是字符串s的長(zhǎng)度。外層循環(huán)遍歷字符串s的每個(gè)字符，內(nèi)層循環(huán)遍歷以每個(gè)字符為起始位置的子字符串。因此，總的時(shí)間復(fù)雜度可以近似為N*(N+1)/2，即O(N^2)。
空間復(fù)雜度：
該算法的空間復(fù)雜度為O(1)，因?yàn)槌顺?shù)個(gè)變量之外，沒(méi)有額外使用大量的空間。集合set的空間取決于獨(dú)特子字符串的數(shù)量，但最壞情況下獨(dú)特子字符串的數(shù)量是固定的，最多只有10個(gè)數(shù)字種類。因此，可以看作是常數(shù)級(jí)的空間復(fù)雜度，即O(1)。
go完整代碼如下：
package?main
import?(
????"fmt"
????"strconv"
)
func?equalDigitFrequency(s?string)?int?{
????base?:=?int64(1000000007)
????set?:=?make(map[int64]bool)
????cnts?:=?make([]int,?10)
????for?l?:=?0;?l?<?len(s);?l++?{
????????for?i?:=?0;?i?<?10;?i++?{
????????????cnts[i]?=?0
????????}
????????hashCode?:=?int64(0)
????????curVal,?maxCnt,?maxKinds,?allKinds?:=?0,?0,?0,?0
????????for?r?:=?l;?r?<?len(s);?r++?{
????????????curVal,?_?=?strconv.Atoi(string(s[r]))
????????????hashCode?=?hashCode*base?+?int64(curVal+1)
????????????cnts[curVal]++
????????????if?cnts[curVal]?==?1?{
????????????????allKinds++
????????????}
????????????if?cnts[curVal]?>?maxCnt?{
????????????????maxCnt?=?cnts[curVal]
????????????????maxKinds?=?1
????????????}?else?if?cnts[curVal]?==?maxCnt?{
????????????????maxKinds++
????????????}
????????????if?maxKinds?==?allKinds?{
????????????????set[hashCode]?=?true
????????????}
????????}
????}
????return?len(set)
}
func?main()?{
????s?:=?"11223"
????result?:=?equalDigitFrequency(s)
????fmt.Println(result)
}
rust完整代碼如下：
use?std::collections::HashSet;
fn?equal_digit_frequency(s:?&str)?->?usize?{
????let?base:?i64?=?1_000_000_007;
????let?mut?set:?HashSet<i64>?=?HashSet::new();
????let?mut?cnts:?[i64;?10];
????let?ss?=?s.as_bytes();
????for?l?in?0..ss.len()?{
????????cnts?=?[0;?10];
????????let?mut?hash_code?=?0;
????????let?mut?cur_val;
????????let?(mut?max_cnt,?mut?max_kinds,?mut?all_kinds)?=?(0,?0,?0);
????????let?mut?r?=?l;
????????while?r?<?ss.len()?{
????????????cur_val?=?ss[r]?as?i64?-?'0'?as?i64;
????????????hash_code?=?(hash_code?as?i64).wrapping_mul(base?as?i64)?+?cur_val?+?1;
????????????cnts[cur_val?as?usize]?+=?1;
????????????if?cnts[cur_val?as?usize]?==?1?{
????????????????all_kinds?+=?1;
????????????}
????????????if?cnts[cur_val?as?usize]?>?max_cnt?{
????????????????max_cnt?=?cnts[cur_val?as?usize];
????????????????max_kinds?=?1;
????????????}?else?if?cnts[cur_val?as?usize]?==?max_cnt?{
????????????????max_kinds?+=?1;
????????????}
????????????if?max_kinds?==?all_kinds?{
????????????????set.insert(hash_code);
????????????}
????????????r?+=?1;
????????}
????}
????set.len()
}
fn?main()?{
????let?s?=?"11223";
????let?result?=?equal_digit_frequency(s);
????println!("{}",?result);
}
c++完整代碼如下：
int?equalDigitFrequency(std::string?s)?{
????const?long?long?base?=?1000000007;
????std::unordered_set<long?long>?set;
????std::vector<int>?cnts(10,?0);
????for?(int?l?=?0;?l?<?s.length();?l++)?{
????????std::fill(cnts.begin(),?cnts.end(),?0);
????????long?long?hashCode?=?0;
????????int?curVal,?maxCnt?=?0,?maxKinds?=?0,?allKinds?=?0;
????????for?(int?r?=?l;?r?<?s.length();?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;
????????????}
????????????else?if?(cnts[curVal]?==?maxCnt)?{
????????????????maxKinds++;
????????????}
????????????if?(maxKinds?==?allKinds)?{
????????????????set.insert(hashCode);
????????????}
????????}
????}
????return?set.size();
}
int?main()?{
????std::string?s?=?"11223";
????int?result?=?equalDigitFrequency(s);
????std::cout?<<?result?<<?std::endl;
????return?0;
}
c完整代碼如下：
int?equalDigitFrequency(char*?s)?{
????unsigned?long?long?set[MAX_DIGITS]?=?{?0?};
????int?cnts[MAX_DIGITS]?=?{?0?};
????int?setSize?=?0;
????for?(int?l?=?0;?s[l]?!=?'\0';?l++)?{
????????for?(int?i?=?0;?i?<?MAX_DIGITS;?i++)?{
????????????cnts[i]?=?0;
????????}
????????unsigned?long?long?hashCode?=?0;
????????int?curVal,?maxCnt?=?0,?maxKinds?=?0,?allKinds?=?0;
????????for?(int?r?=?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;
????????????}
????????????else?if?(cnts[curVal]?==?maxCnt)?{
????????????????maxKinds++;
????????????}
????????????if?(maxKinds?==?allKinds)?{
????????????????bool?exists?=?false;
????????????????for?(int?i?=?0;?i?<?setSize;?i++)?{
????????????????????if?(set[i]?==?hashCode)?{
????????????????????????exists?=?true;
????????????????????????break;
????????????????????}
????????????????}
????????????????if?(!exists)?{
????????????????????set[setSize++]?=?hashCode;
????????????????}
????????????}
????????}
????}
????return?setSize;
}
int?main()?{
????char?s[]?=?"11223";
????int?result?=?equalDigitFrequency(s);
????printf("%d\n",?result);
????return?0;
}
