오늘은 다양한 알고리즘 문제를 해결하는 데 사용되는 개념에 대한 개요를 시작하겠습니다. 특정 개념을 이해하면 잠재적인 솔루션에 대해 어떤 각도에서 생각해야 할지 직관할 수 있습니다.
다양하지만 개념이 너무 많지는 않습니다. 오늘은 슬라이딩 윈도우 컨셉에 여러분의 관심을 투자해보겠습니다
미닫이창의 개념은 언뜻 보기보다 좀 더 복잡합니다. 실제 사례를 통해 이를 보여드리겠습니다. 지금은 이동해야 하는 창이 있다는 개념적 아이디어를 염두에 두세요. 바로 예시부터 시작해보겠습니다.
정수 배열과 사전 정의된 하위 배열 크기가 있다고 가정합니다. 다른 값 중에서 값의 합이 최대가 되는 하위 배열(창이라고도 함)을 찾으라는 요청을 받습니다.
아주 간단해 보입니다.
(1) 크기 2의 슬라이딩 창
(2) 하위 배열 2개
(3) 각각의 합을 세어보세요
(4) 둘 사이의 최대값을 찾아보세요
구현해 볼까요
글쎄, 우리는 슬라이딩 윈도우 개념을 효율적으로 활용한 것 같습니다. 실제로는 정확하지 않습니다. 솔루션의 시간 복잡도를 이해함으로써 이에 대한 "증거"를 얻을 수 있습니다.
복잡도는 O(l)*O(w)입니다. 여기서 l은 배열의 창 수이고 w는 창의 요소 수입니다. 즉, l개 창을 순회해야 하며 각 l번째 창에 대해 w개 요소의 합을 계산해야 합니다.
여기서 의문스러운 점은 무엇인가요? 질문에 답하기 위한 반복을 개념적으로 묘사해 보겠습니다.
답은 배열을 슬라이딩하더라도 각 반복마다 이전 반복에서 이미 계산된 k-1 요소를 "다시 계산"해야 한다는 것입니다.
기본적으로 이 통찰력은 우리에게 다음과 같은 질문을 하도록 제안합니다.
"이전 단계의 계산을 활용할 수 있는 방법이 있나요?"
답은 그렇습니다. 창 요소 뒤에 첫 번째 요소와 다음 요소를 더하고 빼면 창 요소의 합을 얻을 수 있습니다. 이 아이디어를 코드에 넣어보겠습니다.
여기서 우리는 크기 길이의 하위 배열을 구성한 시점에서 창 합계에서 첫 번째 요소를 빼기 시작했으며 이를 통해 이전 단계의 계산을 재사용할 수 있다는 것을 알 수 있습니다.
이제 우리는 슬라이딩 윈도우의 개념을 효율적으로 활용했다고 말할 수 있지만, 시간 복잡도를 확인하는 증거를 얻었고 이는 O(l*w)에서 O(l)로 감소했습니다. 여기서 l은 슬라이딩할 윈도우의 양입니다.
제가 강조하고 싶은 주요 아이디어인 슬라이딩 윈도우 개념은 단순히 반복 가능한 항목을 특정 크기의 윈도우로 분할하는 것이 아닙니다.
몇 가지 문제를 드리겠습니다. 여기서는 슬라이딩 창 개념과 관련된 문제를 감지하는 방법과 창 자체로 수행할 수 있는 작업이 정확히 무엇인지 알아볼 것입니다.
여기서는 개념만 이야기하는 것이므로 "창 안에서 숫자를 세는 방법"은 생략하겠습니다.
문제 하나
주어진 배열에서 크기가 K인 모든 인접한 하위 배열의 평균을 구합니다.
좋습니다. 이제 접근 방식을 다음과 같이 정의할 수 있습니다. 크기가 K인 창을 사용하여 입력 배열을 반복합니다. 각 반복에서 창의 평균을 계산합니다...
문제 2
양수 배열과 양수 K가 주어졌을 때 크기가 K인 인접한 부분 배열의 최대 합을 구하세요.
이제: 크기 K의 창으로 입력 배열을 탐색합니다. 각 반복에서 창의 합을 계산합니다 ...
문제 3
양수 배열과 양수 S가 주어지면 합이 S보다 크거나 같은 가장 작은 연속 하위 배열의 길이를 찾습니다.
Maintenant, nous pourrions définir l'approche de la manière suivante : "tout d'abord, parcourez le tableau d'entrée et construisez une telle première fenêtre, qui satisferait aux conditions (la somme est >= à S). Une fois cela fait, déplacez la fenêtre, gérez le démarrage de la fenêtre et fin..."
Quatrième problème
À partir d'une chaîne, recherchez la longueur de la sous-chaîne la plus longue ne contenant pas plus de K caractères distincts.
L'approche ici est un peu plus complexe, je vais donc la sauter ici.
Problème cinq
Étant donné un tableau d'entiers où chaque entier représente un arbre fruitier, vous recevez deux paniers, et votre objectif est de mettre le maximum de fruits dans chaque panier. La seule restriction est que chaque panier ne peut contenir qu'un seul type de fruit.
Vous pouvez commencer avec n’importe quel arbre, mais vous ne pouvez pas sauter un arbre une fois que vous avez commencé. Vous cueillirez un fruit de chaque arbre jusqu'à ce que vous ne puissiez plus, c'est-à-dire que vous vous arrêterez lorsque vous devrez cueillir un troisième type de fruit.
Écrivez une fonction pour renvoyer le nombre maximum de fruits dans les deux paniers.
Cela ne semble pas si évident, simplifions d'abord les conditions.
Il existe un tableau d'entrée. Le tableau peut contenir seulement 2 chiffres distincts (compartiments). Il vous est demandé de trouver un tel sous-réseau contigu dont la longueur serait maximale.
Il est désormais plus facile de voir que nous pourrions travailler avec le concept de fenêtre coulissante.
Problème six
Étant donné une chaîne et un motif, découvrez si la chaîne contient une permutation du motif.
Tout d’abord, nous avons 2 ficelles, originales et à motifs. Nous savons que nous devons d'une manière ou d'une autre comparer l'original et le motif, ce qui a conduit à l'idée, nous devons construire la fenêtre de taille du motif et effectuer ensuite une vérification des permutations. Cela signifie que nous pourrions utiliser le concept de fenêtre coulissante.
Lorsque vous avez affaire à une fenêtre coulissante, gardez à l'esprit les questions suivantes :
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
