عد جميع التكرارات التي تحتوي على منتج أقل من K.  


مستوى الصعوبة سهل
كثيرا ما يطلب في ByteDance عاصمة واحدة CodeNation Databricks اكسبيديا ياندكس
مجموعة البرمجة الديناميكية

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

مثال  

عد جميع التكرارات التي تحتوي على منتج أقل من K.دبوس

a[] = {1, 2, 3, 4, 5}
k = 8
Number of subsequences less than 8: 11

تفسير

هناك 11 نتيجة لاحقة لها منتج أقل من المعطى k (= 8). يتم عرض النتائج اللاحقة في الصورة أعلاه.

الرسالة  

لقد زودتنا المشكلة بسلسلة من الأعداد الصحيحة ، وعددًا صحيحًا K. ثم يُطلب منا إيجاد عدد التكرارات اللاحقة التي تحتوي على منتج أقل من K. لذلك ، كلما تعاملنا مع المتتاليات اللاحقة أو المجموعات الفرعية أو المصفوفات الفرعية. النهج الساذج هو دائمًا إنشاء هذه التسلسلات ثم التحقق مما إذا كان التسلسل الذي تم إنشاؤه يلبي شروطنا أم لا؟

هذا الحل الساذج سيتجاوز بالتأكيد الحد الزمني لدينا. لذلك لحل المشكلة في ظل ضيق الوقت المحدد. نحن مطالبون باستخدام البرمجة الديناميكية. سننتقل هنا إلى مصفوفة الإدخال. أثناء الاجتياز ، سنقوم بملء جدول DP في نفس الوقت. لدينا حالتان لمسألة DP هذه ، الأولى هي المنتج حتى الآن والثانية هي فهرس مصفوفة الإدخال. نبدأ بالمنتج ونتحقق مما إذا كان بإمكاننا الحصول على النتيجة المطلوبة بالأرقام / العناصر من مصفوفة الإدخال.

انظر أيضا
الحد الأقصى 69 رقم حل Leetcode

تشير خلية صفيف dp dp [i] [j] إلى عدد التكرارات اللاحقة التي تحتوي على منتج أقل من i ويتم تشكيلها باستخدام عناصر j الأولى من الإدخال. لذلك من أجل إيجاد dp [i] [j] ، فإننا نعتمد على dp [i / a [j]] [j] و dp [i] [j-1]. لذلك إذا كان a [i]> i ، فإن أخذ هذا العنصر إلى ما يليه سيعني أن [i] نفسه أكبر من K. وبالتالي لن يتم النظر في هذا العنصر. هذه هي الطريقة التي نحسب بها كل التكرارات اللاحقة التي تحتوي على منتج أقل من K.

رمز  

كود C ++ لحساب جميع التكرارات اللاحقة التي تحتوي على منتج أقل من K.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a[] = {1, 2, 3, 4, 5};
    int n = (sizeof a)/(sizeof a[0]);
    int k = 8;
    int dp[k][n+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1;i<k;i++){
        for (int j=1;j<=n;j++){
            dp[i][j] = dp[i][j-1];
            if (a[j-1] <= i && a[j-1] > 0)
                dp[i][j] += dp[i/a[j-1]][j-1] + 1;
        }
    }

    cout<<dp[k-1][n];
}
11

كود Java لحساب جميع التكرارات اللاحقة التي تحتوي على منتج أقل من K.

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int a[] = {1, 2, 3, 4, 5};
      int n = a.length;
      int k = 8;
      int dp[][] = new int[k][n+1];
      for(int i=0;i<k;i++)
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = 0;

      for (int i=1;i<k;i++){
          for (int j=1;j<=n;j++){
              dp[i][j] = dp[i][j-1];
              if (a[j-1] <= i && a[j-1] > 0)
                  dp[i][j] += dp[i/a[j-1]][j-1] + 1;
          }
      }
    System.out.println(dp[k-1][n]);
  }
}
11

تحليل التعقيد  

تعقيد الوقت

O (N * K) ، لأن هناك حالتين ، الأولى هي الفهرس لمصفوفة الإدخال والأخرى هي ناتج حد التتابع. لديهم حد أعلى N و K ، وبالتالي فإن تعقيد الوقت متعدد الحدود.

تعقيد الفضاء

O (N * K) ، لأننا أنشأنا جدولًا ثنائي الأبعاد DP بخلايا N * K. وبالتالي فإن تعقيد الفضاء هو أيضًا متعدد الحدود.