当前位置：网站首页>字符串相关题目
字符串相关题目
2022-08-04 09:04:00 【EvilChou】
一、反转字符串
在反转链表中，使用了双指针的方法。
那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。
因为字符串也是一种数组，所以元素在内存中是连续分布，这就决定了反转链表和反转字符串方式上还是有所差异的。
对于字符串，我们定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。
以字符串hello为例，过程如下：
class Solution{
public void reverseString(char[] s){
//双指针方法
int left = 0;
int right = s.length - 1;
while(right > left){
char temp = s[right];
s[right] = s[left];
s[left] = temp;
left++;
right--;
}
}
}二、反转字符串||
class Solution{
public String reverseStr(String s, int k){
int n = s.length();
char[] arr = s.toCharArray();
for(int i = 0; i < n; i += 2 * k){ //i每次移动2k个字符
reverse(arr, i; Math.min(i + k, n) - 1); //反转2k个字符中前k个字符
}
return new String(arr);
}
private void reverse(char[] arr, int left, int right){
while(right > left){
char temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
left++;
right--;
}
}
}三、替换空格
class Solution{
public String replaceSpace (String s){
//方法一：定义一个可变长度字符对象，将原字符加入，空格替换为%20
if(s == null){
return null;
}
StringBuilder sb = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ' '){ //java中的单引号表示字符，双引号是字符串;
//单引号引的数据一般是char类型的；双引号引的数据是String类型的。s.charAt(i) 为 char 类型
sb.append("%20");
}else{
sb.append(sb.append(i));
}
}
return sb.toString();
}
}方法二：双指针
如果想把这道题目做到极致，就不要只用额外的辅助空间了！
首先扩充数组到每个空格替换成"%20"之后的大小。
然后从后向前替换空格，也就是双指针法，过程如下：
i指向新长度的末尾，j指向旧长度的末尾。
为什么要从后向前填充，从前向后填充不行么？
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
这么做有两个好处：
- 不用申请新数组。
- 从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
class Solution{
public String replaceSpace(String s){
if(s == null || s.length() == 0) return s;
//新增长度
StringBUilder str = new StringBuilder();
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ' '){
str.append(" "); //新增两个空格长度
}
}
if(str.length() == 0) return s;//如果没有新增空格，返回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);
}
}四、颠倒字符串中的单词
这里提高一下本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。
不能使用辅助空间之后，那么只能在原字符串上下功夫了。
将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
所以解题思路如下：
- 移除多余空格
- 将整个字符串反转
- 将每个单词反转
举个例子，源字符串为："the sky is blue "
- 移除多余空格 : "the sky is blue"
- 字符串反转："eulb si yks eht"
- 单词反转："blue is sky the"
class Solution{
public String reverseString(String s){
//分三步：1.去除字符串中所有的空格；2.翻转整个字符串；3.将单个单词进行翻转
StringBuilder sb = trimSpace(s);
reverse(sb, 0 ,sb.length() - 1);
reverseEachWord(sb);
return sb.toString();
}
//去除空格方法
private StringBuilder trimSpace(String s){
int start = 0;
int end = s.length() - 1;
while(start < end && s.charAt(start) == ' ') start++; //去除字符串开头空格
while(Start < end && s.charAt(end) == ' ') end--; //去除字符串尾部空格
StringBuilder sb = new StringBuilder();
while(start <= end){
char c = s.charAt(start);
if(c != ' '){
sb.append(c);
}else if(sb.charAt(sb.length() - 1) != ' '){ //已添加到sb中的单词后加一个空格
sb.append(c);
}
start++;
}
return sb;
}
//翻转整个字符串方法
public void reverse(StringBuilder sb, int start, int end){
while(start < end){
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
//翻转每个单词
private void reverseEachWord(StringBuilder sb){
int n = sb.length();
int start = 0;
int end = 0;
while(start < n){
while(end < n && sb.charAt(end) != ' '){
end++;
}
reverse(sb, start, end - 1);
start = end + 1;
end ++;
}
}
}另一种方法，每次处理一个单词，放入可变长度字符对象
class Solution{
public String reverseString(String s){
int i = s.length() - 1;
StringBuilder sb = new StringBuilder();
while(i > = 0){
while(i > = 0 && s.charAt(i) == ' ') i--; //找到不为空格的每个单词的第一个索引位置
int count = 0; //记录每个单词的长度
while(i > = 0 && s.charAt(i) != ' ')
i--;
count++;
if(count > 0){
sb.append(s.substring(i + 1, i + count + 1);
sb.append(' '); //每个单词后添加一个空格
}
}
sb.delete(sb.length() - 1, sb.length());//删除最后一个单词后的空格
return sb.toString();
}
}五、左旋转字符串
为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作。
不能使用额外空间的话，模拟在本串操作要实现左旋转字符串的功能还是有点困难的。
可以想一下上一题目使用整体反转+局部反转就可以实现，反转单词顺序的目的。
这道题目也非常类似，依然可以通过局部反转+整体反转 达到左旋转的目的。
具体步骤为：
- 反转区间为前n的子串
- 反转区间为n到末尾的子串
- 反转整个字符串
最后就可以得到左旋n的目的，而不用定义新的字符串，完全在本串上操作。
class Solution{
public String reverseLeftWords(String s, int n){
//分为三步操作：1.翻转前n个字符；2.翻转n后的字符；3.翻转整个字符串
int len = s.length();
StringBuilder sb = new StringBuilder(s);
reverseString(sb, 0, n - 1);
reverseString(sb, n, len - 1);
reverseString(sb, 0, len - 1);
return sb.toString();
}
public void reverseString(StringBuilder sb, int start, int end){
while(start < end){
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}六、实现strStr()
采用KMP算法，具体实现见KMP算法详解_EvilChou的博客-CSDN博客
七、重复的字符串
采用KMP算法，具体实现见KMP算法详解_EvilChou的博客-CSDN博客
边栏推荐
- leetcode二叉树系列(一）
- [Punctuality Atom STM32 Serial] Chapter 3 Development Environment Construction Excerpted from [Punctual Atom] MiniPro STM32H750 Development Guide_V1.1
- yolo x 跑起来，详细的不行，且内含800错误解决办法
- 2022-08-02 Analyze RK817 output 32k clock PMIC_32KOUT_WIFI to WiFi module clock register devm_clk_hw_register
- MindSpore：【AIR模型导出】导出时提示源码中select_op参数类型转换失败
- 区分惯性环节与延迟环节
- async - await
- TiCDC迁移-TiDB到MySQL测试
- Apache Druid 实时分析数据库入门介绍
- 去掉js代码文件所有注释
猜你喜欢
随机推荐
递归思想
DOM简述
leetcode动态规划系列(求路径篇）
Post-94 Byte P7 posted the salary slip: It's really good to make up for this...
Since his 97, I roll but he...
GBsae 8 c database using an error, how to do?
关于Oracle RAC 11g重建磁盘组的问题
继承和static关键字
路由/三层交换机DHCP下发地址详解【华为eNSP】
MindSpore:【mindinsight】【Profiler】用execution_time推导出来的训练耗时远小于真实的耗时
[Computer recording screen] How to use bandicam to record the game setting graphic tutorial
请你谈谈网站是如何进行访问的？【web领域面试题】
MindSpore:【model_zoo】【resnet】尝试用THOR优化器运行时报cannot import name ‘THOR‘
如何设计一个注册中心
王爽汇编语言第四章：第一个程序
C＃ DirectoryInfo类
2022-08-02 Analyze RK817 output 32k clock PMIC_32KOUT_WIFI to WiFi module clock register devm_clk_hw_register
华为od项目
微信消息从发送到接收，经历了什么？如何防止丢包
【正点原子STM32连载】第四章 STM32初体验 摘自【正点原子】MiniPro STM32H750 开发指南_V1.1