算法训练营day08(字符串01:反转字符串,反转字符串2,替换数字,反转字符串里的单词,右旋转字符串)
第四章 字符串part01
今日任务
● 344.反转字符串
● 541. 反转字符串II
● 卡码网：54.替换数字
● 151.翻转字符串里的单词
● 卡码网：55.右旋转字符串
详细布置
344.反转字符串
建议： 本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下 平时刷题什么时候用 库函数，什么时候 不用库函数
题目链接/文章讲解/视频讲解：https://programmercarl.com/0344.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2.html
541. 反转字符串II
建议：本题又进阶了，自己先去独立做一做，然后在看题解，对代码技巧会有很深的体会。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0541.%E5%8F%8D%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2II.html
卡码网：54.替换数字
建议：对于线性数据结构，填充或者删除，后序处理会高效的多。好好体会一下。
题目链接/文章讲解：https://programmercarl.com/kama54.%E6%9B%BF%E6%8D%A2%E6%95%B0%E5%AD%97.html
151.翻转字符串里的单词
建议：这道题目基本把 刚刚做过的字符串操作 都覆盖了，不过就算知道解题思路，本题代码并不容易写，要多练一练。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.html
卡码网：55.右旋转字符串
建议：题解中的解法如果没接触过的话，应该会想不到
day08
反转字符串1
双指针
class Solution {
public void reverseString(char[] s) {
//头尾双指针
int len = s.length;
for( int i = 0, j = len-1; i < len/2; i++, j--){
swap(s,i,j);//注意要把s传进去,这样才能实际操作s里的元素
}
}
public void swap( char[] s, int i, int j ){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
}
}
反转字符串2
重点在for循环
class Solution {
public String reverseStr(String s, int k) {
//字符串转化为数组
char[] ch = s.toCharArray();
//每次翻转的起点都会加2k
for( int i = 0; i < ch.length; i +=2*k){
//如果从i开始够k个
//判断一下加不加等号:比如k=3,length=3,相等也可操作
//2*k不是2k
if( i + k <= ch.length){
reverse(ch, i, i+k-1);
continue;
}
//如果不够k个
reverse(ch, i, ch.length - 1);
}
return new String(ch);
//数组转成字符串
}
public void reverse( char[] ch, int i, int j){
while( i < j){
//等于的时候没必要翻转
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
i++;
j--;
}
}
}
替换数字
例如:a1bvf变成anumberbvf
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<oldSize; i++){
if(Character.isDigit( s.charAt(i) )) count++;
}
int newSize = oldSize + 5 * count;
char[] news = new char[newSize];
System.arraycopy(s.toCharArray(),0,news,0,oldSize);
//System.arraycopy不是System.arrayCopy
for(int i = oldSize - 1, j = newSize - 1; i>=0; i--){
//-1不是-i
if(Character.isDigit(news[i])){
news[j - 5] = 'n';
news[j - 4] = 'u';
news[j - 3] = 'm';
news[j - 2] = 'b';
news[j - 1] = 'e';
news[j] = 'r';
j -= 6;
}else{
news[j] = news[i];
j--;
}
}
return new String(news);
//news是char[]不是字符串,需要用String(char[]转换成字符串
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.next();
System.out.println(replaceNumber(s));
sc.close();
}
}
翻转字符串里的单词
class Solution {
//1.双指针移除多余空格 2.翻转字符串 3.翻转单词
public String reverseWords(String s) {
char[] chars = s.toCharArray();
chars = removeExtreSpace(chars);
reverse(chars, 0, chars.length - 1);
reverseEachWorld(chars);
return new String(chars);
}
//1.移除多余空格,快指针只保留非空字符,慢指针判断接收快指针指向字符的时候要不要加一个空格
public char[] removeExtreSpace(char[] chars){
int slow = 0;
int fast = 0;
int len = chars.length;
for( ; fast < len; fast++){//移除空格直接遍历fast
if( chars[fast] == ' '){//遇到空格啥都不用管直接fast++,非空格就继续操作,其实if可以直接写非空格的情况
continue;
}else{
if( slow != 0){//如果slow在最开始,不用加空格;否则slow接受之前先加空格,优化逻辑先写要加空格的情况
chars[slow++] = ' ';
}
while( fast < len && chars[fast] != ' '){
//遍历一个单词,在for里面用while;另外注意fast<len的边界条件要写在前面,不然会报越界异常
chars[slow++] = chars[fast++];
}
}
}
char[] newchars = new char[slow];
System.arraycopy(chars, 0, newchars, 0, slow);
//前面正好slow自增了,传下标[0,solw)刚刚好
return newchars;
}
//2.翻转字符串
public char[] reverse(char[] chars, int i, int j){
for( ; i < j; i++, j--){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
return chars;
}
//3.翻转单词
public char[] reverseEachWorld( char[] chars ){
int start = 0;
int end = 0;
for( ;end <= chars.length; end++){
if( end == chars.length || chars[end] == ' ' ){
//fast<len的边界条件要写在前面,不然会报越界异常
reverse(chars, start, end - 1);
start = end + 1;
}
}
return chars;
}
}
右旋字符串
一个套路,整体反转＋局部翻转即可;先局部反转再整体反转也行
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = Integer.parseInt(in.nextLine());
String s = in.nextLine();
int len = s.length();
char[] chars = s.toCharArray();
reverseString(chars, 0, len - 1); //整体反转
reverseString(chars, 0, n - 1); //局部反转
reverseString(chars, n, len - 1);
System.out.println(chars);
}
注:感谢大佬分享
代码随想录-算法训练营day08【字符串01：反转字符串、替换数字、反转字符串里的单词、右旋转字符串】_代码随想录替换数字-CSDN博客