[100天算法】-根据字符出现频率排序(day 57)

题目描述

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。示例 1:输入:
"tree"输出:
"eert"解释:
'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。
示例 2:输入:
"cccaaa"输出:
"cccaaa"解释:
'c'和'a'都出现三次。此外,"aaaccc"也是有效的答案。
注意"cacaca"是不正确的,因为相同的字母必须放在一起。
示例 3:输入:
"Aabb"输出:
"bbAa"解释:
此外,"bbaA"也是一个有效的答案,但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/sort-characters-by-frequency
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

方法1:哈希表+堆

思路

  • 用哈希表来记录每个字符的出现次数
  • 以字符出现次数建立一个大顶堆
  • 一边弹出堆顶,一边构建新的字符串

复杂度分析

  • 时间复杂度:$O(n+klogk)$,n 是字符串的长度,k 是字符串中字符集的大小。
  • 空间复杂度:$O(k)$,k 是字符串中字符集的大小,堆的大小。

代码

JavaScript Code

/*** @param {string} s* @return {string}*/
var frequencySort = function (s) {const map = {}for (let i = 0; i < s.length; i++) {const c = s[i];map[c] = (map[c] || 0) + 1}// 堆的数据结构 [char, count]const list = Object.keys(map).map(c => [c, map[c]])const heap = new MaxHeap(list, function comparator(inserted, compared) {return inserted[1] < compared[1];});let str = ''while (heap.size() > 0) {const [char, cnt] = heap.pop();str += char.repeat(cnt)}return str
};// **************************************************class Heap {constructor(list = [], comparator) {this.list = list;this.comparator = comparator;this.init();}init() {const size = this.size();for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {this.heapify(this.list, size, i);}}insert(n) {this.list.push(n);const size = this.size();for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {this.heapify(this.list, size, i);}}peek() {return this.list[0];}pop() {const last = this.list.pop();if (this.size() === 0) return last;const returnItem = this.list[0];this.list[0] = last;this.heapify(this.list, this.size(), 0);return returnItem;}size() {return this.list.length;}
}class MaxHeap extends Heap {constructor(list, comparator) {super(list, comparator);}heapify(arr, size, i) {let largest = i;const left = Math.floor(i * 2 + 1);const right = Math.floor(i * 2 + 2);if (left < size && this.comparator(arr[largest], arr[left]))largest = left;if (right < size && this.comparator(arr[largest], arr[right]))largest = right;if (largest !== i) {[arr[largest], arr[i]] = [arr[i], arr[largest]];this.heapify(arr, size, largest);}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/181215.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Docker 安装ELK7.7.1

(注&#xff1a;在安装之前&#xff0c;本方法必须安装jdk1.8以上版本) (注&#xff1a;如果在虚拟机下用可以直接按方法走即可&#xff0c;如果是想进行备份后在别的机器上进行相关操作&#xff0c;必须把所有带有172.17.0.6、192.168.8.166:9200和端口号都改成你自己的方可使…

使用 curator 连接 zookeeper 集群 Invalid config event received

dubbo整合zookeeper 如图&#xff0c;错误日志 2023-11-04 21:16:18.699 ERROR 7459 [main-EventThread] org.apache.curator.framework.imps.EnsembleTracker Caller0 at org.apache.curator.framework.imps.EnsembleTracker.processConfigData(EnsembleTracker.java…

MTK联发科、高通、紫光展锐手机SOC平台型号汇总(含详细参数)

MediaTek联发科手机平台汇总&#xff1a; Qualcomm高通SOC平台汇总&#xff1a; 紫光展锐SOC平台汇总&#xff1a; 新移科技已成功研发手机SOC平台&#xff1a; 联发科平台&#xff1a; MTK6739、MTK6761、MTK6762、MTK6765、MTK8788、MTK6853、MTK6873、MTK6833、MTK6877、…

试试流量回放,不用人工写自动化测试case了

大家好&#xff0c;我是洋子&#xff0c;接触过接口自动化测试的同学都知道&#xff0c;我们一般要基于某种自动化测试框架&#xff0c;编写自动化case&#xff0c;编写自动化case的依据来源于接口文档&#xff0c;对照接口文档里面的请求参数进行人工添加接口自动化case 其实…

DB-GPT介绍

DB-GPT介绍 引言DB-GPT项目简介DB-GPT架构关键特性私域问答&数据处理多数据源&可视化自动化微调Multi-Agents&Plugins多模型支持与管理隐私安全支持数据源 子模块DB-GPT-Hub微调参考文献 引言 随着数据量的不断增长和数据分析的需求日益增多&#xff0c;将自然语言…

Git(七).git 文件夹瘦身,GitLab 永久删除文件

目录 一、问题背景二、问题复现2.1 新建项目2.2 上传大文件2.3 上传结果 三、解决方案3.1 GitLab备份与还原1&#xff09;备份2&#xff09;还原 3.2 删除方式一&#xff1a;git filter-repo 命令【推荐】1&#xff09;安装2&#xff09;删除本地仓库文件3&#xff09;重新关联…

3款免费又好用的 Docker 可视化管理工具

前言 Docker提供了命令行工具&#xff08;Docker CLI&#xff09;来管理Docker容器、镜像、网络和数据卷等Docker组件。我们也可以使用可视化管理工具来更方便地查看和管理Docker容器、镜像、网络和数据卷等Docker组件。今天我们来介绍3款免费且好用的 Docker 可视化管理工具。…

构建mono-repo风格的脚手架库

前段时间阅读了 https://juejin.cn/post/7260144602471776311#heading-25 这篇文章&#xff1b;本文做一个梳理和笔记&#xff1b; 主要聚焦的知识点如下&#xff1a; 如何搭建脚手架工程如何开发调试如何处理命令行参数如何实现用户交互如何拷贝文件夹或文件如何动态生成文件…

贰[2],OpenCV函数解析

1&#xff0c;imread&#xff1a;图片读取 CV_EXPORTS_W Mat imread( const String& filename, int flags IMREAD_COLOR );//参数1(filename)&#xff1a;文件地址 //参数2(flags):读取标志 注:ImreadModes&#xff0c;参数2(flags)枚举定义 enum ImreadModes { IMREAD…

分享68个工作总结PPT,总有一款适合您

分享68个工作总结PPT&#xff0c;总有一款适合您 PPT下载链接&#xff1a;https://pan.baidu.com/s/1juus0gmesBFxJ-5KZgSMdQ?pwd8888 提取码&#xff1a;8888 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;收集整理更不易。知识付…

【Unity】2D角色跳跃控制器

最近加了学校的Nova独游社&#xff0c;本文是社团出的二面题&#xff0c;后续有时间优化下可能会做成一个二维冒险小游戏。本文主要涉及相关代码&#xff0c;参考教程&#xff1a;《勇士传说》横版动作类游戏开发教程 效果演示 【Unity】2D角色跳跃模拟器 主要实现功能&#xf…

AI:53-基于机器学习的字母识别

🚀 本文选自专栏:AI领域专栏 从基础到实践,深入了解算法、案例和最新趋势。无论你是初学者还是经验丰富的数据科学家,通过案例和项目实践,掌握核心概念和实用技能。每篇案例都包含代码实例,详细讲解供大家学习。 📌📌📌本专栏包含以下学习方向: 机器学习、深度学…

前端框架Vue学习 ——(二)Vue常用指令

文章目录 常用指令 常用指令 指令: HTML 标签上带有 “v-” 前缀的特殊属性&#xff0c;不同指令具有不同含义。例如: v-if, v-for… 常用指令&#xff1a; v-bind&#xff1a;为 HTML 标签绑定属性值&#xff0c;如设置 href&#xff0c;css 样式等 <a v-bind:href"…

【四、http】go的http的文件下载

一、日常下载图片到本地 //下载文件func downloadfile(url, filename string) {r, err : http.Get(url)if err ! nil {fmt.Println("err", err.Error())}defer r.Body.Close()f, err : os.Create(filename)if err ! nil {fmt.Println("err", err.Error())…

【深度学习】pytorch——实现CIFAR-10数据集的分类

笔记为自我总结整理的学习笔记&#xff0c;若有错误欢迎指出哟~ 往期文章&#xff1a; 【深度学习】pytorch——快速入门 CIFAR-10分类 CIFAR-10简介CIFAR-10数据集分类实现步骤一、数据加载及预处理实现数据加载及预处理归一化的理解访问数据集Dataset对象Dataloader对象 二、…

Linux的指令和用途(持续更新)

1. 基本指令&#xff1a; 概念介绍&#xff1a; 1. 目录&#x1f7f0;文件夹 Linux指令示范用法说明whowho查看哪些人登陆我的机器whoami (who am i)who am i查看当前账号是谁 pwd pwd查看当前我所在的目录clearclear 清屏 tree 目录名&#xff08;文件夹名&#xff09;tree g…

【JAVA学习笔记】59 - JUnit框架使用、本章作业

项目代码 https://github.com/yinhai1114/Java_Learning_Code/tree/main/IDEA_Chapter15/src/com/yinhai/homework JUnit测试框架 1.基本介绍 1. JUnit是一个Java语言的单元测试框架 2.多数Java的开发环境都已经集成了JUnit作为单元测试的工具 2.如何使用 创建方法后&#x…

2022年ISSCC会议报告分析

Tutorial Fundamentals of Self-Sensing Processor Systems AMD Zen架构的CCD die中有很多传感器检测die的频率、电压、电压和温度 HBM DRAM and 3D Stacked Memory Advances in Digital vs. Analog AI Accelerators Nvidia的Multi-chip架构的DNN加速器 Form1: Compute-in…

流媒体服务实现H5实时预览视频

目录 背景方案业务实践细节注意 待办 背景 客户aws服务磁盘存储告急&#xff0c;最高可扩容16T。排查如下&#xff1a;主要是视频文件存在大量复制使用的情况。例如发布节目时复制、预览时复制&#xff0c;这样上传一份视频后最大会有四份拷贝&#xff08;预览、普通发布、互动…

【m98】abseil-cpp的cmake构建

m79的代码有些头文件没有,比如#include "absl/numeric/bits.h"使用m98版本里的代码,支持cmake构建cmake版本 WIN32 DEBUG configure Selecting Windows SDK version 10.0.22000.0 to target Windows 10.0.22621. The CXX compiler identification is MSVC 19.37.32…