LeetCode 767 重构字符串

题目

重构字符串

描述

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

题解

阅读题目我们可以知道当其中某个字母的数量大于总数的一半的时候就不会有可行的结果（奇数时 >(length+1)/2），得到最大数量的 字母 A,个数为N,然后做N-1个循环
形成 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);
    }
}

提交结果

image.png

方法二

image.png