Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique

Leetcode 1647. Minimum Deletions to Make Character Frequencies Unique

作者头像
Tyan
发布于 2021-08-20 04:13:13
发布于 2021-08-20 04:13:13
25900
代码可运行
举报
文章被收录于专栏:SnailTyanSnailTyan
运行总次数:0
代码可运行

1. Description

2. Solution

**解析:**Version 1,先用字典统计每个英文字符出现的频率,然后对频率进行由大到小排序,由大到小排列是因为频率最高的是可以出现的最大次数,使用count表示删除的字符数量,使用pre来表示为了不重复,当前字符删除一部分后的出现次数,初始值为pre = frequencies[0],比较当前频率与前一个字符频率的大小,如果二者相等,为了不重复,当前频率要减1,即删除一个字符,因此count+=1,同时当前字符的频率减1,如果当前字符频率小于前一个字符的频率,则不需要删除字符,字符频率pre进行更新,如果当前字符频率大于前一个字符的频率,为了不重复,则当前字符要删除frequencies[i] - pre + 1个字符,同时更新pre,如果pre=1,即前一字符的频率已经为1,则后面的字符要全删除,相等和大于的情况可以合并到一起。

  • Version 1
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution:
    def minDeletions(self, s: str) -> int:
        stat = collections.defaultdict(int)
        for ch in s:
            stat[ch] += 1
        frequencies = sorted(stat.values(), reverse=True)
        count = 0
        pre = frequencies[0]
        for i in range(1, len(frequencies)):
            if pre == 1:
                count += frequencies[i]
                continue
            if frequencies[i] >= pre:
                count += frequencies[i] - pre + 1
                pre -= 1
            else:
                pre = frequencies[i]
        return count

Reference

  1. https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2021/08/18 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
Leetcode 567. Permutation in String
文章作者:Tyan 博客:noahsnail.com | CSDN | 简书
Tyan
2021/09/06
3490
Leetcode 974. Subarray Sums Divisible by K
文章作者:Tyan 博客:noahsnail.com | CSDN | 简书
Tyan
2021/08/10
3070
LeetCode 1647. 字符频次唯一的最小删除次数(贪心)
如果字符串 s 中 不存在 两个不同字符 频次 相同的情况,就称 s 是 优质字符串 。
Michael阿明
2021/02/19
6340
Leetcode 1356. Sort Integers by The Number of 1 Bits
文章作者:Tyan 博客:noahsnail.com | CSDN | 简书
Tyan
2021/07/08
4270
LeetCode笔记:387. First Unique Character in a String
最近连续几题都是关于字符串中字母的题目,也都强调了可以假设全为小写字母,基本养成了看到这种东西就想到要用26位数字数组记录的条件反射,这确实是一个很好的方法,实现出来也很快。这里的目的是找出第一个不重复的字母,那么首先肯定要遍历查看每个字母是否重复,所以要拿26位数字数组来记录每个字母出现的次数。因为要找出第一个不重复的,所以还要一个26位数字数组来记录每个数组第一次出现的位置。最后查看有哪些字母只出现了一次并且找到其中出现位置最早的那个字母就是了。
Cloudox
2021/11/23
3020
搞定大厂算法面试之leetcode精讲20.字符串
方法1.截取字符串,循环字符串,遇到#就截掉最后一个字符,循环完毕之后,最后比较两个去除掉#退格之后的字符串是否相等,时间复杂度O(m+n),m、n是两个字符串的长度。空间复杂度O(1)
全栈潇晨
2021/12/04
7160
Leetcode 809. Expressive Words
文章作者:Tyan 博客:noahsnail.com | CSDN | 简书
Tyan
2021/08/06
2780
Leetcode 438. Find All Anagrams in a String
文章作者:Tyan 博客:noahsnail.com | CSDN | 简书
Tyan
2021/09/06
4710
Leetcode 560. Subarray Sum Equals K
文章作者:Tyan 博客:noahsnail.com | CSDN | 简书
Tyan
2021/08/10
2940
Leetcode 1590. Make Sum Divisible by P
文章作者:Tyan 博客:noahsnail.com | CSDN | 简书
Tyan
2021/08/10
4030
04-树6. Huffman Codes--优先队列(堆)在哈夫曼树与哈夫曼编码上的应用
题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916 In 1953, David A. Huffman published his paper "A Method for the Construction of Minimum-Redundancy Codes", and hence printed his name in the history of computer science. As a professor who gives the
llhthinker
2018/01/24
1.2K0
LeetCode 828. 统计子串中的唯一字符(中心扩展)
我们定义了一个函数 countUniqueChars(s) 来统计字符串 s 中的唯一字符,并返回唯一字符的个数。
Michael阿明
2020/07/13
7470
leetcode每日一题:49. 字母异位词分组
题目:https://leetcode-cn.com/problems/group-anagrams
用户3578099
2020/12/30
3810
792. Number of Matching Subsequences
思路: 从note中可以看出words的长度不长,而S的长度最大有50000,暴力的做法:每个word去匹配S,因为S没有记忆成高效数据结构,每次匹配都会重新遍历一次S,时间复杂度为O(len(S)),显然会超时。
用户1147447
2019/05/26
4490
【C++修行之道】string类练习题
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
走在努力路上的自己
2024/07/13
1390
【C++修行之道】string类练习题
LeetCode笔记:Weekly Contest 291
这题我的思路就是先记录下每一个卡出现的位置,然后只要看连续两个位置出现的间隔,找出其中的最小值然后进行返回即可。
codename_cys
2022/05/07
2740
C#版[击败99.69%的提交] - Leetcode 242. 有效的同构异形词 - 题解
在线提交: https://leetcode.com/problems/valid-anagram/
Enjoy233
2019/03/05
5550
Leetcode 1395. Count Number of Teams
**解析:**Version 1,暴力比较,三重循环,超时。Version 2,如果把每个数作为三个数的中间数值,则每个数对应的团队数量为其左边小于它的数字个数乘以右边大于它的数字个数加上其左边大于它的数字个数乘以右边小于它的数字个数。Version 3是Version 2的另一种形式。
Tyan
2021/07/29
4120
Leetcode 1395. Count Number of Teams
LeetCode 1347. 制造字母异位词的最小步骤数
给你两个长度相等的字符串 s 和 t。每一个步骤中,你可以选择将 t 中的 任一字符 替换为 另一个字符。
Michael阿明
2020/07/13
6170
Leetcode【939、1048】
最小面积矩形。给一个坐标列表,计算这些坐标可以组成的最小矩形面积,其中矩形平行于 x 轴和 y 轴。
echobingo
2019/07/31
7750
相关推荐
Leetcode 567. Permutation in String
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验