기술 슬라이딩 윈도우 알고리즘

코딩 문제: 문자열 s와 문자 c가 주어지면 문자열의 모든 문자와 문자열 s의 문자 c까지의 거리를 구합니다. 문자 c가 문자열에 한 번 이상 나타날 것이라고 가정할 수 있습니다. 이 문제는 최근 Uber에서 요청했습니다.

예시:

예를 들어 shortest_dist('helloworld', 'l') 가 주어지면 [2, 1, 0, 0, 1, 2, 2, 1, 0, 1] 를 반환해야 합니다.

문제 해결 방법:

1) 기법: 슬라이딩 윈도우(이 경우 좌우 2개의 윈도우)

창 시작 및 종료 포인터:

창의 시작 및 끝 포인터를 사용하면 창 자체의 크기를 늘리거나 줄이는 체인을 통과할 수 있습니다. 문자가 장면에 나타날 때까지 위치. char 모양으로 피벗이 업데이트되고 창의 크기와 피벗과 해당 시점까지 창을 형성한 요소 사이의 거리가 업데이트됩니다.

창 크기 조정:

char = 'l'에서 해당 문자를 찾으면 창 크기를 조정할 수 있습니다. 창의 인덱스 '끝'은 전체 체인을 통과하고 시작은 피벗 = (문자 발생)을 찾을 때까지 위치를 유지합니다.

피벗:

피벗 변수를 사용하면 체인에서 char = 'l'의 마지막 모양에 대한 기준점을 가질 수 있습니다. 이 피벗을 사용하여 끝 포인터와 마지막 모양의 char 사이의 거리를 계산합니다.

빅 오(N):

요컨대, 이 솔루션에는 'n'이 'st'의 길이이고 'm'이 'char'의 발생인 O(n * m)가 있다고 말할 수 있습니다. 따라서 내부 루프는 '시작' 포인터와 '피벗'을 업데이트하기 위한 것입니다. 문자가 더 많이 나타날수록 이 루프가 더 많이 실행됩니다. 마지막으로 O(n)은 이러한 알고리즘의 동작을 설명하는 가장 좋은 패턴입니다. 체인을 통과하기 위해 두 개의 창을 사용한다는 사실을 강조합니다. 이렇게 하면 업데이트 주기의 크기가 어느 정도 줄어듭니다.

암호:

function shortestDist(st, char) {

    let len = st.length - 1
    let [
        winLeftStart,
        winLeftEnd,
        winRightStart,
        winRightEnd
    ] = [0, 0, len, len];
    let [pivotLeft, pivotRight] = [null, null];
    let dist = [];

    while (winLeftEnd <= len) {

        /** Window Left*/
        if (st[winLeftEnd] === char) {

            pivotLeft = winLeftEnd;
            while (winLeftStart <= pivotLeft) {
                dist[winLeftStart] = pivotLeft - winLeftStart;
                ++winLeftStart;

            }

        } if (!!pivotLeft) {

            if (dist[winLeftEnd]) {
                //End when have first match in dist
                dist[winLeftEnd] =
                    dist[winLeftEnd] < winLeftEnd - pivotLeft ?
                        dist[winLeftEnd] :
                        winLeftEnd - pivotLeft;
                return dist;
            }

            dist[winLeftEnd] = winLeftEnd - pivotLeft;
        }


        /** Window right*/
        if (st[winRightEnd] === char) {

            pivotRight = winRightEnd;
            while (winRightStart >= pivotRight) {

                dist[winRightStart] = winRightStart - pivotRight;
                --winRightStart;
            }

        } else if (!!pivotRight) {

            dist[winRightEnd] = pivotRight - winRightEnd;
        }

        /** Grow Windows*/
        --winRightEnd;
        ++winLeftEnd;
    }
 return [];
}

간단한 테스트:

console.log(shortestDist('helloworld', 'l'))


//        h  e  l  l  o  w  o  r  l  d
// resp. [2, 1, 0, 0, 1, 2, 2, 1, 0, 1]
//        0  1  2  3  4  5  6  7  8  9

당신은 확인할 수 있습니다
code 의해