代码随想录打卡Day6

字符串

344.反转字符串

class Solution {
    public void reverseString(char[] s) {
        //注意遍历范围，可以减少循环次数
        for(int i =0;i<s.length/2;i++){
            char tmp = s[i];
            s[i] = s[s.length-i-1];
            s[s.length-i-1] = tmp;
        }
    }
}

541.反转字符串II

class Solution {
    public String reverseStr(String s, int k) {
        char[] array = s.toCharArray();
        int len = s.length();
        for(int i =0;i<len;i += k*2){
            int start = i;
            int end = Math.min(len-1,k+start-1);
            //交换字符
            while(start<end){
                char tmp = array[start];
                array[start] = array[end];
                array[end] = tmp;
                start++;
                end--;
            }
        }
        String res = new String(array);
        return res;
    }
}

151.反转字符串中的单词

坑：1、if(s.charAt(start)!=' '||sb.charAt(sb.length()-1)!=' ') //注意先后顺序，若交换顺序可能造成结尾出现多余空格的现象

        2、start<=end //注意取等，否则会漏字母

class Solution {
    public String reverseWords(String s) {
        StringBuilder sb = removeSpace(s);
        reverseString(sb,0,sb.length()-1);
        reverseWord(sb);
        return sb.toString();
    }
    //去掉空格(首尾+中间)
    private StringBuilder removeSpace(String s){
        int start = 0,end = s.length()-1;
        while(s.charAt(start)==' '){
            start++;
        }
        while(s.charAt(end)==' '){
            end--;
        }
        StringBuilder sb = new StringBuilder();
        while(start<=end){
            //注意先后顺序，若交换顺序可能造成结尾出现多余空格的现象
            if(s.charAt(start)!=' '||sb.charAt(sb.length()-1)!=' '){ 
                sb.append(s.charAt(start));
        }
        start++;
        }
        return sb;
    }

    //整个字符串反转
    private void reverseString(StringBuilder sb,int start,int end){
        while(start<=end){
        char tmp = sb.charAt(start);
        sb.setCharAt(start,sb.charAt(end));
        sb.setCharAt(end,tmp);
        start++;
        end--;
        }
    }
    //单词反转
    private void reverseWord(StringBuilder sb){
        int start = 0,end = 1;
        while(start<sb.length()){
            while(end<sb.length() && sb.charAt(end)!=' '){
                end++;
            }
            reverseString(sb,start,end-1);
            start = end+1;
            end = start+1;
        }
    }
}

28.找出字符串中第一个匹配项的下标

KMP算法-解决匹配问题

class Solution {
    public int strStr(String haystack, String needle) {
        int[] next = new int[needle.length()];
        getNext(needle,next);
        int j = 0;
        for(int i = 0;i<haystack.length();i++){
            while(j>0 && haystack.charAt(i)!=needle.charAt(j)){
                j = next[j-1];
            }
            if(haystack.charAt(i)==needle.charAt(j)){
                j++;
            }
            if(j==needle.length()){
                return i-j+1;
            }
        }
        return -1;
    }

    private void getNext(String s,int[] next){
        int j = 0;
        next[0] = 0;
        for(int i =1;i<s.length();i++){
            while(j>0 && s.charAt(i)!=s.charAt(j)){
                j = next[j-1];
            }
            if(s.charAt(i)==s.charAt(j)){
                j++;
            }
            next[i] = j;
        }
    }
}

459.重复的子字符串

KMP算法-解决重复子串问题

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        s = " "+s;
        char[] array = s.toCharArray();
        int j = 0;
        int[] next = new int[len+1];
        for(int i = 2;i<=len;i++){
            while(j>0 && array[i]!=array[j+1]){
                j = next[j];
            }
            if(array[i]==array[j+1]){
                j++;
            }
            next[i] = j;
        }

        if(next[len]>0 && len%(len-next[len])==0){
            return true;
        }
        return false;
    }
}