Tam ədədlərin kəsilməsi LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Citadel Facebook google TCSBaxılıb 22

Problem bəyanat

Tam ədədin fasiləsi LeetCode Həlli – Tam ədəd verilir n, cəminə bölün k müsbət tam ədədlər, Harada k >= 2, və həmin tam ədədlərin hasilini maksimuma çatdırın.

Geri dönməliyik əldə edə biləcəyimiz maksimum məhsul.

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Izahat

8-in maksimum hasilini tapmaq üçün 8-i iki şərtin cəminə bölün (artıqlığın qarşısını almaq üçün birinci həddi ikincidən kiçik və ya ona bərabər saxlayın):

1 + 7 --> 1 * 7 = 7
2 + 6 --> 2 * 6 = 12
3 + 5 --> 3 * 5 = 15
4 + 4 --> 4 * 4 = 16

Buradan belə görünür ki, maksimum məhsul 16-dır, lakin biz iki terminin hər birini daha çox terminə bölmək və bütün bunları yoxlamaqdan çəkinmişik. Gəlin 6-nı 3 + 3-ə bölək:

2 + 6 = 2 + 3 + 3 --> 2 * 3 * 3 = 18

doğru cavabla nəticələnir. Ancaq bunu əldə etməyin başqa bir yolu 6 olduğunu bildiyimiz 9-nın əvvəllər hesablanmış maksimum məhsulunu təkrar istifadə etməkdir:

2 * (3 * 3) = 2 * max_product_of_6 = 2 * 9 = 18

Beləliklə, i <= j və i + j = n ilə i və j-nin hər seçimi üçün yoxlayın i * j lakin DA i və j üçün əvvəllər hesablanmış maksimum məhsulların i və j-dən böyük olub olmadığını yoxlayın. n = 1 ilə başlayın və son n-ə qədər qurun. Əvvəllər hesablanmış dəyərləri dp massivində saxlayın.

Kodu

Tam Ədədi Fasilə LeetCode Həlli üçün Java Kodu

class Solution {
    public int integerBreak(int n) {
       int[] dp = new int[n + 1];
       dp[1] = 1;
       for(int i = 2; i <= n; i ++) {
           for(int j = 1; j < i; j ++) {
               dp[i] = Math.max(dp[i], (Math.max(j,dp[j])) * (Math.max(i - j, dp[i - j])));
           }
       }
       return dp[n];
    }
}

Tam Ədədi Fasilə LeetCode Həlli üçün C++ Kodu

class Solution {
public:
    int integerBreak(int n) {
        
        if (n <= 2)
            return 1;

        vector<int> maxArr(n+1, 0);
        maxArr[1] = 0;
        maxArr[2] = 1; // 2=1+1 so maxArr[2] = 1*1
        
        for (int i=3; i<=n; i++) {
            for (int j=1; j<i; j++) {
                maxArr[i] = max(maxArr[i], max(j*(i-j), j*maxArr[i-j]));
            }
        }
        return maxArr[n];
    }
};

Tam Ayı Fasilə LeetCode Həlli üçün Python Kodu

class Solution(object):
    def integerBreak(self, n):
        dp = [None, 1]
        for m in range (2, n + 1):
            j = m - 1
            i = 1
            max_product = 0
            while i <= j:
                max_product = max(max_product, max(i, dp[i]) * max(j, dp[j]))
                j -= 1
                i += 1
            dp.append(max_product)
        return dp[n]

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Hər bir “i” üçün 1-dən “i”yə qədər hesablayırıq, buna görə də zaman mürəkkəbliyi O(n^2) olur.

Kosmik Mürəkkəblik

Bir dp istifadə edirik massiv ölçüsü n beləliklə fəzanın mürəkkəbliyi O(n) olacaq

Referans: https://en.wikipedia.org/wiki/Dynamic_programming

Translate »