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


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

Энэ асуудалд бид хоёрыг өгдөг мөр. Хоёрдахь мөрийг эхний мөрийн тэмдэгтүүдийг санамсаргүй байдлаар хольж, дараа нь дурын байрлалд нэмэлт тэмдэгт нэмж оруулах замаар үүсгэдэг. Бид хоёр дахь мөрөнд нэмэгдсэн тэмдэгтийг буцааж өгөх хэрэгтэй. Тэмдэгтүүд нь үргэлж Англи үсгийн жижиг үсгүүд байх болно.

Жишээ нь

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

Тайлбар # 1

Мөрөнд нэмсэн нэмэлт тэмдэгт b нь 'f' тэмдэгт мөр юм a үүнийг агуулаагүй болно.

Тайлбар # 2

String мөрөнд 4 'а' үсэгтэй байна 5. Тэгэхээр нэмэлт үсэг нь 'а' байна.

Хандалт (ангилах)

Бид мөрүүдийг хоёуланг нь эрэмбэлээд дараа нь хоёуланг нь үсгээр нь давтаж, эхний байр суурийг олж болно. Хоёр дахь мөр нь үргэлж нэг утастай байх болно нэмэлт тэмдэгт. Тиймээс бид мөр байх цэгийг үргэлж олох болно a болон b ялгаатай. Гэсэн хэдий ч, мөр байх тохиолдол байж болно b эрэмбэлсний дараа тэмдэгт мөр бүр таарч байна a in гэхдээ эцэст нь нэг нэмэлт тэмдэгт байна. Бид энэ нэг онцгой хэргийг шийдвэрлэх хэрэгтэй.

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

Алгоритм

  1. Хоёр утсыг эрэмбэл, a болон b. Java-д боломжгүй тул бид эхлээд тэдгээрийг хөрвүүлдэг char массивууд
  2. Богинохон мөрөнд байгаа тэмдэгт бүрийн хувьд бид үсэг бүрээр шалгалт хийдэг.
    • Хэрэв тэмдэгт мөр тэмдэгт мөрийн харгалзах тэмдэгттэй тэнцүү биш байна b:
      • энэ дүрийг буцаана уу.
  3. Мөрний сүүлчийн тэмдэгтийг буцаана уу Энэ бол нэмэлт тэмдэгт юм
  4. Үр дүнг хэвлэ

Ялгааг олох 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 шийдлийн нарийн төвөгтэй байдлын шинжилгээ

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

O (NlogN), энд N = урт мөрийн урт. O (NlogN) хугацаа шаардагдах мөр / char массивыг ангилдаг.

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

O (N) java ба O (1) мөрүүдийг хөрвүүлэхдээ C ++ дээр char массив java дээр.

Хандалт (Hashing)

Хоёр мөрөнд тэмдэгт бүрийг давтамжаар нь хэш болгож, давтамжаар ялгаатай тэмдэгтийг олох боломжтой. Бидэнд олон тооны өвөрмөц дүрүүд байдаг. Энэ алгоритм нь дээр дурьдсанаас хурдан юм. Үр ашигтай хэрэгжилтийн хувьд бид a хэш хүснэгт тэмдэгт мөр бүрийн давтамжийг нэмэгдүүлэх a тэмдэгт мөр бүрийн давтамжийг бууруулна b. Энэ нь яг нэг тэмдэгтийн давтамж байх тохиолдолд биднийг үлдээх болно тэг биш энэ нь мөрийн нэмэлт тэмдэгт байх болно b.

Алгоритм

  1. Бүх тэмдэгтүүдийн давтамжийг хадгалахын тулд хэш хүснэгтийг эхлүүлнэ үү давтамж
  2. Мөр дэх тэмдэгт бүрийн хувьд a:
    • хэш хүснэгтэд түүний давтамжийг нэмэгдүүлэх
  3. Мөр дэх тэмдэгт бүрийн хувьд b:
    • хэш хүснэгтэд түүний давтамжийг багасгах
    • Хэрэв түүний давтамж нь тэнцүү бол -1:
      • энэ дүрийг буцаана уу
  4. Функцийн синтаксийг хадгалахын тулд '-' буцаана уу
  5. Үр дүнг хэвлэ

Ялгааг олох 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 шийдлийн нарийн төвөгтэй байдлын шинжилгээ

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

O (N), N = тэмдэгт давтамжийг шинэчлэхийн тулд хоёр мөрийг нэг удаа туулж өнгөрөхөд илүү урт мөрийн хэмжээ.

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

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