Minimum Sideway Jumps LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Pony.aiBaxılıb 22

Problem bəyanat

Minimum Sideway Jumps LeetCode Həlli – Bir var 3 zolaqlı yol uzunluğu n olan ibarətdir n + 1 xal -dan etiketlənmişdir 0 üçün n. Qurbağa başlayır nöqtədə 0 ci ikinci zolaq və nöqtəyə keçmək istəyir n. Bununla belə, yolda maneələr ola bilər.

Sizə massiv verilir obstacles uzunluğu n + 1 harada obstacles[i] (0 ilə 3 arasında dəyişir) zolaqdakı maneəni təsvir edir obstacles[i] nöqtədə i. Əgər obstacles[i] == 0, nöqtədə heç bir maneə yoxdur i. Olacaq ən çox biri hər nöqtədə 3 zolaqda maneə.

  • Məsələn, əgər obstacles[2] == 1, onda 1-ci nöqtədə 2-ci zolaqda maneə var.

Qurbağa yalnız nöqtədən hərəkət edə bilər i işarə etmək i + 1 nöqtədə zolaqda maneə olmadıqda eyni zolaqda i + 1. Maneələrin qarşısını almaq üçün qurbağa da a yerinə yetirə bilər yan tullanma atlamağa digər zolaqda (bitişik olmasa belə). eyni yeni zolaqda heç bir maneə olmadıqda nöqtə.

  • Məsələn, qurbağa 3-cü nöqtədəki 3-cü zolağından 1-cü nöqtədəki 3-ci zolağa tullana bilər.

Qayıtmaq bu minimum sayı yan atlamalar qurbağa çatmalıdır istənilən zolaq zolaqdan başlayaraq n nöqtəsində 2 0 nöqtəsində.

Qeyd: Xallarda heç bir maneə olmayacaq 0 və n.

Minimum Sideway Jumps LeetCode HəlliPin

Input: obstacles = [0,1,2,3,0]
Output: 2 
Explanation: The optimal solution is shown by the arrows above. There are 2 side jumps (red arrows).
Note that the frog can jump over obstacles only when making side jumps (as shown at point 2).

Izahat

dp[0] = 1-ci zolağa çatmaq üçün minimum tullanma
dp[1] = 2-ci zolağa çatmaq üçün minimum tullanma
dp[2] = 3-ci zolağa çatmaq üçün minimum tullanma
Bir daşla qarşılaşsanız, onu qoyun dp[i] sonsuzluğa.
nəticə bərabərdir min(dp)

Kodu

Minimum yandan tullanmalar üçün C++ kodu

class Solution {
public:
    int minSideJumps(vector<int>& A) {
        int dp[] = {1, 0, 1};
        for (int a: A) {
            if (a > 0)
                dp[a - 1] = 1e6;
            for (int i = 0; i < 3; ++i)
                if (a != i + 1)
                    dp[i] = min(dp[i], min(dp[(i + 1) % 3], dp[(i + 2) % 3]) + 1);
        }
        return min(dp[0], min(dp[1], dp[2]));
    }
};

Minimum yan tullanmalar üçün Java kodu

class Solution {
    public int minSideJumps(int[] A) {
        int[] dp = new int[]{1, 0, 1};
        for (int a: A) {
            if (a > 0)
                dp[a - 1] = 1000000;
            for (int i = 0; i < 3; ++i)
                if (a != i + 1)
                    dp[i] = Math.min(dp[i], Math.min(dp[(i + 1) % 3], dp[(i + 2) % 3]) + 1);
        }
        return Math.min(dp[0], Math.min(dp[1], dp[2]));
    }
}

Minimum yan tullanmalar üçün Python kodu

class Solution:
    def minSideJumps(self, A):
        dp = [1, 0, 1]
        for a in A:
            if a:
                dp[a - 1] = float('inf')
            for i in range(3):
                if a != i + 1:
                    dp[i] = min(dp[i], dp[(i + 1) % 3] + 1, dp[(i + 2) % 3] + 1)
        return min(dp)

Minimum Sideway Jumps üçün Mürəkkəblik Təhlili LeetCode Həlli

Zamanın mürəkkəbliyi

O (N)

Kosmik Mürəkkəblik

O (1)

Translate »