Fərq Leetcode həllini tapın

Problem bəyanat

“Fərqi tap” problemində bizə ikisi verilir strings s və t. T simli s sətrinin simvollarını təsadüfi doldurmaq və təsadüfi bir yerə bir simvol əlavə etməklə istehsal olunur.

vəzifəmiz t sətrinə əlavə edilmiş xarakteri tapmaqdır.

misal

s = "abcd", t = "abcde"

e

Explanation:

Pin

T sətrinin simvollarını yenidən düzəltdikdən sonra "abcde" olur. "Abcd" s sətrində artıq mövcud olduğundan, t-ə əlavə olunan simvol "e" dir.

Fərq Leetcode həllini tapmaq üçün çeşidləmə yanaşması

Problemi görmək üçün perspektivimizi dəyişdirsək, bəzən problemi həll etmək asan olur. burada olduğu kimi problem t sətrini qarışdırmaqla və təsadüfi vəziyyətdə bir element əlavə etməklə t sətrinin yaradıldığını deyir. Beləliklə, bunu s sətrinə təsadüfi bir vəziyyətdə bir simvol əlavə etməklə t sətri yaradıldığı üçün görə bilərik. İndi yalnız s sətrinin xarakterinin t sətri ilə uyğun gəlmədiyi yeri tapmaq lazımdır və sonra həmin vəziyyətdə olan simvolu qaytara bilərik. Beləliklə, bu addımları izləyəcəyik:

1. Hər iki simli də çeşidləyin.
2. Həm simli həm də simvolla xarakteri yoxlayın və uyğun gəlmədikləri nöqtə əlavə xarakterdir və cavab budur.
3. Bütün simvollar bir-birinə uyğundursa, t sətrinin son mövqeyindəki simvol bizim cavabımızdır.

Həyata keçirilməsi

Fərqi tapın üçün C ++ kodu

#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

Fərqi tapın üçün Java kodu

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

Fərqi tap Leetcode həllinin mürəkkəbliyi təhlili

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (nlogn) çünki hər iki ipi də çeşidləyirik. Burada n verilən s sətrinin uzunluğudur.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (n) java həlli üçün, çünki ipləri bir massivə çeviririk, amma C ++ üçün O (1) olur, çünki stingin yerində çeşidlənməsinə imkan verir.

Fərq Leetcode Çözümünü Tapmaq üçün Hashing Yanaşması

Bu addımları izləyəcəyik:

1. Simvolların tezliyini saxlamaq üçün 26 ölçülü bir tezlik massivi yaradın. 0 ilə başladacağıq.
2. S sətrini keçin və simvolların tezliyini tezlik massivində saxlayın.
3. İndi t sətrini keçin və t sətrinin tezlik aralığından keçməsi zamanı qarşılaşdığınız hər bir xarakterin tezliyini azaldın.
4. Sonda, tezlik massivini keçin və dəyəri bir olan mövqeyə uyğun olan simvol əlavə edilmiş xarakterdir və bu lazımi cavabdır.

Həyata keçirilməsi

Fərqi tapın üçün C ++ kodu

#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

Fərqi tapın üçün Java kodu

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

Fərqi tap Leetcode həllinin mürəkkəbliyi təhlili

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki ipləri yalnız bir dəfə dolaşırıq. Burada n verilən sətrin uzunluğudur.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki tezlik massivi üçün daimi yerdən istifadə edirik.

References