代码随想录算法训练营第八天| 344.反转字符串 541. 反转字符串II 54.替换数字
Leetcode 344.反转字符串
题目链接：https://leetcode.cn/problems/reverse-string/description/
题目描述：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
思路：
1、双指针
1、定义暂存指针
2、定义头尾指针
3、交换头尾指针
2、使用栈
先压栈，后出栈
代码1：
class Solution {
public void reverseString(char[] s) {
// 栈
Deque<Character> stack1 = new LinkedList<Character>();
// 压栈
for(char c:s){
stack1.push(c);
}
// 出栈
for(int i = 0 ;i<s.length;i++){
s[i] = stack1.pop();
}
}
}
代码2：
class Solution {
public void reverseString(char[] s) {
// 双指针
int i = 0 , j = s.length - 1;
while(i<j){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
Leetcode 541. 反转字符串II
题目链接：https://leetcode.cn/problems/reverse-string-ii/description/
题目描述：
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
- 如果剩余字符少于
k个，则将剩余字符全部反转。 - 如果剩余字符小于
2k但大于或等于k个，则反转前k个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2
输出："bacd"
思路 ：
1、封装reverse函数
2、两种情况下的字符是否反转
图示：
代码1：
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0; i<ch.length;i+=2*k){
// 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样
if(i+k <= ch.length){
reverse(ch , i ,i + k -1 );
continue;
}
reverse(ch ,i ,ch.length - 1);
}
return new String(ch);
}
public void reverse(char[] ch , int i ,int j){
for(; i<j;i++,j--){
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
}
代码2：
class Solution {
public String reverseStr(String s, int k) {
char[] ch = s.toCharArray();
for(int i = 0 ; i<ch.length; i += 2 * k){
int start = i;
// 判断尾数够不够k个，来取决end的位置
int end = Math.min(ch.length - 1 , start + k -1);
while(start < end){
char temp = ch[start];
ch[start] = ch[end];
ch[end] = temp;
start++;
end--;
}
}
return new String(ch);
}
}
总结：
注意：函数调用一般遵循左闭右开原则
54.替换数字
题目链接：https://kamacoder.com/problempage.php?pid=1064
题目描述：
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。
思路：双指针法
本题难点在于将数字替换为number
1、统计数字个数
2、声明新字符数组
3、遍历，将数字替换为number
图示：
代码:
// 统计数字个数
// 扩充字符串大小
// 遍历新数组，遇到数字，开始填充number
// 当ch[i] = ch[j]时，替换结束
import java.util.Scanner;
public class Main{
public static String replaceNumber(String s){
// 统计数字个数
int count = 0;
// 统计旧字符串长度
int OldSize = s.length();
for(int i = 0 ; i<s.length();i++){
if(Character.isDigit(s.charAt(i))){
count++;
}
}
// 扩充字符串大小
char[] news = new char[s.length()+count*5];
int NewSize = news.length;
// 将旧字符的内容填入新数组
System.arraycopy(s.toCharArray(),0,news,0,OldSize);
// 从后往前将空格替换为number
for(int i = NewSize - 1, j = OldSize - 1;j<i;j--,i--){
if(!Character.isDigit(news[j])){
news[i] = news[j];
}else{
news[i] = 'r';
news[i - 1] = 'e';
news[i - 2] = 'b';
news[i - 3] = 'm';
news[i - 4] = 'u';
news[i - 5] = 'n';
i-=5;
}
}
return new String(news);
}
public static void main (String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.next();
System.out.println(replaceNumber(s));
scanner.close();
}
}
总结：
个人觉得，选好指针从哪里开始遍历也是难点
标签：char,ch,String,int,反转,II,字符串,news From： https://blog.csdn.net/m0_65709641/article/details/140334052