151. 文字列内の単語を反転する
この問題は、これまでに学んだ文字列操作の多くの要素をカバーしています。解法の理解だけでなく、コードの実装も重要です。
主な難点は余分なスペースの削除で、これは双方向ポインタを使用して実現します。具体的には、新しい配列の位置を指すスローポインタがあり、ファストポインタが追加すべき要素を見つけた場合、スローポインタの現在の位置にスペースを挿入し、位置を後ろにずらしてから目標要素を挿入します。ここで重要なのは、新しい単語の前にスペースを挿入することです。
コードを見る
public class Solution {
public String reverseWords(String s) {
char[] chars = s.toCharArray();
// 1. 首尾および中間の余分なスペースを削除
chars = removeExtraSpaces(chars);
// 2. 全体の文字列を反転
reverse(chars, 0, chars.length - 1);
// 3. 各単語を反転
reverseEachWord(chars);
return new String(chars);
}
// 1. 余分なスペースを削除
private char[] removeExtraSpaces(char[] chars) {
int slow = 0;
for (int fast = 0; fast < chars.length; fast++) {
if (chars[fast] != ' ') {
if (slow != 0)
chars[slow++] = ' ';
while (fast < chars.length && chars[fast] != ' ')
chars[slow++] = chars[fast++];
}
}
char[] newChars = new char[slow];
System.arraycopy(chars, 0, newChars, 0, slow);
return newChars;
}
// 2. 指定範囲の文字列を反転
private void reverse(char[] chars, int left, int right) {
while (left < right) {
chars[left] ^= chars[right];
chars[right] ^= chars[left];
chars[left] ^= chars[right];
left++;
right--;
}
}
// 3. 各単語を反転
private void reverseEachWord(char[] chars) {
int start = 0;
for (int end = 0; end <= chars.length; end++) {
if (end == chars.length || chars[end] == ' ') {
reverse(chars, start, end - 1);
start = end + 1;
}
}
}
}
55. 右回転文字列
この問題は、左右の回転の原理を理解することが重要です。例えば、長さ10の文字列がある場合、左側の3文字を右に回転することは、右側の7文字を左に回転することと同じです。
全体を一度反転させ、その後部分的に反転させる方法があります。
コードを見る
import java.util.Scanner;
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);
}
private static void reverseString(char[] ch, int start, int end) {
while (start < end) {
ch[start] ^= ch[end];
ch[end] ^= ch[start];
ch[start] ^= ch[end];
start++;
end--;
}
}
}