리트코드 챌린지 #1

추신 여기에 처음 오신 분은 이 게시물을 확인하기 전에 확인하세요!


그럼 도전을 시작합시다.

알고리즘 연구 계획

leetcode 홈 페이지에서 이것을 찾았습니다study plan. 좋은 시작이 될 수 있습니다. 첫 번째 부분의 계획에는 매일 2~3개의 문제(대부분 쉬움, 약간 중간, 어렵지 않음)가 포함됩니다. 나는 매일 그것들을 끝내려고 노력할 것이고 아마도 내가 전체 시간을 사용했는지 확인하기 위해 0~2개의 추가 문제가 있을 것입니다.

오늘의 문제

오늘의 주제: Binary Search

ID
이름
어려움
문제
해결책


704
이진 검색
쉬운
link
link

278
첫 번째 나쁜 버전
쉬운
link
link

35
검색 삽입 위치
쉬운
link
link


이진 검색의 많은 구현을 보았습니다. 그들은 모두 O(log(n)) 시간과 O(1) 공간에서 수행되어야 합니다.

내가 가장 좋아하는 것은 사용이 직관적이기 때문에 특정 조건에서 left 및 right 포인터를 유지하는 것입니다. 이것은 위의 세 가지 문제 모두에 적용됩니다.

내가 본 또 다른 흥미로운 구현은 각 반복에서 2^k 또는 0가 추가될 하나의 포인터를 유지하는 것입니다.
예를 들어

function binarySearch(arr, target) {
  let index = 0;
  let step = 1 << 20;
  while (step) {
    const next = index + step;
    if (next < arr.length && arr[next] <= target) {
      index = next;
    }
    step /= 2;
  }
  return index;
}

문제의 제약 조건을 사용하여 초기 단계 크기를 얻을 수 있습니다. 또는 다른 루프로 동적으로 찾으십시오.

추가 문제

오늘 또 다른 중간 이진 검색 문제를 골랐습니다.


ID
이름
어려움
문제
해결책


33
회전 정렬된 배열에서 검색
중간
link
link


먼저 가장 기본적인 아이디어를 떠올립니다. 이진 검색을 사용하여 피벗을 찾은 다음 nums[0] < target 여부에 따라 첫 번째 또는 두 번째 부분에 이진 검색을 적용합니다. 53줄이 걸리고 읽기가 쉽지 않습니다.

그런 다음 realIndex = (originalIndex + pivot) % arr.length 이후 전체 배열에 이진 검색을 간단히 적용할 수 있다는 것을 깨달았습니다.
이 트릭을 사용하면 결과 코드가 40줄로 줄어들고 더 읽기 쉽습니다! 복잡성은 여전히 ​​O(log(n)) 시간과 O(1) 공간입니다.

결론

연습생 첫 포스팅입니다. 어떤 제안이라도 감사하겠습니다! 읽어주셔서 감사합니다.


| -->