Leetcode刷题第三周

字符串：

反转字符串

344

class Solution {
    public void reverseString(char[] s) {
        // 左右指针
        int leftNode = 0;
        int rifhtNode = s.length - 1;
        char temp;
        while(leftNode <= rifhtNode){
            temp = s[rifhtNode];
            s[rifhtNode] = s[leftNode];
            s[leftNode] = temp;
            leftNode++;
            rifhtNode--;
        }
    }
}

反转字符串 II

541

class Solution {
    public String reverseStr(String s, int k) {
        int count = 0;
        StringBuffer target = new StringBuffer();
        for(int i = 0; i < s.length(); i++){
            count++;
            if(count == 2*k){
                target.append(reverse(s.substring(i+1-2*k,i+1-k)));
                target.append(s.substring(i+1-k,i+1));
                count = 0;
            }
        }
        if(count < k){
            target.append(reverse(s.substring(s.length() - count,s.length())));
        }else if(count >= k && count < 2*k){
            target.append(reverse(s.substring(s.length() - count,s.length()- count + k)));
            target.append(s.substring(s.length() - count+k,s.length()));
        }
        return new String(target);
    }
    public String reverse(String s){
        char[] t = s.toCharArray();
        int leftNode = 0;
        int rifhtNode = t.length - 1;
        char temp;
        while(leftNode <= rifhtNode){
            temp = t[rifhtNode];
            t[rifhtNode] = t[leftNode];
            t[leftNode] = temp;
            leftNode++;
            rifhtNode--;
        }
        return new String(t);
    }
}

替换空格

offer 05

class Solution {
    public String replaceSpace(String s) {
        StringBuffer target = new StringBuffer();
        char temp;
        for(int i = 0; i < s.length(); i++){
            temp = s.charAt(i);
            if(temp == ' '){
                target.append("%20");
            }else{
                target.append(temp);
            }
        }
        return new String(target);
    }
}

反转字符串中的单词

151

class Solution {
    public String reverseWords(String s) {
        StringBuffer str = new StringBuffer();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) != ' '){
                int index = i;
                while(i < s.length() && s.charAt(i) != ' '){
                    i++;
                }
                str.insert(0,s.substring(index, i));
                if(i <  s.length() - 1){
                    str.insert(0," ");
                }
            }
        }
        if(str.charAt(0) == ' '){
            str.delete(0,1);
        }
        return new String(str);
    }
}

左旋转字符串

Offer 58 - II

class Solution {
    public String reverseLeftWords(String s, int n) {
// 先整体反转，在根据k进行部分反转
        char[] str = s.toCharArray();
        reverse(str, 0, str.length - 1);
        reverse(str, 0, str.length - 1 - n);
        reverse(str, str.length - n, str.length - 1);
        return new String(str);
    }
    public void reverse(char[] str, int start, int end){
        while(start < end){
            str[start] ^= str[end];
            str[end] ^= str[start];
            str[start] ^= str[end];
            start++;
            end--;
        }
    }
}

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

28

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

重复的子字符串

459

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int[] next = new int[s.length()];
        next[0] = 0;
        for(int i = 1, j = 0; 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;
        }
        if(next[next.length - 1] != 0 && next.length%(next.length - next[next.length - 1]) == 0){
            return true;
        }
        return false;
    }
}