សមត្ថភាពក្នុងការដឹកជញ្ជូនកញ្ចប់ក្នុងរយៈពេល D ថ្ងៃដំណោះស្រាយ Leetcode


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon
អារេ ការស្វែងរកគោលពីរ

សេចក្តីថ្លែងការណ៍បញ្ហា

នៅក្នុងបញ្ហា“ សមត្ថភាពក្នុងការដឹកជញ្ជូនកញ្ចប់ក្នុងរយៈពេល D ថ្ងៃ” យើងមានកញ្ចប់នៅកំពង់ផែ A ដែលត្រូវផ្ទេរទៅកំពង់ផែ B ក្នុងរយៈពេលឃ។

យើងត្រូវបានផ្តល់ឱ្យនូវជួរទម្ងន់ដែលមានទំងន់នៃកញ្ចប់នីមួយៗនិងចំនួនថ្ងៃដែលយើងត្រូវការផ្ទេរកញ្ចប់ព័ត៌មាន។ ភារកិច្ចរបស់យើងគឺស្វែងរកសមត្ថភាពផ្ទុកអប្បបរមានៃកប៉ាល់ដែលត្រូវបានប្រើដើម្បីផ្ទេរកញ្ចប់ព័ត៌មានពីកំពង់ផែ A ទៅច្រក B ក្នុងរយៈពេលឃ។

ដំណោះស្រាយ leetcode ចំពោះសមត្ថភាពក្នុងការដឹកជញ្ជូនកញ្ចប់ក្នុងរយៈពេលឃ

ឧទាហរណ៍

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

ការពន្យល់: កប៉ាល់នឹងផ្ទេរកញ្ចប់ព័ត៌មានតាមវិធីដូចខាងក្រោមៈ

ថ្ងៃដំបូង: 1,2,3,4,5

ថ្ងៃទី ២ ថ្ងៃទី ២: ៦,៧

ថ្ងៃទី ៣ ថ្ងៃទី ៣: ៨

ថ្ងៃទីបួនថ្ងៃទី ៤: ៩

ថ្ងៃទី ៥- ថ្ងៃទី ៥: ១០

តាមរបៀបនេះសមត្ថភាពផ្ទុកអប្បបរមានៃកប៉ាល់គួរតែមានចំនួន 15 ដើម្បីផ្ទេរកញ្ចប់ទាំងអស់ក្នុងរយៈពេល 5 ថ្ងៃ។

វិធីសាស្រ្តសម្រាប់សមត្ថភាពក្នុងការដឹកជញ្ជូនកញ្ចប់ក្នុងរយៈពេល D ថ្ងៃដំណោះស្រាយ Leetcode

រឿងដំបូងនិងសំខាន់បំផុតដើម្បីដោះស្រាយបញ្ហានេះគឺត្រូវធ្វើការសង្កេត។ នេះគឺជាការសង្កេតមួយចំនួនសម្រាប់ចន្លោះពេលស្វែងរករបស់យើង៖

  1. សមត្ថភាពផ្ទុករបស់កប៉ាល់គួរតែយ៉ាងហោចណាស់ស្មើនឹងកញ្ចប់ដែលមានទំងន់អតិបរិមាដែលជាអតិបរមា (ទំងន់) ។ សូមដាក់ឈ្មោះវាថា ចាប់ផ្តើម.
  2. យើងអាចកំណត់សមត្ថភាពអតិបរមារបស់កប៉ាល់ទៅនឹងផលបូកទំងន់នៃកញ្ចប់ទាំងអស់ដែលជាផលបូក (ទំងន់) ។ សូមដាក់ឈ្មោះវាថា បញ្ចប់.

ឥឡូវនេះយើងមានចន្លោះពេលស្វែងរករបស់យើង។ ឧបមាថាទំហំនៃចន្លោះពេលគឺ ប្រវែង ហើយចំនួនកញ្ចប់ព័ត៌មានគឺ n.  វិធីឆោតល្ងង់អាចជាការត្រួតពិនិត្យតម្លៃនីមួយៗក្នុងចន្លោះពេលប្រសិនបើសមត្ថភាពផ្ទុកនោះអាចផ្ទេរកញ្ចប់ព័ត៌មានបានដោយជោគជ័យក្នុងរយៈពេល D ថ្ងៃហើយជ្រើសរើសយកអប្បបរមាចេញពីពួកគេ។ ភាពស្មុគស្មាញនៃពេលវេលាសម្រាប់វិធីឆោតល្ងង់នឹងមានប្រវែង * n ។

យើងអាចកែលម្អភាពស្មុគស្មាញនៃពេលវេលាដោយប្រើការស្វែងរកគោលពីរជំនួសឱ្យការស្វែងរកលីនេអ៊ែរ។

ពេលវេលាស្មុគស្មាញដោយប្រើឯកសារ ការស្វែងរកគោលពីរ វិធីសាស្រ្តនឹងជាកំណត់ហេតុ (ប្រវែង) * n ។

ការអនុវត្តន៍

លេខកូដ C ++ សម្រាប់សមត្ថភាពបញ្ជូនកញ្ចប់នានាក្នុងរយៈពេលតែប៉ុន្មានថ្ងៃប៉ុណ្ណោះ Leetcode Solution

#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

កូដចាវ៉ាសំរាប់សមត្ថភាពបញ្ជូនកញ្ចប់ទំនិញក្នុងកំឡុងពេលឃ។ ដំណោះស្រាយ 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 ថ្ងៃដំណោះស្រាយ Leetcode

ភាពស្មុគស្មាញពេលវេលា

ពេលវេលាស្មុគស្មាញនៃលេខកូដខាងលើគឺ O (n * កំណត់ហេតុ (ប្រវែង)) ពីព្រោះយើងកំពុងឆ្លងកាត់កំណត់ហេតុនៃទំងន់ (ប្រវែង) ដង។ នៅទីនេះ n និងប្រវែងគឺជាចំនួននៃកញ្ចប់ព័ត៌មាននិងទំហំនៃចន្លោះពេលស្វែងរករៀងៗខ្លួន។

ភាពស្មុគស្មាញនៃលំហ

ភាពស្មុគស្មាញចន្លោះនៃលេខកូដខាងលើគឺ ឱ (១) ពីព្រោះយើងកំពុងប្រើតែអថេរដើម្បីរក្សាទុកចម្លើយ។

ឯកសារយោង