代码随想录_字符串

字符串

344.反转字符串

344. 反转字符串

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

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

思路: 双指针

代码:

class Solution {
    public void reverseString(char[] s) {
        // 双指针
        int l = 0,r = s.length - 1;
        while(l < r) {
            char t = s[l];
            s[l] = s[r];
            s[r] = t;
            l++;
            r--;
        }
    }
}

• 时间复杂度: O(n)
• 空间复杂度: O(1)

541.反转字符串 II

541. 反转字符串 II

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

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

思路: 步长为2k进行循环, 每次循环内对: 2k的前k个 或 不足2k的剩余所有, 进行反转

代码:

class Solution {
    public String reverseStr(String s, int k) {
        char[] str = s.toCharArray();

        // 1. 2k 2k 循环遍历
        for(int i = 0;i < str.length;i += 2*k) {

            // 2. 找2k的前k个 或 不足2k的剩余所有 进行反转
            int start = i;
            int end = Math.min(str.length - 1,start + k - 1);

            while(start < end) {
                char t = str[start];
                str[start] = str[end];
                str[end] = t;

                start++;
                end--;
            }
        }

        // 3. 反转
        return new String(str);
    }
}

54.替换数字

54.替换数字（第八期模拟笔试）

思路: 双指针, 先计算新数组的大小, 将原数组复制到新数组后, 从后往前开始替换

代码:

import java.util.*;
public class Main{
    
    public static void main (String[] args) {
        // 1. 输入
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        char[] oStr = s.toCharArray();
        
        // 2. 计算新数组的长度
        int olen = oStr.length;
        int nlen = olen;
        for(int i = 0;i < olen;i++) {
            if(oStr[i] >= '0' && oStr[i] <= '9') {
                nlen += 5;// number共6位, 覆盖原来字母一位, 每次还需再加5位
            }
        }
        
        // 3. 将原数组的内容copy到新数组
        char[] nStr = new char[nlen];
        for(int i = 0;i < olen;i++) {
            nStr[i] = oStr[i];
        }
        
        // 4. 对新数组进行处理
        for(int i = olen - 1,j = nlen - 1;i >= 0;i--) {
            if(nStr[i] >= '0' && nStr[i] <= '9') {
                nStr[j--] = 'r';
                nStr[j--] = 'e';
                nStr[j--] = 'b';
                nStr[j--] = 'm';
                nStr[j--] = 'u';
                nStr[j--] = 'n';
            }else {
                nStr[j--] = nStr[i]; 
            }
        }
        
        // 5. 打印结果
        System.out.print(nStr);    
        
    }
}

法二: 不将原数组的内容copy到新数组

import java.util.*;
public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char[] s = str.toCharArray();
        // 1. 计算新数组长度
        int len = s.length;
        int newLen = len;
        for(int i = 0;i < len;i++) {
            if(s[i] >= '0' && s[i] <= '9') {
                newLen+=5;
            }
        }
        // 2. 替换
        char[] c = new char[newLen];
        for(int i = len - 1,j = newLen - 1;i >= 0;i--) {
            if(s[i] >= '0' && s[i] <= '9') {
                c[j--] = 'r';
                c[j--] = 'e';
                c[j--] = 'b';
                c[j--] = 'm';
                c[j--] = 'u';
                c[j--] = 'n';
            }else {
                c[j--] = s[i];
            }
        }
        
        // 3. 输出
        System.out.print(c);
        
    }
}

151.反转字符串中的单词

反转字符串中的单词

思路: 双指针, 先去掉多余空格, 再反转整个字符串, 最后反转每个单词

代码:

class Solution {
    public String reverseWords(String s) {
        char[] str = s.toCharArray();
        // 1. 去除 首尾 以及 中间 多余空格
        str = removeSpace(str);
        // 2. 将整个字符串反转
        reverse(str,0,str.length - 1);
        // 3. 将每个单词反转
        reverseEachWords(str);

        return new String(str);
    }

    // 1. 去除 首尾 以及 中间 多余空格
    public static char[] removeSpace(char[] str) {
        int slow = 0;
        // 1. 去空格
        for(int fast = 0;fast < str.length;fast++) {
            
            // 该if 每次操作一个单词
            if(str[fast] != ' ') {// fast所指的是字母时开始移动
                if(slow != 0) {// 处理是否加空格
                    str[slow++] = ' ';
                }
                // 加单词, slow每次增加一个单词的长度
                while(fast < str.length && str[fast] != ' ') {// 顺序不能换, 否则下标越界
                    str[slow++] = str[fast++];
                }
            }

        }

        // 2. 返回有效数组
        return Arrays.copyOfRange(str,0,slow);// 0 ~ (slow - 1
    }

    // 2. 将整个字符串反转
    public static void reverse(char[] str,int left,int right) {
        while(left < right) {
            str[left] ^= str[right];
            str[right] ^= str[left];
            str[left] ^= str[right];
			// 注意两个指针的变换不同
            left++;
            right--;
        }
    }

    // 3. 将每个单词反转
    public static void reverseEachWords(char[] str) {
        for(int start = 0,end = 0;end <= str.length;end++) { 
            // end = str.length 便于与 str[end] = ' ' 统一操作
            if(end == str.length || str[end] == ' ') {// 走到一个单词尽头
                reverse(str,start,end - 1);// 反转该单词
                start = end + 1;// 更新start位置
            }
        }
    }

}

55.右旋字符串（第八期模拟笔试）

右旋字符串（第八期模拟笔试）

题目描述

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

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

输入描述

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

输出描述

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

思路: 反转字符串, 先反转整体, 再依次翻转子串

代码:

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        String s = sc.next();
        char[] str = s.toCharArray();
        int len = str.length;
        // 1. 整体翻转
        reverse(str,0,len - 1);
        // 2. 前半部分翻转
        reverse(str,0,n - 1);
        // 3. 后半部分翻转
        reverse(str,n,len - 1);
        System.out.print(str);
    }
    
    public static void reverse(char[] str,int left,int right) {
        while(left < right) {
            str[left] ^= str[right];
            str[right] ^= str[left];
            str[left] ^= str[right];
            left++;
            right--;
        }
    }
}

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

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

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

提示：

• 1 <= haystack.length, needle.length <= 104
• haystack 和 needle 仅由小写英文字符组成

思路: kmp

代码:

class Solution {
    public int strStr(String haystack, String needle) {
        char[] s1 = haystack.toCharArray();
        char[] s2 = needle.toCharArray();
        int m = s1.length,n = s2.length;

        // 1. 计算next数组
        int[] next = nextArray(s2,n);
        
        // 2. 匹配子串
        int x = 0,y = 0;// x,y分别指向s1,s2当前操作的位置
        while(x < m && y < n) {
            if(s1[x] == s2[y]) {// 两字符串当前位置相等
                x++;// 继续往后匹配
                y++;
            }else if(y > 0) {// 两字符串当前位置不相等, s2要匹配的不是第一个字母
                y = next[y];// y前退
            }else {// 两字符串当前位置不相等, s2要匹配的是第一个字母
                x++;// s1往后走
            }
        }

        return y == n ? x - y : -1;// s2是否完全匹配
    }

    // 1. 计算next数组
    public static int[] nextArray(char[] s2,int len) {
        // 1.1 对0 1位置的特殊判断
        if(len == 1) return new int[] {-1};
        int[] next = new int[len];
        next[0] = -1;
        next[1] = 0;

        // 1.2 完善next数组
        int cnt = 0,i = 2;
        while(i < len) {
            if(s2[i - 1] == s2[cnt]) {// 当前位置和要比对的位置相同
                next[i++] = ++cnt;// 前缀和累加
            }else if(cnt > 0) {
                cnt = next[cnt];// 当前位置和要比对的位置不相同, 能往前退就往前退
            }else {// 当前位置和要比对的位置不相同, 不能往前退, 则next[i] = 0
                next[i++] = 0;
            }
        }

        // 1.3 返回
        return next;
    }
}

注: 不能用for, 因为每次判断i不一定要往后走

459.重复的子字符串

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

思路: kmp求next数组, 求到len + 1的位置, 求出整个串的最长公共前后缀, 原串减去公共前后缀剩下的就是最小重复子字符串

代码随想录讲解

代码:

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 1. 计算next数组(要将整个串的最长公共前后缀计算出来)
        char[] cs = s.toCharArray();
        int len = cs.length;
        int[] next = getNext(cs,len);

        // 2. 判断原字符串的长度是否是 公共前后缀剩余串(最小子串)的整数倍
        if(next[len] > 0 && len % (len - next[len]) == 0) {// 要判断next[len] > 0
            // 3. 返回
            return true;
        }
        return false;
    }

    // 1. 计算next数组(要将整个串的最长公共前后缀计算出来)
    public int[] getNext(char[] cs,int len) {
        // 1. 对0 1位置的特殊判断
        if(len == 1) {
            return new int[] {-1,0};
        }

        // 2. 补充next数组
        int i = 2,cnt = 0;// i代表当前处理的位置(后缀),cnt前缀的位置
        int[] next = new int[len + 1];// 要计算整个数组的最长公共前后缀
        next[0] = -1;
        next[1] = 0;
        while(i <= len) {
            if(cs[i - 1] == cs[cnt]) {
                next[i++] = ++cnt;
            }else if (cnt > 0) {
                cnt = next[cnt];
            }else {
                next[i++] = cnt;
            }
        }

        // 3. 返回
        return next;
    }
}