2023-07-29：給你一個由數字組成的字符串 s，返回 s 中獨特子字符串數量。
<bdo id='mv3oc'></bdo><ul id='mv3oc'></ul>
其中的每一個數字出現的頻率都相同。
答案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完整代碼如下：
```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完整代碼如下：
```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++完整代碼如下：
```cpp
#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完整代碼如下：
```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;
}
```
