리트코드 챌린지 #2

지난 포스팅 이후로 이틀이 지났습니다. 나는 study plan이 매일 해야 한다는 것을 알았다. 그것은 매일 새로운 문제 세트의 잠금을 해제합니다. 그래서 한 번에 이틀씩 끝내고(적어도 I 부분은) 두 번째 부분에 도달하면 일정을 조정해야 하는지 확인하겠습니다.

오늘의 문제

오늘의 주제: Two pointers

ID
이름
어려움
문제
해결책


977
정렬된 배열의 제곱
쉬운
link
link

189
어레이 회전
중간
link
link

283
0 이동
쉬운
link
link

167
Two Sum II - 입력 배열이 정렬됨
중간
link
link


2~5일차 주제는 Two pointers 입니다. 저는 이 단어가 생소하지만 저번에 사용한 이진 검색 방식은 일종의 투 포인터인 것 같습니다.

977, 283, 167번 문제는 실제로 매우 쉽고 솔루션이 직관적이기 때문에 건너뛰겠습니다.

189. 배열 회전

문제는 정말 흥미 롭습니다.
슬라이스+연결 또는 끝에서 회전과 같은 일부 간단한 방법은 공간이 너무 많이 듭니다(각각 O(n) 및 O(k)).
O(1) 공간 솔루션을 생각해 내는 데 시간이 좀 걸렸습니다(모두 O(n) 시간이지만).
주요 아이디어는 다음과 같습니다.
nums[0]을 nums[k]로 이동하고 원래 nums[k]를 nums[2*k]로 이동하면 ...(물론 모듈로 n에서) 다시 nums[0으로 돌아옵니다. ] 어느 시점에서. 그러나 경우에 따라 이 주기에는 모든 숫자가 포함되지 않습니다. 보다 정확하게는 0 + m * gcd(n, k) 형식의 인덱스만 포함됩니다. 따라서 동일한 절차를 반복해야 하지만 1 ~ gcd(n, k)부터 시작합니다.

예를 들어 고려하다n = 9, k = 6

0 -> 6 -> 3 -> 0 -> ...
1 -> 7 -> 4 -> 1 -> ...
2 -> 8 -> 5 -> 2 -> ...

결과 코드:

var rotate = function (nums, k) {
  const g = gcd(nums.length, k);

  for (let i = 0; i < g; i++) {
    let j = i;
    let tmp = nums[j];
    let next;
    while (next != i) {
      next = (j + k) % nums.length;
      [nums[next], tmp] = [tmp, nums[next]];
      j = next;
    }
  }
};

이 솔루션은 일종의 융통성이 없습니다. 그래서 나는 leetcode 토론을 확인하고 아름다운 마법을 발견했습니다. 핵심 개념은 다음과 같습니다.rotate(n, k) = reverse(0, n-1) + reverse(0, k-1) + reverse(k, n-1)
예를 들어 고려하다n = 7, n = 3

   [1, 2, 3, 4, 5, 6, 7] // original
-> [7, 6, 5, 4, 3, 2, 1] // reverse(0, 6)
-> [5, 6, 7, 4, 3, 2, 1] // reverse(0, 2)
-> [5, 6, 7, 1, 2, 3, 4] // reverse(3, 6)

이 마법이 어떻게 발견되었는지는 모르겠지만 정말 충격적이었습니다.

추가 문제

오늘 선택한 또 다른 두 개의 포인터 문제는 다음과 같습니다.


ID
이름
어려움
문제
해결책


11
물이 가장 많은 용기
중간
link
link


예상외로 이 문제는 40분 정도 걸렸습니다. 제약 조건에 따르면 n < 10^5 , O(n^2)는 허용되지 않습니다. 따라서 무차별 열거로는 충분하지 않습니다.

많은 예를 살펴본 후 면적 공식(l - r) * Math.min(height[l], height[r])이 높이의 최소값만 고려한다는 것을 알았습니다. 이 경우 더 작은 높이를 우선시하는 욕심 많은 알고리즘이 유용할 수 있습니다.

최종 알고리즘은 다음과 같습니다.
가장 바깥 쪽 쌍에서 시작하여 면적 값을 기록하고 더 큰 높이를 찾을 때까지 작은 쪽을 안쪽으로 축소합니다. 새 영역이 더 크면 레코드를 업데이트하십시오. 그런 다음 두 포인터가 일치할 때까지 단계를 반복해서 반복합니다. 양쪽의 높이가 같으면 한쪽만 축소하면 면적이 절대 커지지 않으므로 동시에 축소해야 합니다.

테두리를 축소할 때마다 컨테이너의 너비가 작아집니다. 따라서 높이를 최대화하는 데 집중하면 됩니다. 그리디 알고리즘은 면적 공식의 속성으로 인해 작동합니다.

복잡성은 O(n) 시간과 O(1) 공간입니다. 테두리 축소 프로세스는 총 n-1번 수행되고 면적 계산은 O(1)이기 때문입니다.

결론

위의 다섯 문제는 마지막 문제의 예상치 못한 난이도로 인해 약 1.5시간이 걸렸습니다. 또한 지난 번 문제들보다 더 어렵습니다. 마지막 알고리즘의 정확성 증명에는 일부 수학적 기술이 필요합니다. 루프 불변. 하지만 이 시리즈는 알고리즘 튜토리얼이 아닙니다. 죄송합니다. 자세한 내용은 건너뛰겠습니다.

이것이 오늘 제 도전입니다. 즐기시기 바랍니다. :)


<-- | | -->