当前位置：网站首页>字符串相关题目
字符串相关题目
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博客
边栏推荐
猜你喜欢
PD 源码分析- Checker: region 健康卫士
外包干了四年，秋招终于上岸了
2022-08-02 Analyze RK817 output 32k clock PMIC_32KOUT_WIFI to WiFi module clock register devm_clk_hw_register
记录十条工作中便利的API小技巧
VRRP + MSTP configuration, huawei eNSP experiment 】 【
![[Punctuality Atom STM32 Serial] Chapter 4 STM32 First Experience Excerpted from [Punctual Atom] MiniPro STM32H750 Development Guide_V1.1](/img/99/928e86f8a61a905a899dd5d3880def.png)
[Punctuality Atom STM32 Serial] Chapter 4 STM32 First Experience Excerpted from [Punctual Atom] MiniPro STM32H750 Development Guide_V1.1
【高并发基石】多线程、守护线程、线程安全、线程同步、互斥锁
加降息与BTC流动性事件策略研究
递归思想
Fiddler(二)-手机抓包502错误解决方法
随机推荐
我和 TiDB 的故事 | TiDB 对我不离不弃，我亦如此
有坦荡的远方
Libpq 是否支持读写分离配置
[Punctuality Atom STM32 Serial] Chapter 4 STM32 First Experience Excerpted from [Punctual Atom] MiniPro STM32H750 Development Guide_V1.1
LVGL's multi-language conversion tool -- a good assistant for font settings
leetcode每天5题-Day06
GBsae 8 c database using an error, how to do?
How to restore the Youxuan database with only data files
Get the number of cpu cores
MATLAB绘图总结
leetcode二叉树系列(二)
Anton Paar安东帕密度计比重计维修DMA35性能参数
Four common methods of network attacks and their protection
MindSpore:model.train中的dataset_sink_mode该如何理解？
【高并发基石】多线程、守护线程、线程安全、线程同步、互斥锁
如何从PG导入数据到kingbaseES
软件工程国考总结——判断题
PD 源码分析- Checker: region 健康卫士
ansible部署脚本--亲测可用无坑
JSP基本语法