526互联

2023-07-29：给你一个由数字组成的字符串 s，返回 s 中独特子字符串数量。 其中的每一个数字出现的频率都相同。

发布时间 2023-07-29 22:10:13作者: 福大大架构师每日一题

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(N2)，其中N是字符串s的长度。外层循环遍历字符串s的每个字符，内层循环遍历以每个字符为起始位置的子字符串。因此，总的时间复杂度可以近似为N*(N+1)/2，即O(N2)。

空间复杂度：

该算法的空间复杂度为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;
}

在这里插入图片描述