作者：小迅
鏈接：https://leetcode.cn/problems/can-make-palindrome-from-substring/solutions/2309940/qian-zhui-he-zhu-shi-chao-ji-xiang-xi-by-n3ps/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

題目

?

思路

題意 -> 給定一個(gè)字符串，選擇其中任意位置 L-R，可以重排任意字符和替換任意 K 個(gè)字符，使得 L-R 子串為 回文串，能滿足要求則為 TRUE，不能則為 FALSE。

要求轉(zhuǎn)換為 回文串，什么是回文串呢？形如 abccba 則為回文串，其中存在一個(gè)特點(diǎn)為 相同字符為偶數(shù) 或者 在前者基礎(chǔ)上只有一個(gè)字符出現(xiàn)次數(shù)為奇數(shù)。

那么現(xiàn)在就簡(jiǎn)單了，題意只關(guān)心能否到達(dá)要求，不關(guān)心其具體字符。那么就可以將給定字符串轉(zhuǎn)換為 字符出現(xiàn)次數(shù)串，判斷一個(gè)子串能否轉(zhuǎn)換為回文串 -> 判斷將當(dāng)前位置中字符出現(xiàn)次數(shù)是否滿足上述要求

那么如何轉(zhuǎn)換到上述題意要求呢？ 給定一個(gè)子串：

• 相同字符出現(xiàn)的次數(shù)如果為偶數(shù)的話，那么這個(gè)字符就不需要使用 修改次數(shù)
• 相同字符出現(xiàn)的次數(shù)如果為奇數(shù)的話：
  • 只有一個(gè)字符出現(xiàn)奇數(shù)次數(shù)， 不需要使用 修改次數(shù)
  • 多個(gè)字符出現(xiàn)奇數(shù)次數(shù)的話， 需要使用 出現(xiàn)次數(shù) / 2 次 修改次數(shù)，將多余的字符轉(zhuǎn)換為 偶數(shù)次出現(xiàn)

如何統(tǒng)計(jì)每一個(gè)位置字符的出現(xiàn)次數(shù)呢？

• 使用數(shù)組記錄每一個(gè)子串的字符出現(xiàn)次數(shù)
• 因?yàn)樽址挥?6個(gè)，那么可以使用一個(gè)int型位記錄出現(xiàn)次數(shù) 0 表示偶數(shù)次，1表示奇數(shù)次
• 可以使用前綴和，任意位置可以通過(guò)左右兩個(gè)子串狀態(tài)相差得出當(dāng)前狀態(tài)

代碼注釋超級(jí)詳細(xì)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-486249.html

代碼

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

bool* canMakePaliQueries(char * s, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    int n = strlen(s);
    int* count = (int*)malloc((n + 1) * sizeof(int));//二進(jìn)制代替數(shù)組
    memset(count, 0, (n + 1) * sizeof(int));//初始化
    for (int i = 0; i < n; i++) {//前綴和枚舉
        // ^ 為不帶進(jìn)位的加法
        count[i + 1] = count[i] ^ (1 << (s[i] - 'a'));//記錄整體狀態(tài)
    }
    bool* res = (bool*)malloc(queriesSize * sizeof(bool));//返回值數(shù)組
    for (int i = 0; i < queriesSize; i++) {//枚舉子串
        int l = queries[i][0], r = queries[i][1], k = queries[i][2];
        //根據(jù)上述表示，大于13則可以能滿足轉(zhuǎn)換要求
        //if (k >= 13) {res[i] = true; continue;}
        // 由于沒(méi)有負(fù)值， 那么 0 - 1 等價(jià)于 0 + 1
        int bits = 0, x = count[r + 1] ^ count[l];//相差得出當(dāng)前狀態(tài)
        while (x > 0) {//求當(dāng)奇數(shù)出現(xiàn)次數(shù)
            x &= x - 1;
            bits++;
        }
        res[i] = bits / 2 <= k;//保存有效值
    }
    *returnSize = queriesSize;
    free(count);
    return res;
}



作者：小迅
鏈接：https://leetcode.cn/problems/can-make-palindrome-from-substring/solutions/2309940/qian-zhui-he-zhu-shi-chao-ji-xiang-xi-by-n3ps/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

到了這里，關(guān)于LeetCode·每日一題·1177. 構(gòu)建回文串檢測(cè)·前綴和的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！