字符串

344.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例 1：输入：["h","e","l","l","o"] 输出：["o","l","l","e","h"]

示例 2：输入：["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]

解答：

class Solution {
    public void reverseString(char[] s) {
        char c;
        int n =s.length;
        for(int i = 0; i < n/2; i++){
            c = s[i];
            s[i] = s[n - i - 1];
            s[n - i - 1] = c;
        }
    }
}

//异或操作
class Solution {
    public void reverseString(char[] s) {
        int n =s.length;
        for(int i = 0; i < n/2; i++){
            s[i] ^= s[n - i - 1];
            s[n - i - 1] ^= s[i];
            s[i] ^= s[n - i -1];
        }
    }
}

541. 反转字符串II

力扣题目链接

给定一个字符串 s 和一个整数 k，从字符串开头算起, 每计数至 2k 个字符，就反转这 2k 个字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。

如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例:

输入: s = "abcdefg", k = 2 输出: "bacdfeg"

class Solution {
    public String reverseStr(String s, int k) {
        char[] ss = s.toCharArray();
        int n = s.length()/k;
        String res = new String("");
        for(int i = 0; 2*i + 1 <= n; i++){
            reverseString(ss, 2*i*k, k);
        }
        if(n%2 == 0){
            reverseString(ss, k*n, s.length() - k*n);
        }
        return new String(ss);
    }

    public void reverseString(char[] ss , int start, int len) {
        for(int i = 0; i < len/2; i++){
            ss[i + start] ^= ss[start + len - i - 1];
            ss[start + len - i - 1] ^= ss[i + start];
            ss[i + start] ^= ss[start + len - i - 1];
        }
    }
}

替换数字

卡码网题目链接

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。

对于输入字符串 "a5b"，函数应该将其转换为 "anumberb"

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

解答：

//费时费空间
import java.util.*;
 
class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        String res = new String("");
        char[] ss = s.toCharArray();
        for(char c : ss){
            if(c - '9' <= 0 && c - '0' >= 0){
                res += "number";
            } else{
                res += String.valueOf(c);
            }
        }
        System.out.println(res);
    }
}

151.翻转字符串里的单词

力扣题目链接

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：输入: "the sky is blue" 输出: "blue is sky the"

示例 2：输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

解答：

class Solution {
    public String reverseWords(String s) {
        char[] ss = s.toCharArray();
        char[] res = new char[ss.length];
        int cnt = -1;
        int flag = 0; 
        //去除首尾以及中间多余空格
        for(int i = 0; i < ss.length; i++){
            if(ss[i] != ' '){
                cnt++;
                if(flag == -1){
                    res[cnt] = ' ';
                    cnt++;
                }
                res[cnt] = ss[i];
                flag = 1;
            } else if(flag == 1){
                flag = -1;
            }
        }
        //去除首尾以及中间多余空格(更加简洁)
        // for(int i = 0; i < ss.length; i++){
        //     if(ss[i] != ' '){
        //         if(cnt != 0){
        //             res[cnt++] = ' ';
        //         }
        //         while(i < ss.length && ss[i] != ' ') res[cnt++] = ss[i++];
        //     }
        // }
        //反转整个字符串
        reverseString(res , 0, cnt + 1);
        
        //反转各个单词
        char[] res1 = new char[cnt+1]; 
        for(int i = 0,j = 0; i < cnt+1; i++){
            res1[i] = res[i];
            if(res[i] == ' '){
                reverseString(res1 , j, i - j);
                j = i+1;
            } 
            if(i == cnt){
                reverseString(res1 , j, i - j + 1);
                j = i+1;
            }

        }
        return new String(res1);        
    }
    public void reverseString(char[] ss , int start, int len) {
        for(int i = 0; i < len/2; i++){
            ss[i + start] ^= ss[start + len - i - 1];
            ss[start + len - i - 1] ^= ss[i + start];
            ss[i + start] ^= ss[start + len - i - 1];
        }
    }
}

右旋字符串

卡码网题目链接

字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。

输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。

输出：输出共一行，为进行了右旋转操作后的字符串。

样例输入：

2
abcdefg

样例输出：

fgabcde

数据范围：1 <= k < 10000, 1 <= s.length < 10000;

解答：

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int len = Integer.parseInt(scanner.nextLine());
        String s = scanner.nextLine();//next.Int()与next.Line()不能连用，next.Line()不忽略换行符，换行符会被作为next.Line()的值，除非专门加一个next.Line()吸收换行符
        char[] ss = s.toCharArray();
        Main m = new Main();
        m.reverseString(ss, 0, ss.length);
        m.reverseString(ss, 0, len);
        m.reverseString(ss, len, ss.length - len);
        System.out.println(new String(ss));
    }
    public void reverseString(char[] ss , int start, int len) {
        for(int i = 0; i < len/2; i++){
            ss[i + start] ^= ss[start + len - i - 1];
            ss[start + len - i - 1] ^= ss[i + start];
            ss[i + start] ^= ss[start + len - i - 1];
        }
    }

}

28. 实现 strStr()

力扣题目链接

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

解答：

//滑动窗口
class Solution {
    public int strStr(String haystack, String needle) {
        char[] ss = haystack.toCharArray();
        char[] c = needle.toCharArray();
        int fast = 0, slow = 0;
        for(; fast < ss.length; fast++){
            if(ss[fast] == c[slow]) slow++;
            else{
                fast -= slow;
                slow = 0;
            }
            if(slow == c.length) return fast - slow + 1;
        }
        return -1;
    }
}

//kmp next前缀表都减了1
class Solution {
    public int strStr(String haystack, String needle) {
        char[] ss = haystack.toCharArray();
        char[] c = needle.toCharArray();
        int[] next_c = getnext(c);
        int j = -1;
        for(int i = 0; i < ss.length; i++){
            while(j >= 0 && ss[i] != c[j+1]){
                j = next_c[j];
            }
            if(ss[i] == c[j+1]){
                j++;
            }
            if(j == c.length - 1) return i - j;
        }
        return -1;
    }
    public int[] getnext(char[] c){
        int[] next = new int[c.length];
        int j = -1;
        next[0] = j;
        for(int i = 1; i < next.length; i++){
            while(j >= 0 && c[i] != c[j+1]){
                j = next[j];
            }
            if(c[i] == c[j+1]){
                ++j;
            }
            next[i] = j;
        }
        return next;
    }
}

459.重复的子字符串

力扣题目链接

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

示例 1:

输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"
输出: False

示例 3:

输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

解答：

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int len = s.length();
        if(len <= 1) return false;
        char[] ss = s.toCharArray();
        int[] next_ss = getnext(ss);
        if(next_ss[len-1] > 0 && len%(len - next_ss[len-1]) == 0) return true;

        return false;
    }

    public int[] getnext(char[] ss){
        int[] next = new int[ss.length];
        int j = 0;
        next[0] = j;
        for(int i = 1; i < ss.length; i++){
            while(j > 0 && ss[j] != ss[i]){
                j = next[j-1];
            }
            if(ss[j] == ss[i]){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}

总结

双指针法是字符串处理的常客

KMP算法是字符串查找最重要的算法

344.反转字符串​

541. 反转字符串II​

替换数字​

151.翻转字符串里的单词​

右旋字符串​

28. 实现 strStr()​

459.重复的子字符串​

总结​

344.反转字符串

541. 反转字符串II

替换数字

151.翻转字符串里的单词

右旋字符串

28. 实现 strStr()

459.重复的子字符串

总结