د لیټکوډ حل حل کول


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon
ځورول تار

ستونزه بیان

د لارې په اوږدو کې ستونزې a_string ورکړل شوی په کوم کې چې دلته یوازې څلور مختلف حرفونه 'N' ، 'S' ، 'E' یا 'W' دي چې په یو وخت کې د 1 واحد لخوا په یو طرف د یو شي حرکت حرکت ښیې. څیز په پیل کې د پیل (0,0،XNUMX) دی. موږ باید دا ومومو چې آیا اعتراض به په هره مرحله کې په خپل ورکړل شوي تار کې د ټاکل شوي لارې په اوږدو کې خپل لاره تیر کړي.

بېلګه

path = "NES"
false

وضاحت:

د لیټکوډ حل حل کول

په یاد ولرئ چې لاره له یوځل څخه ډیر ټکی نه تیریږي.

path = "NESWW"
true

وضاحت:

د لیټکوډ حل حل کول

په یاد ولرئ چې لاره دوه ځله اصلي څخه لیدنه کوي.

او کړنلاره

د ستونزې بیان څخه دا روښانه ده چې که چیرې یو همغږي (x ، y) د اعتراض په لاره کې واقع شي ، نو دا باید د ټاکلو شمیرو وروسته د اعتراض موقعیت وي ځکه چې دا هر ځل د 1 واحد سره حرکت کوي.
نو که یو ټکی په خپله لاره کې راشي کوم چې یوځل مخکې لیدل شوی و ، نو دا یقینا له لارې تیریږي. نو موږ کولی شو سمدلاسه بیرته راستون شو کله چې موږ دا ډول ټکی وموند.

اوس موږ څنګه پوهیږو چې یوه نقطه دمخه لیدنه شوې. د دې لپاره موږ کولی شو a وکاروو د هش سیټ او ټولې نقطې په دې لاره ساتئ. په هر وخت کې که موږ وموندله چې راتلونکی ټکي چې کوم اعتراض ته ځي لا دمخه په سیټ کې شتون لري ، موږ ریښتیني راستنیدو. د لارې په بشپړولو وروسته که دا پیښ نشي ، نو بیا موږ غلط راستون شو.

الګوریتم:

  1. د کیلي ګانو یو سیټ جوړ کړئ ، چیرې چې کیلي د کوارډینټ نمایندګي کوي (x ، y). د دې لپاره موږ جوړه جوړه وکاروو لکه څنګه چې کلیدي یا موږ کولی شو یو ساده تار وکاروو چې باید دوه ځانګړي انفرادي نمایندګي وکړي. پخوانی- "2_3" د همغږۍ نمایندګي لپاره (2,3،XNUMX).
  2. دوه متغیر x او y رامینځته کړئ. دوی د اصلي همغږۍ سره پیل کړئ (0,0،XNUMX) او په سیټ کې یې دننه کړئ.
  3. د ټاکل شوي حرکتونو تکرار لپاره یوه لوپ چل کړئ. د اوسني اقدام سره سم د x یا y ارزښت لوړول یا کمول په لاندې ډول دي:
    د 'N' معنی د نوي همغږي کول دي (x، y + 1)
    د 'ای' معنی د نوي همغږي کول دي (x + 1 ، y)
    د 'S' معنی د نوي همغږي کول دي (x ، y-1)
    د 'W' معنی نوی همغږی دی (x-1، y)
  4. وګورئ چې کوارډینټ (x ، y) په سیټ کې شتون لري یا نه. که چیرې حاضر وي نو ریښتیا بیرته راشئ ، یا به دا همغږي په سیټ کې اضافه کړئ او دوام ورکړئ.
  5. د لوپ له بشپړیدو وروسته که چیرې تیریدنه ونه موندل شي بیرته راستنیدنه غلطه ده.

تطبیق

C ++ د لیټکوډ حل لارې ته تلو لپاره پروګرام

#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

د لارې کراسینګ لیټکوډ حل لپاره جاوا برنامې

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

د لارې کراسټ لیټکوډ حل لپاره پیچلي تحلیلونه

د وخت پیچلتیا

O (N): چیرې چې N د ورکړل شوي تار اندازه ده. لکه څنګه چې موږ هر کرکټر ته یوازې یو ځل ګورو ، نو د وخت پیچلتیا O (N) ده.

د ځای پیچلتیا 

O (N): اضافي حافظه چې موږ په سیټ کې د لیدل شوي کوارډینټونو ذخیره کولو لپاره کاروو.