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


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

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

Այս խնդրում մեզ տրված է ցուցակ լարային, Մենք պետք է պարզենք այն նիշերը, որոնք ընդհանուր են բոլոր լարերի մեջ: Եթե ​​նիշը բոլոր տողերում առկա է բազմակի անգամ, ապա մենք ստիպված ենք նիշը բազմիցս դուրս բերել:
Ենթադրենք, մենք ունենք տողերի զանգված
[«Բելլա», «պիտակ», «գլան»]
Մենք տեսնում ենք, որ 'e' նիշը մեկ տողում առկա է բոլոր տողերում, l երկու անգամ կա բոլոր տողերում: Ոչ մի այլ կերպար սովորական չէ:
Այսպիսով, մեր արդյունքների ցուցակում «e» նիշը կլինի մեկ անգամ, և «l» նիշը կլինի երկու անգամ:

Օրինակ

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

Մոտեցում  

Մենք տեսնում ենք, որ այստեղ պետք է պարզենք az- ի նիշերի ընդհանուր հաճախականությունը:
Յուրաքանչյուր տողի համար մենք կարող ենք ստեղծել 26 չափի հաշվարկի զանգված, որն ունի az նիշերի հաճախականություն: ինդեքս 0-ը կունենա այդ տողի «a» հաշիվը, իսկ 1 ինդեքսը ՝ «b» և այլն:
Այժմ a- ից z յուրաքանչյուր նիշի համար մենք պետք է պարզենք նվազագույն քանակը, որը կարող է առկա լինել վերևում ստեղծված ցանկացած զանգվածում: Մենք դա անում ենք, քանի որ մեզ հետաքրքրում է բոլոր տողերում նիշի նվազագույն ներկայությունը: Այլ կերպ ասած, մենք յուրաքանչյուր լարից վերցնում ենք միայն ընդհանուր նիշերը:

Տես նաեւ,
Rook Leetcode Solution- ի մատչելի նկարներ

 

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

Այսպիսով, մենք նախ կստեղծենք պատասխաններ դասավորություն 26 չափի, որն ունի բոլոր ցուցանիշները սահմանված առավելագույն արժեքով:
Այնուհետև մենք կանցնենք տողերի զանգվածը ձախից աջ: Յուրաքանչյուր քայլում մենք կստեղծենք ընթացիկ տողի համար հաշվարկի զանգված: Դրանից հետո մենք համեմատելու ենք ընթացիկ ստեղծված զանգվածը ans զանգվածի հետ:
Քանի որ մեզ ամենաքիչը շահագրգռված է, ուստի ans զանգվածի յուրաքանչյուր ինդեքս կփոփոխվի միայն այն դեպքում, եթե ընթացիկ զանգվածում արժեքը փոքր լինի, քան ans ցուցակի արժեքը այդ ինդեքսում:
այսինքն, եթե ans [i]

Տրված ցուցակի բոլոր տողերն անցնելուց հետո մենք կօգտագործենք մեր ans զանգվածը ՝ նիշերի ցուցակ ստեղծելու համար: Ի պատասխան զանգվածի, 0 ցուցիչի արժեքը ցույց է տալիս «a» բնույթի հաշիվը, 1 ցուցիչի արժեքը ցույց է տալիս «b» ինդեքսի հաշվարկը և այլն:
Այսպիսով, այս կերպ մենք կդարձնենք նիշերի մեր ելքային զանգվածը `օգտագործելով յուրաքանչյուր նիշի հաշիվ a- ից z:

Իրականացման  

C ++ ծրագիր ՝ ընդհանուր նիշերի Leetcode լուծում գտնելու համար

#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

Java ծրագիր ՝ ընդհանուր նիշերի Leetcode լուծում գտնելու համար

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

Բարդության վերլուծություն ընդհանուր գծերի համար Leetcode լուծում գտնելու համար  

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

Վրա): որտեղ n- ը բոլոր տողերի երկարության գումարն է:

Տես նաեւ,
Ոսկու հանքի խնդիր

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

O (1): Օգտագործվում է երկու զանգված և տերմ. յուրաքանչյուր 26 չափսով: ինչը ոչ այլ ինչ է, քան կայուն չափի հիշողություն: Այսպիսով, տարածության բարդությունը O է (1):

1