제로 코드 이동 도전

이 도전은 보통 두 가지 변체가 있는데, 유일한 차이점은 0이 그룹의 끝 (오른쪽) 이나 시작 (왼쪽) 으로 이동해야 하는지 여부이다.다음은 geeksforgeeks 웹 사이트에서 복제해야 할 과제입니다.
무작위 수조를 정하고, 수조의 모든 0을 수조의 끝까지 밀어냅니다.
예를 들어 주어진 수조가 {1,9,8,4,0,0,2,7,0,6,0}이면
그것은 {1,9,8,4,2,7,6,0,0,0,0,0}으로 바꿔야 한다.
모든 다른 원소의 순서는 같아야 한다.
예상 시간의 복잡도는 O(n)이고 추가 공간은 O(1)이다.
우리는 이 문제를 해결하는 두 가지 방법을 소개할 것이다. 첫 번째는 abrute force이거나 업무 해결 방안의 첫 번째 가장 좋은 추측이다. 그리고 우리는 the recommended way를 처리하여 비교할 것이다.

여기 영상이 있어요.

폭력 - 첫 번째 솔루션

나의 첫 번째 직감은 다음 단계로 나눌 수 있다.

현재 그룹

의 크기 가져오기

첫 번째 그룹 크기와 같은 두 번째 그룹을 만들고 0으로 채우기

첫 번째 그룹의 모든 0을 필터하면 0이 아닌 순서

를 유지합니다

첫 번째 그룹과 필터 그룹 사이의 길이 차이를 추출하여 편향 인덱스

를 얻습니다

0이 그룹의 끝에 필요하면holder 그룹을 채우기 시작해서 필터의 길이

까지

0이 시작점에 있어야 할 경우 오프셋에서 끝점까지 항목을 교체합니다.

유지 관리 어레이로 돌아가기

현재 우리는 이미 이런 절차가 있으니 코드로 보고 등록을 더욱 쉽게 하기를 바란다.함수 선언부터 시작하겠습니다.

const moveZeroes = ( arr, dir = 'end') => {
    // body of function here
}

우리의 함수는 양호한 형식의 숫자 그룹과 기본적으로'end '인 선택 방향 인자가 필요합니다.이제 함수체의 단계로 이동합니다.

현재 그룹의 크기 가져오기

const size = arr.length;

첫 번째 그룹 크기와 같은 두 번째 그룹을 만들고 0으로 채웁니다

let holder = Array.from({ length: size}, () => 0);

첫 번째 그룹의 모든 0을 필터하면 0이 아닌 순서를 유지합니다

let filtered = arr.filter( v => v !== 0);

첫 번째 그룹과 필터 그룹 사이의 길이 차이를 추출하여 편향 인덱스를 얻습니다

let offset = size - filtered.length;

0이 그룹의 끝에 필요하면holder 그룹을 채우기 시작해서 필터의 길이까지

if( dir === 'end' ) {
    filtered.forEach( (v, i) => holder[i] = v );   
}

0이 시작점에 있어야 할 경우 오프셋에서 끝점까지 항목을 교체합니다.

if( dir === 'start' ) {
    filtered.forEach( (v, i) => holder[ i + offset] = v );
}

유지 관리 어레이로 돌아가기

마지막으로, 우리는 다음과 같은 코드를 우리의 폭력 해결 방안으로 얻었다.

const moveZeroes = ( arr, dir = 'end') => {
    const size = arr.length;
    let holder = Array.from({ length: size}, () => 0);

    const filtered = arr.filter( v => v !== 0);
    const offset = size - filtered.length;

    if( dir === 'end' ) {
        filtered.forEach( (v, i) => holder[i] = v );
    }

    if ( dir === 'start' ) {
        filtered.forEach( (v, i) => holder[ i + offset] = v )
    }

    return holder;
}

다음과 같은 방법으로 테스트를 수행할 수 있습니다.

let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('Zeroes to end: ', moveZeroes(arr));
console.log('Zeroes to start: ', moveZeroes(arr, 'start'));

출력

Zeroes to end   :   [1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0]
Zeroes to start :   [0, 0, 0, 0, 1, 9, 8, 4, 2, 7, 6]

이는 당면 과제의 예상 결과물을 충족하지만 자동 평가를 통해 솔루션을 최적화할 수 있는 여러 요소를 파악해야 합니다.

우선 필터 항목을 저장하기 위한 두 번째 그룹을 만듭니다

두 번째 단계에서 우리는 세 번째 그룹을 만들고 0으로 그것을 채운다. 이 단계의 매 단계는 하나의 추가 계산 절차이고 그룹의 크기가 증가함에 따라 실행 시간이 증가한다

마지막으로 필터된 항목을 놓고 항목의 순서를 지키기 위해 새로 만든 그룹을 교체하고 변경합니다

그래서 가장 큰 문제는 우리가 하나의 수조만 전달함으로써 같은 결과를 실현할 수 있는지이다. 모든 새로운 수조를 만들 필요가 없고, 순서에 영향을 주지 않는 상황에서 어떻게 0을 하나의 단점으로 교환할 수 있는지이다.
첫 번째 해결 방안과 같이 해결 방안의 논리적 해체부터 시작하여 이해에 도움이 되었으면 합니다

최적화 솔루션 - 권장 사항

우리는 하나의 그룹에서만 작업하고 두 개의 인덱스를 추적할 것입니다. 같은 위치에서 시작하는 읽기 인덱스와 쓰기 인덱스입니다.
우리는 readIndex를 사용하여 끝에서 끝까지 그룹을 스캔하고 0을 포함하는 모든 칸을 건너뛸 것입니다.
0이 아닌 값을 만났을 때, 0이 아닌 값으로 write Index의 값을 업데이트한 다음, 필요에 따라 0을 어느 쪽으로 이동해서 write Index를 감소하거나 증가시킵니다.
만약 당신이 상술한 절차를 읽은 후에 머리가 어지럽고 눈앞이 캄캄해진다면, 나는 가시적인 전시를 해서 당신이 신속하게 이해하는 데 도움을 줄 것이다.아래는 한 걸음 한 걸음 왼쪽으로 0을 이동하는 것을 보여 준다

이번에는 두 개의 독립된 함수로 그것을 코드로 바꾸어 왼쪽의 0에서 시작합시다.

[최적화] 왼쪽으로 0 이동

우리는 항상 함수 성명부터 시작한다

const moveZeroesLeft = function(arr) {

}

그리고 write Index와 start 위치를 저장하기 위해 두 개의 국부 변수를 설명합니다

let writeIndex = arr.length - 1;
let start = writeIndex;

두 색인은 모두 수조의 끝에서부터 시작한다.
가시화에서 우리가 두 개의 내부 순환을 실행할 것이라고 짐작할 수 있습니다.
첫 번째 순환은readIndex를 사용하여 0이 아닌 값을 스캔하고 writeIndex에서 찾은 값을 넣습니다.
매번 이런 조작을 실행하면 writeIndex는 감소합니다

for(let readIndex = start; readIndex >= 0; readIndex-- ) {
    if( arr[readIndex] !== 0) {
        arr[writeIndex] = arr[readIndex];
        writeIndex--;
    }
}

두 번째 순환은 지금부터 시작하여, write Index 칸에 도달할 때까지 0으로 값을 교환합니다. 이 칸도 0을 받을 것입니다.

for (let j = 0; j <= writeIndex; j++) {
    arr[j] = 0;
}

마지막으로, 우리는 업데이트된 그룹을 되돌려주기만 하면 된다

return arr;

전체 코드:

const moveZeroesLeft = function(arr) {
    let writeIndex = arr.length - 1;
    let start = writeIndex;

    for(let readIndex = start; readIndex >= 0; readIndex-- ) {
        if( arr[readIndex] !== 0) {
            arr[writeIndex] = arr[readIndex];
            writeIndex--;
        }
    }

    for (let j = 0; j <= writeIndex; j++) {
        arr[j] = 0;
    }

    return arr;
}

이 명령문이 다음 명령문과 출력에 적용되는지 확인할 수 있습니다.

let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('\n------------ Move zeroes left --------\n');
console.log(moveZeroesLeft(arr));
// outputs to console
[0, 0, 0, 0, 1, 9, 8, 4, 2, 7, 6]

[최적화] 오른쪽으로 제로 이동

0을 오른쪽에 놓은 코드는 이전과 같은 논리를 따른다.
주된 차이점은readIndex와 writeIndex는 끝이 아닌 그룹의 시작에서 시작한다는 것이다.
한 걸음 한 걸음 진행할 필요가 없다. 다음은 완성된 코드다.

const moveZeroesRight = function(arr) {
    let writeIndex = 0;
    const size = arr.length;

    for(let readIndex = 0; readIndex < size; readIndex++) {
        if(arr[readIndex] !== 0) {
            arr[writeIndex] = arr[readIndex];
            writeIndex++;
        }
    }

    for(let j = writeIndex; j < size; j++) {
        arr[j] = 0;
    }

    return arr;
}

다음 문을 사용하여 0을 배열 끝으로 이동하는 경우를 다시 한 번 기대하고 검증할 수 있습니다.

let arr = [1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0];
console.log('\n------------ Move zeroes right --------\n');
console.log(moveZeroesRight(arr));
// outputs to console
[1, 9, 8, 4, 2, 7, 6, 0, 0, 0, 0]

결론

나는 너희들에게 이 재미있는 도전을 해결하는 여러 가지 방법을 철저히 보여 주려고 한다.
나는 네가 이 책을 좋아하길 바란다. 더 중요한 것은 이 두 가지 방법을 이해하고, 왜 그 중 한 가지 방법이 다른 것보다 더 좋은지 이해하는 것이다.