Ուղի հատող Leetcode լուծում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
ալգորիթմները կոդավորում Հեշինգ հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions String

Խնդիրի հայտարարություն  

Արահետի անցման խնդրում a_string տրված է, որում առկա են ընդամենը չորս տարբեր նիշ «N», «S», «E» կամ «W», որոնք ցույց են տալիս օբյեկտի շարժումը մի ուղղությամբ մեկ անգամ 1 միավորով: Օբյեկտը սկզբնապես գտնվում է ծագման վայրում (0,0): Մենք պետք է պարզենք, թե արդյոք օբյեկտը հատելու է իր ուղին ցանկացած կետում, որը քայլում է տվյալ լարում նշված արահետով:

Օրինակ

path = "NES"
false

Բացատրությունը.

Ուղի հատող Leetcode լուծում

Ուշադրություն դարձրեք, որ արահետը մեկ կետից ոչ մի կետ չի անցնում:

path = "NESWW"
true

Բացատրությունը.

Ուղի հատող Leetcode լուծում

Ուշադրություն դարձրեք, որ ուղին երկու անգամ այցելում է ծագումը:

Մոտեցում  

Խնդրի հայտարարությունից պարզ է դառնում, որ եթե կոորդինատը (x, y) տեղի է ունենում օբյեկտի ճանապարհին, ապա այն պետք է լինի օբյեկտի դիրքը որոշակի քանակի շարժումներից հետո, քանի որ այն ամեն անգամ շարժվում է 1 միավորով:
Այսպիսով, եթե իր ճանապարհին գալիս է մի կետ, որը նախկինում մեկ անգամ այցելել է, ապա այն, անշուշտ, անցնում է արահետով: Այսպիսով, մենք կարող ենք վերադառնալ իրական, հենց որ գտնենք այս տեսակ կետը:

Հիմա որտեղի՞ց իմանանք, որ կետ է այցելվել նախկինում: Դրա համար մենք կարող ենք օգտագործել ա Հեշ հավաքածու և շարունակ պահեք իր ուղու բոլոր կետերը: Անկացած պահի, եթե մենք հայտնաբերեցինք, որ հաջորդ կետը, որի օբյեկտը գնում է, արդեն առկա է հավաքածուի մեջ, մենք կվերադառնանք իրական: Ուղին ավարտելուց հետո, եթե դա տեղի չի ունենում, ապա մենք կեղծ ենք վերադառնում:

Տես նաեւ,
Լարի համեմատություն, որը պարունակում է վայրի բնիկներ

Ալգորիթմ:

  1. Ստեղծեք ստեղների հեշ հավաքածու, որտեղ ստեղնը ներկայացնում է կոորդինատը (x, y): Դրա համար մենք կարող ենք օգտագործել զույգը որպես բանալի Կամ մենք կարող ենք օգտագործել մի պարզ տող, որը պետք է յուրովի ներկայացնի երկու ամբողջ թիվ: Նախ. «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 լուծման համար  

Timeամանակի բարդություն

ՎՐԱ) : որտեղ N- ը տրված տողի չափն է: Քանի որ լարում յուրաքանչյուր նիշ այցելում ենք միայն մեկ անգամ, ուստի ժամանակի բարդությունը O (N) է:

Տես նաեւ,
Բոլոր կենտ երկարության ենթաշեղերի գումարը Leetcode լուծման

Տիեզերական բարդություն 

ՎՐԱ) : Լրացուցիչ հիշողություն մենք օգտագործում ենք այցելած կոորդինատները հավաքածուում պահելու համար: