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

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

문제 설명

”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 »