LeetCode 767. Reorganize String

Stella981
• 阅读 677

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].

本题首先要想明白的一点:什么情况会不成立即返回空。

通过观察可以看出:出现次数最多的字母个数 - 1 > 其他所有字母出现次数和

此时必有两个出现次数最多的字母连在一起。

反之,必能形成一个隔一个的情形。

我的代码比较长,就意识到不是最简单的做法,不过很好理解。

解释其中必要参数和函数:

int [] table = new int [26]; // 确定每个字母出现次数

int [] judge = new int [26]; // 确定是否能形成一个隔一个的情形

int count = 0; // 统计除出现次数最多的字母其他字母出现次数和

int place = 0; // 这个参数比较重要,用于确定下一个字母应该插入在字符串的哪个位置

public static int find_max(int[] a){} // 返回出现次数最多的字母对应的数组位置

之后的思想就是往res中插入字母,先把出现次数最多的字母放上去,然后向其中插入其他字母,当place到最后一个位置时回到初始位置。

代码如下:

class Solution {
    
    public static int find_max(int[] a){
        int flag = 0;
        for(int i = 0; i < a.length; i++){
            if(flag <= a[i]) flag = a[i];
        }
        int j = 0;
        for(j=0;j<a.length;j++){
            if(flag == a[j]) break;
        }
        return j;
    }
    public String reorganizeString(String a) {
        char[] ch = a.toCharArray();
        int [] table = new int[26];
        int [] judge = new int[26];
        String res = "";
        int num = 0;
        
        for (int i = 0; i < a.length(); i++) {
            table[ch[i] - 'a']++;
            judge[ch[i] - 'a']++;
        }
        
        Arrays.sort(judge);
        int count = 0;
        for(int i = judge.length-2; i >= 0; i--){
            count += judge[i];
        }
        //System.out.println(count);
        if (judge[judge.length-1] - 1 > count) {
            //System.out.println(false);
            return res;
        }
        //for(int  i=0;i<table.length;i++) System.out.println(table[i]);
        for (int i = 0; i < table.length; i++) {
            if(table[i] != 0) num++;
        }
        int place = 1;
        for(int i = 0; i < num; i++){
            int x = find_max(table);
            //System.out.println(x);
//            if(place > res.length() - 1) {
//                System.out.println("run");
//                place = 1;
//            }
            if(res.length() == 0){
                while(table[x] != 0){
                    char q = (char) (x + 'a');
                    res += q;
                    table[x]--;
                }
            }else{
                while(table[x] != 0){
                    if(place > res.length()) place = 1;
                    //System.out.println(place);
                    if(place <= res.length() ){
                        StringBuilder sb = new StringBuilder(res);
                        sb.insert(place, (char)(x + 'a'));
                        res = sb.toString();
                        table[x] --;
                        place = place + 2;
                        //System.out.println(res);
                        //System.out.println("此时place:"+place+"而res长度:"+res.length());
                    }
                }
                
            }
            //System.out.println(res);
        }
        return res;
        //System.out.println(res);
    }
}

声明:该方法只是作者自己的写法,并不是最好的做法,如有更好的方法望在评论区给出。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
2个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
2年前
Java获得今日零时零分零秒的时间(Date型)
publicDatezeroTime()throwsParseException{    DatetimenewDate();    SimpleDateFormatsimpnewSimpleDateFormat("yyyyMMdd00:00:00");    SimpleDateFormatsimp2newS
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
2年前
HIVE 时间操作函数
日期函数UNIX时间戳转日期函数: from\_unixtime语法:   from\_unixtime(bigint unixtime\, string format\)返回值: string说明: 转化UNIX时间戳(从19700101 00:00:00 UTC到指定时间的秒数)到当前时区的时间格式举例:hive   selec
Wesley13 Wesley13
2年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
8个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这