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


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ຈາກຫນາກແອບເປີ Bloomberg ກູໂກ Microsoft TripAdvisor Uber
Array ແຮກ

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

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

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

ຍົກຕົວຢ່າງ

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

 

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

ວິທີການ (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 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 Program

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) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຄົງທີ່ເພື່ອເກັບ ຈຳ ນວນຕົວອັກສອນ.