D Gün ərzində Leetcode həllində paketləri göndərmə qabiliyyəti

Problem bəyanat

“D gün ərzində paketləri göndərmə qabiliyyəti” problemində A limanında paketlərimiz var ki, D günlərdə B limanına köçürməliyik.

hər paketin çəkisini və paketləri köçürməyimiz lazım olan gün sayını ehtiva edən bir çəki seriyası verilir. Bizim vəzifəmiz, paketləri D günlərində A limanından B limanına köçürmək üçün istifadə ediləcək gəminin minimum yük tutumunu tapmaqdır.

Pin

misal

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

15

Explanation: Gəmi paketləri aşağıdakı şəkildə köçürəcək:

Birinci gün: 1,2,3,4,5

İkinci Gün 2: 6,7

Üçüncü gün 3: 8

Dördüncü gün 4: 9

Beşinci Gün 5: 10

Bu şəkildə, bütün paketləri 15 günə köçürmək üçün gəminin minimum yük tutumu 5 olmalıdır.

D Gün ərzində Leetcode Çözümündə Paketləri Göndərmə Tutumuna Yanaşma

Bu problemi həll etmək üçün ilk və ən vacib şey müşahidələr aparmaqdır. Axtarış aralığımız üçün bir neçə müşahidələr:

1. Gəminin yük tutumu ən azı maksimum ağırlığa (çəkiyə) bərabər olan paketə bərabər olmalıdır. kimi adlandıraq start.
2. Gəminin maksimum tutumunu cəmi (ağırlıqlar) olan bütün paketlərin ağırlığının cəmi ilə məhdudlaşdıra bilərik. kimi adlandıraq son.

İndi axtarış aralığımız var. Fərz edək ki, intervalın ölçüsüdür Uzunluq və paket sayı n.  Sadəlövh yanaşma, yükləmə qabiliyyətinin paketləri D günündə müvəffəqiyyətlə köçürə biləcəyini və onlardan minimumu seçə biləcəyini intervaldakı hər bir dəyəri yoxlamaq ola bilər. Sadəlövh yanaşma üçün zaman mürəkkəbliyi Uzunluq * n olacaqdır.

Xətti Axtarış yerinə İkili Axtarışdan istifadə edərək zamanın mürəkkəbliyini yaxşılaşdıra bilərik.

Zamanın mürəkkəbliyi İkili axtarış yanaşma log olacaq (Uzunluq) * n.

Həyata keçirilməsi

D Gün ərzində Leetcode Çözümündə Paketləri Göndərmə Tutumu üçün C ++ kodu

#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 Gün ərzində Paketləri Göndərmə Tutumu üçün Java kodu Leetcode Həlli üçün Java kodu

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 Gün ərzində Leetcode Çözümündə Göndərmə Paketlərinə Tutumun Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n * log (Uzunluq)) çünki çəki massivi jurnalını (Uzunluq) dəfə keçirik. Burada n və Uzunluq sırasıyla paketlərin sayı və axtarış intervalının ölçüsüdür.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

References