Гузариши роҳи ҳалли Leetcode  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon
алгоритмҳо рамзгузорӣ Хашм мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions сатр

Изҳороти мушкилот  

Дар мушкилоти убури роҳ a_ сатр дода мешавад, ки дар онҳо танҳо чаҳор аломатҳои гуногуни 'N', 'S', 'E' ё 'W' мавҷуданд, ки ҳаракати ашёро дар як самт дар як вақт ба 1 адад нишон медиҳанд. Объект дар ибтидо сарчашма мегирад (0,0). Мо бояд фаҳмем, ки оё предмет роҳи худро дар ҳар нуқтае, ки дар роҳи дар сатри додашуда пешбинишуда мегузарад, убур мекунад ё не.

мисол

path = "NES"
false

Шарҳ:

Гузариши роҳи ҳалли Leetcode

Аҳамият диҳед, ки роҳ ягон нуқтаро на бештар аз як маротиба убур мекунад.

path = "NESWW"
true

Шарҳ:

Гузариши роҳи ҳалли Leetcodeпайвандак

Аҳамият диҳед, ки пайроҳа ду маротиба ба пайдоиши пайдоиш ташриф меорад.

усул  

Аз баёни масъала маълум мешавад, ки агар координата (х, у) дар роҳи ҳаракат пайдо шавад, пас он бояд мавқеи ҷисм пас аз шумораи муайяни ҳаракатҳо бошад, зеро ҳар дафъа бо 1 воҳид ҳаракат мекунад.
Пас, агар нуқтае дар роҳи худ пайдо шавад, ки қаблан дидан карда шуда бошад, пас албатта он роҳро убур мекунад. Пас, мо метавонем ҳарчи зудтар ингуна нуқтаро пайдо кунем.

Ҳоло мо аз куҷо медонем, ки қаблан як нуқта дидан карда шуда буд. Барои ин мо метавонем а Хэш Set ва нигоҳ доштани ҳамаи нуқтаҳои дар роҳи худ. Дар ҳар лаҳза, вақте ки мо фаҳмидем, ки нуқтаи навбатӣ ба он объект меравад, аллакай дар маҷмӯъ мавҷуд аст, мо ҳақиқӣ бармегардем. Пас аз хатми роҳ агар ин тавр нашавад, пас мо бардурӯғ бармегардем.

ҳамчунин нигаред
Муқоисаи сатрҳо, ки нишонаҳо доранд

Алгоритм:

  1. Маҷмӯи хэши калидҳоро эҷод кунед, ки дар он калид координатаро (х, у) ифода мекунад. Барои ин мо метавонем ҷуфтро истифода барем ҳамчун калид Ё мо метавонем як сатри оддиро истифода барем, ки бояд ду ададро ба таври беназир нишон диҳад. 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. Дар маҷмӯъ мавҷуд будани координати (х, у) -ро санҷед. Агар мавҷуд бошад, пас ҳақиқӣ баргардад, Дигар ин координатро ба маҷмӯъ илова кунед ва идома диҳед.
  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  

Мураккабии вақт

О (Н): ки N андозаи сатри додашуда мебошад. Вақте ки мо ба ҳар як аломат дар сатр танҳо як маротиба ташриф меорем, аз ин рӯ мураккабии вақт O (N) мебошад.

ҳамчунин нигаред
Ҷамъи ҳама зерсохторҳои дарозии тоқ ҳалли Leetcode

Мураккабии фазо 

О (Н): Хотираи иловагие, ки мо барои нигоҳ доштани координатҳои ташрифоварда дар маҷмӯъ истифода мебарем.