代码随想录--字符串习题总结

news/2025/1/16 2:59:15/

代码随想录–字符串习题总结

1.LeetCode344 反转字符串

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

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

示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

解题思路： 直接使用双指针，分别从数组的第一个和最后一个元素进行遍历，然后交换这两个元素即可。

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;}
}

2.LeetCode541 反转字符串II

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

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

示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：
输入：s = "abcd", k = 2
输出："bacd"

解题思路： 这个题不涉及什么算法，只是复杂逻辑的模拟。

  • 首先要明确的是，这道题中遍历字符串，是以2k个单位进行遍历的。
  • 我们写一个循环，来遍历整个字符串，进入循环后首先需要计算剩余元素的个数s.length() - i，后续我们会根据剩余元素的个数来判断是否执行不同的逻辑
  • 如果剩余元素的个数是>=2k的，那么之间反转前k个元素即可reverseStr(chars, i, i + k - 1), 然后i移动，遍历下一个2k区间
  • 如果剩余元素个数位于[k,2k)区间内，则依然遍历前k个元素即可reverseStr(chars, i, i + k - 1)，只不过直接break掉循环就可以了，因为后面也不可能在凑够2k个元素了，所以循环到这里直接终止就可以了
  • 如果剩余元素<k，则直接将剩余的所有元素反转即可reverseStr(chars, i, chars.length - 1)，同理反转完成后也可以直接break掉
public static String reverseStr(String s, int k) {char[] chars = s.toCharArray();// 开始循环遍历字符串for (int i = 0; i < s.length() - 1;) {// 计算当前剩余元素个数int count = s.length() - i;// 判断是否满足2k的条件if (2 * k <= count) {// 反转前k个元素// TODO 反转reverseStr(chars, i, i + k - 1);i = i + 2 * k;} else if (count < 2 * k && count >= k) {// TODO 反转前k个reverseStr(chars, i, i + k - 1);break;} else if (count < k) {// TODO 反转剩余元素reverseStr(chars, i, chars.length - 1);break;}}return new StringBuffer().append(chars).toString();
}private static void reverseStr(char[] chars, int start, int end) {while (start < end) {char temp = chars[start];chars[start++] = chars[end];chars[end--] = temp;}
}

image-20230120160851580

这个题还需要注意Java中String和char[]的互相转换

String 转 char[]

char[] chars = str.toCharArray();

char[] 转 String 需要借助StringBuilder

String str = new StringBuffer().append(chars).toString();

3. 剑指offer05 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."

解题思路1: 直接使用StringBuilder，遍历数组，只要发现有空格，就向StringBuilder中append%20，否则就把原来字符串中字符append。

public static String replaceSpace(String s) {StringBuilder sb = new StringBuilder();for (int i = 0; i < s.length(); i++) {// 这个地方比较的是字符相等不相等// if (" ".equals(s.charAt(i)))if (s.charAt(i) == ' ') {sb.append("%20");continue;}sb.append(s.charAt(i));}return sb.toString();
}

这个地方需要注意这个条件" ".equals(s.charAt(i))使用charAt(i)函数返回的是一个char，因此应该用==而不是equal方法

解题思路2: 使用双指针

  • 首先遍历整个字符串，统计空格个数
  • 然后按照空格个数，将字符串进行扩容
  • 然后i,j指针分别指向扩容前数组最后的元素，和扩容后数组的元素
  • 然后开始遍历，如果s[i]不是空格，则s[j] = s[i]
  • 如果是空格，则s[i] = '0';s[i - 1] = '2';s[i - 2] = '%';
  • 直到i==j停止循环。

image-20230120164523735

因为在Java中字符串是一个常量，我们没有办法像C++一样直接修改字符串中的某个字符，因此在Java语言中，这种方法实际上要比思路1时间复杂度更高一些。并不推荐使用，但是在C++中是可以的。下面给出C++和Java使用双指针解决这道题的代码。

class Solution {
public:string replaceSpace(string s) {int count = 0; // 统计空格的个数int sOldSize = s.size();for (int i = 0; i < s.size(); i++) {if (s[i] == ' ') {count++;}}// 扩充字符串s的大小，也就是每个空格替换成"%20"之后的大小s.resize(s.size() + count * 2);int sNewSize = s.size();// 从后先前将空格替换为"%20"for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {if (s[j] != ' ') {s[i] = s[j];} else {s[i] = '0';s[i - 1] = '2';s[i - 2] = '%';i -= 2;}}return s;}
};

public String replaceSpace(String s) {if(s == null || s.length() == 0){return s;}//扩充空间，空格数量2倍StringBuilder str = new StringBuilder();for (int i = 0; i < s.length(); i++) {if(s.charAt(i) == ' '){str.append("  ");}}//若是没有空格直接返回if(str.length() == 0){return s;}//有空格情况 定义两个指针int left = s.length() - 1;//左指针：指向原始字符串最后一个位置s += str.toString();int right = s.length()-1;//右指针：指向扩展字符串的最后一个位置char[] chars = s.toCharArray();while(left>=0){if(chars[left] == ' '){chars[right--] = '0';chars[right--] = '2';chars[right] = '%';}else{chars[right] = chars[left];}left--;right--;}return new String(chars);
}

4.Leetcode151 反转单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

解题思路1：

  • 使用trim函数取出字符串开头和结尾的空格
  • 使用split分割单词，形成一个string[], 每一个元素是一个单词
  • 然后反转string[]数组即可。
public String reverseWords(String s) {// 如果一个字符串中有多个连续的空格// trim()的作用String[] strings = s.trim().split(" ");int left = 0, right = strings.length - 1;// 反转数组while (left < right) {String temp = strings[left];strings[left++] = strings[right];strings[right--] = temp;}// 构建字符串StringBuilder sb = new StringBuilder();for (int i = 0; i < strings.length; i++) {if ("".equals(strings[i]))continue;if (i == strings.length - 1) {sb.append(strings[i]);continue;}sb.append(strings[i] + " ");}return sb.toString();
}

这里需要特别注意的是，如果String str = " hello world ";,那么使用split(" ")之后的得到的数组是：

image-20230120174654062

所以需要在添加到StringBuilder中忽略掉这些空字符串。

第二个需要注意的是，如果想去除掉字符串开头和结尾的空格，可以使用str.trim()函数

解题思路2： 将字符串先整体反转一次，然后在每一个单词内部反转一次，就可以得到最终的结果。这个地方的难点是因为给的字符串可能在开头和结尾都包含若干个空格，以及每一个单词之间还有可能存在多个空格，所以需要删除掉字符串中额外的空格。

public String reverseWords(String s) {// 去掉字符串中额外的空格String removeSpaces = removeSpaces(s);// 整个字符串反转一次char[] chars = removeSpaces.toCharArray();reverse(chars, 0, chars.length - 1);// 每个单词内部反转int rec = 0; // 记录单词的左边界for (int i = 0; i <= chars.length; i++) {if (i == chars.length || chars[i] == ' ') {// 第一个单词遍历完毕reverse(chars, rec, i - 1);rec = i + 1;}}return new StringBuilder().append(chars).toString();
}private String removeSpaces(String s) {char[] chars = s.toCharArray();int slow = 0;for (int fast = 0; fast < chars.length; fast++) {if (chars[fast] != ' ') {// 是单词// 判断slow 是不是在初始位置，// 如果不在初始位置，则需要在前面加空格if (slow != 0) {chars[slow++] = ' ';}// while循环将fast指向的单词添加到slow中// 只要chars[fast] != ' ' 那么说明fast一直指向的都是这个单词while (fast < chars.length && chars[fast] != ' ') {chars[slow++] = chars[fast++];}}}return new StringBuilder().append(chars, 0, slow).toString();
}/*** 反转字符串* @param chars* @param start* @param end*/
private void reverse(char[] chars, int start, int end) {while (start < end) {char temp = chars[start];chars[start++] = chars[end];chars[end--] = temp;}
}

image-20230120202653860

for (int i = 0; i < chars.length; i++) {if (chars[i] == ' ') {// 第一个单词遍历完毕reverse(chars, rec, i - 1);rec = i + 1;}
}

需要注意的是，在进行单词内部反转的时候，我们在条件上不能写上面的这种。判断只要有空格，那么就反转之间的单词。如果这样写，就会发现最后一个单词实际上没有反转。

原因是最后一个单词后面没有空格，但是也要反转。下面的这种写法才对。当执行到最后一个元素的时候，也要反转。

为什么是i<=chars.length，是因为要反转的区间是[rec, i - 1] 所以i必须执行到=chars.length

for (int i = 0; i <= chars.length; i++) {if (i == chars.length || chars[i] == ' ') {// 第一个单词遍历完毕reverse(chars, rec, i - 1);rec = i + 1;}
}

5.剑指Offer58 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

解题思路1: 进行两次字符串的反转即可

  • 首先将整个字符串进行反转
  • 然后再以n为界限，分割成两个子字符串，对这两个子字符串分别进行反转，得到最终结果。
public String reverseLeftWords(String s, int n) {// 先完全反转一次char[] chars = s.toCharArray();reverse(chars, 0, chars.length - 1);// 然后再左右分别反转一次reverse(chars, 0, chars.length - 1 - n);reverse(chars, chars.length - n, chars.length - 1);return new StringBuilder().append(chars).toString();
}
private void reverse(char[] chars, int start, int end) {while (start < end) {char temp = chars[start];chars[start++] = chars[end];chars[end--] = temp;}
}

图解如下：

image-20230120211411593


http://www.ppmy.cn/news/18917.html

相关文章

【pytorch】.mul .add_ 和直接 + * 有什么区别

【pytorch】.mul .add_ 和直接 + * 有什么区别

优点&#xff1a;in-place 操作节省内存空间 .mul() 和 .add_() 是 PyTorch 中的 in-place 操作&#xff0c;这意味着它们会直接在原变量上进行操作&#xff0c;而不会返回新的变量。相反&#xff0c;* 和 是 Python 的运算符&#xff0c;它们会返回新的变量&#xff0c;不会…
阅读更多...
Node.js 操作MongoDB (Mongoose) 数据库

Node.js 操作MongoDB (Mongoose) 数据库

在讲Node.js通过使用mongoose模块来操作MongoDB数据库之前首先是关于MongoDB数据库的安装和MongoDB服务以及对MongoDB命令行的操作和可视化工具MongoDBCompass的一个基本使用&#xff1b;那么在这里已经准备好了关于MongoDB数据库的内容了&#xff1a; MongoDB数据库安装详细 &…
阅读更多...
【ARM体系结构】之相关概念与公司简介

【ARM体系结构】之相关概念与公司简介

1、ARM相关的概念 机器码&#xff1a;计算机可以识别的0和1的组合。即高低电平的信号&#xff0c;1高电平信号&#xff0c;0低电平信号 汇编指令&#xff1a;编译器可以将汇编指令&#xff08;存在代码段&#xff09;编译成为机器码&#xff0c;执行汇编指令可以完成相应的汇编…
阅读更多...
目标检测：Focal Loss

目标检测：Focal Loss

目标检测&#xff1a;Focal Loss前言Focal LossCross Entropybalanced Cross EntropyFocal Loss Definition前言 Focal loss这个idea来源于论文《Focal Loss for Dense Object Detection》,主要是为了解决正负样本、难易样本不平衡的问题。 Focal Loss Cross Entropy 在目标…
阅读更多...
【Qt】如何使用QtCreator向工程添加文件

【Qt】如何使用QtCreator向工程添加文件

文章目录一、导读二、盘一盘文件模板&#xff08;2-1&#xff09;添加C/C文件&#xff08;2-2&#xff09;添加Modeling文件&#xff08;2-3&#xff09;添加Qt相关文件&#xff08;2-4&#xff09;添加GLSL相关文件&#xff08;2-5&#xff09;添加其他文件三、总结一、导读 …
阅读更多...
零入门容器云实战之文章目录列表

零入门容器云实战之文章目录列表

建议: 1、网盘资源 零入门容器云网络实战 链接: https://pan.baidu.com/s/1nPLRkAwjItAHmtEU2T1F4g 提取码: rrpd 2、技术交流群 QQ群&#xff1a; 342498897 3、发布说明 绿色字体&#xff0c; 表示已经发布&#xff0c;可以观看 灰色字体&#xff0c; 表示未发布 发布频…
阅读更多...
【Java IO流】缓冲流及原理详解

【Java IO流】缓冲流及原理详解

文章目录前言字节缓冲流原理字符缓冲流Java编程基础教程系列前言 前面我们已经学习了四种对文件数据操作的基本流&#xff0c;字节输入流&#xff0c;字节输出流&#xff0c;字符输入流&#xff0c;字符输出流。为了提高其数据的读写效率&#xff0c;Java中又定义了四种缓冲流…
阅读更多...
C规范编辑笔记(十四)

C规范编辑笔记(十四)

往期文章&#xff1a; C规范编辑笔记(一) C规范编辑笔记(二) C规范编辑笔记(三) C规范编辑笔记(四) C规范编辑笔记(五) C规范编辑笔记(六) C规范编辑笔记(七) C规范编辑笔记(八) C规范编辑笔记(九) C规则编辑笔记(十) C规范编辑笔记(十一) C规范编辑笔记(十二) C规范编辑笔记(…
阅读更多...
最新文章

Copyright @ 2022~2023