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

news/2024/2/21 4:12:32

题目描述

给定一个字符串,请将字符串里的字符按照出现的频率降序排列。示例 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.ppmy.cn/news/1197685.html

相关文章

夜间灯光数据VIIRS Nighttime Day: Night Band Composites Version 1数据集

简介&#xff1a; 新一代对地观测卫星Suomi NPP,搭载的可见光红外成像辐射仪&#xff08;Visible Infrared Imaging Radiometer Suit,VIIRS&#xff09;&#xff0c;能够获取新的夜间灯光遥感影像&#xff08;Day/Night Band,DNB波段&#xff09;。VIIRS_VCMCFG夜光遥感数据的…

Julia文件读写函数:write和read

文章目录 初步认识函数详解read&#xff01; 初步认识 Julia提供了异常便捷的文件读写函数&#xff0c;read和write&#xff0c;例如&#xff0c;下面的代码用write将字符串写入到tiny.txt文件中&#xff0c;然后用read将tiny.txt的内容以字符串的形式读取到变量a中&#xff0…

YOLOv5源码中的参数超详细解析(5)— 验证部分(val.py)参数解析

前言:Hello大家好,我是小哥谈。YOLOv5是一种先进的目标检测算法,它可以实现快速和准确的目标检测。在YOLOv5源码中,train.py和detect.py文件讲完了之后,接着就是讲val.py文件了。本节课就结合源码对val.py文件进行逐行解析~!🌈 前期回顾: YOLOv5源码中的参数超详细解…

Linux学习---有关监控系统zabbix的感悟

监控系统 监控系统就像咱们日常生活中小区监控(Monitor)&#xff0c;用于及时发现问题(PROBLEM)&#xff0c;根据相应的规则可以触发警告(Media)&#xff0c;在后台显示屏(Dashboard)上以某种方面显示出来,高级的报警系统也许还能实现电话通知等功能&#xff0c;目的是为及时发…

MySQL数据库之表的增删查改

目录 表的操作1.创建表创建表案例 2.查看表结构3.修改表4.删除表 表的操作 1.创建表 语法&#xff1a; CREATE TABLE table_name (field1 datatype,field2 datatype,field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎;说明&#xff1a; field 表示列…

Python 生成Android不同尺寸的图标

源代码 # -*- coding: utf-8 -*- import sys import os import shutil from PIL import Imagedef generateAndroidIcons():imageSource icon.pngicon Image.open(imageSource)sizes [(android/drawable,512),(android/drawable-hdpi,72),(android/drawable-ldpi,36),(andro…

gcc: __linux__

判断gcc在什么平台的一个方法 https://gcc.gnu.org/onlinedocs/cpp/System-specific-Predefined-Macros.html 实例是&#xff1a;googletest里有用这个 googletest/include/gtest/internal/gtest-port-arch.h #elif defined __linux__ #define GTEST_OS_LINUX 1这里可能有的疑…

spring-boot中实现分片上传文件

一、上传文件基本实现 1、前端效果图展示&#xff0c;这里使用element-ui plus来展示样式效果 2、基础代码如下 <template><div><el-uploadref"uploadRef"class"upload-demo":limit"1":on-change"handleExceed":auto-…

【嵌入式开发工具】STM32+Keil实现软件工程搭建与开发调试

本篇文章介绍了使用Keil来对STM32F103C8芯片进行初始工程搭建&#xff0c;以及开发与工程调试的完整过程&#xff0c;帮助读者能够在实战中体会到Keil这个开发环境的使用方法&#xff0c;了解一个嵌入式工程从无到有的过程&#xff0c;并且具备快速搭建一个全新芯片对应最小软件…

通过51单片机控制28byj48步进电机按角度正反转旋转

一、前言 本项目基于STC89C52单片机&#xff0c;通过控制28BYJ-48步进电机实现按角度正反转旋转的功能。28BYJ-48步进电机是一种常用的电机&#xff0c;精准定位和高扭矩输出&#xff0c;适用于许多小型的自动化系统和机械装置。 在这个项目中&#xff0c;使用STC89C52单片机…

[uni-app] 防重复点击处理 - 自定义指令

一般用节流防抖的方式处理, 这里通过vue的自定义指令方式也可以 实现: import Vue from vue // 自定义指令防止按钮重复点击 v-debounceconst debounce {install(Vue) {// 防止重复点击Vue.directive(debounce, {inserted: function(el, binding) {el.addEventListener(clic…

物理内存的关系及分配模式

在分配缓存块的时候&#xff0c;要分两种路径&#xff0c;fast path 和 slow path&#xff0c;也就是快速通道和普通通道。其中 kmem_cache_cpu 就是快速通道&#xff0c;kmem_cache_node 是普通通道。每次分配的时候&#xff0c;要先从 kmem_cache_cpu 进行分配。如果 kmem_ca…

Linux文件权限详解

Linux是一款功能强大的操作系统&#xff0c;其文件权限系统是确保文件和系统安全的关键组成部分。正确理解和配置文件权限对于维护系统安全至关重要。初次接触Linux时&#xff0c;在公司服务器上处理文件夹或文件时常常碰到Permission denied的提示。为了解决问题&#xff0c;我…

【漏洞复现】Metinfo5.0.4任意文件包含漏洞复现

感谢互联网提供分享知识与智慧&#xff0c;在法治的社会里&#xff0c;请遵守有关法律法规 文章目录 1、蚁剑直接连接图片马2、读取敏感目录3、读取php源码4、执行PHP命令5、包含木马写Shell &#xff08;图片马制作新方法&#xff09; 以 metinfo_5.0.4为例 该环境的文件上传…

Selenium安装WebDriver Chrome驱动(含 116/117/118/119/120/)

1、确认浏览器的版本 在浏览器的地址栏&#xff0c;输入chrome://version/&#xff0c;回车后即可查看到对应版本 2、找到对应的chromedriver版本 2.1 114及之前的版本可以通过点击下载chromedriver,根据版本号&#xff08;只看大版本&#xff09;下载对应文件 2.2 116版本…

[动态规划] (五) 路径问题: LeetCode 62.不同路径

[动态规划] (五) 路径问题: LeetCode 62.不同路径 文章目录 [动态规划] (五) 路径问题: LeetCode 62.不同路径题目解析解题思路状态表示状态转移方程初始化和填表返回值 代码实现总结 62. 不同路径 题目解析 (1) 机器人从左上角到右下角有多少方法 (2) 机器人只能向左或者向右…

C++中浅复制及其存在的问题

C中浅复制及其存在的问题 之前的示例程序中 MyString 类包含一个指针成员 buffer&#xff0c;它指向动态分配的内存&#xff08;这些内存是在构造函数中使用 new 分配的&#xff0c;并在析构函数中使用 delete[]进行释放&#xff09;。复制这个类的对象时&#xff0c;将复制其…

解决Visual Studio Code 控制台中文乱码问题

C和CPP运行编码指定 "code-runner.executorMap": {"c": "cd $dir && gcc -fexec-charsetGBK $fileName -o $fileNameWithoutExt && $dir$fileNameWithoutExt","cpp": "cd $dir && g -fexec-charsetGBK $…

LVGL_多界面切换

LVGL_多界面切换 1、创建多个界面&#xff08;create_page1();&#xff09; 2、加载一个界面显示&#xff08;lv_scr_load(page1);&#xff09; 3、切换不同界面显示&#xff08;lv_scr_load_anim(page2, LV_SCR_LOAD_ANIM_OVER_LEFT, 300, 0, false);&#xff09; static lv_…

java的几种对象: PO,VO,DAO,BO,POJO

概述 对象释意使用备注PO&#xff08;persistant object&#xff09;持久对象可以看成是与数据库中的表相映射的Java对象&#xff0c;最简单的PO就是对应数据库中某个表中的一条记录。PO中应该不包含任何对数据库的操作VO&#xff08;view object&#xff09;表现层对象主要对…
最新文章