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 完整代码如下：
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++完整代码如下：
#include <iostream>#include <unordered_set>#include <vector>
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 完整代码如下：
#include <stdio.h>#include <stdbool.h>
#define BASE 1000000007#define MAX_DIGITS 10
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;}
复制代码
评论