ຊອກຫາວິທີແກ້ໄຂຕົວອັກສອນທົ່ວໄປ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon Uber
Array ແຮກ

ຖະແຫຼງການບັນຫາ

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບບັນຊີລາຍຊື່ຂອງ string. ພວກເຮົາຕ້ອງຊອກຫາຕົວລະຄອນທີ່ມີລັກສະນະທົ່ວໄປໃນທຸກໆສາຍ. ຖ້າຕົວລະຄອນມີຢູ່ໃນທຸກສາຍໃນຫລາຍໆຄັ້ງ, ຫຼັງຈາກນັ້ນພວກເຮົາຕ້ອງໄດ້ອອກຕົວລະຄອນອອກເປັນຫລາຍຄັ້ງ.
ສົມມຸດວ່າ, ພວກເຮົາມີເສັ້ນລວດ
[“ bella”,“ ປ້າຍ”,“ roller”]
ພວກເຮົາສາມາດເຫັນໄດ້ວ່າ, ຕົວອັກສອນ 'e' ແມ່ນມີຢູ່ດຽວໃນທຸກສາຍ, ຂ້າພະເຈົ້າມີສອງສາຍໃນທຸກສາຍ. ບໍ່ມີລັກສະນະອື່ນໃດທີ່ ທຳ ມະດາ.
ດັ່ງນັ້ນ, ໃນບັນຊີລາຍຊື່ຜົນຜະລິດຂອງພວກເຮົາ, ຕົວອັກສອນ 'e' ຈະຖືກ ນຳ ສະ ເໜີ ຄັ້ງ ໜຶ່ງ ແລະຕົວລະຄອນ 'l' ຈະຖືກ ນຳ ສະ ເໜີ ສອງຄັ້ງ.

ຍົກຕົວຢ່າງ

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

ວິທີການ

ພວກເຮົາສາມາດເຫັນໄດ້ວ່າພວກເຮົາຕ້ອງຊອກຫາຄວາມຖີ່ທົ່ວໄປຂອງຕົວອັກສອນ az ໃນທຸກໆສາຍໃນນີ້.
ສຳ ລັບທຸກໆສາຍ ສຳ ພັນພວກເຮົາສາມາດສ້າງຂອບຂະ ໜາດ ນັບ 26, ເຊິ່ງມີຄວາມຖີ່ຂອງຕົວອັກສອນ az. ດັດສະນີ 0 ຈະມີການນັບ 'a' ໃນສາຍນັ້ນແລະດັດຊະນີ 1 ມີນັບ 'b' ແລະອື່ນໆ.
ໃນປັດຈຸບັນ ສຳ ລັບແຕ່ລະຕົວລະຄອນແຕ່ a ເຖິງ z, ພວກເຮົາຕ້ອງຊອກຫາຕົວເລກຕ່ ຳ ສຸດເຊິ່ງອາດຈະມີຢູ່ໃນບັນດາຂບວນທີ່ສ້າງຂື້ນຂ້າງເທິງ. ພວກເຮົາເຮັດແບບນີ້, ເພາະວ່າພວກເຮົາສົນໃຈທີ່ຈະມີຕົວລະຄອນຕ່ ຳ ສຸດໃນທຸກໆສາຍ. ເວົ້າອີກຢ່າງ ໜຶ່ງ, ພວກເຮົາພຽງແຕ່ເອົາຕົວອັກສອນ ທຳ ມະດາຈາກແຕ່ລະສາຍ.

 

ຊອກຫາວິທີແກ້ໄຂຕົວອັກສອນທົ່ວໄປ Leetcode

ດັ່ງນັ້ນ, ທຳ ອິດພວກເຮົາຈະສ້າງ ຄຳ ຕອບໃຫ້ array ຂອງຂະ ໜາດ 26 ເຊິ່ງມີດັດສະນີທັງ ໝົດ ທີ່ມີມູນຄ່າສູງສຸດ.
ຈາກນັ້ນ, ພວກເຮົາຈະຂ້າມສາຍເຊືອກຈາກຊ້າຍຫາຂວາ. ໃນແຕ່ລະບາດກ້າວ, ພວກເຮົາຈະສ້າງແຖວນັບ ສຳ ລັບສາຍປັດຈຸບັນ. ຫຼັງຈາກນັ້ນພວກເຮົາຈະປຽບທຽບອາເລທີ່ຖືກສ້າງຂື້ນໃນປະຈຸບັນກັບແຖວ array.
ເນື່ອງຈາກວ່າພວກເຮົາສົນໃຈຢ່າງ ໜ້ອຍ ສຸດ, ດັ່ງນັ້ນແຕ່ລະດັດສະນີຂອງ ans array ຈະຖືກດັດແກ້ເທົ່ານັ້ນຖ້າວ່າຄ່າໃນ array ປັດຈຸບັນຈະນ້ອຍກວ່າມູນຄ່າຂອງ ans array ທີ່ດັດຊະນີນັ້ນ.
ie ຖ້າ ans [i]

ຫຼັງຈາກທີ່ພວກເຮົາໄດ້ຜ່ານທຸກສາຍຂອງບັນຊີລາຍຊື່ດັ່ງກ່າວ, ພວກເຮົາຈະໃຊ້ array ຂອງພວກເຮົາເພື່ອສ້າງລາຍຊື່ຕົວອັກສອນ. ໃນແຖວ ຄຳ ຕອບ, ມູນຄ່າທີ່ດັດສະນີ 0 ສະແດງ ຈຳ ນວນຕົວອັກສອນ 'a', ຄ່າທີ່ດັດຊະນີ 1 ສະແດງ ຈຳ ນວນຂອງດັດຊະນີ 'b' ແລະອື່ນໆ.
ດັ່ງນັ້ນ, ດ້ວຍວິທີນີ້ພວກເຮົາຈະເຮັດໃຫ້ຕົວເລກຜົນຜະລິດຂອງພວກເຮົາມີຕົວລະຄອນໂດຍການນັບຕົວເລກແຕ່ລະຕົວລະຫັດຈາກ a ເຖິງ z.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບຊອກຫາລັກສະນະທົ່ວໄປ Leetcode Solution

#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 Program ສຳ ລັບຊອກຫາຕົວອັກສອນທົ່ວໄປ Leetcode Solution

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 Solution

ຄວາມສັບສົນເວລາ

ໂອ (n): ບ່ອນທີ່ n ແມ່ນຜົນລວມຂອງລວງຍາວຂອງທຸກສາຍ.

ຄວາມສັບສົນໃນອະວະກາດ 

O (1): ສອງອາຄານຕອບໂຕ້ແລະວັດ, ແຕ່ລະຂະ ໜາດ 26 ຖືກ ນຳ ໃຊ້. ເຊິ່ງບໍ່ມີຫຍັງເລີຍແຕ່ຄວາມຊົງ ຈຳ ຂະ ໜາດ ຄົງທີ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນ O (1).