当前位置：首页 > news >正文

LeetCode题练习与总结：根据字符出现频率排序--451

news 来源：原创 2025/7/8 5:20:50

一、题目描述

给定一个字符串 s ，根据字符出现的频率对其进行 降序排序 。一个字符出现的频率是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

示例 1:

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

示例 2:

输入: s = "cccaaa"
输出: "cccaaa"
解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。

示例 3:

输入: s = "Aabb"
输出: "bbAa"
解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

提示:

1 <= s.length <= 5 * 10^5
s 由大小写英文字母和数字组成

二、解题思路

首先，我们需要统计每个字符在字符串中出现的频率。这可以通过使用一个哈希表（HashMap）来实现，其中键是字符，值是该字符出现的次数。
然后，我们需要根据字符出现的频率对字符进行排序。由于题目要求按照降序排序，我们可以使用优先队列（PriorityQueue）来实现。Java中的PriorityQueue默认是最小堆，因此我们需要自定义比较器来使其成为最大堆。
接下来，我们将所有字符放入优先队列中，队列会根据字符出现的频率自动排序。
最后，我们从优先队列中取出字符，按照其频率构造最终的字符串。

三、具体代码

import java.util.*;class Solution {public String frequencySort(String s) {// 1. 统计字符频率Map<Character, Integer> frequencyMap = new HashMap<>();for (char c : s.toCharArray()) {frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);}// 2. 使用优先队列对字符进行排序PriorityQueue<Character> pq = new PriorityQueue<>((a, b) -> frequencyMap.get(b) - frequencyMap.get(a));// 3. 将所有字符放入优先队列pq.addAll(frequencyMap.keySet());// 4. 构造结果字符串StringBuilder sb = new StringBuilder();while (!pq.isEmpty()) {char c = pq.poll();int frequency = frequencyMap.get(c);for (int i = 0; i < frequency; i++) {sb.append(c);}}return sb.toString();}
}

这段代码首先统计了每个字符的频率，然后使用优先队列对字符进行了降序排序，最后构造了结果字符串并返回。由于优先队列中元素的顺序是根据频率降序排列的，所以我们可以确保最终构造的字符串是满足题目要求的。

四、时间复杂度和空间复杂度

1. 时间复杂度

统计字符频率：我们遍历了字符串s一次，每次遍历都会更新哈希表frequencyMap。这个过程的时间复杂度是O(n)，其中n是字符串s的长度。
构建优先队列：我们将所有不同的字符放入优先队列中。由于字符串s中的字符种类最多为ASCII字符集的大小（通常为128或256），因此这一步的时间复杂度是O(m log m)，其中m是字符串中不同字符的数量。
构造结果字符串：我们从优先队列中取出每个字符，并按照其频率将其添加到结果字符串中。由于每个字符最多被添加到队列中一次，并且从队列中取出一次，因此这一步的时间复杂度是O(n log m)，其中n是字符串s的长度，m是字符串中不同字符的数量。

综合以上步骤，总的时间复杂度是O(n + m log m + n log m)。由于m ≤ n，因此可以简化为O(n log n)。

2. 空间复杂度

哈希表frequencyMap：用于存储每个字符及其出现的频率。在最坏的情况下，如果字符串s中的每个字符都不同，那么哈希表的大小将是O(m)，其中m是字符串中不同字符的数量。
优先队列pq：存储字符串中所有不同的字符。在最坏的情况下，优先队列的大小也是O(m)。
结果字符串sb：在构造结果字符串时，我们使用了StringBuilder，其空间复杂度是O(n)，其中n是字符串s的长度。

综合以上步骤，总的空间复杂度是O(m + n)，由于m ≤ n，因此可以简化为O(n)。

五、总结知识点

Java集合框架：
- HashMap：用于存储键值对，其中键是字符，值是该字符出现的次数。
- PriorityQueue：实现了优先队列，可以按照元素的自然顺序或者通过比较器（Comparator）来排序元素。
Lambda表达式：
- 在创建PriorityQueue时，使用了Lambda表达式来定义自定义的比较器，使得优先队列根据字符出现的频率降序排列。
方法引用：
- 使用了Character类的set作为addAll方法的参数，这是方法引用的一种形式，它将集合中的所有元素添加到优先队列中。
流的集合操作：
- frequencyMap.keySet()返回一个包含所有键的Set，然后使用addAll方法将其添加到优先队列中。
字符操作：
- 使用toCharArray()方法将字符串转换为字符数组，以便遍历每个字符。
HashMap操作：
- 使用getOrDefault方法来获取字符的频率，如果字符不存在于映射中，则返回默认值0。
循环和条件语句：
- 使用for循环来遍历字符数组，并更新字符频率。
- 使用while循环来处理优先队列中的元素，直到队列为空。
字符串构建：
- 使用StringBuilder来高效地构建最终的字符串结果，避免频繁的字符串连接操作。
优先队列操作：
- 使用poll方法从优先队列中移除并返回队列的头部元素，即当前频率最高的字符。
泛型：
- 在定义HashMap和PriorityQueue时使用了泛型，分别指定了键和值的类型。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

LeetCode题练习与总结：根据字符出现频率排序--451

一、题目描述给定一个字符串 s ，根据字符出现的频率对其进行降序排序。一个字符出现的频率是它出现在字符串中的次数。返回已排序的字符串。如果有多个答案，返回其中任何一个。示例 1: 输入: s "tree" 输出: "eert" …...

编程日记 2025/7/8 5:20:50

Excel VBA学习系列汇总20241205

整理几年工作中，实用VBA代码，绝对干货！ 方便自己查询，方便大家学习， 有缘人可复制使用，记得分享给大家免费学习哦！ 序历史文章1新学期开始，如何新学期开始，如何按成绩名次…...

编程日记 2025/7/7 3:09:15

给el-table表头添加icon图标，以及鼠标移入icon时显示el-tooltip提示内容

在你的代码中，你已经正确地使用了 el-tooltip 组件来实现鼠标划过加号时显示提示信息。el-tooltip 组件的 content 属性设置了提示信息的内容，placement 属性设置了提示信息的位置。你需要确保 el-tooltip 组件的 content 属性和 placement 属性设置正…...

编程日记 2025/7/8 5:11:25

基于LLM智能问答系统【阿里云：天池比赛】

流程： 1、分别识别问题及提供的资料文件中的公司名实体，有公司名的走语义检索，无公司名的走结构化召回 2、结构化召回：Qwen根据问题生成sql，执行sql获取结果数值，把结果数值与问题给到Qwen生成最终结果 …...

编程日记 2025/7/6 18:37:47

k8s-Informer概要解析(2)

Client-go 主要用在 k8s 控制器中什么是 k8s Informer Informer 负责与 kubernetes APIServer 进行 Watch 操作，Watch 的资源，可以是 kubernetes 内置资源对象，也可以 CRD。 Informer 是一个带有本地缓存以及索引机制的核心工具包&#x…...

编程日记 2025/7/7 3:07:30

Leetcode 3376. Minimum Time to Break Locks I

Leetcode 3376. Minimum Time to Break Locks I 1. 解题思路2. 代码实现题目链接：3376. Minimum Time to Break Locks I 1. 解题思路这一题我最开始的思路走的是贪婪算法的路子，优先走X的增长，不过很不幸失败了，后面还是暴力…...

编程日记 2025/7/6 10:02:05

介绍8款开源网络安全产品

01 HFish蜜罐 HFish是一款开源的蜜罐系统，用于模拟各种网络服务和应用，以吸引潜在的黑客攻击。它能够记录攻击尝试并收集攻击者的信息，从而帮助网络管理员识别潜在的威胁。HFish支持多种协议和服务，包括HTTP、FTP、SSH等&#…...

编程日记 2025/7/5 19:59:48

vue2面试题|[2024-12-5]

开题答辩终于结束了，又要开始我的前端面试学习啦！！！ 1.v-model双向绑定原理 class Vue{constructor(options){this.$options optionsthis.$watchEvent {}if(typeof options.beforeCreate function){options.beforeCreate.bind…...

编程日记 2025/7/7 3:40:12

共筑数字安全防线，2024开源和软件安全沙龙即将启幕

随着数字化转型进程的加快以及开源代码的广泛应用，开源凭借平等、开放、协作、共享的优秀创作模式，逐渐成为推动数字技术创新、加速传统行业转型升级的重要模式。但随着软件供应链日趋复杂多元，使得其安全风险不断加剧，针对软件供…...

编程日记 2025/7/6 20:34:44

目标跟踪领域经典论文解析

亲爱的小伙伴们😘，在求知的漫漫旅途中，若你对深度学习的奥秘、JAVA 、PYTHON与SAP 的奇妙世界，亦或是读研论文的撰写攻略有所探寻🧐，那不妨给我一个小小的关注吧🥰。我会精心筹备，在…...

编程日记 2025/7/6 18:18:30

SQL DQL数据查询语言（后续）

SQL DQL数据查询语言（后续） 1.子查询在查询语句中的WHERE条件子句中，又嵌套了另外一个查询语句在返回列中嵌套一个查询 where条件中嵌套要求：查询课程为《高等数学-2》且分数不小于80分的学生的学号和姓名select a.StudentNo,a…...

编程日记 2025/7/7 3:33:17

Gitee配置SSH公钥

采用SSH协议同步Git仓库代码的好处就是高效。在配置好SSH公钥后，不需要每次操作都要输入用户名和密码（主要针对命令行来说）。以我个人项目为例。生成 SSH 公钥 1. 通过命令 ssh-keygen 生成 SSH Key： ssh-keygen -t ed25519…...

编程日记 2025/7/7 3:15:42

机器学习——感知机模型

文章目录前言1.感知机模型介绍1.1基本概念1.2数学表达1.3几何解释1.4优缺点 2.二分类应用2.1应用介绍2.2准备数据集2.2.1环境检查2.2.2数据集介绍2.2.3获取数据2.2.4划分数据集 2.3可视化训练集2.4训练过程2.4.1首轮梯度下降2.4.2多轮梯度下降 2.5可视化分类结果2.6在验证集验…...

编程日记 2025/7/7 3:47:06

如何选择安全、可验证的技术？

澳大利亚信号局的澳大利亚网络安全中心 (ASD 的 ACSC) 发布了一份指导文件，题为《选择安全和可验证的技术》，旨在帮助组织在采购软件（专有或开源）、硬件（例如物联网设备）和云服务（SaaS、MSP 服务…...

编程日记 2025/7/7 4:24:30

STL库中list的使用与迭代器的实现

STL库中list的使用与迭代器的实现 1.使用list中的部分函数assignspliceremoveuniquemeger 2.list的部分功能实现（重点）框架迭代器的实现 1.使用list中的部分函数 assign 功能一：当前链表的节点全部销毁，替换成迭代区间的值功能二…...

编程日记 2025/7/7 2:46:52

android 常用三方框架

说实话， 我是比较讨厌三方框架的， 比如一个eventbus 底层逻辑就是个观察者模式，当然他的场景涵盖的比较丰富， 单从单一原则来说， 还是一个简单的观察者模式就能解决问题， 何必要添加那么多文件到我们的项目…...

编程日记 2025/7/6 12:21:13

Browser.js断点续传上传

通过断点续传上传的方式将文件上传到OSS前，您可以指定断点记录点。上传过程中，如果出现网络异常或程序崩溃导致文件上传失败时，将从断点记录处继续上传未上传完成的部分。 attention： 1、当您使用webpack或browserify等打包工具…...

编程日记 2025/7/7 4:09:43

Java项目实战II基于微信小程序的无中介租房系统（开发文档+数据库+源码）

目录一、前言二、技术介绍三、系统实现四、核心代码五、源码获取全栈码农以及毕业设计实战开发，CSDN平台Java领域新星创作者，专注于大学生项目实战开发、讲解和毕业答疑辅导。一、前言随着城市化进程的加速，租房市场日益繁荣&a…...

编程日记 2025/7/6 21:41:17

了解Cocoa Touch框架与主要组件

Cocoa Touch框架详解及其主要组件一、Cocoa Touch框架概述 Cocoa Touch框架是苹果公司为iOS应用程序开发提供的一套完整的框架，它基于Cocoa框架，并专为触控设备如iPhone、iPad等设计。这套框架不仅包含了构建图形用户界面（GUI）…...

编程日记 2025/7/7 5:02:09

ISO45001职业健康安全管理体系涵盖了丰富的内容

范围与术语适用范围：明确规定了该标准适用于任何有愿望建立、实施和保持职业健康安全管理体系的组织，旨在使组织能够通过管理体系的有效运行，预防和控制职业健康安全风险，持续改进职业健康安全绩效。术语定义：对职业…...

编程日记 2025/7/7 3:27:27

Spring Boot 整合 Druid 并开启监控

文章目录 1. 引言2. 添加依赖3. 配置数据源4. 开启监控功能5. 自定义 Druid 配置（可选）6. 访问监控页面7. 注意事项8. 总结 Druid 是一个由阿里巴巴开源的高性能数据库连接池，它不仅提供了高效的连接管理功能，还自带了强大的监控和…...

编程日记 2025/7/6 12:40:04

【JAVA高级篇教学】第一篇：Springboot对接通义千问大模型

博主今天打算讲解下Java如何对接阿里云的通义千问大模型，可以自己玩玩ai问答之类的！ 目录一、发展历程二、API-KEY的获取与配置三、引用SDK 四、文本模型 1.代码 2.返回数据 3.官方代码案例五、通义千问VL 1.计量计费六、查看API-KEY调用额…...

编程日记 2025/7/7 3:41:46

【Windows 同时安装 MySQL5 和 MySQL8 - 详细图文教程】

卸载 MySQL 参考文章： 完美解决Mysql彻底删除并重装_怎么找到mysql并卸载-CSDN博客使用命令卸载mysql_卸载mysql服务命令-CSDN博客先管理员方式打开 cmd ，切换到 MySQL 安装目录的 bin 文件夹下，执行如下命令，删除 MySQL 服务 my…...

编程日记 2025/7/6 18:13:21

Next.js 系统性教学：深入理解缓存与数据优化策略

更多有关Next.js教程，请查阅： 【目录】Next.js 独立开发系列教程-CSDN博客目录前言 1. 缓存的基本概念 1.1 缓存的作用 1.2 Next.js 中的缓存策略 2. Next.js 的缓存机制 2.1 请求记忆化（Request Memoization） 2.1.1 什…...

编程日记 2025/7/6 22:03:15

JAVA数据结构

1.数组 (Array)：固定大小的容器，用于存储相同类型的元素，数组在内存中是连续存储的，支持通过索引快速访问元素。 int[] numbers = new int[10]; numbers[0] = 1;2.Java Collections Framework (JCF) JCF提供了一组接口和类用于管理和操作集合(如列表，集合，…...

编程日记 2025/7/6 12:56:07

力扣第96题不同的二叉搜索树

力扣第96题 - 不同的二叉搜索树题目描述给定一个整数 n，求以 1 到 n 为节点组成的所有不同的二叉搜索树（BST） 的个数。题目分析二叉搜索树的性质对于一个二叉搜索树，以 i 为根节点： 左子树的节点值来自 [1, i…...

编程日记 2025/7/7 3:28:22

在Ubuntu上使用IntelliJ IDEA：开启你的Java开发之旅！

你好，年轻的学徒！🧑‍💻 是时候踏上进入Java开发世界的史诗之旅了，我们的得力助手将是强大的IntelliJ IDEA。准备好了吗？出发吧！ 在我们开始之前，我们需要下载这个工具。但是&#…...

编程日记 2025/7/7 3:39:07

【C语言】18. 自定义类型：结构体类型

文章目录前言：一、结构体类型的声明1、结构体回顾1）结构的声明2）结构体变量的创建和初始化 2、结构的特殊声明3、结构的⾃引⽤二、结构体变量的创建和初始化1、对⻬规则2、为什么存在内存对⻬?3、修改默认对⻬数三、结构成员访问操作符1、…...

编程日记 2025/7/7 3:41:47

智能租赁管理系统助力规范化住房租赁市场提升用户体验

内容概要在当今的住房租赁市场中，智能租赁管理系统应运而生，为房东和租客带来了前所未有的便利。这套系统就像一位全能助手，将租赁信息、监管机制以及在线签约功能集成在一起，让整个过程变得流畅而高效。换句话说，您…...

编程日记 2025/7/7 3:21:34

ERROR: KeeperErrorCode = NoNode for /hbase/master

原因分析通过上面的情景模拟，我们可以看到报错的原因在于zookeeper中出现问题，可能是zookeeper中的/hbase/master被删除，或者是在hbase集群启动之后重新安装了zookeeper，导致zookeeper中的/hbase/master节点数据异常。 1. 停止…...

编程日记 2025/7/7 3:15:42

springboot第84集：Java进阶之路, Netty

# kafka-map文件夹 cd /usr/local/kafka-map # 根据需求自行修改配置 vi application.yml # 启动 java -jar kafka-map.jar byte minByte -128; byte maxByte 127; 用于表示一个 8 位（1 字节）有符号整数。它的值范围是 -128（-2^7&#xff0…...

编程日记 2025/7/7 3:55:39

DevOps流程第一步安装git 关闭防火墙 systemctl stop firewalld cd /usr/loacl vim docker-compose.yml docker search gitlab 拉取gitlab镜像 2.33GB docker pull gitlab/gitlab-ce:latestvim docker-compose.yml修改docker-compose.yml version: 3.1 services:gitlab:i…...

编程日记 2025/7/6 9:33:08

sql server log文件

确定 SQL Server 实例中具有大量 VDF 的数据库 SELECT [name], COUNT(l.database_id) AS vlf_count FROM sys.databases AS s CROSS APPLY sys.dm_db_log_info(s.database_id) AS l GROUP BY [name] HAVING COUNT(l.database_id) > 100; 在收缩日志文件之前确定事务日志中…...

编程日记 2025/7/7 2:42:48

pip install报错 Missing dependencies for SOCKS support的正确解决办法：离线安装pysocks

今天准备开发python项目的时候，发现在pip install 的时候报错了，提示：Missing dependencies for SOCKS support，查遍csdn所有的回答都统一是只需要执行： unset all_proxy unset ALL_PROXY 然后再执行 pip install p…...

编程日记 2025/7/7 2:53:13

嵌入式学习(15)-stm32通用GPIO模拟串口发送数据

一、概述在项目开发中可能会遇到串口不够用的情况这时候可以用通过GPIO来模拟串口的通信方式。二、协议格式按照1位起始位8位数据位1位停止位的方式去编写发送端的程序。起始位拉低一个波特率的时间；发送8位数据；拉高一个波特率的时间。三、代码 …...

编程日记 2025/7/7 2:43:29

AKE 安全模型：CK, CK+, eCK

参考文献： [BCK98] Mihir Bellare, Ran Canetti, Hugo Krawczyk. A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract). STOC 1998: 419-428.[CK01] Ran Canetti, Hugo Krawczyk. Analysis of Key-E…...

编程日记 2025/7/7 14:51:17

【Linux】通过crond服务设置定时执行shell脚本，实际执行时间却延迟了8小时

一、问题描述通过使用crond服务设置定时任务，在每天凌晨的2:00执行脚本，但检查结果时发现，实际执行时间却在上午10点。检查shell脚本执行结果发现，实际执行脚本时间在上午10:00，延迟了8小时。检查系统时间&#xf…...

编程日记 2025/7/7 2:49:46

什么是云原生数据库 PolarDB？

云原生数据库 PolarDB 是阿里云推出的一款高性能、兼容性强、弹性灵活的关系型数据库产品。它基于云原生架构设计，结合分布式存储和计算分离的技术优势，为用户提供强大的计算能力、卓越的可靠性以及高性价比的数据库解决方案。PolarDB 适合各种业务场景&…...

编程日记 2025/7/7 3:34:10

（6）JS-Clipper2之ClipperOffset

1. 描述 ClipperOffset类封装了对打开路径和关闭路径进行偏移(膨胀/收缩)的过程。这个类取代了现在已弃用的OffsetPaths函数，该函数不太灵活。可以使用不同的偏移量(增量)多次调用Execute方法，而不必重新分配路径。现在可以在一次操作中对开放和封闭路…...

编程日记 2025/7/7 3:20:39

基于51单片机64位病床呼叫系统设计( proteus仿真+程序+设计报告+原理图+讲解视频）

基于51单片机病床呼叫系统设计( proteus仿真程序设计报告原理图讲解视频） 仿真图proteus7.8及以上程序编译器：keil 4/keil 5 编程语言：C语言设计编号：S0095 1. 主要功能： 基于51单片机的病床呼叫系统proteus仿…...

编程日记 2025/7/6 22:33:07

工业智能网关如何为企业实现智能制造赋能？

在数字化转型的浪潮中，工业智能网关作为连接物理世界与数字世界的桥梁，正逐步成为智能制造领域的核心组件。本文将通过一个实际使用案例，深入剖析工业智能网关如何助力企业实现生产流程的优化、数据的高效采集与分析，以及智能化决…...

编程日记 2025/7/7 11:07:44

【Spring项目】表白墙，留言板项目的实现

阿华代码，不是逆风，就是我疯你们的点赞收藏是我前进最大的动力！！ 希望本文内容能够帮助到你！！ 目录一：项目实现准备 1：需求 2：准备工作 （1）…...

编程日记 2025/7/7 11:09:15

Java-WebSocket

文章目录 WebSocket概念SpringBoot实现一个WebSocket示例STOMP消息订阅和发布后端主动发送消息跨域 WebSocket概念应用层协议，底层采用TCP，特点：持续连接，有状态，双向通信当客户端想要与服务器建立WebSocket连接时…...

编程日记 2025/7/7 13:12:56

C#请求https提示未能为 SSL/TLS 安全通道建立信任关系

System.Net.WebException: 基础连接已经关闭: 未能为 SSL/TLS 安全通道建立信任关系 ，这个错误通常表明你的应用程序在尝试建立一个安全的 SSL/TLS 连接时遇到了问题。这通常是由于证书验证失败引起的。证书验证失败可能有几个原因： 证书不受信任&#…...

编程日记 2025/7/7 11:39:45

pdf转word/markdown等格式——MinerU的部署：2024最新的智能数据提取工具

一、简介 MinerU是开源、高质量的数据提取工具，支持多源数据、深度挖掘、自定义规则、快速提取等。含数据采集、处理、存储模块及用户界面，适用于学术、商业、金融、法律等多领域，提高数据获取效率。一站式、开源、高质量的数据提取工具&…...

编程日记 2025/7/7 11:55:39

人工智能与机器学习：真实案例分析及其在各行业的应用前景

目录引言人工智能与机器学习的基础概念人工智能的历史与演变机器学习的算法分类深度学习与传统机器学习的区别行业应用案例分析医疗健康疾病预测与诊断影像识别的运用案例：IBM Watson在肿瘤治疗中的应用金融服务风险评估与欺诈检测投资预测…...

编程日记 2025/7/7 12:08:00

再谈多重签名与 MPC

目录什么是 MPC 钱包以及它们是如何出现的多重签名和智能合约钱包已经成熟超越 MPC 钱包关于小队多重签名已经成为加密货币领域的一部分，但近年来，随着 MPC（多方计算）钱包的出现，多重签名似乎被掩盖了。MPC 钱包之…...

编程日记 2025/7/7 11:14:35

（长期更新）《零基础入门 ArcGIS(ArcMap) 》实验二----网络分析（超超超详细！！！）

相信实验一大家已经完成了，对Arcgis已进一步熟悉了，现在开启第二个实验 ArcMap实验--网络分析目录 ArcMap实验--网络分析 1.1 网络分析介绍 1.2 实验内容及目的 1.2.1 实验内容 1.2.2 实验目的 2.2 实验方案 2.3 实验流程 2.3.1 实验准备 2.3.2 空间校正…...

编程日记 2025/7/7 11:13:55