Ümumi simvollar üçün kod kodu həllini tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Über
alqoritmlər Geyim kodlaşdırma Hashing müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 71

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Bu problemdə bizə bir siyahı verilir sim. Bütün simlərdə ümumi olan simvolları tapmalıyıq. Bir simvol bütün sətirlərdə bir neçə dəfə mövcuddursa, o zaman bir neçə dəfə simvol çıxarmalıyıq.
Tutaq ki, bir sıra simlərimiz var
[“Bella”, “etiket”, “roller”]
'E' xarakterinin bütün simlərdə bir dəfə, l bütün simlərdə iki dəfə olduğunu görə bilərik. Başqa heç bir xarakter yaygındır.
Beləliklə, çıxış siyahımızda 'e' işarəsi bir dəfə, 'l' işarəsi iki dəfə iştirak edəcəkdir.

misal

["bella","label","roller"]
["e","l","l"]
["cool","lock","cook"]
["c","o"]

Yanaşma

Görə bilərik ki, buradakı bütün simlərdə az simvollarının ümumi tezliyini tapmalıyıq.
Hər sətir üçün az simvollarının tezliyi olan 26 ölçülü bir sayma massivi yarada bilərik. indeks 0 bu sətirdə 'a' sayına, 1 indeksi isə 'b' sayına və s.
İndi a-dan z-yə qədər olan hər bir simvol üçün yuxarıda yaradılan hər hansı bir massivdə ola biləcək minimum sayını tapmalıyıq. Bunu edirik, çünki bütün simlərdə bir xarakterin minimum olması bizi maraqlandırır. Başqa sözlə, hər sətirdən yalnız ümumi simvol götürürük.

 

Ümumi simvollar üçün kod kodu həllini tapınPin

Beləliklə, əvvəlcə bir ans yaradacağıq array bütün indeksləri maksimum dəyərində təyin edən 26 ölçülü.
Sonra, dizi soldan sağa keçirik. Hər addımda cari sətir üçün sayma massivi yaradacağıq. Sonra cari yaradılmış massivi ans array ilə müqayisə edəcəyik.
Hər şeyin minimumu ilə maraqlandığımızdan, ans array-ın hər bir indeksinə yalnız indiki massivdəki dəyər ans dizisinin bu indeksdəki dəyərindən kiçik olduqda dəyişiklik ediləcəkdir.
yəni ans [i] olduqda

Verilən siyahının bütün sətirlərini keçdikdən sonra simvolların siyahısını yaratmaq üçün ans massivimizdən istifadə edəcəyik. Cavab massivində, indeks 0-dakı dəyər 'a' simvol sayını, indeks 1-dəki dəyər 'b' indeks sayını və s. Göstərir.
Beləliklə, bu şəkildə hər bir simvolun sayını a-dan z-yə qədər istifadə edərək çıxış simvollarımızı edəcəyik.

Həyata keçirilməsi

Ümumi simvol tapmaq üçün C ++ Proqramı Leetcode Həlli

#include <iostream>
#include <vector>
using namespace std;
vector<string> commonChars(vector<string>& A) {
        int ans[26];
        int temp[26];
        fill(ans,ans+26,100);
        for(string str:A){
            fill(temp, temp+26,0);
            for(int i=0;i<str.size();i++){
                temp[str[i]-'a']++;
            }
            for(int i=0;i<26;i++){
                ans[i]=min(ans[i],temp[i]);
            }
        }
        vector<string>ansChars;
        for(int i=0;i<26;i++){
            for(int j=0;j<ans[i];j++){
                char ch=((char)(i+'a'));
                string s(1, ch); //convert char ch to string s
                ansChars.push_back(s);
            }
        }
        return ansChars;
    }
int main()
{
    vector<string>A{"bella","label","roller"};
    vector<string>ans = commonChars(A);
    for(string str:ans){
        cout<<str<<" ";
    }
    cout<<endl;
}
e l l

Ümumi Simvollar tapma üçün Java Proqramı Leetcode Həlli

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

class Solution
{  
    public static void main(String args[])
    {
        String[]A={"bella","label","roller"};
        List<String>ans=commonChars(A);
        for(String str:ans){
            System.out.print(str+" ");
        }
        System.out.println();
    }
    public static List<String> commonChars(String[] A) {
        int[]ans=new int[26];
        int[]temp=new int[26];
        Arrays.fill(ans,Integer.MAX_VALUE);
        for(String str:A){
            Arrays.fill(temp,0);
            for(int i=0;i<str.length();i++){
                temp[str.charAt(i)-'a']++;
            }
            for(int i=0;i<26;i++){
                ans[i]=Math.min(ans[i],temp[i]);
            }
        }
        List<String>ansChars=new ArrayList<String>();
        for(int i=0;i<ans.length;i++){
            for(int j=0;j<ans[i];j++){
                ansChars.add((char)(i+'a')+"");
            }
        }
        return ansChars;
    }
}
e l l

Ümumi simvolları tapmaq üçün mürəkkəbliyin təhlili Leetcode həll

Zamanın mürəkkəbliyi

O (n): burada n bütün simlərin uzunluğunun cəmidir.

Kosmik Mürəkkəblik 

O (1): hər biri 26 ölçülü iki sıra ans və temp istifadə olunur. sabit bir ölçülü yaddaşdan başqa bir şey deyil. Beləliklə kosmik mürəkkəblik O (1) -dir.

Crack Sistemi Dizayn Müsahibələri
Translate »
1