767. 重构字符串

思路分析

代码实现

//给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。 
//
// 若可行，输出任意可行的结果。若不可行，返回空字符串。 
//
// 示例 1: 
//
// 
//输入: S = "aab"
//输出: "aba"
// 
//
// 示例 2: 
//
// 
//输入: S = "aaab"
//输出: ""
// 
//
// 注意: 
//
// 
// S 只包含小写字母并且长度在[1, 500]区间内。 
// 
// Related Topics 堆 贪心算法 排序 字符串 
// 👍 167 👎 0


package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class ReorganizeString {
    public static void main(String[] args) {
        Solution solution = new ReorganizeString().new Solution();
        System.out.println(solution.reorganizeString("zqugrfbsznyiwbokwkpvpmeyvaosdkedbgjogzdpwawwl"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String reorganizeString(String S) {
            int sLength = S.length();
            if (sLength < 2) {
                return S;
            }
            int[] bucket = new int[26];

            for (int i = 0; i < sLength; i++) {
                int index = S.charAt(i) - 'a';
                bucket[index]++;
            }
            int maxIndex = 0;
            for (int i = 1; i < 26; i++) {
                if (bucket[i] > bucket[maxIndex]) {
                    maxIndex = i;
                }
            }
            if (bucket[maxIndex] > (sLength + 1) / 2) {
                return "";
            }
            char[] answer = new char[sLength];
            int i = 0;
            while (bucket[maxIndex] > 0) {
                answer[i] = (char) (maxIndex + 'a');
                i += 2;
                bucket[maxIndex]--;
            }
            for (int j = 0; j < 26; j++) {
                while(bucket[j] > 0){
                    if(i >= sLength){
                        i = 1;
                    }
                    answer[i] = (char) (j + 'a');
                    i += 2;
                    bucket[j]--;
                }
            }
            return String.valueOf(answer);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}

note

这是一篇从Hexo迁移的文章，创建于2020-11-30 19:02:09