Leetcode шийдлийн ялгааг олох


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Google-ийн
Хаширч байна

Асуудлын мэдэгдэл

“Ялгааг ол” гэсэн дугаарт бидэнд хоёрыг өгсөн болно мөр s ба t. T тэмдэгт мөрийг тэмдэгтүүдээр санамсаргүй байдлаар бөглөж, нэг тэмдэгтийг санамсаргүй байрлал дээр нэмснээр t мөрийг үүсгэдэг.

бидний даалгавар бол t мөрөнд нэмэгдсэн тэмдэгтийг олох явдал юм.

Жишээ нь

s = "abcd", t = "abcde"
e

Тайлбар:

Leetcode шийдлийн ялгааг олох

T мөрийн тэмдэгтүүдийг өөрчилсний дараа “abcde” болдог. “Abcd” нь s мөрөнд аль хэдийн орсон тул t дээр нэмсэн тэмдэгт нь “e” байна.

Leetcode шийдлийг олох ялгааг олох арга

Хэрэв бид асуудлыг харахын тулд хэтийн төлөвөө өөрчилбөл заримдаа үүнийг шийдвэрлэхэд хялбар болдог. энд байгаа шиг асуудал t мөрийг s мөрийг хольж, нэг элементийг санамсаргүй байрлалаар нэмснээр үүсгэгддэг. Тиймээс бид үүнийг тэмдэгт мөрөнд санамсаргүй байрлал дээр тэмдэгт нэмж өгснөөр t мөр үүсгэгдэж байгааг харж болно. Одоо бид зөвхөн s мөрийн тэмдэгт t тэмдэгттэй таарахгүй байгаа байрлалыг олж мэдэх хэрэгтэй бөгөөд дараа нь тухайн байрлалд байгаа тэмдэгтийг буцааж өгч болно. Тиймээс бид эдгээр алхамуудыг дагаж мөрдөх болно.

  1. Мөрийг хоёуланг нь эрэмбэл.
  2. Тэмдэгт мөрийг тэмдэгтээр нь шалгаад тохирохгүй цэг нь нэмэгдсэн тэмдэгт бөгөөд хариулт болно.
  3. Хэрэв бүх тэмдэгтүүд таарч байвал t мөрийн сүүлчийн байрлал дахь тэмдэгт нь бидний хариулт болно.

Хэрэгжүүлэх

Ялгаа олохын тулд C ++ код

#include <bits/stdc++.h> 
using namespace std; 
    char findTheDifference(string s, string t) {
        sort(s.begin(),s.end());
    
    sort(t.begin(),t.end());
    
    
    for(int i=0;i<s.length();i++)
    {
      if(s[i]!=t[i])
      {
        return t[i];
      }
    }
    
    return t[t.length()-1];
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

Ялгаа олоход зориулсан Java код

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
    char[] sortedS = s.toCharArray();
    char[] sortedT = t.toCharArray();
    Arrays.sort(sortedS);
    Arrays.sort(sortedT);
    for(int i=0;i<s.length();i++){
      if (sortedS[i] != sortedT[i]) {
        return sortedT[i];
      }
    }

    return sortedT[s.length()];
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

Ялгаа олох Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Дээрх кодын цаг хугацааны нарийн төвөгтэй байдал нь O (nlogn) Учир нь бид хоёр утсыг хоёуланг нь ялгаж байгаа. Энд n нь өгөгдсөн s мөрийн урт юм.

Сансрын нарийн төвөгтэй байдал

Дээрх кодын орон зайн нарийн төвөгтэй байдал нь O (N) java шийдлийн хувьд бид мөрүүдийг массив болгон хөрвүүлж байгаа тул C ++ - д O (1) байгаа тул энэ нь sting-ийг газар дээр нь ангилах боломжийг олгодог.

Leetcode шийдлийг олох ялгааг олох арга

Бид эдгээр алхмуудыг дагаж мөрдөх болно.

  1. Тэмдэгтүүдийн давтамжийг хадгалахын тулд 26 хэмжээтэй давтамжийн массивыг үүсгээрэй. Бид үүнийг 0-ээр эхлүүлэх болно.
  2. S мөрийг дайрч давтамжийн массив дахь тэмдэгтүүдийн давтамжийг хадгална.
  3. Одоо t мөрийг туулж давтамжийн массиваас t мөрийг туулах явцад тулгарах тэмдэгт бүрийн давтамжийг бууруул.
  4. Төгсгөлд нь давтамжийн массивыг дайрч, нэг утгатай байрлалд тохирох тэмдэгт нь нэмэгдсэн тэмдэгт бөгөөд энэ нь шаардлагатай хариулт болно.

Хэрэгжүүлэх

Ялгаа олохын тулд C ++ код

#include <bits/stdc++.h> 
using namespace std; 
      char findTheDifference(string s, string t) {
        int count[26] = {0};
        for(int i=0;i<s.length();i++) count[s[i]-'a']++;
        for(int i=0;i<t.length();i++) count[t[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return 'a';
    }

int main() 
{ 
 string s="abcd",t="abcde";
 char ans=findTheDifference(s,t);
 cout<<ans<<endl;
 return 0;
}
e

Ялгаа олоход зориулсан Java код

import java.util.Arrays;
import java.util.Set ;
import java.util.HashSet;
import java.util.*; 
public class Tutorialcup {
    public static char findTheDifference(String s, String t) {
        int[] count = new int[26];
        char[] S = s.toCharArray(), T = t.toCharArray();
        for(int i=0;i<S.length;i++) count[S[i]-'a']++;
        for(int i=0;i<T.length;i++) count[T[i]-'a']--;
        for(int i=0;i<26;i++) if(count[i] !=0) return (char)(i+'a');
        return '\0';
    }
  public static void main(String[] args) {
     String s="abcd",t="abcde";
     char ans=findTheDifference(s,t);
        System.out.println(ans);
  }
}
e

Ялгаа олох Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

Дээрх кодын цаг хугацааны нарийн төвөгтэй байдал нь O (N) Учир нь бид мөрүүдийг ганц л удаа туулж байна. Энд n нь өгөгдсөн мөрний урт юм.

Сансрын нарийн төвөгтэй байдал

Дээрх кодын орон зайн нарийн төвөгтэй байдал нь O (1) Учир нь бид давтамжийн массивын хувьд тогтмол зайг ашиглаж байна.

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