344. 反转字符串
很明显的双指针解法
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
char tmp;
while (left < right) {
tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
}541. 反转字符串 II
每次处理从下标 i 开始的前 k 个字符即可，i 从 0 开始，每次移动 2k 个位置。
class Solution {
public String reverseStr(String s, int k) {
char[] str = s.toCharArray();
// i 从 0 开始，每次移动 2k 个位置
for (int i = 0; i < s.length(); i += 2 * k) {
// 反转从 i 开始的前 k 个元素，区间下标是 [i, i + k - 1]
if (i + k - 1 < s.length()) {
reverse(str, i, i + k - 1);
} else {
reverse(str, i, s.length() - 1);
}
}
return new String(str);
}
public void reverse(char[] s, int i, int j) {
while (i < j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}
}卡码网 - 54. 替换数字
题目本身理解起来并不难，无非是遍历字符串，找到数字字符，然后将其替换成 "number"，难的是如何进行数组的操作。像 C 语言这种使用字符数组表示字符串，由于数组大小是固定的，所以得先统计字符串中数字字符的数量，然后按照替换后的字符串的长度申请新数组。这里有个巧妙的方法就是从后往前填充数组，这样可以避免插入元素时数组元素的挨个移动。
function replaceDigit(str) {
// 统计字符串数组中数字字符的数量
let count = 0;
for (let i = 0; i < str.length; i++) {
count++;
}
newStr = new Array(count * 6);
let left = str.length - 1;
let right = newStr.length - 1;
while (left >= 0) {
if (isNaN(Number(str[left], 10))) {
newStr[right] = str[left];
} else {
newStr[right--] = 'r';
newStr[right--] = 'e';
newStr[right--] = 'b';
newStr[right--] = 'm';
newStr[right--] = 'u';
newStr[right] = 'n';
}
left--;
right--;
}
return newStr;
}对于像 Java 这种语言，字符串是不能修改的，所以需要 StringBuilder 来操作字符串，思路和上面不一样。
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
StringBuilder sd = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
sd.append("number");
} else {
sd.append(s.charAt(i));
}
}
System.out.println(sd.toString());
sc.close();
}
}151. 反转字符串中的单词
思路：
- 先去掉字符串中的空格（前后空格 + 单词间多余的空格）
- 再将整个字符串反转（参考前面的题目）
- 再将各个单词再反转回来（小范围的反转字符串，体力活）
#include <string.h>
// 反转字符串
void reverseString(char* s, int i, int j) {
while (i < j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}
// 去掉额外的空格，类似于 27. 移除元素，一个思想
void removeExtraSpace(char* s) {
int i = 0;
int j = 0;
// 用 j 遍历字符串，j 是在查找单词的开头
while (j < strlen(s)) {
// 当前字符不是空格，说明找到了一个单词的开头
if (s[j] != ' ') {
// 重点：i != 0，说明当前已经不是第一个单词了，所以要在该单词前面加空格
if (i != 0) {
s[i] = ' ';
i++;
}
// 重点：然后将单词的各个字母逐个复制给 i
while (j < strlen(s) && s[j] != ' ') {
s[i] = s[j];
i++;
j++;
}
} else {
// 重点：当前字符是空格，j 往后找
j++;
}
}
// i 就是去除空格后字符串的长度，也是结束符的位置
s[i] = '\0';
}
char* reverseWords(char* s) {
removeExtraSpace(s);
reverseString(s, 0, strlen(s) - 1);
int start = 0;
for (int i = 0; i <= strlen(s); i++) {
// 遇到空格，将前面的单词反转
if (s[i] == ' ' || s[i] == '\0') {
reverseString(s, start, i - 1);
start = i + 1;
}
}
return s;
}
55. 右旋字符串
暴力思路，每次将最后一个元素插到最前面，类似于 “头插法”，当然，前面的元素得挨个后移。每次 “头插” 一个元素，都要移动前面的 n - 1 个元素，总共移动 k (n - 1) 次，所以时间复杂度是 O(k n)。如果 k 等于 n 的话，那时间复杂度就是 O(n^2)，所以最好时间复杂度是 O(1)，即 k 等于 0，最坏时间按复杂度是 O(n^2)，即 k 等于 n。
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
sc.nextLine();
String str = sc.nextLine();
char[] arr = str.toCharArray();
// 取最后一个元素
char tmp = arr[arr.length - 1];
while (k > 0 && k <= arr.length) {
// 前面的元素后移
for (int i = arr.length - 1; i > 0; i--) {
// 后移，即低位覆盖高位
arr[i] = arr[i - 1];
}
// 头插法
arr[0] = tmp;
// 取最后一个元素
tmp = arr[arr.length - 1];
k--;
}
System.out.println(new String(arr));
sc.close();
}
}还有一个比较巧妙的 O(n) 的解法。那就是先整个反转，然后再将两部分反转，如 [a b c d e f g] 整个反转为 [g f e d c b a]，然后再将两部分 [g f]、[e d c b a] 反转为 [f g]、[a b c d e]。基础都是反转字符串的代码。和 LC 151 反转单词 类似，一步步反转。
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
sc.nextLine();
String str = sc.nextLine();
char[] arr = str.toCharArray();
if (k > 0 && k <= arr.length) {
// 先整个反转
reverse(arr, 0, arr.length - 1);
// 然后再部分反转
reverse(arr, 0, k - 1);
reverse(arr, k, arr.length - 1);
}
System.out.println(new String(arr));
sc.close();
}
public static void reverse(char[] s, int i, int j) {
while (i < j) {
char tmp = s[i];
s[i] = s[j];
s[j] = tmp;
i++;
j--;
}
}
}