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

数据结构与算法之堆: Leetcode 451. 根据字符出现频率排序 (Typescript版)

根据字符出现频率排序

  • https://leetcode.cn/problems/sort-characters-by-frequency/

描述

  • 给定一个字符串 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 * 1 0 5 10^5 105
  • s 由大小写英文字母和数字组成

算法实现

1 )普通方法实现, 基于原生sort和Map结构

function frequencySort(s: string): string {// 1. 构建map字典,例如: Map{a: 2, b: 3}const map = new Map();s.split('').forEach(item => {map.set(item, map.has(item) ? map.get(item) + 1 : 1);});// 2. 将map转成二维数组进行排序const arr = Array.from(map);arr.sort((a, b) => b[1] - a[1]);// 3. 基于排好序的数组(降序)组装成最终结果let result = '';arr.forEach((item) => {result += item[0].repeat(item[1]);})return result;
};
  • 这里使用平时最简单的原生排序法,结合Map数据结构的特性,和ES6中字符串的特性完成
  • 原生排序,性能不错 O(nlogn),推荐

2 )使用堆排序

class MaxHeap {map: Map<string, number> = new Map()heap: number[] = []init(str:string) {// 构建map字典const { map } = this;str.split('').forEach(item => {map.set(item, map.has(item) ? map.get(item) + 1 : 1);});this.heap = Array.from(map.values());}sort () {const iArr = this.heap;const n = iArr.length;if (n <= 1) return iArr;for (let i = Math.floor(n / 2); i >= 0; i--) {MaxHeap.maxHeapify(iArr, i, n);}for (let j = 0; j < n; j++) {MaxHeap.swap(iArr, 0, n - 1 - j);MaxHeap.maxHeapify(iArr, 0, n - 1 - j - 1);}return iArr;}// 排序并转成字符串sortToString () {const arr = this.sort(); // 这里对值进行排序const str = [];while (arr.length) {const top = arr.pop();for (const [k, v] of this.map) {// 值和值匹配if (v === top) {str.push(k.repeat(v));this.map.delete(k); // 使用过的key防止重复匹配 这里记得删除break}}}return str.join('');}// 交换两个元素static swap (arr, i, j) {if (i === j) return;[arr[i], arr[j]] = [arr[j], arr[i]];}// 构建最大堆的过程static maxHeapify (Arr, i, size) {// 左节点(索引)const l = (i << 1) + 1;// 右节点const r = (i << 1) + 2;let largest = i;// 父节点i和左节点l做比较取最大if (l <= size && Arr[l] > Arr[largest]) largest = l;// 右节点和最大值比较if (r <= size && Arr[r] > Arr[largest]) largest = r;if (largest !== i) {MaxHeap.swap(Arr, i, largest);MaxHeap.maxHeapify(Arr, largest, size);}}
}function frequencySort(s: string): string {const mh = new MaxHeap();mh.init(s);return mh.sortToString();
}
  • 如果这个堆之前构建好,只需要少许修改,即可投入使用
  • 理解了最大堆的构建过程,这个还是比较推荐使用的
  • 需要注意的是在while和for的嵌套循环中的时间复杂度的考量
    • while是每次pop从n直到为0,因此是 n
    • for不会每次都执行n次,匹配到时会被break掉,因此是 logn
    • 所以整体时间复杂度为 O(nlogn)

相关文章:

数据结构与算法之堆: Leetcode 451. 根据字符出现频率排序 (Typescript版)

根据字符出现频率排序 https://leetcode.cn/problems/sort-characters-by-frequency/ 描述 给定一个字符串 s &#xff0c;根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。返回 已排序的字符串 。如果有多个答案&#xff0c;返回其…...

吃透底层:从路由到前缀树

前言 今天学到关于路由相关文章&#xff0c;发现动态路由中有一个很常见的实现方式是前缀树&#xff0c;很感兴趣这个算法&#xff0c;故进行记录。 前缀树 Trie&#xff08;又被叫做字典树&#xff09;可以看作是一个确定有限状态自动机&#xff0c;尽管边上的符号一般是隐含…...

SparkSQL外部数据源

1.简介 1.1 多数据源支持 Spark 支持以下六个核心数据源,同时 Spark 社区还提供了多达上百种数据源的读取方式,能够满足绝大部分使用场景。 - CSV - JSON - Parquet - ORC - JDBC/ODBC connections - Plain-text files 1.2 读数据格式 所有读取 API 遵循以下调用格式: // …...

林沛满-TCP 是如何避免被发送方分片的?

TCP 可以避免被发送方分片&#xff0c;是因为它主动把数据分成小段再交给网络层。最大的分段大小称为 MSS&#xff08;Maximum Segment Size&#xff09;&#xff0c;它相当于把 MTU 刨去 IP头和 TCP 头之后的大小&#xff0c;所以一个 MSS 恰好能装进一个 MTU 中。 图4 图 4 …...

Java中的枚举是什么?

Java枚举详解 枚举&#xff08;Enum&#xff09;是Java编程语言中的一种特殊数据类型&#xff0c;它用于表示一组具名的常量。枚举提供了一种更加类型安全和易于理解的方式来表示常量值&#xff0c;使代码更加清晰和可维护。 为什么需要枚举&#xff1f; 在介绍Java枚举的具…...

java学习--day24(单例模式序列化Lambda表达式)

文章目录 回顾今天的内容1.单例模式2.序列化3.Lambda表达式3.1入门案例3.2lambda表达式语法格式3.2.1无参无返回值的形式3.2.2有参无返返回值的方法3.2.3无参有返回值3.2.4有参有返回值的 回顾 1.三种创建Class对象的形式Class.forName("")类.class对象.getCalss()字…...

从0开始学go第六天

方法一&#xff1a;gin获取querystring参数 package main//querystring import ("net/http""github.com/gin-gonic/gin" )func main() {r : gin.Default()r.GET("/web", func(c *gin.Context) {//获取浏览器那边发请求携带的query String参数//…...

unity设计模式——代理模式

Subject类&#xff0c;定义了Real Subject和Proxy的共用接口&#xff0c;这样就在任何使用Real Subject的地方都可以使用Proxy。 abstract class Subject : MonoBehaviour {public abstract void Request(); } RealSubject类&#xff0c;定义Proxy所代表的真实实体。 class R…...

SpringBoot 如何使用 Grafana 进行可视化监控

使用Spring Boot Sleuth进行分布式跟踪 在现代分布式应用程序中&#xff0c;跟踪请求和了解应用程序的性能是至关重要的。Spring Boot Sleuth是一个分布式跟踪解决方案&#xff0c;它可以帮助您在分布式系统中跟踪请求并分析性能问题。本文将介绍如何在Spring Boot应用程序中使…...

【Codeforces】 CF1762E Tree Sum

题目链接 CF方向 Luogu方向 题目解法 首先考虑 n n n 为奇数的情况无解&#xff0c;这个可以通过乘积矛盾简单证明 接下来考虑一个结论是&#xff1a;偶数个点的树的形态确定之后&#xff0c;只有恰好 1 1 1 种染色方案&#xff0c;即从叶子一层一层往上面染&#xff0c;…...

用《斗破苍穹》的视角打开C#委托2 委托链 / 泛型委托 / GetInvocationList

委托链 经过不懈地努力&#xff0c;我终于成为了斗师&#xff0c;并成功掌握了两种斗技——八极崩和焰分噬浪尺。于是&#xff0c;我琢磨着&#xff0c;能不能搞一套连招&#xff0c;直接把对方带走。 using System; using System.Collections.Generic; using System.Linq; u…...

唐老师讲电赛

dc-dc电源布局要点...

[ICCV-23] DeformToon3D: Deformable Neural Radiance Fields for 3D Toonification

pdf | code 将3D人脸风格化问题拆分为几何风格化与纹理风格化。提出StyleField&#xff0c;学习以风格/ID为控制信号的几何形变残差&#xff0c;实现几何风格化。通过对超分网络引入AdaIN&#xff0c;实现纹理风格化。由于没有修改3D GAN空间&#xff0c;因此可以便捷实现Edit…...

配置Hive使用Spark执行引擎

配置Hive使用Spark执行引擎 Hive引擎概述兼容问题安装SparkSpark配置Hive配置HDFS上传Spark的jar包执行测试速度对比 Hive引擎 概述 在Hive中&#xff0c;可以通过配置来指定使用不同的执行引擎。Hive执行引擎包括&#xff1a;默认MR、tez、spark MapReduce引擎&#xff1a; 早…...

基于FPGA的视频接口之千兆网口(五应用)

简介 相信网络上对于FPGA驱动网口的开发板、博客、论坛数不胜数,为何博主需要重新手敲一遍呢,而不是做一个文抄君呢!因为目前博主感觉网络上描述的多为应用层上的开发,非从底层开始说明,本博主的思虑还是按照老规矩,按照硬件、底层、应用等关系,使用三~四篇文章,来详细…...

车载开发所学内容,有哪些?程序员的转岗位需求

一、高速发展的行业前景 随着全球智能汽车市场的飞速发展&#xff0c;车载开发行业的前景可谓一片光明。各国政府对于自动驾驶和智能交通系统的政策支持&#xff0c;为行业带来了前所未有的机遇。此外&#xff0c;人工智能、大数据、云计算等前沿技术的不断突破&#xff0c;为…...

VSCode Intellij IDEA CE 数据库连接

VSCode & Intellij IDEA CE 数据库连接 大概记一下现在正在用的几个工具/插件 VSCode VSCode 里面的工具我下载了很多&#xff0c;如果只是链接 MySQL 的话&#xff0c;可能用 Jun Han 这位大佬的 MySQL 就好了&#xff1a; 使用这个插件直接打开 .sql 文件单击运行就能…...

直流无刷电机开发应用

下面的链接是笔者在研究无刷电机的过程中&#xff0c;找到的业内无刷电机驱动龙头企业&#xff0c;峰岹科技的各类无刷电机应用设计参考&#xff0c;比较有学习和借鉴意义。 应用手册 - 峰岹科技...

c 语言基础题目:PTA L1-030 一帮一

“一帮一学习小组”是中小学中常见的学习组织方式&#xff0c;老师把学习成绩靠前的学生跟学习成绩靠后的学生排在一组。本题就请你编写程序帮助老师自动完成这个分配工作&#xff0c;即在得到全班学生的排名后&#xff0c;在当前尚未分组的学生中&#xff0c;将名次最靠前的学…...

网工内推 | base郑州,上市公司,最高15薪,五险一金全额缴

01 四方达 招聘岗位&#xff1a;网络工程师 职责描述&#xff1a; 1、负责公司数据中心&#xff08;机房&#xff09;的管理与运维工作。 2、负责公司服务器、路由器、防火墙、交换机等设备的管理、以及网络平台的运行监控和维护&#xff1b; 3、负责公司服务器运维管理工作、…...

GESP学习,如何判断孩子是否适合跳级

判断孩子是否适合跳级&#xff0c;核心是综合评估其学术能力、心理成熟度、社交适应力及政策合规性‌。以下是基于教育规律与官方政策的系统性判断标准&#xff1a; 一、学术能力&#xff1a;是否真正“学有余力” 1、‌成绩特别优异‌&#xff1a; 在当前年级中&#xff0c;各…...

使用 QLineF 从 QTransform 提取角度信息

我们在对 QGraphicsItem 进行变换时&#xff0c;QT 提供了很多便捷的方法。但当我们想获取当前变换的角度时却有些困难&#xff0c;因为 QTransform 没有提供获取角度的方法。在文章Qt 从 QTransform 逆向解出 Translate/Scale/Rotate&#xff08;平移/缩放/旋转&#xff09;分…...

基于Terraform与Azure的Dify AI平台云原生自动化部署实践

1. 项目概述&#xff1a;一键部署AI应用平台的云原生方案最近在折腾AI应用开发平台&#xff0c;发现很多团队在从本地原型验证转向云端生产环境时&#xff0c;总会遇到一堆“部署地狱”的问题。环境配置不一致、资源管理混乱、成本不可控&#xff0c;这些问题在需要整合多个AI模…...

OpenCV 4.x/5.x 在Ubuntu 22.04上安装后,CMake项目死活找不到库?一个环境变量就搞定

OpenCV 4.x/5.x 在Ubuntu 22.04上安装后CMake项目找不到库的终极解决方案 当你满怀期待地在Ubuntu 22.04上安装了最新版的OpenCV&#xff0c;准备开始你的计算机视觉项目时&#xff0c;却遭遇了CMake无法找到OpenCV库的尴尬局面。这种"明明安装了却找不到"的情况&…...

树莓派网络配置全攻略:从有线到无线,新手到进阶

1. 项目概述&#xff1a;为什么网络配置是树莓派的第一课刚拿到一块崭新的树莓派&#xff0c;看着它小巧的主板和闪烁的指示灯&#xff0c;你脑子里想的可能是立刻跑个酷炫的Python项目&#xff0c;或者搭建一个家庭媒体中心。但别急&#xff0c;在这一切开始之前&#xff0c;有…...

OrangePi串口实战:从pyserial配置到USB-TTL数据抓取

1. 环境准备与硬件连接 第一次玩OrangePi串口通信时&#xff0c;我对着桌上那堆USB-TTL模块和杜邦线发呆了半小时。后来才发现&#xff0c;硬件连接其实比想象中简单。你需要准备三样东西&#xff1a;OrangePi开发板&#xff08;我用的是OrangePi 5&#xff09;、USB-TTL转换模…...

【无人机控制】一维环境下LQR与PID控制在无人机悬停控制中的对比分析附matlab代码

✅作者简介&#xff1a;热爱科研的Matlab仿真开发者&#xff0c;擅长数据处理、建模仿真、程序设计、完整代码获取、论文复现及科研仿真。&#x1f34e; 往期回顾关注个人主页&#xff1a;Matlab科研工作室&#x1f34a;个人信条&#xff1a;格物致知,完整Matlab代码及仿真咨询…...

从零构建Claude代码:深入Transformer架构与自回归生成实现

1. 项目概述&#xff1a;从零构建你自己的Claude代码最近在开发者社区里&#xff0c;一个名为“woodx9/build-your-claude-code-from-scratch”的项目引起了我的注意。这个标题直译过来就是“从零开始构建你的Claude代码”&#xff0c;它指向了一个非常具体且富有挑战性的目标&…...

NotebookLM技能集成:自动化文档问答与RAG应用实践

1. 项目概述&#xff1a;当NotebookLM遇上自定义技能最近在折腾AI工具链的时候&#xff0c;发现了一个挺有意思的项目&#xff1a;jasontsaicc/notebooklm-studio-skill。乍一看这个名字&#xff0c;你可能和我最初的反应一样&#xff0c;有点摸不着头脑。NotebookLM我知道&…...

观察智能体项目使用 Taotoken 后的月度 token 消耗与成本趋势

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 观察智能体项目使用 Taotoken 后的月度 token 消耗与成本趋势 对于一个持续运行的智能体项目而言&#xff0c;清晰的成本洞察是项目…...