D 일 이내에 패키지를 배송 할 수있는 용량 Leetcode 솔루션

난이도 중급
자주 묻는 질문 아마존
알고리즘 배열 이진 검색 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 100

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 설명

”D 일 이내에 패키지를 배송 할 수있는 용량”문제에서 D 일 내에 포트 B로 전송해야하는 패킷이 포트 A에 있습니다.

각 패킷의 가중치와 패킷을 전송하는 데 필요한 일 수가 포함 된 가중치 배열이 제공됩니다. 우리의 임무는 D 일 내에 포트 A에서 포트 B로 패킷을 전송하는 데 사용할 선박의 최소 적재 용량을 찾는 것입니다.

D 일 이내에 패키지를 배송 할 수있는 leetcode 솔루션

weights = [1,2,3,4,5,6,7,8,9,10], D = 5
15

설명 : 선박은 다음과 같은 방법으로 패킷을 전송합니다.

첫날 : 1,2,3,4,5

둘째 날 2 : 6,7

셋째 날 3 : 8

넷째 날 4 : 9

다섯째 날 5:10

이런 식으로 15 일 안에 모든 패킷을 전송하려면 선박의 최소 적재 용량이 5이어야합니다.

D 일 이내에 패키지를 배송하는 용량에 대한 접근 방식 Leetcode 솔루션

이 문제를 해결하기위한 첫 번째이자 가장 중요한 것은 관찰을 이끌어내는 것입니다. 다음은 검색 간격에 대한 몇 가지 관찰입니다.

  1. 선박의 적재 능력은 최대 중량 (무게) 인 패킷 이상이어야합니다. 이름을 지정합시다 스타트.
  2. 선박의 최대 용량을 sum (weights) 인 모든 패킷의 무게의 합으로 제한 할 수 있습니다. 이름을 지정합시다 종료.

이제 검색 간격이 있습니다. 간격의 크기가 다음과 같다고 가정합니다. 길이 패킷 수는 n.  순진한 접근 방식은 해당로드 용량이 D 일 내에 패킷을 성공적으로 전송할 수 있는지 간격의 각 값을 확인하고 최소값을 선택하는 것입니다. 순진한 접근 방식의 시간 복잡성은 Length * n입니다.

선형 검색 대신 이진 검색을 사용하여 시간 복잡성을 개선 할 수 있습니다.

사용하는 시간 복잡성 이진 검색 접근 방식은 log (Length) * n입니다.

실시

D 일 이내에 패키지를 배송하는 용량에 대한 C ++ 코드 Leetcode 솔루션

#include <bits/stdc++.h>
using namespace std; 
    int shipWithinDays(vector<int>& weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4,5,6,7,8,9,10}; 
 int d=5;                               

 cout<<shipWithinDays(arr,d)<<endl;
 return 0;
}
15

D 일 이내에 패키지를 배송하는 용량에 대한 Java 코드 Leetcode 솔루션

public class Tutorialcup {
    public static int shipWithinDays(int[] weights, int D) {
        int left = 0, right = 0;
        for (int w: weights) {
            left = Math.max(left, w);
            right += w;
        }
        while (left < right) {
            int mid = (left + right) / 2, requirement = 1, tillnow = 0;
            for (int w: weights) {
                if (tillnow + w > mid) {
                   requirement += 1;
                   tillnow = 0;
                }
                tillnow += w;
            }
            if (requirement > D) left = mid + 1;
            else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {1,2,3,4,5,6,7,8,9,10}; 
     int d=5; 
    int ans= shipWithinDays(arr,d);
    System.out.println(ans);
  }
}
15

D Days Leetcode 솔루션 내 패키지 배송 용량의 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (n * log (길이)) 가중치 배열 로그 (길이) 시간을 순회하기 때문입니다. 여기서 n과 Length는 각각 검색 간격의 패킷 수와 크기입니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. O (1) 답을 저장하는 데 변수 만 사용하고 있기 때문입니다.

참조

균열 시스템 설계 인터뷰
Translate »