Race Car LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur google microsoftBaxılıb 79

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

Race Car LeetCode Həll - Avtomobiliniz mövqedən başlayır 0 və sürət +1 sonsuz ədədlər xəttində. Avtomobiliniz mənfi mövqelərə düşə bilər. Avtomobiliniz təlimatlar ardıcıllığına uyğun olaraq avtomatik hərəkət edir 'A' (sürətləndirmək) və 'R' (əks):

  • Təlimat alanda 'A', avtomobiliniz aşağıdakıları edir:
    • position += speed
    • speed *= 2
  • Təlimat alanda 'R', avtomobiliniz aşağıdakıları edir:
    • Sürətiniz müsbətdirsə speed = -1
    • əksinə speed = 1

    Mövqeyiniz eyni qalır.

Məsələn, əmrlərdən sonra "AAR", avtomobiliniz mövqelərə gedir 0 --> 1 --> 3 --> 3, və sürətiniz gedir 1 --> 2 --> 4 --> -1.

Hədəf mövqe verilir target, qayıt oraya çatmaq üçün təlimatların ən qısa ardıcıllığının uzunluğu.

Input: target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0 --> 1 --> 3.

Izahat

Bəli BFS həll yolu sadədir: yarışdan sonra yarış avtomobilinin bütün mümkün mövqelərini izləyə bilərik n göstərişlər (n = 0, 1, 2, 3, 4, ...) və ən kiçikini qaytarın n hədəf mövqeyə çatmaq üçün. Sadəlövh BFS çalışacaq O(2^n) çünki hər mövqe üçün bizim iki seçimimiz var: ya sürətləndirmək, ya da geriyə. Əlavə müşahidələr göstərir ki, aralıq dövlətlər arasında üst-üstə düşə bilər, ona görə də biz ziyarət edilmiş dövlətləri yadda saxlamalıyıq (hər ştat iki tam ədədlə xarakterizə olunur: avtomobilin mövqeyi və avtomobilin sürəti). Bununla belə, unikal vəziyyətlərin ümumi sayı hələ də böyük hədəf mövqeləri üçün partlayır (çünki mövqe və sürət qeyri-məhdud böyüyə bilər), ona görə də axtarış məkanının daha da budamasına ehtiyacımız var.

Race Car LeetCode HəlliPin

Kodu

Yarış avtomobili üçün C++ kodu

class CarAttributes{
private:
    int position,speed;

public:
    CarAttributes(int position,int speed)
    {
        this->position = position;
        this->speed = speed;
    }

    void setPosition(int position)
    {
        this->position = position;
    }

    void setSpeed(int speed)
    {
        this->speed = speed;
    }

    int getPosition()
    {
        return position;
    }

    int getSpeed()
    {
        return speed;
    }
    
};


class Solution {
    int target;
    
    bool isPositionNotFarFromTarget(int position,int target)
    {
        return abs(target - position) < target;
    }
    
    bool isValidInstruction(int position,unordered_set<string> &visSet,string &key,int target)
    {
        return !visSet.count(key) and isPositionNotFarFromTarget(position,target);
    }
    
    int getMinimumNumberOfInstructions()
    {
        int minimumNumberOfInstructions = 0;
        queue<CarAttributes> bfsQueue;
        unordered_set<string> visSet;
        string key = to_string(0) + "," + to_string(1);
        visSet.insert(key);
        bfsQueue.push(CarAttributes(0,1));
        
        // lambda function to deal with repititive work.
        auto moveToNextPos = [&](int nextPosition,int nextSpeed,CarAttributes &carAttribute,string &key){
            visSet.insert(key);
            carAttribute.setPosition(nextPosition);
            carAttribute.setSpeed(nextSpeed);
            bfsQueue.push(carAttribute);
        };
        
        while(!bfsQueue.empty())
        {
            int size = (int)bfsQueue.size();
            while(size--)
            {
                CarAttributes front = bfsQueue.front();
                bfsQueue.pop();
                int currPos = front.getPosition();
                int currSpd = front.getSpeed();

                if(currPos == target)
                return minimumNumberOfInstructions;

                // Explore option : "A" 
                int nextPos = currPos + currSpd;
                int nextSpd = currSpd * 2;
                key = to_string(nextPos) + "," + to_string(nextSpd);
                if(isValidInstruction(nextPos,visSet,key,target))
                {
                    moveToNextPos(nextPos,nextSpd,front,key);
                }
                
                // Explore option : "R"
                nextPos = currPos;
                nextSpd = currSpd < 0 ? 1 : -1;
                key = to_string(nextPos) + "," + to_string(nextSpd);
                if(isValidInstruction(nextPos,visSet,key,target))
                {
                     moveToNextPos(nextPos,nextSpd,front,key);
                }

            }
            minimumNumberOfInstructions += 1;
        }
        return -1;
    }

public:
    int racecar(int target) 
    {
        this->target = target;
        return getMinimumNumberOfInstructions();
    }
};

Yarış avtomobili üçün Java kodu

    class CarInfo{
        int pos, speed;
        public CarInfo(int p, int s) {
            pos = p;
            speed = s;
        }
    }
class Solution {

    public int racecar(int target) {

        Set<String> visited = new HashSet<>();
        String begin = 0 + "/" + 1;
        visited.add(begin);
        Queue<CarInfo> queue = new LinkedList<>();
        queue.add(new CarInfo(0,1));
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                CarInfo cur = queue.poll();
                if (cur.pos == target) return level;
                String s1 = (cur.pos + cur.speed) + "/" + (cur.speed * 2);
                String s2 = cur.pos + "/" + (cur.speed > 0 ? -1 : 1);
                if (Math.abs(cur.pos + cur.speed - target) < target && !visited.contains(s1)) {
                    visited.add(s1);
                    queue.add(new CarInfo(cur.pos + cur.speed, cur.speed * 2));
                }
                if (Math.abs(cur.pos - target) < target && !visited.contains(s2)) {
                    visited.add(s2);
                    queue.add(new CarInfo(cur.pos, cur.speed > 0 ? -1 : 1));
                }
            }
            
            level++;
        }
        return -1;

    }
}

Yarış avtomobili üçün Python kodu

class Solution:
    def racecar(self, target: int) -> int:
        
        #1. Initialize double ended queue as 0 moves, 0 position, +1 velocity
        queue = collections.deque([(0, 0, 1)])
        while queue:
            
            # (moves) moves, (pos) position, (vel) velocity)
            moves, pos, vel = queue.popleft()

            if pos == target:
                return moves
            
            #2. Always consider moving the car in the direction it is already going
            queue.append((moves + 1, pos + vel, 2 * vel))
            
            #3. Only consider changing the direction of the car if one of the following conditions is true
            #   i.  The car is driving away from the target.
            #   ii. The car will pass the target in the next move.  
            if (pos + vel > target and vel > 0) or (pos + vel < target and vel < 0):
                queue.append((moves + 1, pos, -vel / abs(vel)))

Race Car LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi:

BFS keçid O(V + E) alır

Kosmik Mürəkkəblik

Növbə üçün tələb olunan yer: O(E)

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