题目

767. 重构字符串

思路

代码

// 4ms, 46.99%; 6.3MB, 8.35%
class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> cnt;
        int maxCnt = 0, n = s.size();
        for (auto& ch : s) {
            cnt[ch] ++ ;
            maxCnt = max(maxCnt, cnt[ch]);
        }
        if (maxCnt > (n + 1) / 2) return "";

        string res(n, ' '); // 注意此处 字符串初始化 用法
        int i = 0, j = 1;
        for (char ch = 'a'; ch <= 'z'; ch ++ ) {
            if (cnt[ch] <= n / 2 && j < n) { // 这里也可不加 j < n, 加上好一些
                while (cnt[ch] && j < n){
                    res[j] = ch; // 上面需提前将 res初始化为 s.size()大小的字符串
                    cnt[ch] --;
                    j += 2;
                }
            }

            while (cnt[ch]){ // 可以不加 && i < n
                res[i] = ch;
                cnt[ch] --;
                i += 2;
            }
        }
        return res;
    }
};

• 题目中说 只含 小写字母，所以此处可以 数组哈希

// 0ms, 100%; 5.9MB, 98.45%
// 题目中说 只含 小写字母，所以此处可以 数组哈希
class Solution {
public:
    string reorganizeString(string s) { 
        // int cnt[26]只是声明，并没有初始化，这样会报错
        int cnt[26] = {}; // 声明的同时需要初始化，int cnt[26] = {}; 或int cnt[26] = {0}
        int maxCnt = 0, n = s.size();
        for (auto& ch : s) {
            cnt[ch - 'a'] ++ ;
            maxCnt = max(maxCnt, cnt[ch - 'a']);
        }
        if (maxCnt > (n + 1) / 2) return "";

        string res(n, ' '); // 注意此处 字符串初始化 用法
        int i = 0, j = 1;
        for (char ch = 'a'; ch <= 'z'; ch ++ ) {
            if (cnt[ch - 'a'] <= n / 2 && j < n) { // 这里也可不加 j < n, 加上好一些
                while (cnt[ch - 'a'] && j < n){
                    res[j] = ch; // 上面需提前将 res初始化为 s.size()大小的字符串
                    cnt[ch - 'a'] --;
                    j += 2;
                }
            }

            while (cnt[ch - 'a']){ // 可以不加 && i < n
                res[i] = ch;
                cnt[ch - 'a'] --;
                i += 2;
            }
        }
        return res;
    }
};