Գտեք ընդհանուր նիշերի Leetcode լուծում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Adobe Amazon խնձոր Bloomberg Google Microsoft TripAdvisor Uber
ալգորիթմները Դասավորություն կոդավորում Հեշինգ հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions

Խնդիրի հայտարարություն  

Այս խնդրում մեզ տրվում է ան դասավորություն of տողերը, Մենք պետք է տպենք բոլոր նիշերի ցուցակը, որոնք հայտնվում են զանգվածի յուրաքանչյուր տողում (ներառված են կրկնօրինակները): Դա այն դեպքում, եթե նիշը յուրաքանչյուր լարում հայտնվում է 2 անգամ, բայց ոչ 3 անգամ, արդյունքում պետք է ունենանք 2 անգամ:

Նկատի ունեցեք, որ լարի յուրաքանչյուր նիշը փոքրատառ անգլերեն տառ է, իսկ տողերի առավելագույն երկարությունը 100 է:

Օրինակ

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

 

Գտեք ընդհանուր նիշերի Leetcode լուծում

Մոտեցում (HashMaps 

Ասենք, նախ կարող ենք օգտագործել hashmap վերջնական հաշիվ պահպանել նիշերի թվերը, որոնք տատանվում են ['a', 'z'] - ում `դրանք պահպանելու համար նվազագույն ընդհանուր ներկայություն բոլոր տողերում: Օրինակ, եթե գտնենք, որ զանգվածի յուրաքանչյուր տողի մեջ կա 2 'է, մենք պահպանում ենք դրա հաշվարկը որպես 2. Որպեսզի դրան հասնենք, մենք այցելում ենք զանգվածի յուրաքանչյուր տողի միջև և նվազագույնի ենք հասցնում վերջնական հաշիվ ['a', 'z'] - ի յուրաքանչյուր նիշի համար: Վերջապես, մենք նիշին մղում ենք ըստ դրա վերջնական հաշվարկի արդյունքների զանգվածում / ցուցակում և վերադարձնում այն:

Ալգորիթմ

  1. Նախաձեռնեք հեշ քարտեզը վերջնական հաշիվ պահպանել յուրաքանչյուր նիշի նվազագույն ընդհանուր տեսքը
  2. Յուրաքանչյուր փոքրատառ անգլերեն տառերի համար.
    • Սահմանել իրենց վերջնական հաշիվ քանի որ 100 թ.
  3. Յուրաքանչյուր լարայինի համար բառ տրված զանգվածում.
    • Յուրաքանչյուր նիշի քանակը պահեք հեշ քարտեզում հաշվել
    • Յուրաքանչյուր փոքրատառ անգլերեն տառի համար c:
      • Սահմանել ` վերջնականՀաշիվ [c] = րոպե (վերջնական հաշիվ [գ], հաշվել [գ])
  4. Նախաձեռնեք ցուցակը / զանգվածը արդյունք ընդհանուր նիշերի զանգվածը պահելու համար:
  5. Յուրաքանչյուր կերպարի համար ['a', 'z'] տիրույթում.
    • Ավելացրեք այն ցուցակում այնքան անգամ, որքան finalCount [c]
  6. Տպեք արդյունքը
Տես նաեւ,
Ստեղնաշարի տող Leetcode լուծում

Գտեք ընդհանուր նիշերի 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 լուծման բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) քանի որ մենք կատարում ենք զանգվածի յուրաքանչյուր տողի մեկ փոխանցում `նիշերի հաշվարկները թարմացնելու համար: N = Strանգվածի տողերի երկարությունների հանրագումար:

Տիեզերական բարդություն

Ո (1) քանի որ մենք օգտագործում ենք հիշողության անընդհատ տարածք նիշերի քանակը պահելու համար: