LeetCode의 K 요소 패턴 이해: 기본 사항(1부)

드디어 이해가 됐어요! LeetCode를 배우는 가장 좋은 방법은 문제를 계속해서 헤쳐나가는 것, 때로는 문제를 비효율적으로 해결하는 데 한 시간이 걸리는 것이 아닙니다. LeetCode를 마스터하는 열쇠는 패턴을 공부하는 것입니다. 일반적인 것을 공부해보자!

면접관은 문자열이나 배열에서 K개 요소를 찾고, 유지하고, 조작하는 방법에 대해 질문하는 것을 좋아합니다. 처음에는 각 문제가 완전히 다른 줄 알았는데, 점점 연관성이 보이기 시작했습니다. 이 패턴을 이해하는 데 큰 도움이 된 두 가지 문제가 무엇을 의미하는지 보여드리겠습니다.

문제 1: 합이 가장 큰 길이 K의 부분 수열 찾기

기술적으로는 '쉬운' 수준의 질문(한 회사에서만 질문)이지만, 이러한 k-요소 문제에 대해 어떻게 생각해야 하는지에 대해 많은 것을 가르쳐줍니다!

그들이 묻는 것

숫자 배열과 k 값을 얻었고, 그 배열에서 가능한 가장 큰 합이 되는 k 숫자를 찾아야 합니다. 하지만 (그리고 이것이 제가 처음에 걸려 넘어진 부분입니다) 숫자를 원래 순서대로 유지해야 합니다!

예:

아! 이건 더 까다롭습니다:

알았어 알겠어

처음에는 '가장 큰 숫자 k개만 잡으면 끝!'이라고 생각했습니다. 하지만 아닙니다. 주문 요구 사항이 모든 것을 바꿉니다. 마침내 클릭한 내용은 다음과 같습니다.

1. 각 숫자가 어디서 왔는지 기억해야겠죠? 그래서 나는 "모든 번호를 그 번호와 짝을 맞춰야 해"라고 생각했어요. 입장?"

1. 그런 다음 이러한 쌍을 값을 기준으로 정렬할 수 있습니다(즉, 각 쌍의 첫 번째 숫자), 하지만 우리는 그들이 어디서 왔는지(두 번째 숫자입니다)!

1. 이제 멋진 부분입니다. 이 중 k개만 필요하므로 처음 k 쌍을 입력하고 위치를 유지하세요.

1. 마지막으로 원래 배열을 살펴보고 우리 세트에 위치가 있는 숫자:

코드는 다음과 같습니다.

2: 스트림에서 K번째로 큰 요소

좋아요, 이 문제도 '쉬움'으로 표시되어 있지만(5개 회사에서 요청) 이 문제는 더 어려운 Kth 요소 문제보다 나에게 더 혼란스러웠습니다.

그들이 묻는 것

당신이 대학에서 일하고 있는데 학생들이 계속해서 시험 점수를 제출한다고 상상해 보세요. 당신의 임무는 언제든지 k번째로 높은 점수를 아는 것입니다. 새로운 점수가 계속해서 나오므로 계속 추적해야 합니다.

그들은 k와 몇 가지 초기 점수를 주고 계속해서 새로운 점수를 던지며 매번 k번째로 높은 점수를 알고 싶어합니다. 예를 살펴보겠습니다.

알았어, 알 것 같아

처음에는 새로운 점수가 들어올 때마다 전체 배열을 계속 정렬하려고 했지만 정렬이 비효율적일 수 있다는 것을 알고 있습니다. 그렇다면 나는 상위 k에만 관심을 갖고 있는데 왜 모든 점수를 추적하고 있는지 생각했습니다.

해석 방법은 다음과 같습니다.

1. 먼저 초기 점수를 정렬하고 상위 k개만 유지합니다.

1. 이제 새로운 점수가 나오면:

k번째로 높은(첫 번째 숫자)보다 작으면 무시하세요
더 크면 우리 목록 어딘가에 속할 것입니다

각 추가 사항은 다음과 같습니다.

코드

이 두 가지 문제가 연결된 이유

두 문제 모두 k 요소를 처리하는 데 있어 매우 중요한 사실을 가르쳐 주었습니다.

• 첫 번째 문제: 때로는 요소가 어디에 있는지 추적해야 하는 경우가 있습니다. 에서 왔습니다
• 두 번째 문제: 때로는 k개 요소만 유지해야 하는 경우도 있습니다. 주변

이러한 k-요소 문제는 어떤 정보를 보관하고 무엇을 버릴지에 대한 영리함에 관한 것입니다.
다음번에는 이러한 아이디어를 기반으로 하는 두 가지 k 요소 문제를 더 살펴보겠습니다. 결국에는 패턴을 발견하고 이러한 유형의 문제가 덜 무섭게 느껴지기를 바랍니다!

위 내용은 LeetCode의 K 요소 패턴 이해: 기본 사항(1부)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!