网站建设框架图,温州市人才市场招聘网最新招聘,网站编程所用的语言有,中国建设银行官网站保本理财删除字符串中的子串或者字符以满足题意要求 1234. 替换子串得到平衡字符串680. 验证回文串917. 仅仅反转字母 1234. 替换子串得到平衡字符串
题目链接#xff1a;1234. 替换子串得到平衡字符串 题目内容#xff1a; 题目中给出了平衡字符串的定义——只有’Q’#xff0c;… 删除字符串中的子串或者字符以满足题意要求 1234. 替换子串得到平衡字符串680. 验证回文串917. 仅仅反转字母 1234. 替换子串得到平衡字符串
题目链接1234. 替换子串得到平衡字符串 题目内容 题目中给出了平衡字符串的定义——只有’Q’‘W’‘E’R’四种字符并且每种字符的数量都是n/4。但是现在给出一个字符串s它不一定是平衡字符串。如果不是就要通过替换其中一个子串使其成为平衡字符串。将字符串s看作是待替换部分s1和剩下的部分s2将s1替换成其他字符串后能够保证新的s1插入s2后四种字符的数量都是n/4。新的s1插入s2只能增加字符的数量而不能减少字符的数量因此s2中四种字符的数量均要≤n/4。 这个题目使用滑动窗口滑动窗口内的子串即待删除的s1。其下标用left和right表示s1是s中[leftright)这一段子串。滑动窗口滑动的过程如下
1、先固定left然后right向右移动移动的同时字符s[right]的数量-1直到四种字符数量均≤n/4——此时找到了[leftright)这一段s1使得s中除s1外四种字符数量均≤n/42、此时逐步右移left缩小滑动窗口即s1的长度以便找到最短的s1同时字符s[left]的数量1并判s-s1中四种字符的数量是否均≤n/43、每找到一个满足条件的[leftright)滑动窗口就需要记录窗口的长度并记录最小值
代码如下C
class Solution {
public://判断四种字符的数量是否均≤n/4bool check(vectorint cnt , int num){if(cnt[Q - A] num||cnt[E - A] num||cnt[W - A] num||cnt[R - A] num)return false;return true;}int balancedString(string s) {//先统计s中四种字符的数量vectorint cnt(26,0);for(char ch : s)cnt[ch-A]; int num s.size() / 4;//如果一开始就小于等于【实际上是等于】就直接返回0不需要替换if(check(cnt, num))return 0;//记录最小长度int ans s.size();//滑动窗口更新过程for(int left 0, right 0; left s.size(); left){//right右移直到滑动窗口外四种四字符均≤n/4while(right s.size() !check(cnt, num)){cnt[s[right] - A]--;right;}//上面循环结束可能是rights.size()也可能是满足条件了//如果是rights.size()了right不能右移了之后left右移的过程中只能使得滑动窗口外四种字符的数量增加//如果一旦有left使得有字符数量n/4left继续右移已经没有意义之后的滑动窗口都不满足要求提前跳出循环if(!check(cnt,num))break;//更新长度ans min(ans, right - left);cnt[s[left] - A];}return ans; }
};680. 验证回文串
题目链接680. 验证回文串 题目内容 判断一个字符串是否是回文串的时候使用的是双指针一个left从下标0开始一个right从s.size()-1开始然后如果s[left] s[right]leftright–直到left right遍历完s中的字符。 现在题目是要求我们最多删除一个字符串判断s是否是回文串。此时有三种情况
1、s本身就是回文串能够按照上述的判断过程逐字符对比判断2、s本身不是回文串但是删除一个字符后能够是回文串s不是回文串肯定会出现s[left] !s [right]此时要么删除s[left]然后判断s[left1~right]是否是回文串要么删除s[right]判断s[left~right-1]是否是回文串 这两个只要有一个是回文串即可【也可能两个都是回文比如acac删除a得到cac删除c得到aca都是回文】3、s不是回文串不管删除哪个字符都不能成为回文串——上述第二种情况中如果不管删除s[left]还是s[right]剩下的都不是回文串那么如果考虑继续遍历删除其他字符串但是s[left] ! s[right]不管再去删除s[left1~right-1]中的哪个字符都不能使得s变成回文串。
代码如下C
class Solution {
public://判断left~right这一段子串是否是回文串bool ispalindrome(int left, int right, string s){while(leftright){if(s[left] ! s[right])return false;left;right--;}return true;}bool validPalindrome(string s) {int left 0, right s.size()-1;//前后逐字符对比while(left right){//如果相等就leftright--if(s[left] s[right]){left;right--;}//如果不相等就去判断left~right-1和left1~right这两段子串是否是回文串else return ispalindrome(left,right - 1,s) || ispalindrome(left1,right,s);}return true;}
};
917. 仅仅反转字母
题目链接917. 仅仅反转字母 题目内容 题目说的是英文字母位置反转。看题目以为这个位置反转和之前的反转单词一样只是把非英文的字符当作单词的分隔符……结果原来是和这个反转字符串类似。只是遇到非英文字母的字符直接跳过不处理。 先看看例子 因此这里的位置反转也是双指针left和right在s[left]和s[right]都是英文字母的时候二者交换如果不是英文字母就跳过不处理代码如下C
class Solution {
public://判断是否是英文字母bool check_ch(char ch){if(ch - a 0 ch - a 26)return true;if(ch - A 0 ch - A 26)return true;return false;}string reverseOnlyLetters(string s) {//双指针遍历s中每个字符for(int i 0, j s.size() -1 ; i j;){//s[i]和s[j]都是英文字母的时候交换位置if(check_ch(s[i]) check_ch(s[j])){swap(s[i],s[j]);i;j--;}else {//不是英文字母就跳过if(!check_ch(s[i]))i;if(!check_ch(s[j]))j--;}}return s;}
};
