오늘 나는 매우 흥미로운 알고리즘 질문을 발견했습니다. 다음은 알고리즘 설명이며 트위터의 인터뷰 질문에서 나온 것입니다.
Twitter Puddles 알고리즘 설명
먼저 사진을보세요
위 그림의 숫자는 배열의 내용에 따라 설명됩니다. 마지막으로, 벽의 높이는 각 숫자의 크기에 따라 시뮬레이션되고 벽이 생성됩니다. 비가 오면이 벽을 계산 장치로 1로 얼마나 많이 채울 수 있는지 물어보십시오.
물을 채운 후 벽이 있습니다
위의 그림을 읽은 후 재미 있다고 생각하십니까? 실제로 아래의 알고리즘 구현을 간단히 분석하겠습니다.
실제로이 원칙은 비교적 간단하며 몇 가지 핵심 사항이 있습니다.
1. 왼쪽과 오른쪽에는 확실히 물이 없습니다.
2. 수하의 높이는 자신의 왼쪽과 오른쪽에있는 두 최대 값의 최소값에 따라 다릅니다.
JS를 사용하여 간단히 구현합시다.
코드 사본은 다음과 같습니다.
/**
* 배열 항을 높이로 벽에 설치할 수있는 물의 양을 계산하십시오.
* 배열 예 [2,5,1,2,3,4,7,7,6,9]
**/
함수 getWaterCounts (arg) {
var i = 0,
J = 0,
count = 0;
// 첫 번째와 마지막 항목은 모두 제외해야합니다.
for (i = 1; i <arg.length -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) {
count += min -arg [i];
}
}
Console.log (count);
}
getwatercounts ([2,5,1,2,3,4,7,7,6,9]); // 11
요약
hehe, 구현이 아주 간단하지 않습니까? 사실, 기꺼이 생각하는 한 JS를 사용하여 많은 재미있는 것들을 구현할 수 있습니다.