代码随想录 算法训练 Day8：字符串part01

题目：

344.反转字符串

建议： 本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下 平时刷题什么时候用 库函数，什么时候 不用库函数

力扣题目链接(opens new window)

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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"]

题目链接/文章讲解/视频讲解：https://programmercarl.com/0344.反转字符串.html

541. 反转字符串II

建议：本题又进阶了，自己先去独立做一做，然后在看题解，对代码技巧会有很深的体会。

力扣题目链接(opens new window)

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

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

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

示例:

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

输出: "bacdfeg"

题目链接/文章讲解/视频讲解：https://programmercarl.com/0541.反转字符串II.html

卡码网：54.替换数字

建议：对于线性数据结构，填充或者删除，后序处理会高效的多。好好体会一下。

题目链接/文章讲解：替换数字

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

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

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

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

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

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

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

答案：

public class String1 {/*** 字符串反转函数* 该函数将输入的字符串进行反转，例如"abc"反转后变成"cba"* * 算法思路：使用双指针法，从字符串两端向中间移动，交换对应位置的字符* 时间复杂度：O(n)，其中n是字符串的长度，需要遍历字符串的一半* 空间复杂度：O(1)，不需要额外的空间* * @param s 需要反转的字符数组*/public static char[] reverse(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--;}return s;}/*** 541. 反转字符串 II* 给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。* * 如果剩余字符少于 k 个，则将剩余字符全部反转。* 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。* * 算法思路：按照题目要求，每隔 2k 个字符，反转前 k 个字符* 时间复杂度：O(n)，其中 n 是字符串的长度* 空间复杂度：O(n)，需要创建一个 StringBuffer 来存储结果* * @param s 输入的字符串* @param k 反转的长度参数* @return 按规则反转后的字符串*/public static String reverseStr(String s, int k) {// 边界条件判断if(s.length() == 0||k == 0 ) {return s;}// 创建结果字符串缓冲区StringBuffer res = new StringBuffer();// 获取字符串长度int length = s.length();// 初始化起始位置int start = 0;// 循环处理字符串，每次处理 2k 个字符while (start < length) {// 创建临时字符串缓冲区，用于存储需要反转的部分StringBuffer temp = new StringBuffer();// 计算第一个 k 的位置（可能会超出字符串长度）// 如果 start+k 超出字符串长度，则取字符串长度作为边界int firstK = (start + k > length) ? length : start + k;// 计算第二个 k 的位置（即 2k 处）// 如果 start+2k 超出字符串长度，则取字符串长度作为边界int secondK = (start + (2 * k) > length) ? length : start + (2 * k);// 处理前 k 个字符：将其添加到临时缓冲区并反转// 无论剩余长度如何，都会反转 start 到 firstK 之间的字符temp.append(s.substring(start, firstK));res.append(temp.reverse());// 处理后 k 个字符：如果存在，则直接添加到结果中（不反转）// 只有当 firstK < secondK 时，才有后 k 个字符需要处理if (firstK < secondK) { // 此时剩余长度一定大于 kres.append(s.substring(firstK, secondK));}// 移动起始位置，准备处理下一个 2k 字符块start += (2 * k);}// 返回最终结果字符串return res.toString();}/*** 字符串数字替换函数* 该函数将输入字符串中的所有数字字符替换为"number"字符串* * 算法思路：遍历字符串的每个字符，检测是否为数字，如果是则替换为"number"，否则保持不变* 时间复杂度：O(n)，其中n是字符串的长度，需要遍历整个字符串* 空间复杂度：O(n)，在最坏情况下（全是数字），结果字符串的长度将是原始字符串长度的6倍* * @param s 需要处理的输入字符串* @return 替换数字后的新字符串*/public static String replaceDigitsWithNumber(String s) {// 创建StringBuilder对象用于高效构建结果字符串StringBuilder result = new StringBuilder();// 遍历输入字符串的每个字符for (int i = 0; i < s.length(); i++) {// 获取当前位置的字符char c = s.charAt(i);// 判断当前字符是否为数字（ASCII码范围：'0'=48 到 '9'=57）if (c >= '0' && c <= '9') {  // 判断是否为数字// 如果是数字，则追加"number"字符串到结果中result.append("number");} else {// 如果不是数字（即是字母或其他字符），则直接追加到结果中result.append(c);  // 字母直接保留}}// 将StringBuilder转换为String并返回最终结果return result.toString();}public static void main(String[] args) {// 正确创建字符数组char[] str1 = "abc".toCharArray();// 使用reverse方法char[] str2 = reverse(str1);System.out.println(new String(str2));String s = "jdjnsdjsdok";int k = 3;String str3 = reverseStr(s, k);System.out.println(new String(str3));String input = "a1b2c3";String output = replaceDigitsWithNumber(input);System.out.println(output);  // 输出: anumberbnumbercnumber}
}