目錄鏈接：

力扣編程題-解法匯總_分享+記錄-CSDN博客

GitHub同步刷題項目：

https://github.com/September26/java-algorithms

原題鏈接：

力扣

描述：

給你一個字符串?s，請你對?s?的子串進行檢測。

每次檢測，待檢子串都可以表示為?queries[i] = [left, right, k]。我們可以?重新排列?子串?s[left], ..., s[right]，并從中選擇?最多?k?項替換成任何小寫英文字母。?

如果在上述檢測過程中，子串可以變成回文形式的字符串，那么檢測結果為?true，否則結果為?false。

返回答案數組?answer[]，其中?answer[i]?是第?i?個待檢子串?queries[i]?的檢測結果。

注意：在替換時，子串中的每個字母都必須作為?獨立的?項進行計數，也就是說，如果?s[left..right] = "aaa"?且?k = 2，我們只能替換其中的兩個字母。（另外，任何檢測都不會修改原始字符串?s，可以認為每次檢測都是獨立的）

示例：

輸入：s = "abcda", queries = [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]
輸出：[true,false,false,true,true]
解釋：
queries[0] : 子串 = "d"，回文。
queries[1] :?子串 = "bc"，不是回文。
queries[2] :?子串 = "abcd"，只替換 1 個字符是變不成回文串的。
queries[3] :?子串 = "abcd"，可以變成回文的 "abba"。 也可以變成 "baab"，先重新排序變成 "bacd"，然后把 "cd" 替換為 "ab"。
queries[4] :?子串 = "abcda"，可以變成回文的 "abcba"。

提示：

• 1 <= s.length,?queries.length?<= 10^5
• 0 <= queries[i][0] <= queries[i][1] <?s.length
• 0 <= queries[i][2] <= s.length
• s?中只有小寫英文字母

解題思路：

* 解題思路：

* 構建二維數組，timeList[i]代表第i位出現的次數，length代表26個字母出現的。

* 每次遍歷queries的時候，取timeList[left]和timeList[right]，求之間的各個字符的出現次數。

* 如果是偶數則跳過，奇數則diffTimes++。最終如果right-left為奇數，則diffTimes應該為1。否則為0文章來源地址http://www.zghlxwxcb.cn/news/detail-485049.html

代碼：

class Solution1177
{
public:
    bool check(vector<int> left, vector<int> right, int length, int k)
    {
        int diffTimes = 0;
        for (int i = 0; i < left.size(); i++)
        {
            if ((right[i] - left[i]) % 2 == 0)
            {
                continue;
            }
            diffTimes++;
            if (diffTimes == 2)
            {
                diffTimes = 0;
                k--;
            }
        }
        if (k < 0)
        {
            return false;
        }
        if (length % 2 == 0)
        {
            return diffTimes == 0;
        }
        return diffTimes == 1;
    }

    vector<bool> canMakePaliQueries(string s, vector<vector<int>> &queries)
    {
        vector<bool> list;
        vector<vector<int>> timeList(s.length() + 1, vector<int>(26));
        int length = s.length();
        vector<int> querie(26);
        for (int i = 1; i < length + 1; i++)
        {
            querie[s.at(i - 1) - 'a']++;
            timeList[i] = querie;
        }
        for (int i = 0; i < queries.size(); i++)
        {
            int left = queries[i][0];
            int right = queries[i][1] + 1;
            int k = queries[i][2];
            list.push_back(check(timeList[left], timeList[right], right - left, k));
        }
        return list;
    }
};

到了這里，關于?LeetCode解法匯總1177. 構建回文串檢測的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！