題目

重構(gòu)字符串

描述

給定一個(gè)字符串S，檢查是否能重新排布其中的字母液荸，使得兩相鄰的字符不同。
若可行脱篙，輸出任意可行的結(jié)果娇钱。若不可行，返回空字符串绊困。
示例 1:
輸入: S = "aab"
輸出: "aba"
示例 2:
輸入: S = "aaab"
輸出: ""
注意:
S 只包含小寫字母并且長(zhǎng)度在[1, 500]區(qū)間內(nèi)文搂。

題解

閱讀題目我們可以知道當(dāng)其中某個(gè)字母的數(shù)量大于總數(shù)的一半的時(shí)候就不會(huì)有可行的結(jié)果（奇數(shù)時(shí) >(length+1)/2），得到最大數(shù)量的 字母 A,個(gè)數(shù)為N,然后做N-1個(gè)循環(huán)
形成 ABACA 的串秤朗，之后把剩下的 字母插入到串中就好了

代碼

class Solution {
   
    public  String reorganizeString(String S) {
        int[] nums = new int[26];
        int max = 0;
        int index = 0;
        String result = "";
        for (int i = 0; i < S.length(); i++) {
            int num = S.charAt(i) - 'a';
            nums[num]++;
            if (nums[num] > max) {
                max = nums[num];
                index = num;
            }
        }

        if (max > (S.length() + 1) / 2) {
            return "";
        }
        int nowIndex = 0;
        while (nums[index] > 1) {
            if (nowIndex == index || nums[nowIndex] == 0) {
                nowIndex++;
                continue;
            }
            result = result + (char) ('a' + index) + (char) ('a' + nowIndex);
            System.out.println(result);
            nums[index]--;
            nums[nowIndex]--;
        }
        result = result + (char) ('a' + index);
        nums[index]--;
        System.out.println(result);
        for (; nowIndex < 26; nowIndex++) {
            if (nums[nowIndex] == 0)
                continue;
            while (nums[nowIndex] > 0) {
                int indexFlag = find(result, nowIndex);
                if (indexFlag == 0) {
                    result = (char) ('a' + nowIndex) + result;
                    System.out.println(result);
                } else if (indexFlag == result.length() - 1) {
                    result = result + (char) ('a' + nowIndex);
                    System.out.println(result);
                } else {
                    indexFlag++;
                    result = result.substring(0, indexFlag) + (char) ('a' + nowIndex) + result.substring(indexFlag);
                    System.out.println(result);
                }
                nums[nowIndex]--;
            }
        }
        return result;
    }

    private  int find(String result, int nowIndex) {
        int num = 0;
        for (int i = 0; i < result.length(); i++) {
            if (i == 0 && result.charAt(i) != ('a' + nowIndex)) {
                return i;
            } else if (i == result.length() - 1 && result.charAt(i) != ('a' + nowIndex)) {
                return i;
            } else {
                if (result.charAt(i) != ('a' + nowIndex) && result.charAt(i + 1) != ('a' + nowIndex)) {
                    num = i;
                    break;
                }
            }
        }

        return num;
    }
}

方法二

 public String reorganizeString(String S) {
        int[] nums = new int[26];
        int max = 0;
        int index = 0;
        int count = 0;
        int nowIndex = 0;
        char[] sresult = new char[S.length()];

        for (int i = 0; i < S.length(); i++) {
            int num = S.charAt(i) - 'a';
            nums[num]++;
            if (nums[num] > max) {
                max = nums[num];
                count = num;
            }
        }

        if (max > (S.length() + 1) / 2) {
            return "";
        }
        while (nums[count] > 0) {
            sresult[index] = (char) ('a' + count);
            index += 2;
            nums[count]--;
        }
        while (nowIndex < 26) {

            while (nums[nowIndex] > 0) {
                if (index >= S.length()) {
                    index = 1;
                }
                sresult[index] = (char) ('a' + nowIndex);
                index += 2;
                nums[nowIndex]--;
            }
            nowIndex++;
        }

        return new String(sresult);
    }
}

提交結(jié)果

image.png

方法二

image.png