Дүрийг давтахгүйгээр хамгийн урт шугам  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Алиа Амазоны Apple-ийн Bloomberg БайтДанс Cisco Ebay Expedia Facebook-ийн Goldman Sachs Google-ийн Microsoft- Morgan Stanley Oracle-ийн SAP SAP лабораторууд Spotify Uber VMware Yahoo
Хаш Хаширч байна Гулгадаг цонх String Хоёр заагч

Өгсөн мөр, тэмдэгтүүдийг давтахгүйгээр бид хамгийн урт мөрний уртыг олох ёстой.

Цөөн хэдэн жишээг авч үзье.

Жишээ нь  

pwwkew
3

Тайлбар: Хариулт нь 3-р урттай "wke" байна

aav
2

Тайлбар: Хариулт нь 2-р урттай “av” байна

Хандалт-1 Дүрийг давтахгүйгээр хамгийн урт шугам   

Харгис хүчин 

Давхардсан тэмдэгтүүдийн хувьд нэг мөрийг бүгдийг нь шалгах хэрэгтэй

  • Цаг хугацааны нарийн төвөгтэй байдал
    • Үүсгэх мөрүүдийн тоо = n * (n + 1) / 2
    • Мөр бүрийг шалгахад цаг хугацаа зарцуулдаг = O (n)
    • Тиймээс цаг хугацааны нарийн төвөгтэй байдал = O (n ^ 3)
  • Сансрын нарийн төвөгтэй байдал
    • Өвөрмөц байдлыг шалгахад гарч буй тэмдэгтүүдийн хадгалалт = n
    • Тиймээс орон зайн нарийн төвөгтэй байдал = O (n)

Хандалт-2 Дүрийг давтахгүйгээр хамгийн урт шугам   

Гулгадаг цонх 

Одоо бид хамгийн их урттай дэд мөр хамтран давтагдах тэмдэгт байхгүй.

  • Максимумыг зөвшөөр
  • Ум урт байх хамгийн их 0-ээр эхлүүлсэн
  • Бид үүнийг баталгаажуулдаг  i to j-1 хувилбар аль хэдийн шалгагдсан байна
  • Бид j-р дүртэй таарах бүрт
    • Хэрэв s [j] давтагдахгүй бол
      • Үүнийг дэд мөрөнд нэмж болно
      • Дэд мөрний уртыг нэмэгдүүлэх боломжтой
      • j-г нэмэгдүүлэх боломжтой
      • s [j] -г HashSet дээр бичиж / нэмж болно
    • Хэрэв s [j] давтагдвал
      • Бид тэмдэгтүүдийг хасдаг
      • Эхлэх цэг, өөрөөр хэлбэл би өөрчлөгдөх шаардлагатай
      • Дэд мөр нь давталт үнэгүй болох хүртэл бид үүнийг хийдэг

Java програм

import java.util.*;
class Solution 
{
    public int lengthOfLongestSubstring(String s)
    {
        int max=0;
        HashSet<Character>hash=new HashSet<Character>();
        int i=0;
        int j=0;
        while(i<s.length() && j<s.length())
        {
            if(hash.contains(s.charAt(j)))
            {
                hash.remove(s.charAt(i));
                i=i+1;
            }
            else
            {
             hash.add(s.charAt(j));
             j=j+1;
             max=Math.max(j-i,max);   
            }
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("pwwkew");
    System.out.print(answer);
  }
}
pwwkew
3

C ++ програм

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    set<char>hash;
    int i=0;
    int j=0;
    while(i<s.length() && j<s.length())
    {
      if(hash.count(s[j]))
      {
                hash.erase(s[i]);
                i=i+1;
      }
      else
     {
     hash.insert(s[j]);
     j=j+1;
     max=maxs(j-i,max);   
     }
    }
    return max;    
    }
};
pwwkew
3

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал: O (n)

мөн үзнэ үү
Эрэмбэлэгдсэн эргэсэн массиваас хайх

Сансрын нарийн төвөгтэй байдал: O (k), энд k нь гулсах цонхны хэмжээ юм

Хандалт-3 Дүрийг давтахгүйгээр хамгийн урт шугам   

Оновчтой гүйдэг цонх 

Дээрх арга барилд бид тэмдэгтүүдийг устгаж, тэмдэгтийн мөрийг давтаж давтагдах хүртэл өөрчлөнө.

Хашмапыг давталтын_хүрээний сүүлчийн тохиолдлыг хадгалахад ашиглаж болох бөгөөд би (дэд мөрний эхлэл) -ийг O (1) үйлдэл болгож цэг рүү шилжүүлж болно.

Java програм

import java.util.*;
class Solution 
{
    public int lengthOfLongestSubstring(String s)
    {
        int max=0;
        HashMap<Character,Integer>hash=new HashMap<Character,Integer>();
        int i=0;
        int j=0;
        while(j<s.length())
        {
            if(hash.containsKey(s.charAt(j)))
            {
                i=Math.max(hash.get(s.charAt(j)),i);
            }
             hash.put(s.charAt(j),j+1);
             max=Math.max(j-i+1,max); 
             j=j+1;
        }
        return max;
    }
}

class Main{
  public static void main(String[] args){
    int answer = (new Solution()).lengthOfLongestSubstring("abcdefg");
    System.out.print(answer);
  }
}
abcdefg
7

C ++ хөтөлбөр

class Solution 
{
public:
    int maxs(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLongestSubstring(string s) 
    {
    int max=0;
    map<char,int>hash;
    int i=0;
    int j=0;
    while(j<s.length())
    {
    if(hash.count(s[j]))
    {
    i=maxs(hash[s[j]],i);
    }
    hash[s[j]]=j+1;
    max=maxs(j-i+1,max); 
    j=j+1;
    }
    return max;
    }
};
aabbccddee
2

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал: O (n)

Сансрын нарийн төвөгтэй байдал: O (k), энд k нь гулсах цонхны хэмжээ юм

Ашигласан материал