重构字符串(767)
767. 重构字符串 - 力扣(LeetCode)
解法:
class Solution {
public:string reorganizeString(string s){string res;//因为1 <= s.length <= 500 , uint64_t 类型足够uint16_t n = s.size();if (n == 0) {return res;}unordered_map<char, uint16_t> m;for (auto c : s) {m[c] += 1;}vector<pair<char, uint16_t>> v(m.begin(), m.end());//构建最大堆auto compare_f = [](const pair<char, uint16_t> & i1,const pair<char, uint16_t> & i2){return i1.second < i2.second;};//按照key-value : letter-count,按照count构建最小堆priority_queue<pair<char, uint16_t>, std::vector<pair<char, uint16_t>>, decltype(compare_f)> q (v.begin(), v.end(), compare_f);auto & i = q.top();//如果一个letter,其counter大于一半以上,则肯定无法构建if ((((n & 1) == 1) && (i.second > n/2 + 1)) ||(((n & 1) == 0) && (i.second > n/2))){return res;}//贪心法,每次从优先队列里面取出count最大的元素while (!q.empty()) {auto i = move(q.top());q.pop();if (res.size() > 0 && res.back() == i.first) {//如果letter相同,则再取出次多的auto j = move(q.top());q.pop();res += j.first;j.second -= 1;//如果letter count 大于0,则继续插回队列if (j.second > 0) {q.push(j);}}res += i.first;i.second -= 1;//如果letter count 大于0,则继续插回队列if (i.second > 0) {q.push(i);}}return res;}
};
总结:时间复杂度O(N2logN),空间复杂度O(N),应用到了最小堆、贪心算法。
相关文章:
重构字符串(767)
767. 重构字符串 - 力扣(LeetCode) 解法: class Solution { public:string reorganizeString(string s){string res;//因为1 < s.length < 500 , uint64_t 类型足够uint16_t n s.size();if (n 0) {return res;}unordere…...
IO进程线程复习
IO进程线程复习...
深入理解Linux内核的虚拟地址到物理地址转换机制及缓存优化
在现代计算机系统中,虚拟地址到物理地址的转换是操作系统内存管理的重要组成部分。特别是在基于x86_64架构的Linux系统上,这一转换过程及其相关的缓存机制对系统性能和稳定性至关重要。本文将深入探讨Debian 10上运行Linux 4.19内核时,这些机制的实现细节,特别是页表管理、…...
2025年01月29日Github流行趋势
项目名称:Janus 项目地址url:https://github.com/deepseek-ai/Janus项目语言:Python历史star数:9350今日star数:5969项目维护者:learningpro, hills-code, TheOneTrueGuy, mowentian, soloice项目简介&…...
yolov11、yolov8部署的7种方法(yolov11、yolov8部署rknn的7种方法),一天一种部署方法,7天入门部署
由于涉及量化、部署两个领域,本博文难免有不对之处,欢迎指正。 本博客对 yolov11(yolov8)尝试了7种不同的部署方法,在最基础的模型上一步一步的去掉解码相关的操作(移到后处理种进行)࿰…...
【ArcGIS遇上Python】批量提取多波段影像至单个波段
本案例基于ArcGIS python,将landsat影像的7个波段影像数据,批量提取至单个波段。 相关阅读:【ArcGIS微课1000例】0141:提取多波段影像中的单个波段 文章目录 一、数据准备二、效果比对二、python批处理1. 编写python代码2. 运行代码一、数据准备 实验数据及完整的python位…...
Node.js MySQL:深度解析与最佳实践
Node.js MySQL:深度解析与最佳实践 引言 Node.js作为一种流行的JavaScript运行时环境,以其轻量级、高性能和事件驱动模型受到开发者的青睐。MySQL则是一款功能强大的关系型数据库管理系统,广泛应用于各种规模的应用程序中。本文将深入探讨Node.js与MySQL的集成,分析其优势…...
wordpress外贸独立站常用询盘软件
LiveChat LiveChat是一家提供实时聊天软件的公司,帮助企业通过其平台与客户进行即时通讯,提高客户满意度和忠诚度。他们的产品允许企业在网站、应用程序或电子邮件等多个渠道与客户互动,从而提升客户体验并促进销售增长。 LiveChat的软件特…...
Kotlin 委托详解
Kotlin 委托详解 引言 Kotlin 作为一种现代化的编程语言,在 Android 开发等领域得到了广泛的应用。在 Kotlin 中,委托(Delegation)是一种强大的特性,它可以让我们以更简洁的方式实现代码的复用和扩展。本文将详细解析…...
Cursor 简介:AI 如何改变编程体验
在软件开发领域,效率和质量始终是开发者们追求的目标。随着人工智能技术的飞速发展,编程工具也在不断进化,Cursor 便是这一趋势下的产物。它不仅仅是一个代码编辑器,更是一个集成了 AI 能力的智能编程助手,旨在通过 AI…...
Fiddler(一) - Fiddler简介_fiddler软件
文章目录 一、为什么选择Fiddler作为抓包工具? 二、什么是Fiddler?三、Fiddler使用界面简介四、延伸阅读 一、为什么选择Fiddler作为抓包工具? 抓包工具有很多,小到最常用的web调试工具firebug,大到通用性强大的抓包工具wireshark。为什么使用fid…...
实测数据处理(Wk算法处理)——SAR成像算法系列(十二)
系列文章目录 《SAR学习笔记-SAR成像算法系列(一)》 《wk算法-SAR成像算法系列(五)》 文章目录 前言 一、算法流程 1.1、回波信号生成 2.2 Stolt插值 2.3 距离脉冲压缩 2.4 方位脉冲压缩 2.5 SAR成像 二、仿真实验 2.1、仿真参数…...
P1775 石子合并(弱化版)
P1775 石子合并(弱化版) 题目描述 设有 N ( N ≤ 300 ) N(N \le 300) N(N≤300) 堆石子排成一排,其编号为 1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N 1,2,3,⋯,N。每堆石子有一定的质量 m i ( m i ≤ 1000 ) m_i\ (m_i \le 1000) mi (mi≤…...
一文回顾讲解Java中的集合框架
这篇文章以提问的方式总结回顾下Java中常见的集合框架 Java中的集合框架可以分为两条大的支线:Collection和Map Collection,主要由List、Set、Queue组成; List是有序,可重复的集合,典型代表有封装了动态数组的ArrayList和封装了链…...
多模态论文笔记——NaViT
大家好,这里是好评笔记,公主号:Goodnote,专栏文章私信限时Free。本文详细解读多模态论文NaViT(Native Resolution ViT),将来自不同图像的多个patches打包成一个单一序列——称为Patch n’ Pack—…...
智能小区物业管理系统推动数字化转型与提升用户居住体验
内容概要 在当今快速发展的社会中,智能小区物业管理系统的出现正在改变传统的物业管理方式。这种系统不仅仅是一种工具,更是一种推动数字化转型的重要力量。它通过高效的技术手段,将物业管理与用户居住体验紧密结合,无疑为社区带…...
I2C基础知识
引言 这里祝大家新年快乐!前面我们介绍了串口通讯协议,现在我们继续来介绍另一种常见的简单的串行通讯方式——I2C通讯协议。 一、什么是I2C I2C 通讯协议(Inter-Integrated Circuit)是由Phiilps公司在上个世纪80年代开发的&#…...
护眼好帮手:Windows显示器调节工具
在长时间使用电脑的过程中,显示器的亮度和色温对眼睛的舒适度有着重要影响。传统的显示器调节方式不仅操作繁琐,而且在低亮度下容易导致色彩失真。因此,今天我想为大家介绍一款适用于Windows系统的护眼工具,它可以帮助你轻松调节显…...
MongoDb user自定义 role 添加 action(collStats, EstimateDocumentCount)
使用 mongosh cd mongsh_bin_path mongosh “mongodb://user:passip:port/db”这样就直接进入了对应的db 直接输入: 这样 role “read_only_role" 就获得了3个 action, 分别是 查询,列举集合,集合元数据查询 P.S: 如果没有 …...
mysql学习笔记-数据库其他调优策略
1、如何定位调优问题 用户的反馈(主要) 日志分析(主要) 服务器资源使用监控 数据库内部状况监控 2、调优的维度和步骤 第1步:选择适合的 DBMS 第2步:优化表设计 第3步:优化逻辑查询 第4步&am…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...
Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...
STM32标准库-ADC数模转换器
文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”:输入模块(GPIO、温度、V_REFINT)1.4.2 信号 “调度站”:多路开关1.4.3 信号 “加工厂”:ADC 转换器(规则组 注入…...
