Ҳалли Leetcode фарқиятро ёбед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon Google
Хашм

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

Дар масъалаи "Фарқиятро ёбед" ба мо дуто дода мешавад сатрхо ҳо ва т. Сатри t бо роҳи ба таври тасодуфӣ пур кардани аломатҳои сатри s ва илова кардани як аломат дар ҳолати тасодуфӣ сохта мешавад.

вазифаи мо аз он иборат аст, ки аломатеро, ки дар сатри t илова шудааст.

мисол

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

Шарҳ:

Ҳалли Leetcode фарқиятро ёбед

Пас аз аз нав танзим кардани аломатҳои сатри t он "abcde" мешавад. Азбаски "abcd" аллакай дар сатри s мавҷуд аст, пас аломати ба t иловашуда "e" мебошад.

Тарзи ҷобаҷогузории ҳалли фарқияти Leetcode

Агар мо нуқтаи назари худро барои дидани мушкилот тағйир диҳем, баъзан ҳалли он осон мешавад. Мисли ин ҷо, мушкилот мегӯяд, ки сатри t тавассути омезиши сатри s ва илова кардани як унсур дар ҳолати тасодуфӣ сохта мешавад. Ҳамин тавр, мо инро дида метавонем, зеро сатри t тавассути илова кардани аломат дар ҳолати тасодуфӣ дар сатри s тавлид мешавад. Ҳоло мо бояд танҳо мавқеъеро муайян кунем, ки аломати сатри 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 Solution

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

Мураккабии вақти рамзи боло дар он аст О (нлогн) зеро мо ҳарду сатрро ба навъҳо ҷудо карда истодаем. Дар ин ҷо n дарозии сатри додашудаи s мебошад.

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

Мураккабии фазоии рамзи дар боло зикршуда Эй (н) барои ҳалли java, зеро мо сатрҳоро ба массив табдил медиҳем, аммо барои C ++ ин O (1) аст, зеро он имкон медиҳад, ки неш дар ҷои худ ҷобаҷо карда шавад.

Равиши Hashing барои Фарқияти Solution 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 Solution

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

Мураккабии вақти рамзи боло дар он аст Эй (н) зеро мо сатрҳоро танҳо як маротиба убур мекунем. Дар ин ҷо n дарозии сатри додашуда мебошад.

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

Мураккабии фазоии рамзи дар боло зикршуда О (1) зеро мо барои массиви басомад фазои доимиро истифода мебарем.

Адабиёт