3妹:好冷啊, 冻得瑟瑟发抖啦
2哥 : 这已经是你今年的第几次抖啦?
3妹:昨天20度,今天7度,直降13度呢,能不抖嘛
2哥 : 继哈尔滨之后,全国各地的城市也在发展旅游业。 河北喊话赵丽颖回家呢。
3妹:哈哈哈哈,看来各地都要各显神通了。
2哥:说到回家,我有一个关于回文的题目,我们来做一下吧~
3妹:切,这个弯拐的有点急…, 不过是该题了, 一起来看一下吧
题目:
给你一个长度为 偶数 n ,下标从 0 开始的字符串 s 。
同时给你一个下标从 0 开始的二维整数数组 queries ,其中 queries[i] = [ai, bi, ci, di] 。
对于每个查询 i ,你需要执行以下操作:
将下标在范围 0
每个查询与其他查询都是 独立的 。
请你返回一个下标从 0 开始的数组 answer ,如果第 i 个查询执行操作后,可以将 s 变为一个回文串,那么 answer[i] = true,否则为 false 。
子字符串 指的是一个字符串中一段连续的字符序列。
s[x:y] 表示 s 中从下标 x 到 y 且两个端点 都包含 的子字符串。
示例 1:
输入:s = “abcabc”, queries = [[1,1,3,5],[0,2,5,5]]
输出:[true,true]
解释:这个例子中,有 2 个查询:
第一个查询:
- a0 = 1, b0 = 1, c0 = 3, d0 = 5
- 你可以重新排列 s[1:1] => abcabc 和 s[3:5] => abca服务器托管网bc 。
- 为了让 s 变为回文串,s[3:5] 可以重新排列得到 => abccba 。
- 现在 s 是一个回文串。所以 answer[0] = true 。
第二个查询: - a1 = 0, b1 = 2, c1 = 5, d1 = 5.
- 你可以重新排列 s[0:2] => abcabc 和 s[5:5] => abcabc 。
- 为了让 s 变为回文串,s[0:2] 可以重新排列得到 => cbaabc 。
- 现在 s 是一个回文串,所以 answer[1] = true 。
示例 2:
输入:s = “abbcdecbba”, queries = [[0,2,7,9]]
输出:[false]
解释:这个示例中,只有一个查询。
a0 = 0, b0 = 2, c0 = 7, d0 = 9.
你可以重新排列 s[0:2] => abbcdecbba 和 s[7:9] => abbcdecbba 。
无法通过重新排列这些子字符串使 s 变为一个回文串,因为 s[3:6] 不是一个回文串。
所以 answer[0] = false 。
示例 3:
输入:s = “acbcab”, queries = [[1,2,4,5]]
输出:[true]
解释:这个示例中,只有一个查询。
a0 = 1, b0 = 2, c0 = 4, d0 = 5.
你可以重新排列 s[1:2] => acbcab 和 s[4:5] => acbcab 。
为了让 s 变为回文串,s[1:2] 可以重新排列得到 => abccab 。
然后 s[4:5] 重新排列得到 abccba 。
现在 s 是一个回文串,所以 answer[0] = true 。
提示:
2
思路:
把输入的字符串记作大写 S。为方便计算,把 S 均分为左右两个字符串,其中右半部分反转。左半和右半分别记作 s 和 t。
我们需要预处理三个前缀和:
- s 的每个前缀的每个字符的出现次数,记作 sumS。
- t 的每个前缀的每个字符的出现次数,记作 sumT。
- 前缀中 s[i]≠t[i]的次数,记作 sumNe(Not Equal)。
java代码:
class Solution {
public boolean[] canMakePalindromeQueries(String S, int[][] queries) {
char[] s = S.toCharArray();
int m = s.length;
int n = m / 2;
// 预处理三种前缀和
int[][] sumS = new int[n + 1][26];
for (int i = 0; i 0 || // [0,l1-1] 有 s[i] != t[i]
sumNe[sumNe.length - 1] - sumNe[Mat服务器托管网h.max(r1, r2) + 1] > 0) { // [max(r1,r2)+1,n-1] 有 s[i] != t[i]
return false;
}
if (r2
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
相关推荐: 成功者的黄金法则:为何预案是每一步胜利的秘密武器?
大家好,我是小米!在这个充满创新和变革的时代,我们时常面临着各种机遇和挑战。生活中的每一个决策,每一步行动,都似乎需要我们对未来进行预判和规划。那么,为什么做每一件事情都要先有预案呢?今天,让我们一起来深入探讨这个问题,探寻其中的奥秘。 预案是成功的基石 成功…