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

leetcode 767. Reorganize String(重组字符串)

在这里插入图片描述
重新排列字符串s中的字母,使得任意两个相邻的字母都不相同。

思路:

让相邻字母不同,能想到的办法是先把相同的字母排列,
然后在相同字母的缝隙中插入另一种字母。
比如"aab", 先把"a a"排出来,再在2个a的缝隙中插入b,得到"aba".

那么就需要统计每个字母出现的次数。
为了让能插入字母的缝隙,排列时中间空一位,也就是先把出现最多的字母放在偶数位,
如果不够放就折回来到奇数位,所以字母出现次数不能超过s长度的一半,
不然折回来就是相同字母了。字母的出现次数超过s一半的直接返回“”。

而且一定要先排出现最多的字母(可以试试example1中先排b)。

可以用一个优先队列按字母出现的次数从大到小排列。然后一一取出排列。
也可以只找到出现次数最多的字母,先排列,再直接按顺序排剩下的。

优先队列:

    public String reorganizeString(String s) {HashMap<Character,Integer> map = new HashMap<>();char[] chs = s.toCharArray();//按字母出现的次数倒序排列PriorityQueue<Character> pq = new PriorityQueue<>((a,b)->(map.get(b)-map.get(a)));char[] res = new char[s.length()];for(char c : chs) {map.put(c, map.getOrDefault(c, 0)+1);}pq.addAll(map.keySet());//出现频率最多的字母多于字符串长度的一半if(map.get(pq.peek()) > (s.length()+1)/2) return "";int i = 0;while(!pq.isEmpty()) {char c = pq.poll();for(int j = 0; j < map.get(c); j++) {if(i >= s.length()) i = 1;  //偶数位放满,开始放奇数位res[i] = c;i += 2;}}return new String(res);}

只先排出现次数最多的,剩下的按顺序排。此方法更快。

    public String reorganizeString(String s) {int[] cnt = new int[26];char[] chs = s.toCharArray();int n = chs.length;char[] res = new char[n];for(int i = 0; i < n; i++) cnt[chs[i]-'a']++;//找到出现次数最多的字母和次数int maxCnt = 0;int freqCh = 0;for(int i = 0; i < 26; i++) {if(cnt[i] > maxCnt) {maxCnt = cnt[i];freqCh = i;}}if(maxCnt > (n+1)/2) return "";//先排出现最多的字母,不然可能会出现奇数位和偶数位是同一字母的情况int idx = 0;while(cnt[freqCh] > 0) {res[idx] = (char)(freqCh + 'a');idx += 2;cnt[freqCh] --;}for(int i = 0; i < 26; i++) {while(cnt[i] > 0) {if(idx >= n) idx = 1;res[idx] = (char)(i+'a');idx += 2;cnt[i] --;}}return new String(res);}

相关文章:

leetcode 767. Reorganize String(重组字符串)

重新排列字符串s中的字母&#xff0c;使得任意两个相邻的字母都不相同。 思路&#xff1a; 让相邻字母不同&#xff0c;能想到的办法是先把相同的字母排列&#xff0c; 然后在相同字母的缝隙中插入另一种字母。 比如"aab", 先把"a a"排出来&#xff0c;再…...

java八股文面试[数据结构]——List和Set的区别

List和Set是用来存放集合的接口&#xff0c;并且二者都继承自接接口Collection List 中的元素存放是有序的&#xff0c;可以存放重复的元素&#xff0c;检索效率较高&#xff0c;插入删除效率较低。 Set 没有存放顺序不能存放重复元素检索效率较低&#xff0c;插入删除效率较…...

脑机接口里程碑!一天2篇Nature!

2023年8月23日&#xff0c;《Nature》期刊一口气发表了两项独立的脑机接口方向的研究。 一项来自加州大学旧金山分校华裔科学家张复伦团队&#xff0c;另一项来自斯坦福大学的神经科学家弗朗西斯威利特(Francis Willett)团队。两项研究都旨在帮助那些因脑损伤和疾病而失去语言能…...

C语言strchr函数

描述 strchr函数用于在一个字符串中查找某个字符的第一次出现的位置。 函数的声明&#xff1a; char * strchr(const char *s, int c); 其中&#xff0c;s是要进行查找的字符串&#xff0c;c是要查找的字符。函数返回指向第一次出现字符 c 的指针&#xff0c;如果未找到&…...

Linux下的Shell基础——Shell概述和入门(一)

前言&#xff1a; Shell还是一个功能相当强大的编程语言&#xff0c;易编写、易调试、灵活性强。为了方便后续的学习&#xff0c;我们需要学习在Linux系统下的Shell编程 目录 一、Shell概述 1.Linux 提供的 Shell 解析器有 2. 默认的解析器是 bash 二、Shell 脚本入门 1.脚…...

当你在浏览器中输入了网址访问时产生了哪些技术步骤

当你在浏览器中输入了网址访问时产生了哪些技术步骤 前段时间在知乎上了看一些网络方面的知识&#xff0c;刚好小编自己也是从事这一块的相关工作由对网络方面有一定的了解。今天我们来讲讲&#xff0c;当你在浏览器中输入本站域名并回车后&#xff0c;这背后到底发生来什么事…...

嵌入式Linux人脸检测libfacedetection

人脸检测 此库依赖Opencv&#xff0c;所以首先要移植Opencv到板子上。 笔者使用LVGL搭建了一个界面&#xff0c;界面有些卡顿&#xff08;主要原因是文件存取较慢&#xff09;&#xff0c;演示效果如下&#xff1a; OpenCV 首先要交叉编译Opencv 参考&#xff1a;https://…...

Hugo托管到Github Pages

Github通过其Github Pages服务可以user、project或organization提供免费快速的静态托管&#xff0c;同时使用Github Actions自动化开发工作流和构建。 1.创建Github仓库 可见性为public。 命名为username.github.io&#xff0c;username为你的Github用户名。 2.添加远程仓库…...

Python经典面试题——在txt里面添加字段和数据

1. 问题&#xff1a; 如何在txt中实现第一行的字段加一个"test",如果第二行开始有数据&#xff0c;在每条数据的最后加"ok" 2.条件 提供的txt文本如下 时间--地区--人口---降雨量----- 20220101--北京--200--0.5----- 20230101--成都--100--0.55----- …...

【观察】打造以AI为导向的基础设施,联想锚定AI算力“主航道”

毫无疑问&#xff0c;人工智能对人类社会来说并不是一项简单的技术革命&#xff0c;它象征着一个时代的到来&#xff0c;如同工业时代之于农业时代一样&#xff0c;会带来天翻地覆的变革&#xff0c;影响人类社会百年、甚至千年的进程。 而AI算力对于推动人工智能应用的重要性毋…...

预防缓存穿透工具类

1. 前言 缓存穿透大家都知道&#xff0c;这里简单过一下 缓存和数据库中都没有的数据&#xff0c;而用户不断发起请求。比如查询id -1 的值 想着很多面向C端的查询接口&#xff0c;可能都需要做一下缓存操作&#xff0c;这里简单写了个自定义注解&#xff0c;将查询结果(包含…...

会员管理系统实战开发教程04-会员开卡

我们已经用3篇篇幅介绍了会员管理的功能&#xff0c;接着就要开发会员的业务。通常我们开通会员之后需要给会员开通会员卡&#xff0c;一个会员可以有多张会员卡。 在数据源设计的时候&#xff0c;像这种一个会员有多张会员卡的&#xff0c;我们称之为一对多的关系&#xff0c…...

数据结构(2)

冒泡排序&#xff1a; 1.比较相邻的两个元素。如果前一个元素比后一个元素大&#xff0c;则交换两者位置。 2.对每一对相邻元素做相同工作&#xff0c;从第一对元素到最后一对元素&#xff0c;最后的一个元素就是最大的元素。 for(int ia.length-1;i>0;i--){for (int j 0…...

使用ELK(ES+Logstash+Filebeat+Kibana)收集nginx的日志

文章目录 Nginx日志格式修改配置logstash收集nginx日志引入Redis收集日志写入redis从redis中读取日志 引入FilebeatFilebeat简介Filebeat安装和配置 配置nginx转发ES和kibanaELK设置账号和密码 书接上回&#xff1a;《ELK中Logstash的基本配置和用法》 Nginx日志格式修改 默认…...

TDengine server连接遇到的坑

一、TDengine安装 TDengine目前只有linux版本的server端&#xff0c;安装教程参考 https://zhuanlan.zhihu.com/p/302413259 二、TDengine连接 TDengine连接目前支持两种方式&#xff0c;一种是原生连接&#xff0c;该方法的默认端口号为6030&#xff1b;另一种是REST API连…...

什么是NetDevOps

NetDevOps 是一种新兴的方法&#xff0c;它结合了 NetOps 和 DevOps 的流程&#xff0c;即将网络自动化集成到开发过程中。NetDevOps 的目标是将虚拟化、自动化和 API 集成到网络基础架构中&#xff0c;并实现开发和运营团队之间的无缝协作。 开发运营&#xff08;DevOps&…...

中小金融机构数字化转型最大的挑战是什么?

中国银保监会办公厅印发的《关于银行业保险业数字化转型的指导意见》强调&#xff0c;银行保险机构要加强顶层设计和统筹规划&#xff0c;科学制定数字化转型战略&#xff0c;统筹推进工作&#xff0c;并从战略规划与组织流程建设、业务经营管理数字化、数据能力建设、科技能力…...

Facebook HiPlot “让理解高维数据变得容易”

在这个全球信息化的时代&#xff0c;数据量呈爆炸式增长&#xff0c;数据的复杂性也是如此。如何有效地处理高维数据并找到隐藏在其中的相关性和模式是一个严峻的挑战。近年来&#xff0c;可视化和可视化分析已被应用于该任务&#xff0c;并取得了一些积极成果。Facebook的新Hi…...

【python】:python新设备环境移植(requirements.txt)

环境移植 condapip conda 你可以使用conda命令来创建一个包含所有已安装包的requirements.txt文件&#xff0c;并将其复制到新电脑上。然后&#xff0c;你可以在新电脑上使用pip命令来安装这些包及其依赖项。 以下是一个示例命令&#xff1a; conda list --export > requ…...

分类预测 | MATLAB实现1D-2D-CNN-GRU的多通道输入数据分类预测

分类预测 | MATLAB实现1D-2D-CNN-GRU的多通道输入数据分类预测 目录 分类预测 | MATLAB实现1D-2D-CNN-GRU的多通道输入数据分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 结合1D时序-2D图像多模态融合的CNN-GRU故障识别算法&#xff0c;基于一维时序信号和二维图…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南

在RK3588上搭建ROS1环境:创建节点与数据可视化实战指南 背景介绍完整操作步骤1. 创建Docker容器环境2. 验证GUI显示功能3. 安装ROS Noetic4. 配置环境变量5. 创建ROS节点(小球运动模拟)6. 配置RVIZ默认视图7. 创建启动脚本8. 运行可视化系统效果展示与交互技术解析ROS节点通…...