Evə çatmaq üçün minimum atlamalar LeetCode Həll

Problem bəyanat

Evə çatmaq üçün minimum sıçrayışlar LeetCode Solution deyir - Müəyyən bir səhvin evi x oxundakı mövqedədir x.

Onlara 0 mövqeyindən oraya çatmağa kömək edin.

Səhv aşağıdakı qaydalara uyğun olaraq sıçrayır:

• Tam olaraq atlaya bilər a vəzifələri irəli (sağda).
• Tam olaraq atlaya bilər b vəzifələri geri (sola).
• Ardıcıl olaraq iki dəfə geriyə atlaya bilməz.
• Heç birinə atlaya bilməz qadağan mövqeləri.

Səhv irəli atlaya bilər Beyond onun evi, amma o atlaya bilmir ilə nömrələnmiş vəzifələrə mənfi tam ədədlər.

Tam ədədlər massivi verilmişdir qadağan, Harada qadağan [i] o deməkdir ki, səhv mövqeyə atlaya bilməz qadağan [i], və tam ədədlər a, bvə x, qayıt bu səhvə çatmaq üçün lazım olan minimum atlama sayı onun evi. Böcəyi mövqeyə salan mümkün atlama ardıcıllığı yoxdursa x, qayıt -1.

Misal:

Test işi 1:

Input:

qadağan = [6, 14, 17]

a = 3

b = 1

x = 13

Çıxış:

7

Explanation:

i) Birinci test işi üçün 0-dan 13-ə keçmək üçün müxtəlif variantlar var. Amma biz 0->3, 3->2, 2->5, 5->8, 8->7, 7-dən hərəkət edə bilərik. ->10, 10->13. 7 addım tələb edir. Bu minimum yol götürə bilərik. Beləliklə, cavab 7-dir.

Yanaşma

Idea:

Burada ilk baxışdan bunun bir olduğunu düşünə bilərik Üst-üstə düşən alt problem. Amma məsələ buradadır ki, biz də geriyə gedirik. Beləliklə, biz sonsuz bir döngəyə düşə bilərik. Beləliklə, biz onu olan bir qrafik kimi düşünə bilərik Arxa kənarlar götürə bilmədiyimiz kimi məhdudiyyətlərlə mənbədən təyinat yerinə keçməli olduğumuz yer Arxa kənarlar ardıcıl olaraq iki dəfə və biz təcrid olunmuş təpə kimi düşünülə bilən müəyyən mövqelərə gedə bilmirik. Əgər yoxdursa çata biləcəyimiz yoldur qayıtmalı olduğumuz mənbədən başlayaraq təyinat -1.       

Mövqe İzləmə: 

Kodu

Evə çatmaq üçün minimum atlamalar üçün Java proqramı LeetCode Həll

class Solution {
    public int minimumJumps(int[] forbidden, int a, int b, int x) {
        int stepCount = 0, furthest = x + a + b;
        Queue<Pair<Integer, Integer>> queue = new LinkedList();
        queue.offer(new Pair(0, 0)); 
        Set<Pair<Integer, Integer>> visited = new HashSet<>(queue);
        for (int pos : forbidden) {
            visited.add(new Pair(0, pos));
            visited.add(new Pair(1, pos));
            furthest = Math.max(furthest, pos + a + b);
        }
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; --size) {
                Pair<Integer, Integer> p = queue.poll();
                int dir = p.getKey(), pos = p.getValue();
                if (pos == x) {
                    return stepCount;
                }
                Pair<Integer, Integer> forward = new Pair<>(0, pos + a), backward = new Pair<>(1, pos - b);
                if (pos + a <= furthest && visited.add(forward)) {
                    queue.offer(forward);
                }
                if (dir == 0 && pos - b >= 0 && visited.add(backward)) {
                    queue.offer(backward);
                }
            }
            ++stepCount;
        }
        return -1;    
    }
}

Evə çatmaq üçün minimum atlamalar üçün C++ proqramı LeetCode Həlli

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        unordered_map<int,int> visited;
        queue<pair<int,int>> positionQueue; 
        for(auto i:forbidden){
            visited[i]=true;
        }
        positionQueue.push({0,0}) ; 
        int stepCount = 0;
        while(!positionQueue.empty()){
            int size = positionQueue.size() ;
            while(size--){
                auto curr = positionQueue.front() ;
                positionQueue.pop() ;
                int num = curr.first;
                if(num == x){
                    return stepCount;
                }
               
                if(visited[num] == true){
                    continue;
                } 
                visited[num]=true;
                if(curr.second == 0 && num-b>=0) {
                    positionQueue.push({(num-b),1});
                }
                if(num <= 2000+b){
                    positionQueue.push({(num+a),0});                 
                }
            }
            stepCount++;
        }
        return -1;
    }
};

LeetCode Həllində Evə çatmaq üçün minimum sıçrayışlar üçün mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Ən çox səhvə çatmaq lazımdır ən uzaq = max(x, qadağan) + a +b çatmaq üçün x. Beləliklə, zamanın mürəkkəbliyi O(max(x, max(qadağan)) + a + b).

Kosmik Mürəkkəblik

Burada hər bir mümkün mövqe üçün mövqeyi saxlamalıyıq. Beləliklə, kosmik mürəkkəblik O(max(x, max(qadağan)) + a + b).

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