트위터 웅덩이 알고리즘의 JavaScript 구현 example_javascript 기술

오늘 매우 흥미로운 알고리즘 질문을 발견했습니다. 다음은 트위터 인터뷰 질문에서 파생된 알고리즘 설명입니다.

트위터 퍼들 알고리즘 설명

먼저 사진을 보세요

위 그림의 숫자는 배열의 내용을 기준으로 설명됩니다. 마지막으로 각 숫자의 크기를 기준으로 벽의 높이를 시뮬레이션하고, 마지막으로 벽이 생성되는 시점을 묻습니다. 비가 오면 이 벽을 설치할 수 있습니다. 물의 양은 1개 단위입니다.

물을 채운 벽의 모습은 다음과 같습니다

위 그림을 읽은 후 매우 흥미롭다고 생각합니다. 실제로 알고리즘 구현을 간략하게 분석해 보겠습니다.

사실 이 원칙은 비교적 간단합니다. 전체적으로 몇 가지 핵심 사항이 있습니다.

1. 가장 왼쪽과 가장 오른쪽에는 물이 채워져 있으면 안 됩니다
2. 물을 채우는 높이는 왼쪽과 오른쪽의 두 최대값 중 최소값에 따라 달라집니다

아래에서는 js를 사용하여 간단히 구현합니다.

코드 복사 코드는 다음과 같습니다.

/**
* 배열 아이템을 사용하여 벽이 높이에 따라 얼마나 많은 물을 담을 수 있는지 계산하세요
* 배열 예시 [2,5,1,2,3,4,7,7,6,9]
**/
함수 getWaterCounts(arg){
var i = 0,
        j = 0,
개수 = 0;
// 첫 번째 항목과 마지막 항목을 모두 제외해야 합니다
for(i = 1; i       var left = Math.max.apply(null, arg.slice(0, i 1));
      var right = Math.max.apply(null, arg.slice(i, arg.length));
        var min = 왼쪽 >= 오른쪽 ? 오른쪽 : 왼쪽;
              // 왼쪽과 오른쪽의 최대값 중 작은 값이 우선합니다.
​​​​ //현재 값이 이 값보다 크거나 같으면 아무 것도 하지 않습니다
           if(arg[i] < min){
개수 = 최소 - arg[i];
}
}
console.log(개수);
}
getWaterCounts([2,5,1,2,3,4,7,7,6,9]) // 11

요약

구현은 꽤 간단합니다. 사실, 생각만 하면 js로 많은 재미있는 것들을 얻을 수 있습니다.