重构字符串Java版（力扣）

重构字符串：
给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。
若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:
输入: S = “aab”
输出: "aba"

示例 2:
输入: S = “aaab”
输出: ""

注意:
S 只包含小写字母并且长度在[1, 500]区间内。

题意：一个字符串，看是否可以重新排列后使相邻的两个字符不相等，如果可以输出重新排列的字符串，如果不可以输出空字符串。
思路：如果出现的次数最多的那个字符的个数大于字符串长度的一半就不可能重新排列成满足要求的字符串。如果小于一半就可以重新排列达到要求，先把出现次数最多那个字符从0开始放到结果数组的偶数位，然后接着填充剩余的部分，让下标一直加，如果下标超过了结果数组的长度，就让下标从1开始继续填充。

假设S="aaaabbbccdef"
结合着图和下面的代码看更好理解
填充过程如下图（手绘很丑，见谅！）

代码：

package com.Keafmd.day30;


import java.util.*;

import static java.lang.Integer.max;

/**
 * Keafmd
 *
 * @ClassName: ReorganizeString
 * @Description: 重构字符串
 * @Author: 牛哄哄的柯南
 * @Date: 2020/11/30 19:57
 **/
public class ReorganizeString { /*给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。 若可行，输出任意可行的结果。若不可行，返回空字符串。*/ public static void main(String[] args) { Solution solution = new Solution(); String str = "aaaabbbccdef"; String re = solution.reorganizeString(str); System.out.println(re); }

}

class Solution { public String reorganizeString(String S) { //把S转为字符数组 char[] ss = S.toCharArray(); //长度 int length = S.length(); //统计每个字符出现的次数 int[] counts = new int[26]; // 结果数组 char[] result = new char[length]; //统计每个字符出现的次数 for (int i = 0; i < length; i++) { counts[ss[i] - 'a']++; } int maxx = 0, theMostFrequentCharacter = 0, maximumNumber = (length + 1) >> 1; // theMostFrequentCharacter 出现次数最多的字符 //找出出现次数最多的那个字符 for (int i = 0; i < counts.length; i++) { if (counts[i] > maxx) { maxx = counts[i]; theMostFrequentCharacter = i; if (maxx > maximumNumber) { return ""; } } } int index = 0; //先把出现次数最多的字符从0开始放到偶数位 while (counts[theMostFrequentCharacter]-- > 0) { result[index] = (char) (theMostFrequentCharacter + 'a'); index += 2; } //把剩下的放到其他位置 for (int i = 0; i < counts.length; i++) { while (counts[i]-- > 0) { if (index >= result.length) { index = 1; } result[index] = (char) (i + 'a'); index += 2; } } return new String(result); }

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
 

运行结果：

abacacadbebf

Process finished with exit code 0

  

 

  
1
  
2
  
3
 

看完如果对你有帮助，感谢点赞支持！
如果你是电脑端，看到右下角的 “一键三连” 了吗，没错点它[哈哈]

加油！

共同努力！

Keafmd

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/110408150