مساعد في حل مساله برمجه من LeetCode ؟

Ali Ahmed55 · 15 مارس

السلام عليكم

دي المساله

You are given two arrays of integers, fruits and baskets, each of length n, where fruits[i] represents the quantity of the ith type of fruit, and baskets[j] represents the capacity of the jth basket.

From left to right, place the fruits according to these rules:

Each fruit type must be placed in the leftmost available basket with a capacity greater than or equal to the quantity of that fruit type.
Each basket can hold only one type of fruit.
If a fruit type cannot be placed in any basket, it remains unplaced.
Return the number of fruit types that remain unplaced after all possible allocations are made.

ودي الكود بتاعي فا انا عاوز اعرف اي المشكله في الكود وهل فيه افضل من كده

class Solution(object):
    def numOfUnplacedFruits(self, fruits, baskets):
        """
        :type fruits: List[int]
        :type baskets: List[int]
        :rtype: int
        """
        fruits.sort()
        baskets.sort()

        f_index = 0  
        b_index = 0

        while f_index < len(fruits) and b_index < len(baskets):
            if fruits[f_index] <= baskets[b_index]:  
                f_index += 1  
            b_index += 1  

        return len(fruits) - f_index        
                               

solution = Solution()
print(solution.numOfUnplacedFruits([4, 2, 5], [3, 5, 4]))
print(solution.numOfUnplacedFruits([3, 6, 1], [6, 4, 7]))

Mustafa Suleiman · 15 مارس

الحل لا يتبع المسألة، حيث يجب وضع كل نوع من الفاكهة في أول سلة متاحة لها سعة كافية، أيضًا تقوم بزيادة b_index في كل دورة بغض النظر عما إذا تم تخصيص الفاكهة أم لا، بالتالي سيتجاوز سلال متاحة تستوعب الفاكهة.

والترتيب التصاعدي لكلا المصفوفتين لا يضمن الحل المثالي، لأن المسألة تتطلب التعامل مع الفواكه من اليسار إلى اليمين بالترتيب الأصلي لـ fruits، وليس بترتيب تصاعدي.

عليك إذن عدم ترتيب fruits لأننا نتبع الترتيب الأصلي من اليسار إلى اليمين، واستخدام طريقة لتتبع السلال المستخدمة.

class Solution(object):
    def numOfUnplacedFruits(self, fruits, baskets):
        """
        :type fruits: List[int]
        :type baskets: List[int]
        :rtype: int
        """
        used_baskets = [False] * len(baskets)  
        placed_fruits = 0

        for fruit in fruits:
            for i in range(len(baskets)):
                if not used_baskets[i] and baskets[i] >= fruit:
                    used_baskets[i] = True
                    placed_fruits += 1
                    break

        return len(fruits) - placed_fruits

solution = Solution()
print(solution.numOfUnplacedFruits([4, 2, 5], [3, 5, 4]))  
print(solution.numOfUnplacedFruits([3, 6, 1], [6, 4, 7]))

بالنسبة للتحسين، فلديك التعقيد الزمني هو O(n * m) حيث n عدد الفواكه و m عدد السلال، وتستطيع تحسينه من خلال هيكل بيانات مثل Binary Search على السلال غير المستخدمة، ليصبح O(n * log m).

محمد عاطف17 · 15 مارس

وعليكم السلام ورحمة الله وبركاته.

أحسنت الكود الخاص بك ممتاز ويعمل بشكل صحيح دون أى مشاكل ويقوم بإخراج العدد الصحيح للفاكهة التي لم توضع في السلة.

ولكن لاحظ أن المشكلة التي يطلب منك حلها مختلفة عن الحل الخاص بك .

فلاحظ هنا :

بتاريخ 26 دقائق مضت قال Ali Ahmed55:
ach fruit type must be placed in the leftmost available basket

لاحظ أنه لا يجب عليك ترتيب المصفوفات حيث يجب عليك العمل على نفس الترتيب الذي يتم إدخاله . حيث تقوم بالتكرار على قائمة السلال وترى هل هي تكفي الفاكهة الحالية أم لا . وإ ذا كانت تكفي فيمكنك وضعها في تلك السلة .

فلاحظ مثلا المدخلات التالية :

print(solution.numOfUnplacedFruits([4, 10, 5], [10, 5, 5]))

هنا الكود الخاص بك سيخرج ناتج 0 . ولكن يجب أن يخرج 1 . لأنه في أول سلة حجمها 10 إذا يجب وضع ال 4 بها لأنها أول نوع فاكهة .

إذا السلة ذات الحجم 10 تم وضع بها فاكهة . نأتي لنوع الفاكهة الثانية وعددها 10 هنا لن تجد سلة لأن السلة 10 قد تم وضع بها فاكهة أخرى.

لذلك يمكنك محاولة حل المسألة من تلك الطريقة حيث تنشأ قائمة بها السلال التي تم إستخدامها مسبقا وعدم ترتيب القوائم . وإعادة رفع الحل لتقيمه لك.

Ali Ahmed55 · 15 مارس

الف شكراا جدا لحضرتكم

جزاك الله كل خير

مساعد في حل مساله برمجه من LeetCode ؟

السؤال

Ali Ahmed55

3 أجوبة على هذا السؤال

Recommended Posts

Mustafa Suleiman

محمد عاطف17

Ali Ahmed55

انضم إلى النقاش

إعلانات

تابعنا على

الرئيسية

كيف أتعلم؟

تابعنا

دروس ومقالات

أسئلة وأجوبة

كتب

دورات

بطاقات هدية