字符串|CK博客

1、反转字符1

题目:

https://leetcode.cn/problems/reverse-string/description/

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

2、反转字符串2

题目:https://leetcode.cn/problems/reverse-string/description/

代码：

class Solution {
    public String reverseStr(String s, int k) {
        int n=s.length();
        char[] arr=s.toCharArray();
        for(int i=0;i<n;i+=2*k){
            reverse(arr,i,Math.min(i+k,n)-1);
        }
        return new String(arr);
    }

     public void reverse(char[] arr, int left, int right) {
        while(left<right){
            char temp=arr[left];
            arr[left]=arr[right];
            arr[right]=temp;
            left++;
            right--;
        }
     }
}

主要是for循环这里的简化以及最后的k和length的判断(看是否有k个字符了，不判断的话会移动空字符串)

3、替换数字

题目：https://programmercarl.com/kamacoder/0054.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html

代码

import java.util.*;

public class Main {
     public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String s = sc.next();
        int n=s.length();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)>='0'&&s.charAt(i)<='9')
                n+=5;
        }
        char[] ch=new char[n];
        for(int i=0;i<s.length();i++){
            ch[i]=s.charAt(i);
        }
        for(int i=n-1,j=s.length()-1;j>=0;j--){
            if(ch[j]>='0'&&ch[j]<='9'){
                ch[i--]='r';
                ch[i--]='e';
                ch[i--]='b';
                ch[i--]='m';
                ch[i--]='u';
                ch[i--]='n';
            }
            else{
                ch[i--]=ch[j];
            }
        }
        System.out.println(ch);
        }
}

双指针

java 字符串不能修改

为什么要从后向前填充，从前向后填充不行么？

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素整体向后移动。

其实很多数组填充类的问题，其做法都是先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

这么做有两个好处：

不用申请新数组。
从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

4、反转字符串中的单词

https://leetcode.cn/problems/reverse-words-in-a-string/description/

代码

class Solution {
    public String reverseWords(String s) {
        s=s.trim();//去除前后多余空格
        List<String> list=Arrays.asList(s.split("\\s+"));//以空格分割
        Collections.reverse(list);//反转
        return String.join(" ",list);//空格拼接
    }
}

class Solution {
    public String reverseWords(String s) {
        s = s.trim();                                    // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') i--;     // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while (i >= 0 && s.charAt(i) == ' ') i--;     // 跳过单词间空格
            j = i;                                       // j 指向下个单词的尾字符
        }
        return res.toString().trim();                    // 转化为字符串并返回
    }
}

5、右旋转字符串

https://kamacoder.com/problempage.php?pid=1065

import java.util.*;

public class Main {
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();
        int len = s.length();  //获取字符串长度
        StringBuilder sb=new StringBuilder();
        char[] arr=s.toCharArray();
        for(int i=len-n;i<len;i++){
            sb.append(arr[i]);
        }
        for(int i=0;i<len-n;i++){
             sb.append(arr[i]);
        }   
        
        System.out.println(sb.toString());
         in.close();  // 关闭 Scanner
        }
}



import java.util.*;

public class Main {
     public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();
        int len = s.length();  //获取字符串长度
        StringBuilder sb=new StringBuilder();
        char[] arr=s.toCharArray();
        sb.append(s.substring(s.length() - n, s.length()));
        sb.append(s.substring(0, s.length() - n));
        
        System.out.println(sb.toString());
         in.close();  // 关闭 Scanner
        }
}

// 版本一
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();

        int len = s.length();  //获取字符串长度
        char[] chars = s.toCharArray();
        reverseString(chars, 0, len - 1);  //反转整个字符串
        reverseString(chars, 0, n - 1);  //反转前一段字符串，此时的字符串首尾尾是0,n - 1
        reverseString(chars, n, len - 1);  //反转后一段字符串，此时的字符串首尾尾是n,len - 1
        
        System.out.println(chars);

    }

    public static void reverseString(char[] ch, int start, int end) {
        //异或法反转字符串，参照题目 344.反转字符串的解释
        while (start < end) {
            ch[start] ^= ch[end];
            ch[end] ^= ch[start];
            ch[start] ^= ch[end];
            start++;
            end--;
        }
    }
}


// 版本二
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();

        int len = s.length();  //获取字符串长度
        char[] chars = s.toCharArray();
        reverseString(chars, 0, len - n - 1);  //反转前一段字符串，此时的字符串首尾是0,len - n - 1
        reverseString(chars, len - n, len - 1);  //反转后一段字符串，此时的字符串首尾是len - n,len - 1
        reverseString(chars, 0, len - 1);  //反转整个字符串

        System.out.println(chars);

    }

    public static void reverseString(char[] ch, int start, int end) {
        //异或法反转字符串，参照题目 344.反转字符串的解释
        while (start < end) {
            ch[start] ^= ch[end];
            ch[end] ^= ch[start];
            ch[start] ^= ch[end];
            start++;
            end--;
        }
    }
}

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

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

class Solution {
    //前缀表（不减一）Java实现
    public int strStr(String haystack, String needle) {
        if(haystack.length()<needle.length())
            return -1;
        if (needle.length() == 0) return 0;
        int[] next = new int[needle.length()];
        getNext(next,needle);
        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 (needle.charAt(j) == haystack.charAt(i)) 
                j++;
            if (j == needle.length()) 
                return i - needle.length() + 1;
        }
        return -1;
        }
    

    public void getNext(int[] next,String needle){
        int j=0;
        next[0]=0;
        for(int i=1;i<needle.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;
        }
    }
}

7、重复的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/description/

解法① kmp匹配

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int[] next=new int[s.length()];
        getNext(next,s);
        int max1=s.length()-next[s.length()-1];
        if(s.length()%max1==0&&next[s.length()-1]!=0)
            return true;
    return  false;
    }

    public  void getNext(int[] next,String s){
        int j=0;
        next[j]=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;
        }
    }
}

解法②

s+s

去除前后字符

看新的字符串是否包含s

class Solution {
    public boolean repeatedSubstringPattern(String s) {

        return  (s.substring(1, s.length()) + s.substring(0, s.length() - 1)).contains(s);
    
    }

}

③

s=abc s+s=abcabc

从下标1开始包含abc的索引是下标3 正好等于s的长度

从第二个字符开始，看是否包含s 且索引是否等于s的长度

class Solution {
    public boolean repeatedSubstringPattern(String s) {

       return (s + s).indexOf(s, 1) != s.length();
    
    }

}

栈与队列

Navicat导入SqlServer备份的bak文件(超详细)

lucky