算法-字符串笔记

双指针

反转字符串

344. 反转字符串 - 力扣（LeetCode）

public class Solution {/*** 反转字符串的方法* @param s 需要被反转的字符数组*/public void reverseString(char[] s) {// 初始化左右指针，分别指向字符串的首尾int left = 0;int right = s.length - 1;// 当左指针小于右指针时，继续循环while(left < right) {// 交换左右指针所指向的字符char temp = s[left];s[left] = s[right];s[right] = temp;// 左指针向右移动，右指针向左移动left++;right--;}}
}

反转字符串II

541. 反转字符串 II - 力扣（LeetCode）

public class Solution {/*** 反转字符串的方法，每k个字符进行一次反转* @param s 需要被部分反转的字符串* @param k 每k个字符进行一次反转* @return 反转后的字符串*/public String reverseStr(String s, int k) {// 获取字符串长度int len = s.length();// 将字符串转换为字符数组char ch[] = s.toCharArray();// 遍历字符数组，步长为2k，确保每次处理k个字符for (int i = 0; i < len; i += 2 * k) {// 反转从索引i开始的k个字符reverse(ch, i, Math.min(len - 1, i + k - 1));}// 将字符数组转换回字符串并返回return new String(ch);}/*** 反转字符数组中从begin到end的部分* @param ch 字符数组* @param begin 反转的起始索引* @param end 反转的结束索引*/void reverse(char[] ch, int begin, int end) {// 当begin小于end时，继续循环while (begin < end) {// 交换begin和end位置的字符char temp = ch[end];ch[end] = ch[begin];ch[begin] = temp;// 移动指针begin++;end--;}}
}

反转字符串（局部与全部反转）

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

import java.util.*;public class Main {public static void main(String[] args) {// 创建 Scanner 对象用于读取标准输入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);  // 反转字符串的前 n 个字符reverseString(chars, 0, n - 1);  // 反转字符串从索引 n 到末尾的部分reverseString(chars, n, len - 1);  // 使用 Arrays 类的 toString 方法将字符数组转换为字符串，并打印结果System.out.println(new String(chars));}// 定义一个方法来反转字符数组中指定区间的字符public static void reverseString(char[] ch, int start, int end) {// 使用异或操作进行原地字符串反转，这种方法不需要额外的存储空间while (start < end) {// 交换 ch[start] 和 ch[end] 的值ch[start] ^= ch[end];ch[end] ^= ch[start];ch[start] ^= ch[end];// 移动 start 和 end 指针，向中间靠拢，继续交换下一对字符start++;end--;}}
}

拼接字符串

替换数字

54. 替换数字（第八期模拟笔试） (kamacoder.com)

import java.util.*;public class Main {public static void main(String[] args) {// 创建Scanner对象，用于从标准输入读取数据Scanner input = new Scanner(System.in);// 读取用户输入的一行文本String s = input.nextLine();// 创建StringBuilder对象，用于构建最终的字符串StringBuilder sb = new StringBuilder();// 遍历输入字符串的每个字符for (int i = 0; i < s.length(); i++) {char temp = s.charAt(i);// 如果字符是小写字母，将其添加到StringBuilder中if (temp >= 'a' && temp <= 'z') {sb.append(temp);}// 如果字符是数字（1-9），则将字符串"number"添加到StringBuilder中if (temp >= '1' && temp <= '9') {sb.append("number");}}// 输出最终构建的字符串System.out.println(sb.toString());// 关闭Scanner对象input.close();}}

java操作字符串的api

翻转字符串里的单词（去首尾空白符，分割字符串，反转字符串，合并List为字符串）

151. 反转字符串中的单词 - 力扣（LeetCode）

class Solution {public String reverseWords(String s) {// 除去开头和末尾的空白字符s = s.trim();// 正则匹配连续的空白字符作为分隔符分割List<String> wordList = Arrays.asList(s.split("\\s+"));Collections.reverse(wordList);return String.join(" ", wordList);}
}

trim方法：

// 除去开头和末尾的空白字符s = s.trim();

去掉两端的空白字符，截取中间的非空白字符，并且返回一个新的String字符串。

split方法：

// 正则匹配连续的空白字符作为分隔符分割List<String> wordList = Arrays.asList(s.split("\\s+"));

• s 是一个字符串变量。
• split 方法是String类的一个方法，它根据给定的正则表达式将字符串分割成子字符串数组。
• \\s+ 是一个正则表达式，\\s 匹配任何空白字符（包括空格、制表符、换行符等），+ 表示匹配一个或多个空白字符。
• 因此，s.split("\\s+") 的作用是将字符串 s 按照一个或多个空白字符进行分割，返回一个字符串数组，数组中的每个元素都是原字符串中的一个单词。

join方法：

String.join(" ", wordList);

这行代码的作用是：

• 使用空格（" "）作为分隔符，将wordList列表中的所有单词连接成一个单一的字符串。
• 返回这个连接后的字符串。

例如，如果wordList包含单词["hello", "world", "this", "is", "Kimi"]，那么String.join(" ", wordList);将返回字符串"hello world this is Kimi"。

KMP算法

KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。

在这里我做了详细的介绍

KMP算法-CSDN博客

判断是否含有子串 （难）

. - 力扣（LeetCode）

class Solution {public int strStr(String haystack, String needle) {// 获取haystack和needle的长度int n = haystack.length();int m = needle.length();// 将haystack和needle转换为字符数组char hayChar[] = haystack.toCharArray();char needChar[] = needle.toCharArray();// 创建next数组，用于KMP算法int next[] = new int[m];int j = 0; // j用于指向needle的当前字符// 构建next数组for(int i = 1; i < m; i++){// 当当前字符与模式中的字符不匹配时，更新jwhile(needChar[i] != needChar[j] && j > 0){j = next[j - 1]; // 回退到上一个匹配的位置}// 如果字符匹配，j自增if(needChar[i] == needChar[j]){j++;}next[i] = j; // 记录next数组}j = 0; // 重置j用于haystack的匹配// 遍历haystack进行匹配for(int i = 0; i < n; i++){// 如果当前字符不匹配，更新jwhile(haystack.charAt(i) != needle.charAt(j) && j > 0){j = next[j - 1]; // 回退到上一个匹配的位置}// 如果字符匹配，j自增if(needle.charAt(j) == haystack.charAt(i)){j++;}// 如果j达到了needle的长度，说明找到了匹配if(j == m){return i - m + 1; // 返回匹配的起始索引}}// 如果没有找到匹配，返回-1return -1;}
}

判断是否有重复的子字符串（难）

459. 重复的子字符串 - 力扣（LeetCode）

public class Solution {/*** 检查字符串 s 是否为某个子串的重复模式。* 例如，字符串 "abab" 是 "ab" 的重复模式，因为 "abab" 可以由 "ab" 重复两次构成。* * @param s 输入的字符串* @return 如果字符串是某个子串的重复模式，则返回 true，否则返回 false*/public boolean repeatedSubstringPattern(String s) {// 获取字符串的长度int len = s.length();// 创建一个数组用于存储next数组，next数组用于计算字符串的前缀函数int[] next = new int[len];// 初始化next数组的第一个元素为0，因为空字符串是任何字符串的前缀next[0] = 0;// j用来记录当前比较的子串的起始位置int j = 0;// 遍历字符串的每个字符for (int i = 1; i < len; i++) {// 当当前字符不等于j位置的字符，且j不为0时，j回溯到next数组指定的位置while (s.charAt(i) != s.charAt(j) && j > 0) {j = next[j - 1];}// 如果当前字符等于j位置的字符，j向前移动一位if (s.charAt(i) == s.charAt(j)) {j++;}// 更新next数组next[i] = j;}// 检查是否为重复子串模式// 如果next数组的最后一个元素不为0，说明存在重复模式// 并且字符串长度能够被(长度 - next数组的最后一个元素)整除// 则说明字符串可以由某个子串重复构成if (next[len - 1] != 0 && len % (len - next[len - 1]) == 0) {return true;}// 如果不是重复模式，则返回falsereturn false;}
}