Аломатҳои умумии ҳалли Leetcode -ро ёбед


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon себ Блумберг Google Microsoft TripAdvisor Uber
тартиботи ҳарбӣ Хашм

Изҳороти мушкилот

Дар ин масъала, ба мо як асал of сатрхо. Мо бояд рӯйхати ҳамаи аломатҳоеро, ки дар ҳар сатри массив пайдо мешаванд (нусхаҳои дохилшуда) чоп кунем. Яъне агар дар ҳар як сатр аломат 2 маротиба пайдо шавад, аммо 3 маротиба не, мо бояд дар натиҷа 2 маротиба дошта бошем.

Дар хотир доред, ки ҳар як аломат дар сатр ҳарфи хурди англисӣ мебошад ва сатрҳо ҳадди аксар 100 мебошанд.

мисол

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

 

Аломатҳои умумии ҳалли Leetcode -ро ёбед

Равиш (HashMaps)

Мо аввал метавонем ҳашмапро истифода барем ҳисоб барои нигоҳ доштани ҳисобҳои аломатҳои дорои ['a', 'z'] барои нигоҳ доштани онҳо ҳадди аққал маъмул ҳузур дар ҳама сатрҳо. Масалан, агар дар ҳар як сатри массив 2 'e мавҷуд бошад, мо ҳисобро ҳамчун 2 нигоҳ медорем. Барои ноил шудан ба ин, ҳар сатри массивро аз назар мегузаронем ва шумораи камро ҳисоб барои ҳар як аломат дар ['a', 'z']. Ниҳоят, мо аломатро мувофиқи ҳисоби ниҳоӣ дар массиви / рӯйхати натиҷаҳо пахш карда, онро бармегардонем.

Алгоритм

  1. Харитаи ҳешро оғоз кунед ҳисоб барои нигоҳ доштани ҳадди ақали намуди умумии ҳар як аломат
  2. Барои ҳар як ҳарфи хурди англисӣ:
    • Танзими онҳо ҳисоб ҳамчун 100.
  3. Барои ҳар як сатр сухан дар массиви додашуда:
    • Ҳисоби ҳар як аломатро дар харитаи хэш нигоҳ доред шумурдан
    • Барои ҳар як ҳарфи хурди англисӣ c:
      • Танзими: finalCount [c] = ба ман (finalCount [c], count [c])
  4. Рӯйхат / массивро оғоз кунед натиҷа барои нигоҳ доштани массиви аломатҳои умумӣ.
  5. Барои ҳар як аломат дар ҳудуди ['a', 'z']:
    • Онро ба рӯйхат чанд маротиба илова кунед finalCount [c]
  6. Натиҷаро чоп кунед

Татбиқи аломатҳои маъмулии Solution 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

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

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

О (Н) чунон ки мо ҳар як сатри як қатор гузаришро барои навсозии ҳисобҳои аломатҳо анҷом медиҳем. N = Ҷамъи дарозии сатрҳо дар массив.

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

О (1) зеро мо фазои хотираи доимиро барои нигоҳ доштани шумори аломатҳо истифода мебарем.