北京工程信息网站,怎么推广我做的网站,网络宣传网站建设建站,房子竣工验收在哪个网站查1. 题目
给你一个字符串 s#xff0c;请你对 s 的子串进行检测。
每次检测#xff0c;待检子串都可以表示为 queries[i] [left, right, k]。我们可以 重新排列 子串 s[left], ..., s[right]#xff0c;并从中选择 最多 k 项替换成任何小写英文字母。
如果在上述检测过程…1. 题目
给你一个字符串 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 中只有小写英文字母来源力扣LeetCode 链接https://leetcode-cn.com/problems/can-make-palindrome-from-substring 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
记录到每个字符位置处的前缀字符计数通过 r - (l-1) 得到区间 [ l, r ] 的字符计数统计奇数字符出现的次数区间长度为偶数 odd-2*k 0区间长度为奇数 odd-2*k 1
class Solution {
public:vectorbool canMakePaliQueries(string s, vectorvectorint queries) {int i, j, l, r, n queries.size(), odd;vectorvectorint count(s.size(),vectorint(26,0));vectorint temp(26,0);vectorbool ans(n);for(i 0; i s.size(); i){temp[s[i]-a];count[i] temp;//前缀字符计数}for(i 0; i n; i){l queries[i][0];r queries[i][1];temp count[r];if(l-10){for(j 0; j 26; j)temp[j] - count[l-1][j];}odd 0;for(j 0; j 26; j)if(temp[j]%2)odd;if((r-l)%2)//长度偶数ans[i] (odd-2*queries[i][2]0);elseans[i] (odd-1-2*queries[i][2]0);}return ans;}
};
