פתרון Leetcode חוצה שבילים


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית
חבטות מחרוזת

הצהרת בעיה

בבעיית מעבר שבילים מחרוזת ניתן בהן רק ארבע תווים שונים 'N', 'S', 'E' או 'W' המציגים את תנועת האובייקט בכיוון אחד בכל פעם על ידי יחידה אחת. ראשית האובייקט במקורו (1). עלינו לברר אם האובייקט יחצה את דרכו בנקודה כלשהי בדרך בשביל שצוין במחרוזת הנתונה.

דוגמה

path = "NES"
false

הסבר:

פתרון Leetcode חוצה שבילים

שימו לב שהשביל לא חוצה אף נקודה יותר מפעם אחת.

path = "NESWW"
true

הסבר:

פתרון Leetcode חוצה שבילים

שימו לב שהדרך מבקרת את המקור פעמיים.

גישה

מהצהרת הבעיה ברור שאם מתרחשת קואורדינטה (x, y) בנתיב האובייקט, אז זה חייב להיות המיקום של האובייקט לאחר מספר מהלכים מסוים שכן הוא נע עם יחידה אחת בכל פעם.
אז אם נקודה באה בדרכה שפעם ביקרו בה בעבר, אז היא בוודאי עוברת את הנתיב. כדי שנוכל לחזור נכון ברגע שמצאנו נקודה מסוג זה.

עכשיו איך נדע כי נקודה ביקרה בעבר. לשם כך אנו יכולים להשתמש ב- סט האש והמשיכו לאחסן את כל הנקודות בדרכו. בכל עת אם גילינו שהנקודה הבאה אליה הולך אובייקט כבר קיימת בקבוצה, אנו מחזירים נכון. לאחר השלמת הנתיב אם זה לא קורה, אנו מחזירים שקר.

אלגוריתם:

  1. צור ערכת מפתחות hash, כאשר המפתח מייצג קואורדינטות (x, y). לשם כך אנו יכולים להשתמש בזוג כמפתח או שאנחנו יכולים להשתמש במחרוזת פשוטה שאמורה לייצג שני מספרים שלמים באופן ייחודי. Ex- "2_3" לייצוג הקואורדינטות (2,3).
  2. צור שני משתנים x ו- y. ראשית אותם באמצעות קואורדינטת המקור (0,0) והכנסו לסט.
  3. הפעל לולאה לאיתור המהלכים שצוינו. הגדל או הקטן את הערך של x או y בהתאם למהלך הנוכחי כדלקמן:
    'N' פירושו הקואורדינטה החדשה היא (x, y + 1)
    'E' פירושו הקואורדינטה החדשה היא (x + 1, y)
    'S' פירושו הקואורדינטה החדשה היא (x, y-1)
    'W' פירושו הקואורדינטה החדשה היא (x-1, y)
  4. בדוק אם הקואורדינטה (x, y) קיימת בערכה או לא. אם קיים אז חזור נכון, אחר הוסף את הקואורדינטה הזו לסט והמשיך.
  5. לאחר השלמת הלולאה אם ​​לא נמצא מעבר החזרה כוזב.

יישום

תוכנית C ++ לפתרון Leetcode חוצה שבילים

#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

תוכנית Java לפתרון Leetcode חוצה שבילים

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

ניתוח מורכבות לפתרון Leetcode חוצה שבילים

מורכבות זמן

O (N): כאשר N הוא גודל המחרוזת הנתונה. כאשר אנו מבקרים בכל תו במחרוזת רק פעם אחת, לכן מורכבות הזמן היא O (N).

מורכבות בחלל 

O (N): זיכרון נוסף בו אנו משתמשים כדי לאחסן את הקואורדינטות שביקרתם בערכה.