იპოვნეთ განსხვავება Leetcode Solution


Რთული ტური Easy
ხშირად ეკითხებიან Adobe Amazon Google
ჰაშინგი სიმებიანი

ამ პრობლემის დროს, ჩვენ გვეძლევა ორი სიმები. მეორე სტრიქონი წარმოიქმნება პირველი სტრიქონის სიმბოლოების შემთხვევითი შეცვლით და შემდეგ დამატებითი სიმბოლოს დამატებით ნებისმიერ შემთხვევით პოზიციაზე. ჩვენ უნდა დავაბრუნოთ დამატებითი სიმბოლო, რომელიც დაემატა მეორე სტრიქონს. სიმბოლოები ყოველთვის იქნება მცირე ზომის ინგლისური ასოები.

მაგალითი

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

განმარტება # 1

დამატებითი სიმბოლო, რომელიც ემატება სტრიქონს b არის 'f', როგორც სიმებიანი a არ შეიცავს მას.

განმარტება # 2

სიმებიანი აქვს 4 'a' ასო სტრიქონის დროს აქვს 5. ასე რომ, დამატებითი ასო არის "a".

მიდგომა (დალაგება)

ჩვენ შეგვიძლია დავალაგოთ ორივე სტრიქონი და შემდეგ ორივე განვახორციელოთ ასოებით ასოზე, რომ იპოვოთ პირველი პოზიცია, სადაც ისინი განსხვავდებიან. მეორე სტრიქონი ყოველთვის იქნება დამატებითი ხასიათი ასე რომ, ჩვენ ყოველთვის ვიპოვით წერტილს, სადაც სიმებიანია a და b განსხვავდება. ამასთან, შეიძლება იყოს შემთხვევა, როდესაც სტრიქონი b დახარისხების შემდეგ სტრიქონში შეესაბამება ყველა სიმბოლოს a მაგრამ საბოლოოდ აქვს ერთი დამატებითი ხასიათი. ჩვენ უნდა მოვაგვაროთ ეს ერთი განსაკუთრებული საქმე.

იპოვნეთ განსხვავება Leetcode Solution

ალგორითმი

  1. დაალაგეთ ორივე სტრიქონი, a და b. რადგან ეს არ არის შესაძლებელი java- ში, ისინი პირველ რიგში გადავაქციოთ მათ char მასივები
  2. მოკლე სტრიქონში მოცემული ყველა სიმბოლოსთვის, ჩვენ ასო-ასო ვამოწმებთ:
    • თუ სიმბოლო სიმში სიმების ტოლი არ არის შესაბამისი სიმბოლო b:
      • დააბრუნე ეს პერსონაჟი.
  3. დააბრუნე სტრიქონის ბოლო სიმბოლო რადგან ეს არის დამატებითი ხასიათი
  4. დაბეჭდე შედეგი

იმპლემენტაცია Find the Difference Leetcode Solution

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;
}

ჯავა პროგრამა

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) დროს იღებს.

კოსმოსური სირთულის

O (N) ჯავაში და O (1) C ++ - ში, როდესაც სტრიქონებს ვაქცევთ char მასივები ჯავაში.

მიდგომა (hashing)

ორივე სტრიქონში შეგვიძლია გავაშალოთ თითოეული სიმბოლო თავისი სიხშირით და ვიპოვნოთ სიმბოლოთი განსხვავებული სიმბოლო. მას შემდეგ, რაც ჩვენ გვაქვს უნიკალური სიმბოლოების მუდმივი რაოდენობა. ეს ალგორითმი უფრო სწრაფია, ვიდრე ზემოთ განხილული. როგორც ეფექტური განხორციელება, ჩვენ შეგვიძლია შევქმნათ ა ჰაშის ცხრილი და სტრიქონის თითოეული სიმბოლოს სიხშირის გაზრდა a და სტრიქონის თითოეული სიმბოლოს სიხშირის შემცირება b. ეს დაგვტოვებს იმ შემთხვევაში, როდესაც ზუსტად ერთი პერსონაჟის სიხშირეა ნულოვანი და ეს იქნება სიმბოლოს დამატებითი სიმბოლო b.

ალგორითმი

  1. ჰეშის ცხრილის ინიცირება ყველა სიმბოლოს სიხშირის შესანახად სიხშირე
  2. სიმების თითოეული პერსონაჟისთვის a:
    • მისი სიხშირის გაზრდა ჰეშის ცხრილში
  3. სიმების თითოეული პერსონაჟისთვის b:
    • შემცირება მისი სიხშირე ჰეშის ცხრილში
    • თუ მისი სიხშირე ტოლია -1:
      • დააბრუნე ეს პერსონაჟი
  4. დაუბრუნე '-' ფუნქციის სინტაქსის შესანარჩუნებლად
  5. დაბეჭდე შედეგი

იმპლემენტაცია Find the Difference Leetcode Solution

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;
}

ჯავა პროგრამა

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- ს სიმბოლოების შესანახად მათი სიხშირეებით, ჩვენ ვიყენებთ მუდმივ ადგილს, შეყვანის მიუხედავად. ასე რომ, სივრცის სირთულე მუდმივია.