字符串

相关理论：代码随想录 字符串

1. 反转字符串

link: LeetCode 344

思考：使用双指针

class Solution {

    public void reverseString(char[] s) {

        int left = 0, right = s.length-1;

        while(left < right){

            char temp = s[left];

            s[left] = s[right];

            s[right] = temp;



            left++;

            right--;

        }

    }

}

2. 反转字符串Ⅱ

link: LeetCode 541

思路：

对数组进行遍历，每一次 \(i\) 移动 \(2k\) 个字符, 然后判断 \(i+k\) 是否超过了数组长度，如果超过则全部反转，如果没超过则只反转 \([i, i+k]\)

class Solution {

    public String reverseStr(String s, int k) {

        // 将字符串转为字符数组

        char ch[] = s.toCharArray();

        // 使用i开始遍历数组

        for (int i=0; i<ch.length; i+=2*k){

            // 当剩余字符大于k, 反转前k个

            if (i + k < ch.length) revise(ch, i, i+k-1);

            // 如果剩余字符少于k, 全部反转

            else revise(ch, i, ch.length-1);

        }



        return new String(ch);

    }




    public void revise(char[] s, int i, int j){

        while(i < j){

            char temp = s[i];

            s[i] = s[j];

            s[j] = temp;

            i++;

            j--;

        }

    }

}

方法二：使用 Java中的 StringBuffer

class Solution {

    public String reverseStr(String s, int k) {

        StringBuffer resBuffer = new StringBuffer();

        for (int i=0; i<s.length(); i+=2*k){

            // 首先判断是否还有k个字符

            // 寻找第k个字符的索引, 如果剩余的字符少于k个字符, 则索引为最后的字符

            int firstK = i + k < s.length()? i+k : s.length();

            // 寻找第2k个字符的索引, 如果剩余的字符少于 2k 个字符, 则索引为最后的字符

            int secondK = i + 2*k < s.length()? i+2*k : s.length();



            // 反转[i, firstK), 使用String自带的reverse方法

            StringBuffer tempBuffer = new StringBuffer();

            // subString 是左边右开

            tempBuffer.append(s.substring(i, firstK));

            resBuffer.append(tempBuffer.reverse());



            // 如果firstK到secondK之间有元素, 则直接添加到 resBuffer 中

            resBuffer.append(s.substring(firstK, secondK));

        }



        return resBuffer.toString();

    }

}

3. 替换数字

link: 卡码网 54

思考：

如果直接在原字符串进行修改，则先确定修改后的字符串长度，然后使用双指针，从后向前修改

但是： Java 的 String 不能原地修改, 因此必须再定义新的 StringBuffer

import java.lang.*;

import java.util.*;

public class Main{

    public static void main (String[] args) {
        StringBuffer resBuffer = new StringBuffer();
        String s;
        Scanner sc = new Scanner(System.in);
        s = sc.nextLine();

        for (int i=0; i<s.length();i++){
            if (Character.isDigit(s.charAt(i))){
                resBuffer.append("number");
            }else {
                resBuffer.append(s.charAt(i));
            }
        }
        System.out.println(resBuffer.toString());
    }
}

4. 反转字符串里的单词

link: LeetCode 151

思考： 首先移除多余的空格，然后将整个字符串反转，然后将每个单词再次反转

class Solution {

    public String reverseWords(String s) {

      // 1. 首先通过双指针去除空格

      // 因为对原字符串的长度发生了更改, 因此需要返回

      StringBuilder sb = reverseSpace(s);

      // 2. 将整个字符串进行反转

      reverseString(sb, 0, sb.length()-1);

      // 3. 反转每一个单词

      reverseEachWord(sb);



      return sb.toString();




    }

    // 反转整个字符串

    // 左闭右闭

    public void reverseString(StringBuilder sb, int start, int end){

        while(start < end){

            char temp = sb.charAt(start);

            sb.setCharAt(start, sb.charAt(end));

            sb.setCharAt(end, temp);

            start++;

            end--;

        }

    }

    // 反转每一个单词

    public void reverseEachWord(StringBuilder sb){

        int len = sb.length();

        // start 定义每一个单词的起始位置, 通过start遍历字符串, 找到每一个单词的起始位置

        // end定义每一个单词后面的空格的位置

        int start = 0, end = 1;

        while(start<len){

            // 寻找这个单词后面的空格的索引

            while (end < len && sb.charAt(end) != ' ') end++;

            // 寻找到单词的空格后

            // 反转这个单词

            reverseString(sb, start, end-1);

            start = end+1;

            end = end+2;

        }

    }



    // 去除空格

    public StringBuilder reverseSpace(String ss){

        // 先去除前面的元素和后面的元素

        int start=0;

        int len=ss.length()-1;

        while(ss.charAt(start) == ' ') start++;

        while(ss.charAt(len) == ' ') len--;




        // 定义需要返回的结果

        StringBuilder sb = new StringBuilder();

        // 寻找满足条件的元素

        while(start <= len){

            if (ss.charAt(start) != ' ' || ss.charAt(start-1) != ' ')

            {

                sb.append(ss.charAt(start));

            }

            start++;

        }



        return sb;




    }

}

class Solution {

    public String reverseWords(String s) {

       String ss[] = s.trim().split("\\s+");



       StringBuilder resBuilder = new StringBuilder();

       for (int i=ss.length-1; i>=0; i--){

            resBuilder.append(ss[i]);

            if (i > 0) resBuilder.append(" ");

       }



       return resBuilder.toString();



    }

}

5. 右旋转字符串

link : 卡码网 55

思考： 如果不申请额额外的空间，只在原字符串上操作

将后面的k个字符移动到前面，相当于将字符串向后移动 k 位，可以将字符串分为两部分

如果直接将整个字符串反转：

此时第一段和第二段正好是想要的，只不过他们是倒序的，再将他们分别反转

import java.lang.*;
import java.util.*;

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

        // System.out.println(k + " " + s);
        char ss[] = s.toCharArray();
        // 整体反转
        reverseChar(ss, 0, ss.length-1);
        // System.out.println(ss);
        // 反转第一段
        reverseChar(ss, 0, k-1);
        // 反转第二段
        reverseChar(ss, k, ss.length-1);

        System.out.println(ss);


    }

    // 对字符串进行反转 左闭右闭
    public static void reverseChar(char[] ss, int left, int right){
        while(left < right){
            char temp = ss[right];
            ss[right] = ss[left];
            ss[left] = temp;
            left++;
            right--;
        }

    }
    }