ヘビーローテーション
557. Reverse Words in a String III
这就是5开头的新题,完全没有价值把它当做新题来出,leetcode现在出的新题很多都没什么价值,要么是特别难写不好处理,要么没有难度模仿前题,这种滥竽充数的感觉特别不好,拉低了leetcode的质量,因为很多新题不涉及新的数据结构,不能反映新的算法思想,只是一个新的壳子。啰嗦了两句。
III比II简单,因为III只需要倒转单词,II比I简单,因为已经告诉你了没有 trailing zeros 而且中间空格只有一个。就像是当时的二叉树路径问题中,也是有一道题II比I简单。
while 循环里套 while 的时候,记得把外层的判断条件也放到内层,否则容易越界。
public class Solution {
public String reverseWords(String s) {
char[] array = s.toCharArray();
int start = 0;
int index = 0;
while (index < array.length) {
while (index < array.length && array[index] != ' ') index++;
reverse(array, start, index - 1);
index++;
start = index;
}
StringBuilder sb = new StringBuilder();
for (char ch : array) {
sb.append(ch);
}
return sb.toString();
}
private void reverse(char[] array, int start, int end) {
while (start < end) {
char tmp = array[start];
array[start] = array[end];
array[end] = tmp;
start++;
end--;
}
}
}
186. Reverse Words in a String II
把每个词都翻转一下,最后把整个string都倒过来输出。这么做是因为输入是char数组,完全打碎的字母,不是单词。
public class Solution {
public void reverseWords(char[] s) {
int start = 0;
int index = 0;
while (index < s.length) {
while (index < s.length && s[index] != ' ') {
index++;
}
reverse(s, start, index - 1);
index++;
start = index;
}
reverse(s, 0, s.length - 1);
}
private void reverse(char[] s, int start, int end) {
while (start < end) {
char tmp = s[start];
s[start] = s[end];
s[end] = tmp;
start++;
end--;
}
}
}
151. Reverse Words in a String
稍微麻烦点,要处理各种 trailing space 和中间。当然这题也没说要in-place,但不in-place就没做的价值了。
String题目里StringBuilder和trim()以后可能会经常用到。
public class Solution {
public String reverseWords(String s) {
if (s == null || s.length() == 0) return "";
int start = 0;
int index = 0;
char[] array = s.toCharArray();
while (index < array.length) {
while (index < array.length && array[index] == ' ') index++;
start = index;
while (index < array.length && array[index] != ' ') index++;
reverse(array, start, index - 1);
}
StringBuilder sb = new StringBuilder();
index = array.length - 1;
while (index >= 0) {
while (index >= 0 && array[index] == ' ') index--;
while (index >= 0 && array[index] != ' ') sb.append(array[index--]);
sb.append(' ');
}
return sb.toString().trim();
}
private void reverse(char[] s, int start, int end){
while(start < end){
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start ++;
end --;
}
}
}
344. Reverse String / 541. Reverse String II
344太过trivial就不说了,稍微说一下541,注意尾指针的取值,用一个min函数取较小的index别越界就行了。
public class Solution {
public String reverseStr(String s, int k) {
if (s == null || s.length() == 0) return s;
char[] array = s.toCharArray();
int i = 0;
while (i < array.length) {
int j = Math.min(i + k - 1, array.length - 1);
swap(array, i, j);
i += 2 * k;
}
StringBuilder sb = new StringBuilder();
for (char ch : array) {
sb.append(ch);
}
return sb.toString();
}
private void swap (char[] array, int start, int end) {
while (start < end) {
char tmp = array[start];
array[start++] = array[end];
array[end--] = tmp;
}
}
}
189. Rotate Array
多步翻转法的另一个应用。
这题让我想起了链表,肯定有很多种做法,用多步翻转是比较简洁的。
public class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
reverse(nums, 0, nums.length - k - 1);
reverse(nums, nums.length - k, nums.length - 1);
reverse(nums, 0, nums.length - 1);
}
private void reverse(int[] nums, int start, int end){
while(start < end){
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start ++;
end --;
}
}
}