前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >内推米哈游(原神),38岁被拒。。。

内推米哈游(原神),38岁被拒。。。

作者头像
宫水三叶的刷题日记
发布2024-04-26 16:12:12
830
发布2024-04-26 16:12:12
举报

回归主线。

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

题目描述

平台:LeetCode

题号:1781

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

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

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

示例 1:

代码语言:javascript
复制
输入:s = "aabcb"

输出:5

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

示例 2:

代码语言:javascript
复制
输入: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 原来的频次进行分情况讨论(使用 maxmin 分别记录当前最大最小频次):

  • 若字符 c 为首次出现,即原频次为
0

,此时有最小频次 min = 1

  • 当字符 c 为并非首次出现,假设原频次数为 x,此时频次为 x 的字符数量减一;频次为 x + 1 的字符数量加一,若频次为 x 的字符数量在减一后
map[min] \leq 0

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

Java 代码:

代码语言:javascript
复制
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++ 代码:

代码语言:javascript
复制
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 代码:

代码语言:javascript
复制
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 代码:

代码语言:javascript
复制
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
}
  • 时间复杂度:
O(n^2)
  • 空间复杂度:
O(C)

,其中

C = 26

为字符集大小

本文参与?腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2024-04-26,如有侵权请联系?cloudcommunity@tencent.com 删除

本文分享自 宫水三叶的刷题日记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述
  • 模拟 + 哈希表
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
http://www.vxiaotou.com