湘潭网站建站公司,网站页面优化内容包括哪些,南昌网站维护,网站使用教程想了解更多数据结构以及算法题#xff0c;可以关注微信公众号“数据结构和算法”#xff0c;每天一题为你精彩解答。问题描述给定一个字符串S#xff0c;检查是否能重新排布其中的字母#xff0c;使得两相邻的字符不同。若可行#xff0c;输出任意可行的结果。若不可行可以关注微信公众号“数据结构和算法”每天一题为你精彩解答。问题描述给定一个字符串S检查是否能重新排布其中的字母使得两相邻的字符不同。若可行输出任意可行的结果。若不可行返回空字符串。示例 1:输入: S “aab”输出: “aba”示例 2:输入: S “aaab”输出: “”注意:S 只包含小写字母并且长度在[1, 500]区间内。问题分析这题是让重新排布字符串S中的字符让任何两个相邻的字符都不相同如果能做到就返回排布后的字符串如果做不到就返回空字符串。如果要使得两相邻的字符不同那么出现次数最多的那个数的数量必须满足下面条件如下图所示比如下面的a是出现次数最多的这个时候a的数量已经达到了临界值如果再多一个a那么至少有两个a是相邻的。所以这里出现次数最多的那个字符数量的临界值是threshold (length 1) 1(其中 length 是字符串的长度)如果能使得两相邻的字符不同我们可以先把出现次数最多的那个字符放到新数组下标为偶数的位置上也就是从数组的第一个位置开始放放完之后在用其他的字符填充数组剩下的下标为偶数的位置如果下标为偶数的位置都填满了我们就从下标为1开始也就是数组的第2个位置开始填下标为奇数的位置。注意这里能不能先把出现次数最多的字符放到字符串下标为奇数的位置呢当然是不可以的。比如我们上面举的例子abacaba本来是可以满足的如果放到下标为奇数的位置最后一个 a 就没法放了除非放到最前面那又变成了放到下标为偶数的位置了。代码如下public String reorganizeString(String S) { //把字符串S转化为字符数组 char[] alphabetArr S.toCharArray(); //记录每个字符出现的次数 int[] alphabetCount new int[26]; //字符串的长度 int length S.length(); int max 0, alphabet 0, threshold (length 1) 1; //找出出现次数最多的那个字符 for (int i 0; i length; i) { alphabetCount[alphabetArr[i] - a]; if (alphabetCount[alphabetArr[i] - a] max) { max alphabetCount[alphabetArr[i] - a]; alphabet alphabetArr[i] - a; //如果出现次数最多的那个字符的数量大于阈值 // 说明他不能使得两相邻的字符不同 // 直接返回空字符串即可 if (max threshold) return ; } } //到这一步说明他可以使得两相邻的字符不同 // 我们随便返回一个结果res就是返回 //结果的数组形式最后会再转化为字符串的 char[] res new char[length]; int index 0; //先把出现次数最多的字符存储在数组下标为偶数的位置上 while (alphabetCount[alphabet]-- 0) { res[index] (char) (alphabet a); index 2; } //然后再把剩下的字符存储在其他位置上 for (int i 0; i alphabetCount.length; i) { while (alphabetCount[i]-- 0) { //如果偶数位置填完了我们就让index从1开始 // 填充下标为奇数的位置 if (index res.length) { index 1; } res[index] (char) (i a); index 2; } } return new String(res);}总结这题直接判断比较简单我们只需要统计出出现次数最多的字符即可。但这题还要返回结果所以最简单的方式就是把出现次数最多的字符从数组的第一个位置开始放每隔一个放一次。放完之后再用其他的字符从后面接着放也是每隔一个如果超出数组之后再从数组的第2个位置开始放也是每隔一个这样就能保证结果一定不会出错并且也少了很多的判断。