Решение проблем | Задача «Ликоу» 1177: построение обнаружения строки палиндрома

алгоритм

Резюме: Этот вопрос должен полностью изучить природу палиндрома, сосредоточиться на понимании ключевых слов в вопросе «перестановка» и полностью понять характеристики операции «исключающее ИЛИ».

Решение проблем | Задача «Ликоу» 1177: построение обнаружения строки палиндрома

дает вам строку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≤1051 \le s.length, queries.length \le 10^5
  • 0≤queries[i][0]≤queries[i][1]<s.length0 \le queries[i][0] \le queries[i][1] < s.length
  • 0≤queries[i][2]≤s.length0 \le queries[i][2] \le s.length
  • sТолько строчные английские буквы в

Точка знаний:

  • Сумма префикса XOR и суммы составляет информацию в интервале;
  • В этом вопросе также используется метод «сжатия состояния».

Анализ мыслей:

  • заменить большинствоkВы также можете отрегулировать положение строчных английских букв, чтобы сформировать палиндром;
  • Решение грубой силы состоит в том, чтобы перечислить все подстрокиs[i..j]Количество вхождений 26 строчных английских букв в
  • Сосредоточьтесь на понимании слова «перестановка», как расположить заголовок, на самом деле не важно, поэтому нам нужно только заботитьсяКаждыйqueryколичество вхождений символа;
  • иqueryПредставляет непрерывный поддиапазон строки, поэтому нам нужно знать количество вхождений символов в поддиапазоне строки;
  • фокус: В свойстве палиндрома, если символ появляется четное количество раз, его можно разместить в симметричной позиции в строке, и нам не нужно заботиться о строке с четным номером. другими словами,kВторая возможность использования должна сначала удовлетворять нечетному количеству вхождений строки и должна заменять только одиночные, а не парные символы;
  • Чтобы понять информацию в непрерывных подынтервалах, легко придумать использование сумм префиксов.

Код ссылки:

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<Boolean> canMakePaliQueries(String s, int[][] queries) {
        int len = s.length();
        char[] charArray = s.toCharArray();

        // 第 1 步：计算前缀异或和
        int[] preSum = new int[len + 1];
        preSum[0] = 0;
        for (int i = 0; i < len; i++) {
            preSum[i + 1] = preSum[i] ^ (1 << (charArray[i] - 'a'));
        }
        // 第 2 步：根据前缀异或和计算结果
        List<Boolean> res = new ArrayList<>();
        for (int[] query : queries) {
            // 注意理解这里计算区间和的异或相减关系
            res.add(Integer.bitCount(preSum[query[0]] ^ preSum[query[1] + 1]) / 2 <= query[2]);
        }
        return res;
    }
}

инструкция:

preSum[query[0]] ^ preSum[query[1] + 1]

Сумма префикса XOR является суммой интервалов, потому что операция XOR характеризуется: сложением без переноса. После XOR одних и тех же цифр результирующие цифры00.

Проблема ассоциации:

191. Количество бит 1

Код ссылки:

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n &= n - 1;
            res++;
        }
        return res;
    }
}
Категории