K 빈 슬롯 LeetCode

난이도 쉽게
자주 묻는 질문 아마존 구글
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 순서없는지도조회수 31

K Empty Slots는 LeetCode에서 매우 유명한 문제입니다. 문제 설명은 다음과 같습니다. 정원은 각각 꽃이 들어있는 n 개의 슬롯으로 구성되어 있습니다. 모든 꽃은 처음에는 개화하지 않습니다. 주어진 정렬 꽃의 a []와 정수 k. i가 0에서 시작하는 것을 고려하면 i + 1 번째 꽃은 a [i] 날에 피어납니다. 예를 들어 – a [] = {1, 3, 2}은 첫 번째 꽃이 1 일에 피고 두 번째 꽃이 3 일에, 세 번째 꽃이 2 일에 피는 것을 의미합니다. 두 꽃 사이에 꽃이 피지 않은 k 꽃이 되십시오. 답이 없으면 -1을 인쇄하십시오. 예를 들어 – ln a [] = {1, 3, 2} 및 k = 1, 두 번째 날 첫 번째와 마찬가지로 출력은 2이고 세 번째 꽃은 k 즉 그 사이에 꽃이 피지 않은 1 개의 꽃으로 피어납니다.

입력

a [] = {1, 4, 3, 2, 5}

k = 2

산출

2

입력 

a [] = {1, 2, 3, 4}

k = 1

산출

-1

암호알고리즘

이제 우리는 K Empty Slots LeetCode의 문제 설명을 알고 있습니다. 따라서 많은 시간을 들이지 않고이 문제를 해결하는 데 사용되는 알고리즘으로 이동합니다.

  1. 배열 a와 정수 k를 초기화합니다.
  2. 각 꽃이 피게 될 날짜를 저장하기 위해 다른 배열 날짜를 초기화합니다.
  3. 1에서 시작하는 i로 days 배열을 탐색하고 days [a [i]] = i + XNUMX로 배열을 업데이트합니다.
  4. 결과를 INT_MAX로 설정합니다.
  5. 어레이를 다시 횡단하십시오. 2 개의 변수 사이에 k 개의 슬롯이있는 왼쪽 및 오른쪽 값을 저장하고 최대 값을 찾습니다.
  6. 각 단계에서 1에서 k로 이동하고 days [i + j]가 최대 값보다 작은 지 확인합니다. 내부 루프를 중단하고 플래그를 false로 설정합니다.
  7. 플래그가 참이면 결과를 최대 값으로 설정합니다.
  8. 결과가 INT_MAX와 같으면 -1을 반환하고 그렇지 않으면 res를 반환합니다.

실시

K 빈 슬롯 LeetCode를위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;
int kSlots(int a[], int k, int n) {
    int days[n+1];
    for(int i=0; i<n; i++){
        days[a[i]] = i+1;
    }    
    int res = INT_MAX;    
    n = sizeof(days)/sizeof(days[0]);   
    for(int i=1; i<n; i++){
        int l = days[i];
        int r = days[i+k+1];
        int m1 = max(l, r);
        int m2 = min(l, r); 
        bool flag = true;
        for(int j=1; j<=k; j++){
            if(days[i + j]<m1){
                flag = false;
                break;
            }
        }
        if(flag && m1<res){
            res = m1;
        }
    }
    return res == INT_MAX ? -1 : res;
}
int main(){
  int a[] = {1, 3, 2}; 
  int k = 1;
  int n = sizeof(a)/sizeof(a[0]);
  cout<<kSlots(a, k, n);
  return 0;
}
2

K 빈 슬롯 LeetCode를위한 자바 프로그램

class kEmptySlots{
    
    static int kSlots(int[] a, int k) {
        int[] days = new int[a.length + 1];
        
        for(int i=0; i<a.length; i++) {
            days[a[i]] = i+1;
        }
        
        int res = Integer.MAX_VALUE;
        
        for(int i=1; i< days.length-k-1; i++){
            int l = days[i];
            int r = days[i+k+1];
            
            int max = Math.max(l, r);
            int min = Math.min(l, r);
            
            boolean flag = true;
            for(int j=1; j<=k; j++){
                if(days[i + j]<max){
                    flag = false;
                    break;
                }
            }
        
            if(flag && max<res){
                res = max;
            }
        }
    
        return res == Integer.MAX_VALUE ? -1 : res;
    }
    
    public static void main (String[] args){
        int a[] = {1, 3, 2};
        int k = 1;
        System.out.println(kSlots(a, k));
    }
}
2

복잡성 분석

시간 복잡성 : O (N * K) 여기서 N은 주어진 배열의 크기이고 K는 두 개화 한 꽃 사이에 개화하지 않은 꽃의 수를 나타내는 주어진 값입니다.

공간 복잡성 : O (N) 여기서 N은 주어진 배열의 크기입니다. 여기에 개화 한 꽃 정보를 저장하기위한 days [n] 배열이 있습니다.

참조

코멘트를 남겨

Translate »