ዱካ መሻገሪያ Leetcode መፍትሔ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን
ሃምሽንግ ሕብረቁምፊ

የችግሩ መግለጫ

በመንገድ መሻገሪያ ችግር ውስጥ አንድ ገመድ በአንድ አቅጣጫ በአንድ አቅጣጫ የአንድ ነገርን እንቅስቃሴ በ 1 አሃድ የሚያሳዩ አራት የተለያዩ ቁምፊዎች ‹N’ ፣ ‘S’ ፣ ‘E’ or ‘W’ የተሰጡበት ነው ፡፡ ነገር መጀመሪያ ላይ መነሻ (0,0) ነው። በተጠቀሰው ገመድ ውስጥ በተጠቀሰው መንገድ ላይ እቃው በማንኛውም ጊዜ መንገዱን የሚያልፍ መሆኑን ማወቅ አለብን ፡፡

ለምሳሌ

path = "NES"
false

ማብራሪያ:

ዱካ መሻገሪያ Leetcode መፍትሔ

መንገዱ ማንኛውንም ነጥብ ከአንድ ጊዜ በላይ እንደማያልፍ ልብ ይበሉ ፡፡

path = "NESWW"
true

ማብራሪያ:

ዱካ መሻገሪያ Leetcode መፍትሔ

መንገዱ መነሻውን ሁለት ጊዜ እንደሚጎበኝ ልብ ይበሉ ፡፡

ቀረበ

ከችግሩ መግለጫው በእቃው ጎዳና ላይ መጋጠሚያ (x, y) ከተከሰተ ታዲያ በእያንዳንዱ ጊዜ ከ 1 ዩኒት ጋር ስለሚንቀሳቀስ ከተወሰነ ቁጥር በኋላ የእቃው ቦታ መሆን አለበት ፡፡
ስለዚህ አንድ ጊዜ ቀደም ሲል በተጎበኘው ጎዳና ላይ አንድ ነጥብ ቢመጣ በእርግጥ መንገዱን እያቋረጠ ነው ፡፡ ስለዚህ እንደዚህ ዓይነቱን ነጥብ እንዳገኘን ወዲያውኑ ወደ እውነት መመለስ እንችላለን ፡፡

አሁን አንድ ነጥብ ቀደም ሲል እንደተጎበኘ እንዴት እናውቃለን? ለዚህም እኛ ሀ የሃሽ ስብስብ እና በመንገዱ ላይ ያሉትን ሁሉንም ነጥቦች ማከማቸቱን ይቀጥሉ። ወደየትኛው ነገር የሚሄድበት ቀጣይ ነጥብ ቀደም ሲል በተቀመጠው ውስጥ የሚገኝ መሆኑን ካወቅን በማንኛውም ጊዜ ወደ እውነት እንመለሳለን ፡፡ ይህ ካልሆነ መንገዱን ከጨረስን በኋላ ወደ ሐሰት እንመለሳለን ፡፡

ስልተ-ቀመር

  1. ቁልፉ ቅንጅትን (x, y) በሚወክልበት የቁልፍ ሃሽ ስብስብ ይፍጠሩ። ለዚህ እኛ ጥንድ መጠቀም እንችላለን እንደ ቁልፍ ወይም ሁለት ልዩ ቁጥሮችን ልዩ በሆነ መንገድ መወከል የሚችል ቀለል ያለ ገመድ መጠቀም እንችላለን ፡፡ Ex- “2_3” መጋጠሚያን ለመወከል (2,3)።
  2. ሁለት ተለዋዋጭ x እና y ይፍጠሩ። ከመጀመሪያው መጋጠሚያ (0,0) ጋር የመጀመሪያ ያደርጓቸው እና በስብስቡ ውስጥ ያስገቡት።
  3. የተገለጹትን መንቀሳቀሻዎች (ኢቲዎች) ለማሰራጨት አንድ ዙር ያሂዱ ፡፡ አሁን ባለው እንቅስቃሴ መሠረት የ x ወይም y እሴት መጨመር ወይም መቀነስ እንደሚከተለው ነው
    'N' ማለት አዲስ መጋጠሚያ ማለት ነው (x, y + 1)
    ‹ኢ› ማለት አዲስ መጋጠሚያ ማለት ነው (x + 1, y)
    ‹ኤስ› ማለት አዲስ መጋጠሚያ ማለት ነው (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

የጃቫ ፕሮግራም ለመንገድ መሻገሪያ 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) ነው ፡፡

የቦታ ውስብስብነት 

ኦ (ኤን) የተጎበኙትን መጋጠሚያዎች በአንድ ስብስብ ውስጥ ለማከማቸት የምንጠቀምበት ተጨማሪ ማህደረ ትውስታ።