【算法系列-字符串】反转字符串中的单词
【算法系列-字符串】反转字符串中的单词
文章目录
- 【算法系列-字符串】反转字符串中的单词
- 1. 算法分析
- 2. 解题过程
- 2.1 去除多余空格
- 2.2 反转整个字符串
- 2.3 对每个单词进行反转
- 3. 代码示例
1. 算法分析
【题目链接】151. 反转字符串中的单词 - 力扣（LeetCode）
这道题比较麻烦的是需要去除多余的空格并保留单词间的空格，我这里提供一份使用库函数(java中的split)解决的代码:
class Solution {
public String reverseWords(String s) {
String[] arr = s.split(" ");
reverse(arr, 0, arr.length - 1);
StringBuffer sub = new StringBuffer();
for (int i = 0;i < arr.length;i++) {
if ("".equals(arr[i])) {
continue;
}
sub.append(arr[i]);
sub.append(" ");
}
if (sub.substring(sub.length() - 1).equals(" ")) {
return sub.substring(0, sub.length() -1).toString();
}
return sub.toString();
}
public void reverse(String[] arr, int left, int right) {
while (left < right) {
String temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
}
}
但这样做空间复杂度就会比较高，为了起到锻炼作用，我这里也用另一种方式解决这道题，那就是双指针！
分三步走：
- 去除多余空格
- 反转整个字符串
- 对每个单词进行反转
2. 解题过程
2.1 去除多余空格
使用快慢指针的方式来删除多余的空格，具体方式与之前写过的一篇文章类似，不理解的可以参考一下： 【算法系列-移除元素】
需要注意：
- 当fast指向了一个新的单词，且当slow指向位置不是数组首位时，需要在这个新单词前面加一个空格；
- 每一次都要将新单词的所有字符都遍历完毕才能结束循环；
代码如下：
public char[] removeSpace(char[] arr) {
int slow = 0;
for (int fast = 0;fast < arr.length;fast+
if (arr[fast] != ' ') {
// 进入这里表示fast指向了一个新的单词，且当slow指向位置不是数组首位时，需要在这个新单词前面加一个空格
if (slow != 0) {
arr[slow++] = ' ';
// 需要循环将这个单词遍历完
while (fast < arr.length && arr[fast] != ' ') {
arr[slow++] = arr[fast++];
}
}
}
char[] retArr = new char[slow];
System.arraycopy(arr, 0, retArr, 0, slow);
return retArr;
}
2.2 反转整个字符串
这一个方法与上篇文章【算法系列-反转字符串】介绍的一样，这里就不过多赘述
代码如下：
public void reverse(char[] arr, int left, int right
while (left < right) {
char temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
}
2.3 对每个单词进行反转
需要注意：
- fast == arr.length 是为了判断指向最后一个单词时的情况；
- 当fast指向数组末尾 或 fast指向的字符为空时，对这个单词进行反转(slow 到 fast - 1 便是当前单词的范围)；
- slow = fast + 1 这里的 + 1 是为了跳过空字符；
代码如下：
public void reverseWord(char[] arr
int slow = 0;
for (int fast = 0;fast <= arr.length;fast++) {
if (fast == arr.length || arr[fast] == ' ') {
// fast == arr.length 是为了判断指向最后一个单词时的情况
// 当fast指向数组末尾 或 fast指向的字符为空时，对这个单词进行反转(slow 到 fast - 1 便是当前单词的范围)
reverse(arr, slow, fast - 1);
slow = fast + 1; // +1 是为了跳过空字符
}
}
}
3. 代码示例
总的代码如下：
class Solution {
public String reverseWords(String s) {
char[] arr = s.toCharArray();
// 1. 去除多余空格
arr = removeSpace(arr);
// 2. 反转所有字符
reverse(arr, 0, arr.length - 1);
// 3. 对每个单词进行反转
reverseWord(arr);
return new String(arr);
}
public char[] removeSpace(char[] arr) {
int slow = 0;
for (int fast = 0;fast < arr.length;fast++) {
if (arr[fast] != ' ') {
// 进入这里表示fast指向了一个新的单词，且当slow指向位置不是数组首位时，需要在这个新单词前面加一个空格
if (slow != 0) {
arr[slow++] = ' ';
}
// 需要循环将这个单词遍历完
while (fast < arr.length && arr[fast] != ' ') {
arr[slow++] = arr[fast++];
}
}
}
char[] retArr = new char[slow];
System.arraycopy(arr, 0, retArr, 0, slow);
return retArr;
}
public void reverse(char[] arr, int left, int right) {
while (left < right) {
char temp = arr[left];
arr[left++] = arr[right];
arr[right--] = temp;
}
}
public void reverseWord(char[] arr) {
int slow = 0;
for (int fast = 0;fast <= arr.length;fast++) {
if (fast == arr.length || arr[fast] == ' ') {
// fast == arr.length 是为了判断指向最后一个单词时的情况
// 当fast指向数组末尾 或 fast指向的字符为空时，对这个单词进行反转(slow 到 fast - 1 便是当前单词的范围)
reverse(arr, slow, fast - 1);
slow = fast + 1; // +1 是为了跳过空字符
}
}
}
}
以上便是对反转字符串中的单词问题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨