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


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ກູໂກ Microsoft TripAdvisor Uber
ຂັ້ນຕອນວິທີ Array ລະຫັດ ແຮກ ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions

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

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບ array of strings. ພວກເຮົາ ຈຳ ເປັນຕ້ອງພິມລາຍຊື່ຕົວອັກສອນທັງ ໝົດ ທີ່ປາກົດຢູ່ໃນທຸກໆສາຍໃນແຖວ (ລວມທັງຊ້ ຳ ຊ້ອນ). ນັ້ນແມ່ນຖ້າຕົວລະຄອນປະກົດຕົວ 2 ຄັ້ງໃນທຸກໆສາຍ, ແຕ່ບໍ່ແມ່ນ 3 ຄັ້ງ, ພວກເຮົາ ຈຳ ເປັນຕ້ອງມີມັນ 2 ຄັ້ງໃນຜົນ.

ໃຫ້ສັງເກດວ່າທຸກໆຕົວອັກສອນໃນສາຍແມ່ນຕົວອັກສອນພາສາອັງກິດທີ່ນ້ອຍແລະສາຍລິງມີຄວາມຍາວສູງສຸດ 100.

ຍົກຕົວຢ່າງ

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

 

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

ວິທີການ (HashMaps 

ພວກເຮົາ ທຳ ອິດສາມາດ ນຳ ໃຊ້ hashmap, ເວົ້າ ສຸດທ້າຍ ເພື່ອເກັບ ຈຳ ນວນຕົວອັກສອນທີ່ຕັ້ງຢູ່ໃນ ['a', 'z'] ເພື່ອຈັດເກັບຂອງພວກເຂົາ ຕໍາ່ສຸດທີ່ທົ່ວໄປ ມີຢູ່ໃນທຸກສາຍ. ຕົວຢ່າງ: ຖ້າພວກເຮົາພົບວ່າມີ 2 'e ໃນທຸກໆສາຍໃນແຖວ, ພວກເຮົາຮັກສາການນັບຂອງມັນໄວ້ເປັນ 2. ເພື່ອບັນລຸເປົ້າ ໝາຍ ດັ່ງກ່າວ, ພວກເຮົາໄປຢ້ຽມຢາມທຸກສາຍໃນແຖວແລະຫຼຸດຜ່ອນ ສຸດທ້າຍ ສຳ ລັບທຸກໆຕົວລະຄອນໃນ ['a', 'z']. ສຸດທ້າຍ, ພວກເຮົາຍູ້ຕົວລະຄອນຕາມ ຈຳ ນວນສຸດທ້າຍຂອງມັນໃນຜົນໄດ້ຮັບ / ບັນຊີແລະສົ່ງມັນຄືນ.

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນແຜນທີ່ hash ສຸດທ້າຍ ເພື່ອເກັບຮູບລັກສະນະ ທຳ ມະດາທີ່ນ້ອຍທີ່ສຸດຂອງທຸກໆຕົວ
  2. ສຳ ລັບທຸກໆຕົວອັກສອນພາສາອັງກິດທີ່ມີພາສາຕ່ ຳ:
    • ຕັ້ງຄ່າຂອງພວກເຂົາ ສຸດທ້າຍ ເປັນ 100.
  3. ສຳ ລັບທຸກໆສາຍ ຄໍາ ໃນອາເລທີ່ໃຫ້:
    • ເກັບຮັກສາການນັບຂອງທຸກໆລັກສະນະໃນແຜນທີ່ hash ນັບ
    • ສຳ ລັບທຸກໆຈົດ ໝາຍ ສະບັບທີ່ເປັນພາສາອັງກິດຕ່ ຳ c:
      • ຕັ້ງຄ່າ: finalCount [c] = ນາທີ (ຈຳ ນວນສຸດທ້າຍ [ຄ], ນັບ [ຄ])
  4. ເລີ່ມຕົ້ນບັນຊີລາຍຊື່ / ຂບວນ ຜົນ ເພື່ອເກັບຮັກສາແຖວຂອງຕົວອັກສອນທົ່ວໄປ.
  5. ສຳ ລັບທຸກໆຕົວລະຄອນ ໃນຂອບເຂດ ['a', 'z']:
    • ເພີ່ມມັນເຂົ້າໃນບັນຊີລາຍຊື່ຫຼາຍເທົ່າທີ່ finalCount [ຄ]
  6. ພິມຜົນໄດ້ຮັບ
ເບິ່ງ
ການແກ້ໄຂຄີບອດ Leetcode

ການຈັດຕັ້ງປະຕິບັດການຄົ້ນຫາຕົວອັກສອນສາມັນ Leetcode Solution

ໂຄງການ 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 Solution

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

ໂອ (N) ດັ່ງທີ່ພວກເຮົາເຮັດຜ່ານດຽວຂອງທຸກໆສາຍໃນແຖວເພື່ອອັບເດດ ຈຳ ນວນຕົວອັກສອນ. N = ຜົນບວກຂອງຄວາມຍາວຂອງສາຍໃນແຖວ.

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

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຄົງທີ່ເພື່ອເກັບ ຈຳ ນວນຕົວອັກສອນ.

1