重排字符串

C++ 解法, 执行用时: 6ms, 内存消耗: 1032KB, 提交时间: 2022-07-17

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
    string rearrangestring(string str) {
        // write code here
          vector<int> v(27, 0);
        int max_num = 0;
        for (int i = 0; i < str.size(); i++) {
            v[str[i] - 'a'] += 1;
            max_num = max(max_num, v[str[i] - 'a']);
        }
         
        if (max_num > (str.size() + 1) / 2) {
            return "";
        }
         
        string res = "";
        int idx = 0;
        for (int j = 0; j < 26; j++) {
            while (v[j]) {
                str[idx] = j + 'a';
                idx = idx + 2;
                v[j] -= 1;
                if (idx >= str.size()) {
                    idx = 1;
                }
            }
        }
        return str;
    }
};

C++ 解法, 执行用时: 6ms, 内存消耗: 1084KB, 提交时间: 2022-07-22

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串
     */
    string rearrangestring(string str) {
        // write code here
        vector<int> v(27, 0);
        int max_num = 0;
        for (int i = 0; i < str.size(); i++) {
            v[str[i] - 'a'] += 1;
            max_num = max(max_num, v[str[i] - 'a']);
        }
          
        if (max_num > (str.size() + 1) / 2) {
            return "";
        }
          
        string res = "";
        int idx = 0;
        for (int j = 0; j < 26; j++) {
            while (v[j]) {
                str[idx] = j + 'a';
                idx = idx + 2;
                v[j] -= 1;
                if (idx >= str.size()) {
                    idx = 1;
                }
            }
        }
        return str;
    }
};

C 解法, 执行用时: 7ms, 内存消耗: 776KB, 提交时间: 2022-07-22

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param str string字符串 
 * @return string字符串
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
void quickSort(int sorted[26], int hash[26], int start, int end) {
    if (start < end) {
        int targetHash = hash[sorted[start]], target = sorted[start], i = start, j = end;
        while(i < j) {
            while(i < j && hash[sorted[j]] > targetHash) {
                j--;
            }
            if(i < j) {
                sorted[i++] = sorted[j];
            }
            while(i < j && hash[sorted[i]] <= targetHash) {
                i++;
            }
            if(i < j) {
                sorted[j--] = sorted[i];
            }
        }
        sorted[i] = target;
        
        quickSort(sorted, hash, start, i - 1);
        quickSort(sorted, hash, i + 1, end);
    }
}

char* rearrangestring(char* str ) {
    int hash[26] = { 0 }, sorted[26] = { 0 }, sLen = strlen(str), key;
    for (int i = 0; i < sLen; i++) {
        hash[str[i] - 'a'] += 1;
    }
    for (int i = 0; i < 26; i++) {
        sorted[i] = i;
    }
    quickSort(sorted, hash, 0, 25);
    
    char *result = (char *)malloc(sizeof(char) * (sLen + 1));
    memset(result, 0, sizeof(char) * (sLen + 1));
    int rIndex = 0;
    result[rIndex++] = sorted[25] + 'a';
    hash[sorted[25]] -= 1;
    int chIndex = sorted[25], chHash = hash[sorted[25]], j;
    for (j = 24; j >= 0; j--) {
        if (hash[sorted[j]] > chHash) {
            sorted[j+1] = sorted[j];
        } else {
            sorted[j+1] = chIndex;
            break;
        }
    }
    if (j == -1) {
        sorted[0] = chIndex;
    }
    
    int lastChIndex;
    lastChIndex = result[0] - 'a';
    while(rIndex < sLen) {
        for (j = 25; j >= 0; j--) {
            if (sorted[j] != lastChIndex && hash[sorted[j]] > 0) {
                break;
            }
        }
        
        if (j == -1) {
            result[0] = '\0';
            return result;
        }
        
        chIndex = sorted[j];
        result[rIndex++] = chIndex + 'a';
        hash[chIndex] -= 1;
        chHash = hash[chIndex];
        
        for (j -= 1; j >= 0; j--) {
            if (hash[sorted[j]] > chHash) {
                sorted[j+1] = sorted[j];
            } else {
                sorted[j+1] = chIndex;
                break;
            }
        }
        if (j == -1) {
            sorted[0] = chIndex;
        }
        
        lastChIndex = chIndex;
    }
    
    return result;
}

C++ 解法, 执行用时: 7ms, 内存消耗: 1024KB, 提交时间: 2022-07-17

class Solution {
  public:
    string rearrangestring(string str) {
        vector<int> v(27, 0);
        int a = 0;
        for (int i = 0; i < str.size(); i++) {
            v[str[i] - 'a'] += 1;
            a = max(a, v[str[i] - 'a']);
        }
        if (a > (str.size() + 1) / 2) {
            return "";
        }
        string s = "";
        int k = 0;
        for (int j = 0; j < 26; j++) {
            while (v[j]) {
                str[k] = j + 'a';
                k = k + 2;
                v[j] -= 1;
                if (k >= str.size()) {
                    k = 1;
                }
            }
        }
        return str;
    }
};

C++ 解法, 执行用时: 7ms, 内存消耗: 1028KB, 提交时间: 2022-08-06

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串
     */
    static bool cmp(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }
    string rearrangestring(string str) {
        // write code here
        if (str.length() < 2) { //长度太短，不用排
            return str;
        }
        //求计数
        vector<int> counts(26, 0); //26个元素，全部初始化为0
        int maxCount = 0;
        int length = str.length();
        for (int i = 0; i < length; i++) {
            char c = str[i];
            counts[c - 'a']++; //用偏移量c - 'a'来表示小写字母
            maxCount = max(maxCount, counts[c - 'a']); //判断最大计数值
        }
        if (maxCount > (length + 1) /
                2) { //如果最多的超过了(length + 1) / 2，则不能重新排列
            return "";
        }
        //排列
        string reorganizeArray(length, ' '); //初始化字符串，全为空
        int evenIndex = 0, oddIndex = 1;
        int halfLength = length / 2;
        for (int i = 0; i < 26; i++) {
            char c = 'a' + i; //恢复字符
            while (counts[i] > 0 && counts[i] <= halfLength && oddIndex < length) {
                reorganizeArray[oddIndex] = c; //先填奇数位置
                counts[i]--;
                oddIndex += 2;
            }
            while (counts[i] > 0) { //再填偶数位置
                reorganizeArray[evenIndex] = c;
                counts[i]--;
                evenIndex += 2;
            }
        }
        return reorganizeArray;
    }
};

详情