K Ölçmə Əməliyyatları LeetCode Həlli ilə Boş Verilən Minimum Ümumi Məkan

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Media.netBaxılıb 12

Problem bəyanat

K Ölçmə Əməliyyatları ilə Boşa Verilən Minimum Ümumi Məkan LeetCode Həlli – Siz hazırda a dinamik serial. Sizə verilir 0 indeksli tam sıra nums, Harada nums[i] zamanda massivdə olacaq elementlərin sayıdır i. Bundan əlavə, sizə tam ədəd verilir kKi, maksimum neçə dəfə edə bilərsiniz boyutlandır massiv (to hər ölçüsü).

Massivin vaxtında ölçüsü tsizet, ən azı olmalıdır nums[t] çünki bütün elementləri saxlamaq üçün massivdə kifayət qədər yer olmalıdır. The boş yer vaxtında t kimi müəyyən edilir sizet - nums[t]Və ümumi boş yerə sərf olunur məbləğ boş yerə hər dəfə boş yerə t hara 0 <= t < nums.length.

Qayıtmaq bu minimum ümumi boş yer əgər siz ən çox massivin ölçüsünü dəyişə bilsəniz k dəfə.

Qeyd: Massiv ola bilər istənilən ölçüdə başlanğıcda və edir yox ölçüsünü dəyişmə əməliyyatlarının sayına hesablayın.

K Ölçmə Əməliyyatları LeetCode Həlli ilə Boş Verilən Minimum Ümumi MəkanPin

misal

Test işi 1:

Input:

ədədlər= [10, 20]

k = 0

Çıxış:

10

Test işi 2:

ədədlər= [1,2,3]

k = 0

Çıxış:

10

K ölçüsünü dəyişdirmə əməliyyatları ilə sərf olunan minimum ümumi yerin izahı LeetCode Həlli:

i) 1-ci sınaq işi üçün ilkin ölçüsü 20 olaraq təyin edə bilərik. Boş yerə sərf olunan ümumi boşluq (20 – 10) + (20 – 20) = 10-dur.

ii) 2-ci sınaq işi üçün biz ilkin ölçüsü 20-yə təyin edə və 30-ci anda 2-a dəyişə bilərik. Boş yerə sərf olunan ümumi boşluq (20 – 10) + (20 – 20) + (30 – 30) = 10-dur.

Yanaşma

Fikir

  1. Qoy dp(i, k) ölçüsünü dəyişdirə bilsək, boş yerə sərf olunan minimum yeri qeyd edin k dəfə nums[i..n-1].
  2. İdeya ondan ibarətdir ki, biz a istifadə etdikdə boyutlandır bütün elementləri uyğunlaşdırmaq imkanı nums[i..j], seçməliyik size maksimum sayına bərabərdir nums[i..j] Beləliklə, boş yerə sərf olunan ümumi yerdir max(nums[i...j]) * (j-i+1) - sum(nums[i..j).

K Ölçmə Əməliyyatları ilə Boşa Verilən Minimum Ümumi Məkan üçün Kod LeetCode Həlli

Java Proqramı

class Solution {
    int n, INF = (int) (200 * 1e6);
    Integer[][] memo = new Integer[200][200];
    public int minSpaceWastedKResizing(int[] nums, int k) {
        n = nums.length;
        return dp(nums, 0, k);
    }
    int dp(int[] nums, int i, int k) {
        if (i == n) return 0;
        if (k == -1) return INF;
        if (memo[i][k] != null) return memo[i][k];
        int ans = INF, maxNum = nums[i], totalSum = 0;
        for (int j = i; j < n; ++j) {
            maxNum = Math.max(maxNum, nums[j]);
            totalSum += nums[j];
            int wasted = maxNum * (j - i + 1) - totalSum;
            ans = Math.min(ans, dp(nums, j + 1, k - 1) + wasted);
        }
        return memo[i][k] = ans;
    }
}

C ++ Proqramı

class Solution {
public:
    int n, INF = 200 * 1e6;
    int memo[200][200] = {};
    int minSpaceWastedKResizing(vector<int> &nums, int k) {
        memset(memo, -1, sizeof(memo));
        n = nums.size();
        return dp(nums, 0, k);
    }
    int dp(vector<int> &nums, int i, int k) {
        if (i == n) return 0;
        if (k == -1) return INF;
        if (memo[i][k] != -1) return memo[i][k];
        int ans = INF, maxNum = nums[i], totalSum = 0;
        for (int j = i; j < n; ++j) {
            maxNum = max(maxNum, nums[j]);
            totalSum += nums[j];
            int wasted = maxNum * (j - i + 1) - totalSum;
            ans = min(ans, dp(nums, j + 1, k - 1) + wasted);
        }
        return memo[i][k] = ans;
    }
};

Python proqramı

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n, INF = len(nums), 200 * 1e6

        @lru_cache(None)
        def dp(i, k):
            if i == n: return 0
            if k == -1: return INF
            ans = INF
            maxNum = nums[i]
            totalSum = 0
            for j in range(i, n):
                maxNum = max(maxNum, nums[j])
                totalSum += nums[j]
                wasted = maxNum * (j - i + 1) - totalSum
                ans = min(ans, dp(j + 1, k - 1) + wasted)
            return ans

        return dp(0, k)

LeetCode Həlli K-dən az olan Subarray Məhsulu üçün mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O(N^2*K), Harada N <= 200 massivdəki elementlərin sayıdır nömrə, K < N maksimum sayıdır boyutlandırma istifadə edə biləcəyimiz variantlar. Cəmi var N*K dp dövlətlər, onlar dp[0][0], dp[0][1].., dp[N][K]. Hər bir dövlətə bir döngə lazımdır O (N) nəticəni hesablamaq üçün. Beləliklə, ümumi zaman mürəkkəbliyi O(N^2*K).

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O(N*K).

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

 

Şərh yaz

Translate »