Reverse a String

s를 뒤집은 문자열은 s의 마지막 문자로 시작하고, 끝에서 두 번째 문자로 이어지며, 첫 번째 문자로 끝납니다. 그러므로 인덱스를 n-1에서 0까지 거꾸로 이동하며 각 문자를 만날 때마다 답에 추가하세요. Coddy2026의 경우 6, 2, 0, 2, y 등을 추가하면 6202yddoC가 됩니다.

각 문자를 한 번씩 읽고 한 번씩 쓰므로 작업량은 O(n)입니다. 답은 n개의 문자로 이루어진 두 번째 문자열이므로 추가 공간은 O(n)입니다.

문자를 어떻게 추가하는지가 중요합니다. 변경할 수 없는 문자열에 +로 문자 하나를 추가하면 매번 문자열 전체가 복사되며, n = 10^4일 때 약 5 × 10^7개의 문자가 복사됩니다. 문자를 리스트나 문자열 빌더에 모은 다음 마지막에 한 번만 결합하세요.

反転では、文字を外側から内側に向かってペアにします。最初の文字と最後の文字を入れ替え、次に2番目の文字と最後から2番目の文字を入れ替える、というように中央に向かって進みます。インデックス 0 にポインター left を置き、インデックス n-1 にポインター right を置いて、2つの文字を入れ替え、両方のポインターを内側に1つずつ進めます。

ポインターが一致するか、交差したら停止します。noon では、ポインターは 0 と 3 から始まり、次に 1 と 2 に進み、その後交差します。入れ替えは2回です。xYz のように長さが奇数の場合、中央の文字でポインターが一致します。この文字はすでに最終位置にあるため、触れることはありません。入れ替えのたびに2つの文字が最終位置に収まるので、n / 2 回の入れ替えで完了します。

入れ替え自体に必要なのは一時変数1つだけで、追加の領域は O(1) です。ほとんどの言語では文字列をその場で変更できないため、まず文字配列にコピーする必要があり、これには O(n) のコストがかかります。入力がすでに文字配列である面接の問題では、この方法なら追加メモリをまったく使わずに反転できます。