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


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Amazon Uber
тартиботи ҳарбӣ Хашм

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

Дар ин мушкилот, ба мо рӯйхати данд. Мо бояд аломатҳое пайдо кунем, ки дар ҳама сатрҳо маъмуланд. Агар аломат дар ҳамаи сатрҳо якчанд маротиба мавҷуд бошад, пас мо бояд аломатро якчанд маротиба барорем.
Фарз мекунем, ки мо сатрҳо дорем
["Bella", "label", "roller"]
Мо мебинем, ки аломати 'e' дар ҳама сатрҳо як маротиба, l дар ҳамаи сатрҳо ду маротиба мавҷуд аст. Ягон хислати дигар маъмул нест.
Ҳамин тавр, дар рӯйхати баромади мо, аломати 'e' як маротиба ва аломати 'l' ду маротиба ҳузур хоҳанд дошт.

мисол

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

усул

Мо мебинем, ки мо бояд басомади умумии аломатҳоро аз ҳама сатрҳоро дар ин ҷо муайян кунем.
Барои ҳар як сатр мо метавонем массиви ҳисобкунии андозаи 26 созмон диҳем, ки басомади аломатҳоро аз. индекси 0 ҳисобро 'a' дар он сатр хоҳад дошт ва индекси 1 ҳисобро 'b' ва ғайра дорад.
Ҳоло барои ҳар як аломат аз a то z, мо бояд миқдори ҳадди аққалеро ёбем, ки дар ҳама гуна массивҳои дар боло сохташуда мавҷуд бошад. Мо ин корро карда истодаем, зеро мо ба ҳузури минималии аломат дар ҳамаи сатрҳо манфиатдорем. Ба ибораи дигар, мо танҳо аз ҳар як сатр аломатҳои умумӣ мегирем.

 

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

Ҳамин тавр, мо пеш аз ҳама анс эҷод хоҳем кард асал андозаи 26, ки дорои ҳамаи индексҳо бо арзиши максималӣ мебошад.
Пас, мо массиви сатрҳоро аз чап ба рост убур хоҳем кард. Дар ҳар як қадам, мо массиви ҳисобро барои сатри ҷорӣ эҷод мекунем. Он гоҳ мо массиви ҷории сохташударо бо массиви ans муқоиса хоҳем кард.
Азбаски мо ба ҳадди аққал манфиатдорем, бинобар ин, ҳар як индекси ans array танҳо дар он сурат тағир дода мешавад, ки агар арзиши массиви ҷорӣ аз арзиши ans array дар ин индекс хурд бошад.
яъне агар ans [i]

Пас аз гузаштани ҳамаи сатрҳои рӯйхати додашуда, мо массивҳои худро барои эҷоди рӯйхати аломатҳо истифода хоҳем кард. Дар массиви ҷавоб, арзиши индекси 0 ҳисобкунии аломати 'а' -ро нишон медиҳад, қимати индекси 1 ҳисоб индекси 'b' ва ғайраро нишон медиҳад.
Ҳамин тавр, бо ин роҳ мо бо истифода аз ҳисобкунии ҳар як аломат аз a ба z массиви баромади худро месозем.

татбиќи

Барномаи C ++ барои дарёфти аломатҳои умумӣ Solution 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

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

O (n): ки n ҷамъи дарозии ҳамаи сатрҳо мебошад.

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

О (1): ду массиви ans ва temp, ҳар як андозаи 26 истифода мешавад. ки чизе ҷуз хотираи андозаи доимӣ нест. Ҳамин тавр мураккабии фазо O (1) мебошад.