767. Reorganize String_bohu83的博客-程序员宝宝

技术标签: 贪婪算法  算法  字符串  数组  排序法  leetcode  LeetCode  

Given a string S, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result.  If not possible, return the empty string.

Example 1:

Input: S = "aab"
Output: "aba"

Example 2:

Input: S = "aaab"
Output: ""

Note:

  • S will consist of lowercase letters and have length in range [1, 500].

二 分析

看着很短,实际上真难。我一开始这么想的。从前到后交换下顺序嘛?后来发现行不通,因为字符串可能不是顺序的vv,遇到这种case:vvvlo 拍序后lovvv搞不定啊,于是放弃。再换个思路:我先遍历一遍,找出次数最大的字母,然后依次为准,去生成新字符串,最后追加剩余的字符。

 public static String reorganizeString(String S) {
		 if(S== null || S.equals("")||S.length()==0 ){
			 return "";
		 }
		 int length = S.length();
		 Map<Character,Integer> map = new HashMap<Character,Integer>(); 
		 //先遍历一遍,找出出现最多的字母		
		for(char c:S.toCharArray()){
			if(map.containsKey(c)){
				int tmp = map.get(c);
				map.put(c, ++tmp);
			}else{
				map.put(c, 1);
			}
		}
		int max =0;
		char maxc =S.charAt(0);
		 for (Character key : map.keySet()) {			
			if(map.get(key)>max){
				max = map.get(key);
				maxc = key;
			}
		}
		String left = S.replaceAll(maxc+"", "");
		char[] lefts =  left.toCharArray();
		int tmplength = map.get(maxc);
		//太长了
		if(tmplength>((length+1)/2)){
			return "";
		}
		
		String result = "";
		 for(int i=0;i<tmplength;i++ ){
			 if(i<left.length() ){
				 result += maxc+""+ lefts[i]+"";
				 
			 }else{
				 result += maxc+"";
			 }
			 
		 }
		 if (tmplength< left.length() ) {
			 left = left.substring(tmplength);
			 result  += left; 
		}
		
			 
		 return result;   
	}

很快就卡住了。eqmeyggvp,还有这种:"nlmxhnpifuaxinxpxlcttjnlggmkjioewbecnofqpvcikiazmn"。

贪婪算法

以上发现,只取最大值是不行的,除了最大值之外后面还有可能出现多个>=2的(就是连着的)。还是要统计出字母出现的次数,这样形成字母与次数的对应关系(同时判断下如果某个字母出现的频率大于总长度的一半了,那么必然会有两个相邻的字母出现,这可以用鸽巢原理来解释),字母已经去重过了,这样相邻的两个也会不同。单纯使用map去迭代不太方便,还是希望出现多的放在前面,由此引入了优先级队列(最大堆),之前类似的Min Cost to Connect Ropes问题已经有最小堆:(使用完之后可以放回再排序根据条件使用)。

    这里也是一个思路,吧map计算完的结果放入优先级队列,取出两个字母。对应的次数-1,如果还有剩余的次数》0,就在放回队列重新获取。这样如果两两的获取,如果还有剩余,就追加到结果字符串。

package leetcode.str;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
//bohu83
public class ReorganizeStringTest {

	public static void main(String[] args) {
	   String s ="eqmeyggvp";
	   System.out.println(reorganizeString(s));
       String s1 ="nlmxhnpifuaxinxpxlcttjnlggmkjioewbecnofqpvcikiazmn";
       System.out.println(reorganizeString(s1));
       String s2 ="bfrbs";
       System.out.println(reorganizeString(s2));
	}

	
	 public static String reorganizeString(String S) {
		 if(S== null || S.equals("")||S.length()==0 ){
			 return "";
		 }
		 int length = S.length();
		 Map<Character,Integer> map = new HashMap<Character,Integer>(); 
		 //先遍历一遍,找出出现最多的字母		
		for(char c:S.toCharArray()){
			if(map.containsKey(c)){
				int tmp = map.get(c);
				tmp = tmp+1;				
				map.put(c, tmp);
				if(tmp>(length+1)/2 ){
					return "";
				}
			}else{
				map.put(c, 1);
			}
		}

		 PriorityQueue<Node> queue = new PriorityQueue<>(length, new Comparator<Node>() {
	            @Override
	            public int compare(Node o1, Node o2) {
	                return o2.count - o1.count;
	            }
	        });
		 for (Character key : map.keySet()) {	
			int num = map.get(key);
			queue.offer(new Node(key,num));
		}
		 StringBuilder res = new StringBuilder();
		while(queue.size()>=2){
			Node c1 = queue.poll();
			Node c2 = queue.poll();
			res.append(c1.c);
			res.append(c2.c);
			c1.count--;
			c2.count--;
			if(c1.count>0 ) queue.offer(c1);
			if(c2.count>0) queue.offer(c2);			
		}
		//剩余拼上
		if(queue.size()>0){
			res.append(queue.poll().c);
		}
		
		 return res.toString() ;   
	}
	
}
class Node {
    char c;
    int count;

    Node(char c, int count) {
        this.c = c;
        this.count = count;
    }
}

Runtime: 4 ms, faster than 69.37% of Java online submissions for Reorganize String.

Memory Usage: 34.5 MB, less than 92.86% of Java online submissions forReorganize String.

Complexity Analysis

  • Time Complexity: O(N \log{\mathcal{A}}))O(NlogA)), where NN is the length of SS, and \mathcal{A}A is the size of the alphabet. If \mathcal{A}A is fixed, this complexity is O(N)O(N).

  • Space Complexity: O(\mathcal{A})O(A). If \mathcal{A}A is fixed, this complexity is O(1)O(1).

 

差值法

官网的solution代码就优秀多了。不是一个level。真的厉害。

class Solution {
    public String reorganizeString(String S) {
        int N = S.length();
        //[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        int[] counts = new int[26];
        // 计数[0, 0, 0, 0, 200, 0, 200, 0, 0, 0, 0, 0, 100, 0, 0, 100, 100, 0, 0, 0, 0, 100, 0, 0, 100, 0]
        for (char c: S.toCharArray()) counts[c-'a'] += 100;
       //为后面的排序准备,次数相同的按照字母顺序先后 [0, 1, 2, 3, 204, 5, 206, 7, 8, 9, 10, 11, 112, 13, 14, 115, 116, 17, 18, 19, 20, 121, 22, 23, 124, 25]
        for (int i = 0; i < 26; ++i) counts[i] += i;
        //Encoded counts[i] = 100*(actual count) + (i)
        //替代了优先级队列 ,用一个数实现了字母-次数的关系
        Arrays.sort(counts);

        char[] ans = new char[N];
        int t = 1;//从第二个位置开始,因为次数最大的字母在第一个
        for (int code: counts) {
            //decode求次数
            int ct = code / 100;
            //decode求字母
            char ch = (char) ('a' + (code % 100));
            //判断是否不然出现相连字母一致 
            if (ct > (N+1) / 2) return "";
            for (int i = 0; i < ct; ++i) {
                if (t >= N) t = 0;//越界了从0开始,相当于偶数位
                ans[t] = ch;
                //每次跨两个位置去隔位更新,一开始及奇数位,再次循环就是偶数位
                t += 2;
            }
        }

        return String.valueOf(ans);
    }
}

Complexity Analysis

  • Time Complexity: O(\mathcal{A}(N + \log{\mathcal{A}}))O(A(N+logA)), where NN is the length of SS, and \mathcal{A}Ais the size of the alphabet. In Java, our implementation is O(N + \mathcal{A} \log {\mathcal{A}})O(N+AlogA). If \mathcal{A}A is fixed, this complexity is O(N)O(N).

  • Space Complexity: O(N)O(N). In Java, our implementation is O(N + \mathcal{A})O(N+A).

 

可以看到他不用hashmap来计数,而是使用了长度为26的一位数组counts来代替,很巧妙的利用了差值算出字母与a的相对距离。次数用一个整数的高位(这里是100),位置用低位(+i),这样来替代了hashmap的字母-数字键值对,这属于encode步骤,而且之后decode也很方便。数组数值确认之后,用了数组的排序替代了上面算法的优先级队列实现堆排序。

   每行代码都很牛逼,后面的decode跟前面encode对应,也是判断了是否单个字母超长产生相邻一致的情况。更加牛的地方是生成过程中,从1开始(因为默认一开始字母是最大的),进行隔位更新。然后越界后认为奇数次已经填完,再从0开始,处理偶数位。大神就是不一样,用了我不到一半的代码,速度却快多了。而且我那个那么不堪的代码,也不是一气写完的,其实也是写了半天,调整了几次才过。

  感兴趣的可以看看官网的详细介绍:强烈推荐,你值得拥有。天天搬砖头写增删改查,让人眼前一亮的代码真的很少。

https://leetcode.com/problems/reorganize-string/solution/

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/bohu83/article/details/98975545

智能推荐

比特币国内全节点IP_yzpyzp的博客-程序员宝宝_比特币ip地址

以上节点含有完整的区块数据。参考: 最新国内全节点IP数据

scrapy分布式的应用学习笔记(一)_编程_人生的博客-程序员宝宝

1. 创建项目,在项目目录执行命令 scrapy startproject webbot 生成下面的目录和文件 scrapy.cfg: 项目配置文件webbot//: 项目的 python 源代码 modulewebbot//items.py: 定义 item 类,用来存储爬取的数据.webbot//pipelines.py: pipelines文件,定义清洗,处理数据的类webbot

快速学会!2021Android精选面试实战总结整理,附大厂真题面经_程序员大婕的博客-程序员宝宝

前言IT行业薪水高,这是众所周知的,所以很多人大学都选择IT相关专业,即使非该专业的人,毕业了也想去一个培训机构镀镀金,进入这一行业。但是有关这个行业35岁就退休的说法,也一直盛传。加上这几年不断有各大公司裁员,最著名的就是华为,35岁以上的被剔除的甚多。但是这都是被媒体放大的数据,真实情况往往不是表面看到的那样残酷。很多在这方面有能力的人,30岁之前可以频繁跳槽,30岁之后找一个稳定的跟自己投缘的大企业,你为企业带来的价值大于企业给予你的付出,你的职位肯定是稳稳的。而且上升趋势也不错。一般到了

QT随机生成验证码 四位数字并 禁止编辑的方法_-ypchen的博客-程序员宝宝

// 随机生成数字int Widget::generateRandomNumber(){qsrand(QTime(0,0,0).secsTo(QTime::currentTime()));for(int i=0; i&lt;4; i++){int test =qrand();return test;}return 0;}//数字转换为qstring 4位数int i=this-&gt;generateRandomNumber();QString b=QString("%1").ar

xpython实战_python实战笔记(一)_weixin_39630440的博客-程序员宝宝

[Python注释][Python变量][Python运算符][Python输入输出]* [输入函数]* [输出函数(3.x)]* [格式化输出][分支][循环]### Python注释#### 单行注释```# 这是一个单行注释print("test")```#### 多行注释```'''这里就是python的多行注释方式可以直接分行进行注释操作本质上是字符串'''import th...

JupyterNotebook的.ipynb_checkpoints文件版本控制保存机制_weixin_44322234的博客-程序员宝宝_ipynb_checkpoints

每当你创建一个新的 notebook 时,都会创建一个检查点文件以及你的 notebook 文件;它将位于你保存位置的隐藏子目录中称作 .ipynb_checkpoints,也是一个 .ipynb 文件。默认情况下,Jupyter 将每隔 120 秒自动保存你的 notebook,而不会改变你的主 notebook 文件。当你“保存和检查点”时,notebook 和检查点文件都将被更新。因此,检查点使你能够在发生意外事件时恢复未保存的工作。你可以通过 “File &gt; Revert to Checkpo

随便推点

【MVVM】Data Binding高级用法-Observable、动态生成Binding Class(三)_Session__csdn的博客-程序员宝宝

设置View的id虽然说Data Binding这种分层模式使得我们对数据的传递简单明了,一般情况下我们可以不设置View的id,不使用findViewById即可对View进行数据上一系列的操作,不过有时候根据情况我们需要对某些View设置id,但是还是可以不findViewById即可得到该控件的对象,因为设置id后ViewDataBinding类会自动生成对应的控件对象,如:la

通过Nginx实现前后分离的项目部署_AI-0的博客-程序员宝宝_nginx 前后分离

通过Nginx实现前后分离的项目部署前言一、安装Nginx1、下载源码2、安装Nginx编译依赖库3、编译安装4、补充二、配置WebApi服务1、启动springboot项目2、配置nginx.conf3、启动测试三、打包上传Vue项目到Nginx1、打包上传2、补充总结前言项目使用springboot作为后端,vue为前端开发,简述一下项目的部署方式,操作系统为CentOS7一、安装NginxNginx是一款用途广泛,而且非常受欢迎的服务器,可用用它做应用的负载均衡,反向代理等1、下载源码.

Netty学习笔记(六)Springboot实现基于http协议的简单服务器---浏览器和客户端访问_香菇青菜包的博客-程序员宝宝

转载至 https://blog.csdn.net/wangshuang1631/article/details/73251180上代码建服务器启动类EchoServer public class EchoServer { private final int port; private Logger log = LoggerFactory.getLogger(this.getClas...

数据库之事务及事务的 ACID 性质_大前端之旅的博客-程序员宝宝

1.什么是事务DBMS中的事务是一系列的数据库操作,是数据库应用程序的基本逻辑单元事务的基本概念所谓事务是用户定义的一个数据库操作序列,这些操作要么都做,要么都不做,是一个不可分割的工作单位。在关系数据库中,事务可以是一条SQL语句、一组SQL语句。事务通常由高级数据操纵语言或编程语言(如SQL、COBOL、C、C++或Java)书写的用户程序的执行所引起,由事务开始与结束之间执行的全体操...

RMAN 备份恢复系列之controlfile恢复_kevin-ke的博客-程序员宝宝

RMAN备份恢复系列之controlfile 控制文件的恢复

推荐文章

热门文章

相关标签