Frog Jump Leetcode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Facebook google microsoft Kahin Salesforce Snapchat Yahoo
Geyim Dinamik proqramlaşdırma tiktokBaxılıb 77

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 Frog Jump LeetCode Həlli - "Qurbağa Jump" siyahısı verildiyini bildirir daş (vəzifələr) sıralanır artan sifariş, qurbağanın üzərinə enərək çayı keçə biləcəyini müəyyən edin son daş (massilin son indeksi). Əvvəlcə qurbağa birinci daşın üzərindədir və ilk atlamada qurbağa 1 vahid uzunluğa tullanır.

Qeyd edək ki, əgər qurbağanın son sıçrayışı olubsa k vahidlər, onda onun növbəti atlama ya olmalıdır k-1, kvə ya k + 1. Həmçinin, qurbağa yalnız irəli istiqamətdə tullana bilər.

Misal:

Input:  stones = [0,1,3,5,6,8,12,17]
Output: true

Explanation:

  • Əvvəlcə qurbağa 1-ci daşa çatmaq üçün 2 vahid tullanır.
  • Sonra qurbağa 2-cü daşa çatmaq üçün 3 vahid tullanır.
  • Sonra qurbağa 2-cü daşa çatmaq üçün 4 vahid tullanır.
  • Sonra qurbağa 3-cı daşa çatmaq üçün 6 vahid tullanır.
  • Sonra qurbağa 4-cı daşa çatmaq üçün 7 vahid tullanır.
  • Sonra qurbağa 5-cı daşa çatmaq üçün 8 vahid tullanır.
Input:  stones = [0,1,2,3,4,8,9,11]
Output: false

Explanation:

  • Son daşa çatmaq üçün heç bir yol yoxdur, çünki 5 və 6-cı daşlar arasındakı boşluq çox böyükdür.

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir dinamik proqramlaşdırma.
  2. kimi dövlət hesab edin dp[i][j] = doğrudur, ith daşa çatmaq üçün hər hansı bir yol varsa son atlama j vahidləri idi.
  3. Baza halını dp[0][0] = true kimi təyin edək.
  4. [1,n-1]-dən i-ni təkrarlayın və hər i üçün [0,i-1]-dən j-i təkrarlayın və gəlin müəyyən edək fərq = daşlar[i] – daşlar[j] qurbağanın j-ci daşdan i-ci daşa çatmaq üçün etdiyi tullanmadır Əgər mümkünsə.
  5. Qurbağa yalnız o halda i-ci daşa çata bilər hər aşağıdakı şərtlər doğrudur:
    1. dp[j][fərq] doğrudur.
    2. dp[j][fərq+1] doğrudur.
    3. dp[j][fərq-1] doğrudur.
  6. Cavabımız olacaq doğru j-nin [1,n-0]-dən dəyişdiyi dp[n-1][j] mövqeyində hər hansı həqiqi dəyər varsa.

Kodu

Frog Jump Leetcode C++ Həlli:

class Solution {
public:
    bool canCross(vector<int>& stones) {
        int n = stones.size();
        vector<vector<bool>> dp(n,vector<bool>(n));
        dp[0][0] = true;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                int diff = stones[i] - stones[j];
                if(diff>=n){
                    continue;
                }
                if(dp[j][diff] or (diff-1>=0 and dp[j][diff-1]) or (diff+1<n and dp[j][diff+1])){
                    dp[i][diff] = true;
                }
            }
        }
        for(int j=0;j<n;j++){
            if(dp[n-1][j]){
                return true;
            }
        }
        return false;
    }
};

Frog Jump Leetcode Java Həlli:

class Solution {
    public boolean canCross(int[] stones) {
        int n = stones.length;
        boolean[][] dp = new boolean[n][n];
        dp[0][0] = true;
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                int diff = stones[i] - stones[j];
                if(diff>=n){
                    continue;
                }
                if(dp[j][diff] || (diff+1<n && dp[j][diff+1]) || (diff-1>=0 && dp[j][diff-1])){
                    dp[i][diff] = true;
                }
            }
        }
        for(int j=0;j<n;j++){
            if(dp[n-1][j]){
                return true;
            }
        }
        return false;
    }
}

Frog Jump 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 ^ 2) bütün giriş massivindən N*(N-1)/2 dəfə keçdiyimiz üçün.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N ^ 2) çünki biz N*N ölçülü boolean matrisini yaradırıq.

Crack Sistemi Dizayn Müsahibələri
Translate »