문자열 반전 방법

알고리즘과 데이터 구조 문제를 더욱 잘 해결하려면 유일한 방법은 몇 가지를 통과하는 것이다.
우리는 최선의 준비 방법in this lesson, inthis one, here을 소개했다.만약 네가 더 많은 지도를 필요로 한다면 반드시 그들을 방문해야 한다.그렇지 않으면, 우리를 뛰어들게 해라.

문자열 반전

우리 밧줄을 거꾸로 합시다!

내장 Array#reverse 방법을 사용하지 않고 입력한 문자열을 반전시키는 함수를 작성할 수 있습니까?
예를 좀 봅시다.그래서 전화:reverseString("jake")로 돌아가야 합니다"ekaj".reverseString("reverseastring")로 돌아가야 합니다"gnirtsaesrever".

이 과정은 https://algodaily.com에 처음 발표되었고 저는 그곳에서 기술 면접 과정을 개설했고 웅대한 개발자를 위해 사고문을 썼습니다.

맞아요, 틀렸어요?

Java, C#, JavaScript, Python 및 Go에서 문자열은 immutable 입니다.이것은 생성된 문자열 대상의 상태를 변경할 수 없다는 것을 의미합니다.
솔루션: True

면접관의 심리 상태를 논하다

반전 문자열은 지원자들이 가장 흔히 볼 수 있는 기술 면접 문제 중의 하나다.면접관은 간단해 보이기 때문에 그것을 좋아한다.어쨌든 소프트웨어 엔지니어로서 당신이 가장 좋아하는 #reverse 클래스에서 String 방법을 호출할 수 있습니다. 여기까지!
따라서 이 점을 소홀히 해서는 안 된다. 놀라운 몸풀기나 축적 문제인 것 같다.많은 면접관들이 이런 간단한 문제를 채택하는데, 실제로는 판단이 훨씬 엄격하다.너는 네가 진정으로 이 점을 할 수 있도록 확보해야 한다.

우리는 어떻게 해결을 시작할 것인가

우리는 문자열이 뒤바뀌기를 바란다. 이것은 우리의 마지막 모든 자모가 뒤로 놓여 있다는 것을 의미한다.빠른 복습string이 필요한 경우 our lesson on arrays and strings 을 참조하십시오.
우리는 string 문자의 수조로 여겨질 수 있다는 것을 안다. 즉, 수조의 모든 요소는 하나의 문자이다.만약 우리가 가정할 수 있다면, 우리는 모든 문자의 위치(수조 위치)와 array가 끝날 때의 색인을 알고 있다.
문자열을 문자 그룹으로 간주하는 경고가 있습니다. 항상 정확한 것은 아닙니다.독자와 관중들이 지적한 바와 같이 문자열은 알파벳으로 구성된 텍스트 (쓰기 시스템의 최소 기능 단원) 를 유니코드의 문자 서열로 조합한 것을 나타낸다.
문자열과 수조는 length, concat, 문자 위치 접근과 같은 비슷한 방법을 포함하지만, 그것들은 완전히 같지 않다.예를 들어 배열은 변할 수 있지만 문자열은 그렇지 않습니다.문자열을 수조로 조작하기 전에, 우리는 호출 .split() 방법을 통해 단원 (JS에서) 을 분리하거나, 원시 문자열을 조작하지 않고 새로운 문자열을 생성해서 이 속성을 돌려야 한다.
그러나 split 조작 후에 우리는 이 모델을 이 문자열에 대한 조작에 적용할 수 있다.따라서 우리는 모든 색인을 점차적으로 훑어볼 수 있다.문자열의 시작을 통해 우리는 각 점에서 다음과 같은 관찰을 할 것이다.

const str = "JAKE";
// position 0 - "J"
// position 1 - "A"
// ...

역방향 문자열 자체가 뒤쪽이기 때문에 만력 해결 방안은 색인을 사용하고 뒤에서 앞으로 교체할 수 있다.
첨부된 코드를 참조하고 Run Sample Code 를 사용하여 실행하십시오.문자열 뒤에서 모든 문자를 로그아웃하는 것을 보실 수 있습니다!

function reverseString(str) {
  let newString = '';

    // start from end
  for (let i = str.length-1; i >= 0; i--) {
    console.log('Processing ', newString, str[i]);
        // append it to the string builder
    newString = newString + str[i];
  }

    // return the string
  return newString;
}

console.log(reverseString('test'));

기입하다

저희는 console.log 탈퇴하고 싶습니다.

5
4
3
2
1

여기에 무엇이 부족합니까?

var arr =  [1, 2, 3, 4, 5];

for (var i = ___________; i >= 0; i--) {
    console.log(arr[i]);
}

솔루션: arr.length-1

우리가 폭력보다 더 잘할 수 있을까?

그러나 더 좋은 방법이 없다면 이것은 진정으로 재미있는 알고리즘 문제가 아니다.그것을 어떻게 최적화시키는지, 아니면 더 빨리 운행시키는지 봅시다.일을 더욱 효율적으로 하려고 할 때, 삭감하거나 줄여야 할 일을 고려하는 것이 도움이 된다.
주의해야 할 것은, 우리는 모든 문자열을 훑어보고 있다는 것이다. 우리는 정말 모든 자모를 훑어봐야 합니까?
최악의 상황을 봅시다.만약 문자열이 백만 개의 문자가 길다면?이것은 백만 개의 행동이 통과될 것이다.우리가 개선할 수 있습니까?

네, 더 많은 지침이 있습니다!

응, 우리는 지금 바늘 하나만 사용하고 있어.순환 중인 교체기는 뒤에서 시작하여 모든 문자를 새 문자열에 하나씩 추가합니다.The Two Pointer Technique을 통해 우리는 우리가 사용하는 바늘의 수량을 증가함으로써 현저한 개선을 실현할 수 있음을 인식할 수 있다.

내 말은 우리가 조작 수량을 절반으로 줄일 수 있다는 것이다.어떻게저희가 장소를 바꾸면요?while 순환과 두 개의 지침을 사용합니다. 하나는 왼쪽, 하나는 오른쪽입니다.
이 점을 감안하면 가장 중요한 발견은 매번 교체될 때마다 우리는 바늘 색인에서 자모를 교환할 수 있다는 것이다.교환 후, 우리는 left 바늘을 증가하고, 동시에 right 바늘을 감소할 것이다.이것은 상상하기 어려울 수도 있으니 열거한 기본 예시를 봅시다.

jake    // starting string

eakj    // first pass
^  ^

ekaj    // second pass
 ^^

다중 선택

쌍바늘 기술의 좋은 용례는 무엇입니까?

매번 교체할 때마다 색인을 더 크게 이동

플러그인 for 순환과 O(n^2) 복잡성을 가진 해를 O(n)

로 감소

for 순환에서 쌍과 중복 항목 찾기

없음

해결 방안: 플러그인 for 순환과 O(n^2)의 복잡성을 가진 해결 방안을 O(n)로 줄인다
두 개의 바늘을 사용하면 우리는 조작 수를 절반으로 줄일 수 있다.이제 얼마 안 남았어!그러나 만력과 비슷하고 시간의 복잡도는 여전하다O(n).

왜 이러지?

알겠습니다. 만약 n 문자열의 길이라면, 우리는 최종적으로 n/2 교환을 진행할 것입니다.그러나 Big O Notation 은 하나의 알고리즘에 필요한 원시 작업수가 아니라 숫자가 입력에 따라 어떻게 축소되는지 기억하십시오.
따라서 절반의 숫자 연산이 필요하지만 4 문자열은 쌍바늘 방법으로 2 교환해야 한다.그러나 8 문자열은 4 교환이 필요합니다.입력이 배로 증가했고 조작 수량도 배로 증가했다.

최종 솔루션

function reverseString(str) {
  let strArr = str.split("");
  let start = 0;
  let end = str.length - 1;

  while (start <= end) {
    const temp = strArr[start];
    strArr[start] = strArr[end];
    strArr[end] = temp;
    start++;
    end--;
  }

  return strArr.join("");
}