在Leetcode练习中面临与字符串相关的问题

Question

单击此处查看问题链接。

从今天起我一直在努力解决这个问题，但我缺乏一些知识。我试图用受沃耶摩尔多数投票算法启发的方法来解决这个问题。

• 我的直觉是，假设第一个字符将具有max count，然后如果我们找到另一个字符，则减少ptr的值并增加count，同时将值存储在max中。
• 如果在某个时候，ptr==0，并且仍然有字符剩余，则将当前字符作为max_character并重复相同的过程。类似于多数投票算法。
• 但是，我犯了一些错误，我不知道是什么，但我真的很接近，想用这种方法解决这个问题。

class Solution {
    public int characterReplacement(String s, int k) {
        
        int count = 0;
        int max = Integer.MIN_VALUE; 
        int ptr = k;  
        char ch = ' ';
        
        for(int i = 0; i < s.length(); i++){
            
            // if at sometime, ptr equals zero then count will also be zero
            if(count == 0){
                ch = s.charAt(i);
                count = 1;
            }
            else{
                if(s.charAt(i) == ch){
                    count++;
                    max = Math.max(count, max);
                }
                else{
                    if(ptr == 0){
                        ch = s.charAt(i);
                        ptr = k;
                        count = 0;
                        continue;
                    }
                    ptr--;
                    count++;
                    max = Math.max(count, max);
                }
            }
        }
        return max;
    }
}

我希望，我能够清楚地解释我的方法，英语不是我的母语，所以语法错误可能会发生。而且，我知道用hashmap解决这个问题的方法，但我想用这个方法解决这个问题。

Answer 1

您有一个逻辑错误，即一旦您耗尽k，代码就需要返回到第一个替换索引以恢复搜索。

您的实现只需从最后一个索引恢复搜索，其中k已用完。

使用第一个失败的案例（字符替换（"BABABBA"，1）），发布的代码会找到这些子序列（以粗体显示的子序列-第一行是测试用例）：

巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴

当它应该找到：

巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴巴

要解决此问题，应首先将for循环更改为while循环：

i = 0;
while (i < s.length()) {
}

并引入一个索引变量lastStart，它指示第一次不匹配时子序列的开始：

int lastStart = 0;

并将其重置为0，只要有序列匹配：

if (count == 0) {
    // .. existing code
    lastStart = 0;
}

当替换耗尽时，重置循环变量子序列不匹配，并在第一个子序列不匹配时保持上次启动。

else {
    if (ptr == 0) {
        // existing code
        i = lastStart;
    }
    if (ptr == k) lastStart = i;
    // existing code
}

结果：