Жолды кесіп өту әдісі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon
Хэш String

Проблемалық мәлімдеме

Жолды кесіп өту проблемасы а_жіп онда бір мезгілде заттың бір бағытта қозғалуын 1 бірлікке көрсететін 'N', 'S', 'E' немесе 'W' тек төрт түрлі таңба болатыны келтірілген. Нысан бастапқыда пайда болады (0,0). Берілген жолда көрсетілген жол бойымен кез-келген нүктеде объект өз жолын кесіп өтетіндігін білуіміз керек.

мысал

path = "NES"
false

Түсіндіру:

Жолды кесіп өту әдісі

Жолдың кез-келген нүктеден бірнеше рет өтпейтініне назар аударыңыз.

path = "NESWW"
true

Түсіндіру:

Жолды кесіп өту әдісі

Жолдың шыққан жеріне екі рет келетініне назар аударыңыз.

жақындау

Есептерден, егер координатаның (х, у) объектінің жүру жолында пайда болатыны анық болса, онда ол әр уақытта 1 бірлікпен қозғалған кезде объектінің белгілі бір қозғалыстардан кейінгі орны болуы керек.
Демек, егер оның нүктесінде бұрын барған нүкте пайда болса, онда ол сөзсіз жолды кесіп өтеді. Осылайша біз осы тармақты тапқаннан кейін шындыққа орала аламыз.

Енді бір нүктеге бұрын барғанын қайдан білеміз. Ол үшін а Хэш жиынтығы және барлық нүктелерді оның жолында сақтай беріңіз. Кез-келген уақытта объект жүретін келесі нүкте жиынтықта бар екенін анықтаған кезде, біз шындыққа ораламыз. Жолды аяқтағаннан кейін, егер бұл орын алмаса, біз жалған деп жауап береміз.

Алгоритм:

  1. Перне координатты (х, у) білдіретін хэштер жиынтығын жасаңыз. Ол үшін біз жұпты қолдана аламыз кілт ретінде Немесе біз екі жолды бірегей етіп көрсетуі керек қарапайым жолды қолдана аламыз. Ex- “2_3” (2,3) координатасын көрсету үшін.
  2. X және y екі айнымалысын жасаңыз. Оларды бастапқы координатамен (0,0) инициалдаңыз және оны жиынға енгізіңіз.
  3. Көрсетілген қадамдарды қайталауға арналған циклды іске қосыңыз. Ағымдағы қозғалысқа сәйкес х немесе у мәндерін келесідей көбейтіңіз немесе азайтыңыз:
    'N' жаңа координатаны білдіреді (x, y + 1)
    'E' жаңа координатаны білдіреді (x + 1, y)
    'S' жаңа координатаны білдіреді (x, y-1)
    'W' жаңа координатаны білдіреді (x-1, y)
  4. Жинақта координатаның бар-жоғын (х, у) тексеріңіз. Егер бар болса, «true» мәнін қайтарады, Else осы координатты жиынға қосып, жалғастырады
  5. Егер цикл аяқталғаннан кейін ешқандай қиылысу табылмаса, қайтару жалған болады.

Іске асыру

Жолды кесіп өтуге арналған C ++ бағдарламасы Leetcode Solution

#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 бағдарламасы

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): Біз координаттарды жиынтықта сақтау үшін қолданатын қосымша жадымыз.