Leetcode Solution жалпы каармандарын табуу


Кыйынчылык деңгээли жеңил
Көп суралган Adobe Amazon алма Bloomberg Гугл Microsoft TripAdvisor Uber
согуштук тизме Hashing

Маселени билдирүү

Бул маселеде, бизге берилет согуштук тизме of саптар. Массивдеги ар бир сапта пайда болгон бардык белгилердин тизмесин басып чыгарышыбыз керек (дубликаттар камтылган). Эгерде ар бир сапта 2 жолу символ пайда болсо, 3 жолу эмес, натыйжада биз аны 2 жолу алышыбыз керек.

Саптагы ар бир тамга англисче тамгадан турган кичинекей тамга экендигин жана саптардын максималдуу узундугу 100гө барабар экендигин эске алыңыз.

мисал

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

 

Leetcode Solution жалпы каармандарын табуу

Мамиле (HashMaps)

Алгач, хэшмапты колдонсок болот finalCount ['a', 'z'] аралыгындагы белгилердин санын эсептөө үчүн, аларды сактоо үчүн минималдуу жалпы бардык кылдарда болуу. Мисалы, массивдин ар бир сабында 2 'e бар болсо, анын санын 2 деп эсептейбиз. Буга жетишүү үчүн, массивдеги ар бир сапты карап чыгып, finalCount ['a', 'z'] ар бир каарман үчүн. Акыр-аягы, биз натыйжалар массивинде / тизмедеги акыркы белгилерге ылайык символду түртүп, аны кайтарабыз.

Algorithm

  1. Хэш картасын баштаңыз finalCount ар бир каармандын минималдуу жалпы көрүнүшүн сактоо
  2. Англисче кичинекей тамгалар үчүн:
    • Алардын орнотуу finalCount 100 катары.
  3. Ар бир сап үчүн сөз берилген массивде:
    • Хэш-картада ар бир тамгалардын санын сактаңыз эсептөө
    • Ар бир кичинекей англис тамгасы үчүн c:
      • Set: 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 Solution

Убакыт татаалдыгы

O (N) биз белгилердин санактарын жаңыртуу үчүн массивдеги ар бир саптын бир өтүүсүн жасайбыз. N = Массивдеги узундуктардын узундугу.

Космостун татаалдыгы

O (1) биз белгилердин санын эсептөө үчүн туруктуу эс тутумун колдонобуз.