内推米哈游（原神），38岁被拒。。。

宫水三叶的刷题日记

发布于 2024-04-26 16:12:12

860

发布于 2024-04-26 16:12:12

文章被收录于专栏：宫水三叶的刷题日记宫水三叶的刷题日记

回归主线。

来一道和「米哈游」无关的算法原题。

题目描述

平台：LeetCode

题号：1781

一个字符串的美丽值定义为：出现频率最高字符与出现频率最低字符的出现次数之差。

比方说，"abaacc" 的美丽值为 3 - 1 = 2。

给你一个字符串 s ，请你返回它所有子字符串的美丽值之和。

示例 1：

输入：s = "aabcb"

输出：5

解释：美丽值不为零的字符串包括 ["aab","aabc","aabcb","abcb","bcb"] ，每一个字符串的美丽值都为 1 。

示例 2：

输入：s = "aabcbaa"

输出：17

提示：

1 <= s.length <= 500

s 只包含小写英文字母。

模拟 + 哈希表

数据范围只有

500

，我们可以通过两层循环的方式枚举所有子串，当枚举子串左端点 i 的时候，可以同步开一个大小为

C = 26

的数组来记录每个字母的出现次数，随后通过遍历该数组来得知最大和最小频次，将当前子串对应的美丽值累加到答案。

该做法复杂度为

O(n^2 \times C)

，计算量约为

500 \times 500 \times 26 = 6.5 \times 10^6

，可以过。

在确定了子串的左端点 i，枚举右端点 j 的过程中，维护最大频次是简单的，关键在于如果知晓最小频次，我们可以额外起一个哈希表 map 来记录出现频次为 x 的字符有多少个，map[x] = cnt 含义为频次为 x 的字符类型有 cnt 种。

假设当前我们处理的字符为 c，根据字符 c 原来的频次进行分情况讨论（使用 max 和 min 分别记录当前最大最小频次）：

若字符 c 为首次出现，即原频次为

，此时有最小频次 min = 1

当字符 c 为并非首次出现，假设原频次数为 x，此时频次为 x 的字符数量减一；频次为 x + 1 的字符数量加一，若频次为 x 的字符数量在减一后

map[min] \leq 0

，说明没有频次为 min 的字符了，此时最小频次为 min + 1

Java 代码：

class Solution {
    public int beautySum(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < n; i++) {
            int[] cnts = new int[26];
            Map<Integer, Integer> map = new HashMap<>();
            int min = -1, max = -1;
            for (int j = i; j < n; j++) {
                int c = s.charAt(j) - 'a';
                map.put(cnts[c], map.getOrDefault(cnts[c], 0) - 1);
                map.put(cnts[c] + 1, map.getOrDefault(cnts[c] + 1, 0) + 1);
                cnts[c]++;
                if (cnts[c] == 1) min = 1;
                else if (map.get(min) <= 0) min++;
                max = Math.max(max, cnts[c]);
                ans += max - min;
            }
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public: 
    int beautySum(string s) {
        int n = s.size(), cnts[26], ans = 0;
        unordered_map<int, int> map;
        for(int i = 0; i < n; ++i) {
            memset(cnts, 0, sizeof(cnts));
            map.clear();
            int min = -1, maxv = -1;
            for(int j = i; j < n; ++j) {
                int c = s[j] - 'a';
                map[cnts[c]]--; map[cnts[c] + 1]++;
                cnts[c]++;
                if(cnts[c] == 1) min = 1;    
                else if(map[min] <= 0) min++;
                maxv = max(maxv, cnts[c]);
                ans += maxv - min;
            }
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def beautySum(self, s: str) -> int:
        n, ans = len(s), 0
        for i in range(n):
            cnts = [0] * 26
            dmap = defaultdict(int)
            maxv, minv = -1, -1
            for j in range(i, n):
                c = ord(s[j]) - ord('a')
                dmap[cnts[c]] -= 1
                dmap[cnts[c] + 1] += 1
                cnts[c] += 1
                if cnts[c] == 1:
                    minv = 1
                elif dmap[minv] <= 0:
                    minv += 1
                maxv = max(maxv, cnts[c])
                ans += maxv - minv
        return ans

TypeScript 代码：

function beautySum(s: string): number {
    let n = s.length, ans = 0
    for (let i = 0; i < n; i++) {
        const cnts = new Array<number>(26).fill(0)
        const map = new Map()
        let min = 0, max = 0
        for (let j = i; j < n; j++) {
            const c = s.charCodeAt(j) - 'a'.charCodeAt(0)
            if (!map.has(cnts[c])) map.set(cnts[c], 0)
            map.set(cnts[c], map.get(cnts[c]) - 1)
            if (!map.has(cnts[c] + 1)) map.set(cnts[c] + 1, 0)
            map.set(cnts[c] + 1, map.get(cnts[c] + 1) + 1)
            cnts[c]++
            if (cnts[c] == 1) min = 1
            else if (map.get(min) <= 0) min++
            max = Math.max(max, cnts[c])
            ans += max - min
        }
    }
    return ans
}