ການແຊກຊືມຂັ້ນຕ່ ຳ ເພື່ອປະກອບ palindrome ທີ່ມີການອະນຸຍາດ  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon ລະຫັດປະເທດ Directi ກູໂກ ແທ້ຈິງແລ້ວ Intuit
ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ string

ບັນຫາ“ ການແຊກແຊງຂັ້ນຕ່ ຳ ເພື່ອປະກອບ palindrome ທີ່ມີການອະນຸຍາດອະນຸຍາດ” ກ່າວວ່າທ່ານໄດ້ຖືກມອບໃຫ້ກັບຕົວອັກສອນທັງ ໝົດ ທີ່ຢູ່ໃນຕົວອັກສອນນ້ອຍ. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ຊອກຫາການແຊກຕົວອັກສອນຂັ້ນຕ່ ຳ ສຸດຂອງຕົວລະຄອນເຖິງສາຍທີ່ມັນສາມາດກາຍເປັນ Palindrome. ຕຳ ແໜ່ງ ຂອງຕົວລະຄອນສາມາດປ່ຽນເປັນເຊືອກໄດ້.

ຍົກຕົວຢ່າງ  

ການແຊກຊືມຂັ້ນຕ່ ຳ ເພື່ອປະກອບ palindrome ທີ່ມີການອະນຸຍາດ

malyalam
1

ຄໍາອະທິບາຍ

ຖ້າພວກເຮົາສາມາດເພີ່ມ 'a' ເຂົ້າໄປໃນສາຍເລີ່ມຕົ້ນ, ພວກເຮົາສາມາດສ້າງ palindrome.

madaam
1

ຄໍາອະທິບາຍ

ບໍ່ວ່າຈະເພີ່ມ 'd' ຫລື 'a' ເພື່ອເຮັດໃຫ້ palindrome ຊ່ອຍແນ່ເດີມ.

ລະບົບວິເຄາະ  

  1. ຕັ້ງຄວາມຍາວຂອງຊ່ອຍແນ່ l ແລະຜົນຜະລິດເປັນ 0.
  2. ປະກາດເປັນ integer array.
  3. ເກັບຮັກສາແລະຮັກສາການນັບຂອງແຕ່ລະຕົວລະຄອນໄວ້ໃນສາຍ.
  4. ລອກລວງອາເລເລີ່ມແຕ່ 0 ເຖິງໃນຂະນະທີ່ຂ້ອຍ <26.
    1. ກວດສອບວ່າ countChar [i] % 2 == 1,
      1. ຖ້າຫາກວ່າແມ່ນຄວາມຈິງ, ຫຼັງຈາກນັ້ນເຮັດຜົນຜະລິດ ++.
  5. ຖ້າຜົນໄດ້ຮັບເທົ່າກັບ 0, ຫຼັງຈາກນັ້ນໃຫ້ກັບຄືນ 0.
  6. ຜົນຕອບແທນອີກຄັ້ງ ໜຶ່ງ -1.

ຄໍາອະທິບາຍ

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

ເບິ່ງ
Stone ເກມ II Leetcode

ພວກເຮົາ ກຳ ລັງຈະນັບທຸກໆຕົວຂອງຕົວອັກສອນໃນສາຍປ້ອນຂໍ້ມູນແລະເກັບມັນໄວ້ເປັນແຖວ. ດັ່ງທີ່ພວກເຮົາໄດ້ກ່າວມາແລ້ວ, ເຊືອກທີ່ເປັນ palindrome ສາມາດມີພຽງແຕ່ຕົວອັກສອນ ໜຶ່ງ ທີ່ເກີດຂື້ນເປັນ ຈຳ ນວນຄີກຂອງ ຈຳ ນວນຄັ້ງ. ສະນັ້ນຜົນຜະລິດຈະ ໜ້ອຍ ໜຶ່ງ ກ່ວາຕົວເລກຕົວເລກ. ຫຼັງຈາກເກັບຮັກສາທຸກໆຕົວອັກສອນທີ່ເກີດຂື້ນໃນແຖວ. ຈາກນັ້ນພວກເຮົາ ກຳ ລັງສ້າງຂບວນການປ່ຽນຈາກ i = 0 ເຖິງ i ແມ່ນຕ່ ຳ ກ່ວາ 26. ນີ້ແມ່ນຍ້ອນວ່າມັນມີຕົວເລກທັງ ໝົດ 26 ຕົວອັກສອນແລະພວກເຮົາຄວນສົມມຸດວ່າມັນຈະມີຄວາມເປັນໄປໄດ້ທີ່ຈະເກີດຂື້ນກັບ 26 ຕົວອັກສອນໃນສະຕິງໃດ ໜຶ່ງ.

ໃນຂະນະທີ່ ກຳ ລັງຜ່ານແຖວ, ພວກເຮົາຈະກວດເບິ່ງວ່າການແບ່ງແຕ່ລະນັບໂດຍ 2 ໃບເປັນສ່ວນທີ່ເຫຼືອ 1 ຖ້າມັນເປັນຄວາມຈິງ, ແລ້ວມັນຈະເຮັດໃຫ້ ຈຳ ນວນຜົນຜະລິດເພີ່ມ 1 ໂດຍ ຫຼັງຈາກຜ່ານແຖວ, ຖ້ານັບວ່າຍັງຄົງເປັນສູນ, ໝາຍ ຄວາມວ່າພວກເຮົາບໍ່ພົບຫຍັງໃນຕົວອັກສອນຊຶ່ງເປັນຄີກ ໝາຍ ຄວາມວ່າສະຕິງແມ່ນ palindrome ຢູ່ແລ້ວ, ພວກເຮົາຈະກັບຄືນ 0 ອີກຢ່າງ ໜຶ່ງ ພວກເຮົາຈະກັບມາ (output-1) ດັ່ງທີ່ພວກເຮົາໄດ້ກ່າວເຖິງຜົນຜະລິດຈະ ໜ້ອຍ ໜຶ່ງ ນັບຕົວເລກແລະດັ່ງນັ້ນພວກເຮົາໄດ້ຮັບຜົນຜະລິດ.

ລະຫັດ  

ລະຫັດ C ++ ເພື່ອຊອກຫາການແຊກຂັ້ນຕ່ ຳ ສຸດເພື່ອປະກອບ palindrome ໂດຍມີການອະນຸຍາດ

#include<iostream>

using namespace std;

int getMinimumInsertion(string str)
{
    int l = str.length(),output = 0;

    int countChar[26] = { 0 };
    for (int i = 0; i < l; i++)
        countChar[str[i] - 'a']++;

    for (int i = 0; i < 26; i++)
        if (countChar[i] % 2 == 1)
            output++;

    return (output == 0) ? 0 : output - 1;
}
int main()
{
    string str = "malyalam";
    cout << getMinimumInsertion(str);

    return 0;
}
1

ລະຫັດ Java ເພື່ອຊອກຫາການແຊກຂັ້ນຕ່ ຳ ເພື່ອປະກອບ palindrome ໂດຍມີການອະນຸຍາດ

class insertionToPalindrome
{
    public static int getMinimumInsertion(String str)
    {
        int l = str.length(),output = 0;

        int countChar[] = new int[26];

        for (int i = 0; i < l; i++)
            countChar[str.charAt(i) - 'a']++;

        for (int i = 0; i < 26; i++)
        {
            if (countChar[i] % 2 == 1)
                output++;
        }

        return (output == 0) ? 0 : output - 1;
    }
    public static void main(String[] args)
    {
        String str = "malyalam";
        System.out.println(getMinimumInsertion(str));
    }
}
1

ການວິເຄາະຄວາມສັບສົນ  

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຕົວອັກສອນໃນແຖວປ້ອນຂໍ້ມູນ.

ເບິ່ງ
ຊອກຫາຕົວເລກ Top K (ຫຼືເລື້ອຍໆ) ໃນກະແສ

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

ໂອ (1), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ສ້າງຂບວນພິເສດທີ່ມີຂະ ໜາດ ຄົງທີ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຄົງທີ່.

0 ຮຸ້ນ
Tweet
ແບ່ງ​ປັນ
ແບ່ງ​ປັນ
Pin