【算法通关村 Day12】字符串

字符串青铜挑战

字符串转换

转换为小写字母

给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。leetcode791

public class ToLowerCase {/*** 将字符串中的大写字母转换为小写字母。** @param s 输入字符串* @return 转换后的字符串，其中所有大写字母都已转换为小写字母*/public String toLowerCase(String s) {StringBuilder result = new StringBuilder(); // 使用 StringBuilder 以提高效率for (char c : s.toCharArray()) {if (c >= 'A' && c <= 'Z') {// 大写字母的 ASCII 码在 'A' 到 'Z' 之间// 小写字母的 ASCII 码比对应的大写字母大 32result.append((char) (c + 32));} else {// 非大写字母，直接添加到结果中result.append(c);}}return result.toString();}//使用Java内置函数public String toLowerCaseBuiltIn(String s) {return s.toLowerCase(); // 直接使用 String 类的 toLowerCase() 方法}public static void main(String[] args) {ToLowerCase tlc = new ToLowerCase();// 示例用法String str1 = "Hello";String lowerStr1 = tlc.toLowerCase(str1);System.out.println(str1 + " 转换为小写: " + lowerStr1); // 输出: Hello 转换为小写: helloString str2 = "here";String lowerStr2 = tlc.toLowerCase(str2);System.out.println(str2 + " 转换为小写: " + lowerStr2); // 输出: here 转换为小写: hereString str3 = "LOVELY";String lowerStr3 = tlc.toLowerCase(str3);System.out.println(str3 + " 转换为小写: " + lowerStr3); // 输出: LOVELY 转换为小写: lovelyString str4 = "HeLlO wOrLd";String lowerStr4 = tlc.toLowerCase(str4);System.out.println(str4 + " 转换为小写: " + lowerStr4); // 输出: HeLlO wOrLd 转换为小写: hello worldString str5 = "Hello";String lowerStr5 = tlc.toLowerCaseBuiltIn(str5);System.out.println(str5 + " 转换为小写 (使用内置函数): " + lowerStr5); //输出: Hello 转换为小写 (使用内置函数): hello}
}

字符串转换整数

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

函数 myAtoi(string s) 的算法如下：

1. 空格：读入字符串并丢弃无用的前导空格（" "）
2. 符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
3. 转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
4. 舍入：如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被舍入为 −231 ，大于 231 − 1 的整数应该被舍入为 231 − 1 。

返回整数作为最终结果。

public class MyAtoi {/*** 实现一个 myAtoi(String s) 函数，将字符串转换为一个 32 位有符号整数。** @param s 输入字符串* @return 转换后的 32 位有符号整数*/public int myAtoi(String s) {int index = 0; // 指向当前字符的索引int sign = 1;  // 符号 (1 表示正数, -1 表示负数)int result = 0; // 结果// 1. 跳过前导空格while (index < s.length() && s.charAt(index) == ' ') {index++;}// 2. 处理符号if (index < s.length() && (s.charAt(index) == '+' || s.charAt(index) == '-')) {sign = (s.charAt(index) == '-') ? -1 : 1;index++;}// 3. 读取数字while (index < s.length() && Character.isDigit(s.charAt(index))) {int digit = s.charAt(index) - '0'; // 获取数字值// 4. 检查溢出 (关键步骤)// 如果 result > Integer.MAX_VALUE / 10, 那么 result * 10 一定会溢出// 如果 result == Integer.MAX_VALUE / 10, 但是 digit > 7, 那么 result * 10 + digit 也会溢出 (因为 Integer.MAX_VALUE 最后一位是 7)if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && digit > 7)) {return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;}result = result * 10 + digit;index++;}// 5. 返回结果return sign * result;}public static void main(String[] args) {MyAtoi atoi = new MyAtoi();// 示例用法String str1 = "42";int num1 = atoi.myAtoi(str1);System.out.println("\"" + str1 + "\" 转换为整数: " + num1); // 输出: "42" 转换为整数: 42String str2 = "   -42";int num2 = atoi.myAtoi(str2);System.out.println("\"" + str2 + "\" 转换为整数: " + num2); // 输出: "   -42" 转换为整数: -42String str3 = "4193 with words";int num3 = atoi.myAtoi(str3);System.out.println("\"" + str3 + "\" 转换为整数: " + num3); // 输出: "4193 with words" 转换为整数: 4193String str4 = "words and 987";int num4 = atoi.myAtoi(str4);System.out.println("\"" + str4 + "\" 转换为整数: " + num4); // 输出: "words and 987" 转换为整数: 0String str5 = "-91283472332";int num5 = atoi.myAtoi(str5);System.out.println("\"" + str5 + "\" 转换为整数: " + num5); // 输出: "-91283472332" 转换为整数: -2147483648 (Integer.MIN_VALUE)}
}

字符串白银挑战

字符串反转

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。详见leetcode344

public class ReverseString {/*** 反转字符数组。** @param s 要反转的字符数组。*/public void reverseString(char[] s) {int left = 0;               // 指向数组开头的指针int right = s.length - 1;    // 指向数组末尾的指针// 使用双指针法进行反转while (left < right) {// 交换 left 和 right 指针指向的字符char temp = s[left];s[left] = s[right];s[right] = temp;// 移动指针left++;right--;}}public static void main(String[] args) {ReverseString rs = new ReverseString();// 示例用法char[] str1 = {'h', 'e', 'l', 'l', 'o'};rs.reverseString(str1);System.out.println("反转后的字符串: " + String.valueOf(str1)); // 输出: 反转后的字符串: ollehchar[] str2 = {'H', 'a', 'n', 'n', 'a', 'h'};rs.reverseString(str2);System.out.println("反转后的字符串: " + String.valueOf(str2)); // 输出: 反转后的字符串: hannaH}
}

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。如果剩余字符少于 k 个，则将剩余字符全部反转。如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。详见leetcode541

public class ReverseKGroup {/*** 根据规则反转字符串 s 的特定部分。** @param s 要操作的字符串* @param k 一个整数，指定反转字符的组大小* @return 修改后的字符串*/public String reverseStr(String s, int k) {char[] arr = s.toCharArray();  // 将字符串转换为字符数组，以便进行原地修改int n = arr.length;for (int i = 0; i < n; i += 2 * k) { // 以 2k 的步长迭代字符串// 确定要反转的子字符串的起始位置和结束位置int start = i;int end = Math.min(i + k - 1, n - 1); //确保end不超过数组的边界。如果剩余的字符小于 k 个，则将反转剩余的所有字符// 反转从 start 到 end 的字符reverse(arr, start, end);}return new String(arr); // 将修改后的字符数组转换回字符串}/*** 反转字符数组指定部分。** @param arr 要修改的字符数组* @param start 反转的起始索引* @param end   反转的结束索引*/private void reverse(char[] arr, int start, int end) {while (start < end) {char temp = arr[start];arr[start] = arr[end];arr[end] = temp;start++;end--;}}public static void main(String[] args) {ReverseKGroup rkg = new ReverseKGroup();// 示例用法String s1 = "abcdefg";int k1 = 2;String reversed1 = rkg.reverseStr(s1, k1);System.out.println("\"" + s1 + "\" 反转后的字符串 (k=" + k1 + "): " + reversed1); // 输出: "abcdefg" 反转后的字符串 (k=2): bacdfegString s2 = "abcd";int k2 = 2;String reversed2 = rkg.reverseStr(s2, k2);System.out.println("\"" + s2 + "\" 反转后的字符串 (k=" + k2 + "): " + reversed2); // 输出: "abcd" 反转后的字符串 (k=2): bacdString s3 = "abcdefghij";int k3 = 3;String reversed3 = rkg.reverseStr(s3, k3);System.out.println("\"" + s3 + "\" 反转后的字符串 (k=" + k3 + "): " + reversed3); //输出: "abcdefghij" 反转后的字符串 (k=3): cbadefihgj}
}

仅反转字母

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。leetcode917

public class ReverseOnlyLetters {/*** 反转字符串中的英文字母，同时保留其他字符的位置。** @param s 输入字符串* @return 反转后的字符串*/public String reverseOnlyLetters(String s) {char[] arr = s.toCharArray(); // 将字符串转换为字符数组int left = 0;                  // 左指针int right = arr.length - 1;       // 右指针while (left < right) {// 从左侧找到一个字母while (left < right && !Character.isLetter(arr[left])) {left++;}// 从右侧找到一个字母while (left < right && !Character.isLetter(arr[right])) {right--;}// 交换两个字母if (left < right) {char temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}return new String(arr); // 将修改后的字符数组转换回字符串}public static void main(String[] args) {ReverseOnlyLetters rol = new ReverseOnlyLetters();// 示例用法String s1 = "ab-cd";String reversed1 = rol.reverseOnlyLetters(s1);System.out.println("\"" + s1 + "\" 反转后的字符串: " + reversed1); // 输出: "ab-cd" 反转后的字符串: dc-baString s2 = "a-bC-dEf-ghIj";String reversed2 = rol.reverseOnlyLetters(s2);System.out.println("\"" + s2 + "\" 反转后的字符串: " + reversed2); // 输出: "a-bC-dEf-ghIj" 反转后的字符串: j-Ih-gfE-dCbaString s3 = "Test1ng-Leet=code-Q!";String reversed3 = rol.reverseOnlyLetters(s3);System.out.println("\"" + s3 + "\" 反转后的字符串: " + reversed3); // 输出: "Test1ng-Leet=code-Q!" 反转后的字符串: Qedo1ct-eeLg=ntse-T!}
}

反转字符串里的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词 之间用单个空格连接的结果字符串。
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

import java.util.Arrays;
import java.util.Collections;
import java.util.List;public class ReverseWords {/*** 反转字符串中单词的顺序，同时处理多余的空格。** @param s 输入字符串* @return 反转单词顺序后的字符串*/public String reverseWords(String s) {// 1. 去除首尾空格并按空格分割字符串成单词数组String[] words = s.trim().split("\\s+"); // \\s+ 表示一个或多个空格// 2. 反转单词数组List<String> wordList = Arrays.asList(words);Collections.reverse(wordList);// 3. 使用单个空格将单词连接成一个字符串return String.join(" ", wordList);}public static void main(String[] args) {ReverseWords rw = new ReverseWords();// 示例用法String s1 = "the sky is blue";String reversed1 = rw.reverseWords(s1);System.out.println("\"" + s1 + "\" 反转后的字符串: \"" + reversed1 + "\""); // 输出: "the sky is blue" 反转后的字符串: "blue is sky the"String s2 = "  hello world  ";String reversed2 = rw.reverseWords(s2);System.out.println("\"" + s2 + "\" 反转后的字符串: \"" + reversed2 + "\""); // 输出: "  hello world  " 反转后的字符串: "world hello"String s3 = "a good   example";String reversed3 = rw.reverseWords(s3);System.out.println("\"" + s3 + "\" 反转后的字符串: \"" + reversed3 + "\""); // 输出: "a good   example" 反转后的字符串: "example good a"}
}

字符串黄金挑战

字符串冲刺题

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。详见leetcode14

public class LongestCommonPrefix {/*** 查找字符串数组中的最长公共前缀。** @param strs 字符串数组* @return 最长公共前缀，如果不存在则返回 ""*/public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return ""; // 空数组或 null 数组，没有公共前缀}String prefix = strs[0]; // 假设第一个字符串是初始公共前缀// 遍历数组中的其余字符串for (int i = 1; i < strs.length; i++) {// 不断缩短 prefix，直到它成为 strs[i] 的前缀while (strs[i].indexOf(prefix) != 0) {prefix = prefix.substring(0, prefix.length() - 1); // 移除 prefix 的最后一个字符if (prefix.isEmpty()) {return ""; // 如果 prefix 为空，表示没有公共前缀}}}return prefix; // 返回最长公共前缀}public static void main(String[] args) {LongestCommonPrefix lcp = new LongestCommonPrefix();// 示例用法String[] strs1 = {"flower", "flow", "flight"};String prefix1 = lcp.longestCommonPrefix(strs1);System.out.println("最长公共前缀: " + prefix1); // 输出: 最长公共前缀: flString[] strs2 = {"dog", "racecar", "car"};String prefix2 = lcp.longestCommonPrefix(strs2);System.out.println("最长公共前缀: " + prefix2); // 输出: 最长公共前缀: ""String[] strs3 = {"cir", "car"};String prefix3 = lcp.longestCommonPrefix(strs3);System.out.println("最长公共前缀: " + prefix3); // 输出: 最长公共前缀: c}
}

压缩字符串

给你一个字符数组 chars ，请使用下述算法压缩：

从一个空字符串 s 开始。对于 chars 中的每组 连续重复字符 ：

• 如果这一组长度为 1 ，则将字符追加到 s 中。
• 否则，需要向 s 追加字符，后跟这一组的长度。

压缩后得到的字符串 s 不应该直接返回 ，需要转储到字符数组 chars 中。需要注意的是，如果组长度为 10 或 10 以上，则在 chars 数组中会被拆分为多个字符。

请在 修改完输入数组后 ，返回该数组的新长度。

你必须设计并实现一个只使用常量额外空间的算法来解决此问题。详见leetcode443

public class StringCompression {/*** 使用给定算法压缩字符数组。** @param chars 要压缩的字符数组。* @return 压缩后数组的新长度。*/public int compress(char[] chars) {int indexAns = 0;  // 写入压缩字符的位置int index = 0;     // 读取字符的位置while (index < chars.length) {char currentChar = chars[index]; // 当前字符int count = 0; // 当前字符的重复次数// 统计当前字符的重复次数while (index < chars.length && chars[index] == currentChar) {index++;count++;}// 将字符添加到数组中chars[indexAns++] = currentChar;// 如果重复次数大于 1，则将计数添加到数组中if (count > 1) {String countStr = String.valueOf(count); // 将计数转换为字符串for (int i = 0; i < countStr.length(); i++) {chars[indexAns++] = countStr.charAt(i); // 将计数的每个数字添加到数组中}}}return indexAns; // 返回数组的新长度}public static void main(String[] args) {StringCompression sc = new StringCompression();// 示例用法char[] chars1 = {'a', 'a', 'b', 'b', 'c', 'c', 'c'};int newLength1 = sc.compress(chars1);System.out.print("压缩后的数组: ");for (int i = 0; i < newLength1; i++) {System.out.print(chars1[i] + " ");}System.out.println("\n新长度: " + newLength1);// 输出: 压缩后的数组: a 2 b 2 c 3//       新长度: 6char[] chars2 = {'a'};int newLength2 = sc.compress(chars2);System.out.print("压缩后的数组: ");for (int i = 0; i < newLength2; i++) {System.out.print(chars2[i] + " ");}System.out.println("\n新长度: " + newLength2);// 输出: 压缩后的数组: a//       新长度: 1}
}