Yol Keçidi Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon
alqoritmlər kodlaşdırma Hashing müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions SimBaxılıb 19

Problem bəyanat

Yol keçidi problemində a_sifli bir obyektin bir istiqamətdə 1 vahid hərəkətini göstərən yalnız dörd fərqli simvol olan 'N', 'S', 'E' və ya 'W' verilir. Obyekt əvvəlcə mənşəlidir (0,0). Verilən sətirdə göstərilən yol boyunca gedən bir nöqtədə cismin yolunu keçib keçməyəcəyini öyrənməliyik.

misal

path = "NES"
false

Explanation:

Yol Keçidi Leetcode Həlli

Diqqət yetirin ki, yol heç bir nöqtəni bir dəfədən çox keçmir.

path = "NESWW"
true

Explanation:

Yol Keçidi Leetcode HəlliPin

Yolun mənşəyi iki dəfə ziyarət etdiyinə diqqət yetirin.

Yanaşma

Problem ifadəsindən aydın olur ki, obyektin yolunda bir koordinat (x, y) meydana gəlirsə, hər dəfə 1 vahidlə hərəkət etdiyi üçün cismin müəyyən sayda hərəkətdən sonra mövqeyi olmalıdır.
Yəni əvvəllər ziyarət edilən bir nöqtə öz yoluna gəlirsə, şübhəsiz ki, yolu keçib gedir. Beləliklə, bu cür məqamı tapan kimi həqiqətə qayıda bilərik.

İndi haradan bilirik ki, əvvəllər bir məqam ziyarət edilmişdir. Bunun üçün a Hash Set və yolundakı bütün nöqtələri saxlamağa davam et. Hər hansı bir zamanda obyektin gedəcəyi növbəti nöqtənin artıq çoxluqda olduğunu tapsaq, doğru qayıdırıq. Bu olmazsa yolu tamamladıqdan sonra yalnış qayıdırıq.

Alqoritm:

  1. Düymənin koordinatını (x, y) təmsil etdiyi bir hash dəsti yaradın. Bunun üçün cüt istifadə edə bilərik açar kimi Və ya iki tam ədədi misilsiz şəkildə göstərməli olan sadə bir simli istifadə edə bilərik. Ex- “2_3” koordinatı (2,3) təmsil etmək üçün.
  2. İki dəyişən x və y yaradın. Onları başlanğıc koordinatı (0,0) ilə başladın və dəstə daxil edin.
  3. Göstərilən hərəkətləri təkrarlamaq üçün bir döngə işlədin. X və ya y dəyərini cari hərəkətə görə aşağıdakı şəkildə artırın və ya azalın:
    'N' yeni koordinatın (x, y + 1) olduğu deməkdir
    'E' yeni koordinatın (x + 1, y) olduğu deməkdir
    'S' yeni koordinatın (x, y-1) olduğu deməkdir
    'W' yeni koordinatın (x-1, y) olduğu deməkdir
  4. Koordinatın (x, y) çoxluqda olub olmadığını yoxlayın. Mövcud olduqda doğru qayıdın, Else bu koordinatı setə əlavə edin və davam edin.
  5. Döngə başa çatdıqdan sonra heç bir keçid tapılmadığı təqdirdə qayıdan səhvdir.

Həyata keçirilməsi

Yol Keçidi Leetcode Həlli üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;

bool isPathCrossing(string path) 
{
    set< pair<int,int> > s;
    int x=0,y=0;
    s.insert({x,y});

    for(char c: path)
    {
        if(c=='N') y++;
        if(c=='E') x++;
        if(c=='S')  y--;
        if(c=='W')  x--;

        if(s.count({x,y}))
        return true;

        s.insert({x,y});
    }

    return false;
}

int main() 
{
    string path = "NESWW";
    if(isPathCrossing(path))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

Yol Keçidi Leetcode Həlli üçün Java Proqramı

import java.lang.*;
import java.util.*;

class PathCrossing
{  
    public static boolean isPathCrossing(String path) 
    {
        Set<String> set=new HashSet<String>();

        int x=0,y=0;
        String key= x + "_" + y;

        set.add(key);

        for(int i=0;i<path.length();i++)
        {
            char c= path.charAt(i);
            if(c=='N') y++;
            if(c=='E') x++;
            if(c=='S') y--;
            if(c=='W') x--;

            key= x + "_" + y;
            if(set.contains(key)) return true;

            set.add(key);
        }

        return false;
    }
    
    public static void main(String args[])
    {
       String path = "NESWW";
  
       System.out.println(isPathCrossing(path));
        
    }
}
true

Yol Keçidi Leetcode Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N): burada N verilən sətrin ölçüsüdür. Sıradakı hər bir simvolu yalnız bir dəfə ziyarət etdiyimiz üçün zamanın mürəkkəbliyi O (N) -dir.

Kosmik Mürəkkəblik 

O (N): Ziyarət olunan koordinatları bir dəstdə saxlamaq üçün istifadə etdiyimiz əlavə yaddaş.

Şərh yaz

Translate »
1