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


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

Дар ин мушкилот, ба мо дуто медиҳанд сатрхо. Сатри дуюм бо роҳи омезиши аломатҳои сатри аввал ва сипас илова кардани аломати изофӣ дар ҳама гуна ҳолати тасодуфӣ тавлид мешавад. Мо бояд аломати иловагиро, ки ба сатри дуюм илова шуда буд, баргардонем. Аломатҳо ҳамеша ҳарфҳои хурди англисӣ хоҳанд буд.

мисол

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

Шарҳи №1

Аломате, ки ба сатр илова карда мешавад b ҳамчун 'f' ҳамчун сатр аст a онро дар бар намегирад.

Шарҳи №2

сатр ҳангоми сатр 4 'а' ҳарф дорад дорад 5. Пас, ҳарфи изофӣ 'а' аст.

Равиш (ҷобаҷогузорӣ)

Мо метавонем ҳарду сатрро ҷобаҷо кунем ва пас ҳардуи онҳоро ҳарф ба ҳарф такрор карда, мавқеи аввалро фарқ кунем. Сатри дуюм ҳамеша як хоҳад дошт иловагӣ хислат. Ҳамин тавр, мо ҳамеша нуқтаеро пайдо хоҳем кард, ки сатр a ва b фарқ мекунад. Аммо, метавонад ҳолате бошад, ки сатр b пас аз ҷобаҷогузорӣ ба ҳар як аломат дар сатр мувофиқат мекунад a дар, аммо дар охир як аломати изофӣ дорад. Мо бояд ин як парвандаи махсусро баррасӣ кунем.

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

Алгоритм

  1. Ҳарду сатрро ҷудо кунед, a ва b. Азбаски дар java имконнопазир аст, мо аввал онҳоро ба табдил медиҳем массиви char
  2. Барои ҳар як аломате, ки дар сатри кӯтоҳ мавҷуд аст, мо ҳарф ба ҳарф санҷиш мегузаронем:
    • Агар аломат дар сатр бошад ба аломатҳои мувофиқи сатр баробар нест b:
      • ин аломатро баргардонед.
  3. Аломати охирини сатрро баргардонед чунон ки ин аломати изофӣ мебошад
  4. Натиҷаро чоп кунед

Татбиқи Solution Leetcode-ро фарқ кунед

Барномаи C ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Барномаи Java

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

Таҳлили мураккабии Ёфтани фарқияти Leetcode Solution

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

О (NlogN), ки N = Дарозии сатри дарозтар. Мо сатрҳо / массивҳоро ҷудо мекунем, ки вақти O (NlogN) -ро мегиранд.

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

О (Н) дар Java ва О (1) дар C ++, вақте ки мо сатрҳоро ба табдил медиҳем char Arrays дар Java.

Равиш (Hashing)

Дар ҳарду сатр, мо метавонем ҳар як аломатро бо басомади худ хэш карда, аломатеро фарқ кунем, ки бо басомада фарқ мекунад. Азбаски мо шумораи доимии аломатҳои беназир дорем. Ин алгоритм нисбат ба алгоритми дар боло баррасишуда тезтар аст. Ҳамчун татбиқи муассир, мо метавонем ҷадвали хэш ва басомади ҳар як аломатро дар сатр афзоиш диҳед a ва басомади ҳар як аломатро дар сатр кам кунед b. Ин моро дар ҳолате мегузорад, ки басомади дақиқи як аломат бошад ғайри сифр ва ин аломати изофӣ дар сатр хоҳад буд b.

Алгоритм

  1. Ҷадвали хэшро оғоз кунед, то басомади ҳамаи аломатҳоро ҳамчун нигоҳ доред басомад
  2. Барои ҳар як аломат дар сатр a:
    • афзоиши басомади он дар ҷадвали хэш
  3. Барои ҳар як аломат дар сатр b:
    • кам кардани басомади он дар ҷадвали хэш
    • Агар басомади он ба -1:
      • ин аломатро баргардонед
  4. Бозгаштан '-' барои нигоҳ доштани синтаксиси функсия
  5. Натиҷаро чоп кунед

Татбиқи Solution Leetcode-ро фарқ кунед

Барномаи C ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Барномаи Java

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

Таҳлили мураккабии Ёфтани фарқияти Leetcode Solution

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

О (Н), N = андозаи сатри дарозтар, зеро мо ҳарду сатрро як маротиба тай карда, басомади аломатҳои онҳоро нав мекунем.

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

О (1). Гарчанде ки мо барои нигоҳ доштани аломатҳо бо басомадҳо hashtable истифода мебарем, новобаста аз вуруд мо фазои доимиро истифода мебарем. Пас, мураккабии фазо доимист.