每日OJ题_贪心算法四⑧_力扣767. 重构字符串

目录

力扣767. 重构字符串

解析代码

力扣767. 重构字符串

767. 重构字符串

难度 中等

给定一个字符串 s ，检查是否能重新排布其中的字母，使得两相邻的字符不同。

返回 s 的任意可能的重新排列。若不可行，返回空字符串 "" 。

示例 1:

输入: s = "aab"
输出: "aba"

示例 2:

输入: s = "aaab"
输出: ""

提示:

• 1 <= s.length <= 500
• s 只包含小写字母

class Solution {
public:
    string reorganizeString(string s) {

    }
};

解析代码

和力扣1054. 距离相等的条形码基本一致。

贪心策略：

• 每次处理一批相同的字母，往 n 个空里面摆放。
• 每次摆放的时候，隔一个格子摆放一个字母。
• 先处理出现次数最多的那个字母，剩下的字母可任意。如果出现次数最多的那个数不超过（n + 1）/ 2，则有解，下一个数想相邻的话只能“填一圈”（不可能）。

class Solution {
public:
    string reorganizeString(string s) {
        int hash[26] = {0};
        char mostVal = s[0];
        int maxCount = 0;
        for(auto& e : s) // 统计每个数出现的频次
        {
            ++hash[e - 'a'];
            if(maxCount < hash[e - 'a'])
            {
                maxCount = hash[e - 'a'];
                mostVal = e;
            }
        }
        
        int n = s.size(), index = 0;
        if(maxCount > (n + 1) / 2)
            return "";
        string ret(n, ' ');
        for(int i = 0; i < maxCount; ++i) // 先处理出现次数最多的数
        {
            ret[index] = mostVal;
            index += 2;
        }

        hash[mostVal - 'a'] = 0;
        for(int i = 0; i < 26; ++i) // 处理剩下的数
        {
            for(int j = 0; j < hash[i]; ++j)
            {
                if(index >= n)
                    index = 1;
                ret[index] = i + 'a';
                index += 2;
            }
        }
        return ret;
    }
};