代码随想录算法训练营day8 | 题目344、题目541、卡码网54、题目151、卡码网55
题目一描述
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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 <= s.length <= 10^5
s[i] 都是 ASCII 码表中的可打印字符
解题思路
双指针在数组的运用，两边相向移动。
代码实现
方法一：
class Solution {
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while(left<right){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
}
题目二描述
给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
示例 1：
输入：s = "abcdefg", k = 2
输出："bacdfeg"
示例 2：
输入：s = "abcd", k = 2
输出："bacd"
提示：
1 <= s.length <= 104
s 仅由小写英文组成
1 <= k <= 104
解题思路
字符串转为字符数组是常用操作
把字符串划分为区间，反转每个区间的前几个字母。
代码实现
方法一：
class Solution {
public String reverseStr(String s, int k) {
char[] ss = s.toCharArray();
for (int i = 0; i < ss.length; i += 2 * k) {
int left = i;
int right = Math.min(i + k - 1, ss.length - 1);
while (left < right) {
char temp = ss[left];
ss[left] = ss[right];
ss[right] = temp;
left++;
right--;
}
}
String res = new String(ss);
return res;
}
}
题目三描述
时间限制：1.000S 空间限制：128MB
题目描述
给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。 例如，对于输入字符串 "a1b2c3"，函数应该将其转换为 "anumberbnumbercnumber"。
输入描述
输入一个字符串 s,s 仅包含小写字母和数字字符。
输出描述
打印一个新的字符串，其中每个数字字符都被替换为了number
输入示例
a1b2c3
输出示例
anumberbnumbercnumber
提示信息
数据范围：
1 <= s.length < 10000。
解题思路
遍历然后判断数据类型，重点在于如何判断以及不定长字符串的构建。
代码实现
方法一：
import java.util.*;
class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
char[] ss = s.toCharArray();
StringBuilder sb = new StringBuilder();
for(char c: ss){ // 应该用char而不是Char
if(Character.isDigit(c)){
sb.append("number");
}else if(Character.isLetter(c)){
sb.append(c);
}
}
// return sb.toString(); // main 方法不能返回值
System.out.println(sb.toString());
}
}
技巧总结
手写算法，学会import java.util.*;
学会Scaner
学会StringBuilder，其转为字符串要用toString()，而char[] 要用String.valueOf 或者 new String
注意遍历是小写，定义map或者set，list才是Character
学会判断数据类型，Character.isDigit和Character.isLetter
题目四描述
给你一个字符串 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 <= s.length <= 10^4
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
解题思路
直接的想法是扫描出所有的单词，压入栈内，再取出后在中间填加空格。
第二个思路是先把整体所有字符串反转，再找到每个单词对其进行反转，然后去掉首尾的和中间的多余的空格。
代码实现
方法一：
class Solution {
public String reverseWords(String s) {
StringBuilder sb = new StringBuilder();
Stack<String> stack = new Stack<>();
char[] ss = s.toCharArray();
int start = 0;
while (start < ss.length) {
while (start < ss.length && ss[start] == ' ') {
start++;
}
StringBuilder word = new StringBuilder();
while (start < ss.length && ss[start] != ' ') {
word.append(ss[start]);
start++;
}
if (word.length() != 0)
stack.push(word.toString());
}
while (!stack.empty()) {
sb.append(stack.pop());
if (!stack.empty())
sb.append(' ');
}
return sb.toString();
}
}
方法二：
class Solution {
public String reverseWords(String s) {
char[] ss = s.toCharArray();
reverse(ss, 0, ss.length - 1);
// ss = reverse(ss, 0, ss.length - 1); // 没必要接收返回值
int start = 0;
int end = 0;
while (start < ss.length) {
while (start < ss.length && ss[start] == ' ') {
start++;
}
end = start;
while (end < ss.length && ss[end] != ' ') {
end++;
}
reverse(ss, start, end - 1);
start = end;
}
// 去空格
StringBuilder sb = new StringBuilder();
boolean flag = false;
int left = 0;
int right = ss.length - 1;
while (ss[left] == ' ') {
left++;
}
while (ss[right] == ' ') {
right--;
}
for (int i = left; i < right + 1; i++) {
char c = ss[i];
if (c != ' ' || c == ' ' && ss[i - 1] != ' ') {
sb.append(c);
}
}
return String.valueOf(sb);
}
public void reverse(char[] ss, int start, int end) {
while (start < end) {
char temp = ss[start];
ss[start] = ss[end];
ss[end] = temp;
start++;
end--;
}
}
}
技巧总结
栈的初始化，进出栈与判空
引用类型被当作形参传递，直接就会被修改。
题目五描述
时间限制：1.000S 空间限制：128MB
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。
例如，对于输入字符串 "abcdefg" 和整数 2，函数应该将其转换为 "fgabcde"。
输入描述
输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出描述
输出共一行，为进行了右旋转操作后的字符串。
输入示例
2
abcdefg
输出示例
fgabcde
提示信息
数据范围：
1 <= k < 10000,
1 <= s.length < 10000;
解题思路
先反转前一部分，再反转后一部分，再反转全部
代码实现
方法一：
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int k = Integer.valueOf(sc.nextLine());
String s = sc.nextLine();
char[] ss = s.toCharArray();
int start = 0;
int end = ss.length - k - 1;
reverse(ss, start, end);
start = end + 1;
end = ss.length - 1;
reverse(ss, start, end);
reverse(ss, 0, ss.length - 1);
System.out.println(ss);
}
public static void reverse(char[] ss, int start, int end){
while(start < end){
char temp = ss[start];
ss[start] = ss[end];
ss[end] = temp;
start++;
end--;
}
}
}
技巧总结
判断下标减几的时候，最好还是用例子试试。
