ຊອກຫາວິທີແກ້ໄຂທີ່ແຕກຕ່າງ Leetcode


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

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບສອງຢ່າງ strings. ສາຍທີສອງແມ່ນຜະລິດໂດຍການສັ່ນຕົວລະຄອນຂອງສາຍ ທຳ ອິດແບບສຸ່ມແລະຫຼັງຈາກນັ້ນເພີ່ມຕົວລະຄອນພິເສດຢູ່ບ່ອນ ຕຳ ແໜ່ງ ແບບສຸ່ມ. ພວກເຮົາ ຈຳ ເປັນຕ້ອງສົ່ງຄືນຕົວອັກສອນພິເສດທີ່ຖືກເພີ່ມເຂົ້າໃນສາຍທີສອງ. ຕົວອັກສອນຈະເປັນຕົວອັກສອນພາສາອັງກິດຕ່ ຳ ສະ ເໝີ.

ຍົກຕົວຢ່າງ

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

ຄຳ ອະທິບາຍ # 1

ລັກສະນະພິເສດທີ່ເພີ່ມເຂົ້າໃນສາຍ b ແມ່ນ 'f' ເປັນຊ່ອຍແນ່ a ບໍ່ມີມັນ.

ຄຳ ອະທິບາຍ # 2

string ມີຕົວອັກສອນ 4 'a' ໃນຂະນະທີ່ຊ່ອຍແນ່ ມີ 5. ສະນັ້ນ, ຈົດ ໝາຍ ພິເສດແມ່ນ 'a'.

ວິທີການ (ການຈັດຮຽງ)

ພວກເຮົາສາມາດຈັດຮຽງທັງສອງເຊືອກແລະຫຼັງຈາກນັ້ນໃຫ້ມັນທັງສອງຈົດ ໝາຍ ໂດຍຈົດ ໝາຍ ເພື່ອຊອກຫາ ຕຳ ແໜ່ງ ທຳ ອິດທີ່ມັນແຕກຕ່າງກັນ. ເຊືອກທີສອງຈະມີສະ ເໝີ ພິເສດ ລັກສະນະ. ດັ່ງນັ້ນ, ພວກເຮົາຈະຊອກຫາຈຸດທີ່ສະຕິງ a ແລະ b ແຕກຕ່າງກັນ. ຢ່າງໃດກໍ່ຕາມ, ມັນສາມາດມີກໍລະນີທີ່ຊ່ອຍແນ່ b ຫຼັງຈາກການຮຽງລໍາດັບກົງກັບທຸກໆລັກສະນະໃນສາຍ a ໃນແຕ່ມີລັກສະນະພິເສດ ໜຶ່ງ ໃນທີ່ສຸດ. ພວກເຮົາຕ້ອງຈັດການກັບກໍລະນີພິເສດນີ້.

ຊອກຫາວິທີແກ້ໄຂທີ່ແຕກຕ່າງ Leetcode

ລະບົບວິເຄາະ

  1. ຄັດທັງສອງເຊືອກ, a ແລະ b. ຍ້ອນວ່າມັນເປັນໄປບໍ່ໄດ້ໃນພາສາຈາວາ, ພວກເຮົາ ທຳ ອິດປ່ຽນມັນເປັນ ຕາຕະລາງ char
  2. ສຳ ລັບທຸກໆຕົວ ໜັງ ສືທີ່ມີຢູ່ໃນສາຍສັ້ນ, ພວກເຮົາກວດເບິ່ງຕົວ ໜັງ ສືໂດຍ:
    • ຖ້າມີຕົວລະຄອນໃນສາຍ ບໍ່ເທົ່າກັບຕົວອັກສອນທີ່ສອດຄ້ອງກັນໃນສາຍ b:
      • ກັບຄືນລັກສະນະນີ້.
  3. ກັບຄືນລັກສະນະສຸດທ້າຍຂອງຊ່ອຍແນ່ ຍ້ອນວ່າມັນເປັນລັກສະນະພິເສດ
  4. ພິມຜົນໄດ້ຮັບ

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

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Java Program

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

ການວິເຄາະຄວາມສັບສົນຂອງການຊອກຫາວິທີແກ້ໄຂທີ່ແຕກຕ່າງ Leetcode

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

O (NlogN), ບ່ອນທີ່ N = ຄວາມຍາວຂອງສາຍຍາວຕໍ່ໄປ. ພວກເຮົາຈັດຮຽງແຖວ / ສາຍໄຟທີ່ໃຊ້ເວລາ O (NlogN).

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

ໂອ (N) ໃນຈາວາແລະ O (1) ໃນ C ++ ດັ່ງທີ່ພວກເຮົາປ່ຽນສາຍເຊືອກເປັນ char Arrays ໃນຈາວາ.

ວິທີການ (Hashing)

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

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນຕາຕະລາງ hash ເພື່ອເກັບຄວາມຖີ່ຂອງຕົວອັກສອນທັງ ໝົດ ຄື ຄວາມຖີ່
  2. ສຳ ລັບທຸກໆຕົວລະຄອນໃນສາຍ a:
    • ເພີ່ມຄວາມຖີ່ຂອງມັນຢູ່ໃນຕາຕະລາງ hash
  3. ສຳ ລັບທຸກໆຕົວລະຄອນໃນສາຍ b:
    • ຫຼຸດລົງຄວາມຖີ່ຂອງມັນໃນຕາຕະລາງ hash
    • ຖ້າຄວາມຖີ່ຂອງມັນເທົ່າກັບ -1:
      • ກັບຄືນລັກສະນະນີ້
  4. ກັບຄືນ '-' ເພື່ອຮັກສາໄວຍາກອນການເຮັດວຽກ
  5. ພິມຜົນໄດ້ຮັບ

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

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Java Program

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

ການວິເຄາະຄວາມສັບສົນຂອງການຊອກຫາວິທີແກ້ໄຂທີ່ແຕກຕ່າງ Leetcode

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

ໂອ (N), N = ຂະ ໜາດ ຂອງສາຍຍາວທີ່ຍາວກວ່າ, ດັ່ງທີ່ພວກເຮົາຍ່າງຜ່ານທັງສອງເຊືອກດຽວເພື່ອປັບປຸງຄວາມຖີ່ຂອງຕົວ ໜັງ ສືຂອງພວກເຂົາ.

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

O (1). ເຖິງແມ່ນວ່າພວກເຮົາໃຊ້ hashtable ເພື່ອເກັບຮັກສາຕົວອັກສອນດ້ວຍຄວາມຖີ່ຂອງພວກມັນ, ພວກເຮົາໃຊ້ພື້ນທີ່ຄົງທີ່ໂດຍບໍ່ ຄຳ ນຶງເຖິງວັດສະດຸປ້ອນ. ສະນັ້ນ, ຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນຄົງທີ່.