Leetcode шийдлийн нийтлэг тэмдэгтүүдийг олох


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

Асуудлын мэдэгдэл

Энэ асуудалд бидэнд массив of мөр. Бид массивын бүх мөрөнд гарч ирэх бүх тэмдэгтүүдийн жагсаалтыг хэвлэх хэрэгтэй (давхардсан орно). Хэрэв тэмдэгт тэмдэгт мөр бүрт 2 удаа гарч харин 3 удаа гарч ирэхгүй бол бид үр дүнд нь 2 удаа оруулах хэрэгтэй.

Мөрний тэмдэгт бүр нь Англи үсгийн жижиг үсэг бөгөөд тэмдэгт мөрүүд хамгийн ихдээ 100 урттай болохыг анхаарна уу.

Жишээ нь

String_Array = {"bella" , "ciao" , "espanol"}
a
String_Array = {"qweerty" , "weerty" , "eerty"}
e e r t y

 

Leetcode шийдлийн нийтлэг тэмдэгтүүдийг олох

Хандалт (HashMaps)

Бид эхлээд hashmap ашиглаж болно finalCount тэмдэгтүүдийн тоог ['a', 'z'] дотор хадгалахын тулд тэдгээрийг хадгалах хамгийн бага нийтлэг бүх мөрөнд байх. Жишээлбэл, хэрэв массивын мөр бүрт 2 'e гэж байгаа бол бид түүний тоог 2 гэж хадгална. Үүнийг хэрэгжүүлэхийн тулд массивын мөр бүрээр зочилж, finalCount ['a', 'z'] дэх тэмдэгт бүрийн хувьд. Эцэст нь тэмдэгтийг үр дүнгийн массив / жагсаалтад эцсийн тооллын дагуу түлхэж буцааж өгнө.

Алгоритм

  1. Хэш газрын зургийг эхлүүлэх finalCount тэмдэгт бүрийн хамгийн бага нийтлэг дүр төрхийг хадгалах
  2. Англи үсгийн жижиг үсэг бүрийн хувьд:
    • Тэднийг тохируул finalCount 100.
  3. Мөр бүрийн хувьд үг өгөгдсөн массивт:
    • Тэмдэгт бүрийн тоог хэш газрын зураг дээр хадгална уу тоолох
    • Англи үсгийн жижиг үсэг бүрийн хувьд c:
      • Тодорхойлолт: finalCount [c] = мин (finalCount [c], count [c])
  4. Жагсаалт / массивыг эхлүүлэх үр дүн нийтлэг тэмдэгтүүдийн массивыг хадгалах.
  5. Дүр бүрийн хувьд ['a', 'z'] мужид:
    • Үүнийг жагсаалтад хэдэн ч удаа нэмээрэй finalCount [c]
  6. Үр дүнг хэвлэ

Нийтлэг тэмдэгтүүдийг олох Leetcode шийдлийн хэрэгжилт

C ++ програм

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

vector <string> commonChars(vector <string> A)
{
    unordered_map <char , int> finalCount;

    for(char c = 'a' ; c <= 'z' ; ++c)
        finalCount[c] = 100;

    unordered_map <char , int> count;

    for(string &word : A)
    {
        count.clear();
        for(char c : word)
            count[c]++;

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount[c] = min(finalCount[c] , count[c]);
    }

    vector <string> result;

    string temp;

    int times;
    for(char c = 'a' ; c <= 'z' ; ++c)
    {
        times = finalCount[c];
        temp = c;
        while(times > 0)
        {
            result.push_back(temp);
            --times;
        }
    }
    return result;
}

int main()
{
    vector <string> A = {"qweerty" , "weerty" , "eerty"};
    vector <string> result = commonChars(A);
    if(result.empty())
        cout << "No common characters\n";
    else
    {
        for(string &s : result)
            cout << s << " ";
    }

    return 0;
}

Java програм

import java.util.*;
import java.lang.*;

class common_chars
{
    public static void main(String args[])
    {
        String[] A = {"qweerty" , "weerty" , "eerty"};
        List <String> result = commonChars(A);
        if(result.size() == 0)
            System.out.println("No common characters");
        else
        {
            for(String s : result)
                System.out.print(s + " ");
        }
    }

    static List <String> commonChars(String[] A)
    {
        HashMap <Character , Integer> finalCount = new HashMap<>();

        for(char c = 'a' ; c <= 'z' ; ++c)
            finalCount.put(c , 100);

        HashMap <Character , Integer> count = new HashMap<>();
        for(String word : A)
        {
            count.clear();
            for(char c : word.toCharArray())
                count.put(c , count.getOrDefault(c , 0) + 1);

            for(char c = 'a' ; c <= 'z' ; ++c)
                finalCount.put(c , Math.min(finalCount.get(c) , count.getOrDefault(c , 0)));
        }

        List <String> result = new ArrayList<>();

        int times;
        for(char c = 'a' ; c <= 'z' ; ++c)
        {
            times = finalCount.get(c);
            while(times > 0)
            {
                result.add(Character.toString(c));
                --times;
            }
        }
        return result;
    }
}
e e r t y

Нийтлэг тэмдэгтүүдийг олох Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

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

O (N) тэмдэгтүүдийн тоог шинэчлэхийн тулд массив дахь мөр бүрээс нэг дамжуулалт хийдэг. N = Массив дахь мөрийн уртын нийлбэр.

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

O (1) тэмдэгтүүдийн тоог хадгалахын тулд тогтмол санах ойн зайг ашигладаг тул.