Mükəmməl Kvadratlar LeetCode Həlli

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The Mükəmməl Kvadratlar LeetCode Həlli - “Mükəmməl Kvadratlar” n tam ədədinin verildiyini bildirir və siz onu qaytarmalısınız minimum sayı cəmi n-ə bərabər olan mükəmməl kvadratlar. Qeyd edək ki, eyni mükəmməl kvadrat istifadə edilə bilər dəfələrlə.

Misal:

Pin

Input: n = 12

Output: 3

Explanation:

• 4 cəmini almaq üçün üç dəfə 12-dən istifadə edə bilərik, buna görə də cavab minimum olan 3-dür.
• Qeyd edək ki, eyni mükəmməl kvadrat bir neçə dəfə istifadə edilə bilər.

Input: n = 13

Output: 2

Explanation:

• Biz 4 cəmini almaq üçün bir dəfə 9 və bir dəfə 13-dan istifadə edə bilərik, buna görə də cavab minimum mümkün olan 2-dir.

Yanaşma

Idea:

1. Əsas fikir istifadə etməkdir dinamik proqramlaşdırma bu problemi səmərəli həll etmək.
2. dp-nin vəziyyətini nəzərə alın, dp[i] = i-yə cəmlənən mükəmməl kvadratların minimum sayı.
3. Hər biri üçün [1,n] diapazonunda i və hər mükəmməl kvadrat üçün j i-dən kiçik və ya bərabər, dp[ij*j] varsa, yeniləmə dp[i] = min(dp[i],1+dp[ij*j]), çünki j*j-dən mükəmməl kvadrat kimi istifadə etməklə (ij*j) ədədindən i vəziyyətinə çata bilərik.
4. Cavabımız olacaq dp[n], cəmi n olan mükəmməl kvadratların minimum sayı.

Kodu

Mükəmməl Kvadratlar Leetcode C++ Həlli:

class Solution {
public:
    int numSquares(int n) {
        vector<int> perfectSquares;
        for(int i=1;i*i<=n;i++){
            perfectSquares.push_back(i*i);
        }
        vector<int> dp(n+1,INT_MAX);
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            for(auto& j:perfectSquares){
                if(j<=i && dp[i-j]!=INT_MAX){
                    dp[i] = min(dp[i],1+dp[i-j]);
                }
            }
        }
        return dp[n];
    }
};

Mükəmməl kvadratlar Leetcode Java Həlli:

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i=1;i<=n;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j*j<=i;j++){
                int square_integer = j*j;
                if(dp[i-square_integer]!=Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i],1+dp[i-square_integer]);
                }
            }
        }
        return dp[n];
    }
}

Mükəmməl Kvadratlar Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O(n*sqrt(n)) çünki bütün mükəmməl kvadratları tapmaq üçün ən pis halda xarici döngə n dəfə, daxili dövrə isə sqrt(n) vaxtını işlədir.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (n) çünki biz n ölçülü xətti dp vektoru edirik.