Dairə ilə məhdudlaşan robot LeetCode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Airbnb Amazon alma Bloomberg Expedia Goldman Sachs google microsoftBaxılıb 22

Problem bəyanat

Dairə ilə məhdudlaşan robot LeetCode Həlli – Sonsuz müstəvidə robot əvvəlcə dayanır (0, 0) və şimala baxır. Qeyd edək ki:

  • The şimal istiqaməti y oxunun müsbət istiqamətidir.
  • The cənub istiqaməti y oxunun mənfi istiqamətidir.
  • The şərq istiqaməti x oxunun müsbət istiqamətidir.
  • The qərb istiqaməti x oxunun mənfi istiqamətidir.

Robot üç təlimatdan birini ala bilər:

  • "G": düz 1 vahid gedin.
  • "L": 90 dərəcə sola dönün (yəni, saat yönünün əksinə).
  • "R": 90 dərəcə sağa dönün (yəni, saat əqrəbi istiqamətində).

Robot yerinə yetirir instructions qaydada verilir və onları əbədi olaraq təkrarlayır.

Qayıtmaq true yalnız və yalnız təyyarədə robotun heç vaxt dairəni tərk etmədiyi bir dairə varsa.

misal

Test işi 1:

Input:

təlimat = "GGLLGG"

Çıxış:

doğru

Izahat

Robot əvvəlcə (0, 0) şimal istiqamətinə baxır.

“G”: bir addım hərəkət edin. Mövqe: (0, 1). İstiqamət: Şimal.

“G”: bir addım hərəkət edin. Mövqe: (0, 2). İstiqamət: Şimal.

“L”: saat yönünün əksinə 90 dərəcə çevirin. Mövqe: (0, 2). İstiqamət: Qərb.

“L”: saat yönünün əksinə 90 dərəcə çevirin. Mövqe: (0, 2). İstiqamət: Cənub.

“G”: bir addım hərəkət edin. Mövqe: (0, 1). İstiqamət: Cənub.

“G”: bir addım hərəkət edin. Mövqe: (0, 0). İstiqamət: Cənub.

Təlimatları təkrarlayaraq robot dövrəyə daxil olur: (0, 0) –> (0, 1) –> (0, 2) –> (0, 1) –> (0, 0). Buna əsaslanaraq, həqiqətə qayıdırıq.

Yanaşma:

Bir neçə nümunə çəkib işlətsəniz problemi başa düşmək bir qədər sadədir.

Siz başa düşəcəksiniz ki, verilmiş təlimatlar ardıcıllığı robotu IFF dairəsi ilə məhdudlaşdıracaq birinci iterasiyanın sonunda:
Hadisə 1: Geri qayıtdı ilkin mövqe (0, 0) OR
Hadisə 2: Geri qayıtmadı ilkin mövqe VƏ ilə qarşılaşmır ilkin istiqamət (yuxarı)

Birinci halda, aydındır ki, təlimatların hər təkrarlanmasından sonra robot 0, 0-a qayıdacaq. Bu, robotun bağlıdır bir dairə ilə (nümunə 1).

İkinci halda, robot həmişə hərəkət edəcək uzaq ilkin mövqedən ƏGƏR onun istiqamət ilkin istiqamətlə eynidir (nümunə 3); əks halda, robot təlimatların bir neçə sonrakı təkrarlanmasında eyni mövqeyə qayıdacaq (nümunə 2).

Aşağıdakı 3 nümunənin hər birində təlimatların 2 təkrarlanması göstərilir.
Nümunələr —- 1: GGLLGG, 2: LLGRGL, 3: LLGRGR

Dairə ilə məhdudlaşan robot LeetCode HəlliPin

Yuxarıda müzakirə edilən iki etibarlı vəziyyətə əsasən, robotun (və ya onun mənşəyə nisbətən məsafə) və onun istiqamət.

Həll həmçinin Java-dan mühüm istifadə edir Math.floorMod Python-un '%' operatoruna bənzər şəkildə işləyən üsul.
Bu vacibdir EDİLMƏDİ Java-nın '%' operatorundan istifadə edin burada kimi işlədiyi üçün qalan və bir deyil doğru modul.

Dairə ilə məhdudlaşan robot kodu

Java Proqramı

class Solution {
    public boolean isRobotBounded(String instructions) {
        // we consider the 4 directions as: 0 = Up, 1 = Right, 2 = Down, 3 = Left
    
        int dirCounter = 0; // Initially facing Up
    // dirCounter will be incremented for a Right turn & decremented for a Left turn
    // so dirCounter 5 indicates that the robot is facing Right (dirCounter mod 4 = 1)
    
        int[] walked = new int[2];
    // This array will maintain the distance travelled on Y and X axes (from origin)
    // walked[0] -> Y distance, walked[1] -> X distance
    
        for(char c : instructions.toCharArray()) {

            if(c == 'G') {
                
        int dir = Math.floorMod(dirCounter, 4);
        // Java's floorMod gives a true MODULO (like Python's %), whereas Java's % operator gives a REMAINDER
        // floorMod for any positive divisor is always positive
        // so, for dirCounter = -5 (i.e. 5 resultant Left), dir = -5 mod 4 = 3 (i.e. Left)
        // Note: -5 % 4 = -1 (not 3)
  
                walked[dir % 2] += (dir == 0 || dir == 1) ? 1 : -1;
        // dir % 2 = 0 for Y axis (i.e. if dir = 0 or 2)
        // dir % 2 = 1 for X axis (i.e. if dir = 1 or 3)
        // if dir = 0 (Up) or 1 (Right), increment walked distance across X or Y
                // else, decrement walked distance along X or Y
                
            }
            else // when c = 'R' or 'L'
      
                dirCounter += c == 'R' ? 1 : -1;
        // Increment or decrement dirCounter based on 'R' or 'L' respectively
    
        }
        
        return (walked[0] == 0 && walked[1] == 0) || Math.floorMod(dirCounter, 4) != 0;
    // Case 1: walked distance along Y and X is 0
    // Case 2: case 1 is false AND final direction is not Up
    }
}

C ++ Proqramı

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int size = instructions.size();
        if (size == 0) return true;
        pair<int,int> pos = {0,0};
        int d = 0; // current direction;

        for (int i = 0; i < size; ++i) {
          if (instructions[i] == 'L') d = (d+1)%4;//change direction
          else if (instructions[i] == 'R') d = (d+3)%4;// change direction
          else {// transport 
      if (d == 0) pos.second++;
      else if (d == 1) pos.first--;
      else if (d == 2) pos.second--;
      else if (d == 3) pos.first++;
          }
        }
        // check position and direction;
        if (d!=0) return true;
        if (d == 0 && pos.first==0 && pos.second == 0) return true; 

        return false;
    }
};

Dairə ilə məhdudlaşan robot üçü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 »