ຈັດແຈງສາຍບິດເປັນເສັ້ນທາງ x ແລະ y ທີ່ເກີດຂື້ນແທນ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ ຕິຊົມ Cisco Citrix hike IBM ຂອບຂໍ້ມູນ Pinterest ຟລີໂຄ້ດ Tesla
string

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

ສົມມຸດວ່າທ່ານໄດ້ຮັບຖານສອງ string, ແລະສອງຕົວເລກ x ແລະ y. ສະຕິງປະກອບດ້ວຍ 0s ແລະ 1s ເທົ່ານັ້ນ. ບັນຫາ "ຈັດລຽງ ລຳ ດັບສອງຄູ່ເປັນ x ແລະ y ທີ່ເກີດຂື້ນ" ຖາມເພື່ອຈັດລຽງສາຍດັ່ງກ່າວວ່າ 0 ມາ x ເທື່ອ⇒ 1 ມາ y ເທື່ອ⇒ອີກເທື່ອ ໜຶ່ງ 0 ມາ x ເທື່ອ⇒ 1 ມາ y ເທື່ອແລະອື່ນໆຈົນຮອດ 0 ຫລື 1 ແມ່ນສໍາເລັດ. ຫຼັງຈາກນັ້ນ, ສະຫຼຸບສ່ວນທີ່ຍັງເຫຼືອຂອງສາຍແລະພິມມັນ.

ຍົກຕົວຢ່າງ

str = “01101”,

x = 1

y = 1
01011

ຄໍາອະທິບາຍ

ທຳ ອິດ 0 ພິມ x ເທື່ອ, ຫຼັງຈາກນັ້ນພິມ 1 ເທື່ອ y, ຫຼັງຈາກນັ້ນ 0 x ເທື່ອຫຼັງຈາກນັ້ນອີກເທື່ອ ໜຶ່ງ 1 y, ແຕ່ດຽວນີ້ 0 ຍັງເຫຼືອຢູ່ດັ່ງນັ້ນພວກເຮົາສະຫຼຸບສ່ວນທີ່ຍັງເຫຼືອຂອງ string ທີ່ຢູ່ 1

ຈັດແຈງສາຍບິດເປັນເສັ້ນທາງ x ແລະ y ທີ່ເກີດຂື້ນແທນ

 

ສູດການຄິດໄລ່ ສຳ ລັບການຈັດລຽງ ລຳ ດັບຖານສອງເປັນທາງເລືອກ x ແລະ y ທີ່ເກີດຂື້ນ

1. Count the total number of 0s and 1s.
2. Make a loop till the count of either of zeros or ones will be 0.
  1. Traverse in an individual loop for zeroCount, till the value x is reached and till the zeroCount will not be 0, print the 0, and decrease the value of zeroCount by 1.
  2. Traverse in an individual loop for onesCount, till the value y is reached and till the onesCount will not be 0, print the 1, and decrease the value of onesCount by 1.

ຄໍາອະທິບາຍ

ຖານສອງ string ເປັນຂໍ້ສະ ເໜີ ແນະທີ່ພວກເຮົາໄດ້ໃຫ້. ສາຍອັກສອນໄບນາລີນັ້ນປະກອບດ້ວຍ 0s ແລະ 1s ເທົ່ານັ້ນຕາມຊື່ທີ່ຊີ້ບອກ. ພວກເຮົາໄດ້ຖືກມອບໃຫ້ດ້ວຍສອງຄ່າ x ແລະ y. ສິ່ງດັ່ງກ່າວທີ່ພວກເຮົາຕ້ອງເຮັດຄືນ 0 ໃນສາຍຜົນຜະລິດ x ເທື່ອແລະ 1 ໃນແຖວຜົນຜະລິດ "y" ເທື່ອຕິດຕໍ່ກັນ. ແລະຖ້າຫາກວ່າມີສາຍຊ້າຍຫຼັງຈາກນັ້ນເຮັດສາຍສະຕິງທີ່ຍັງເຫຼືອກັບສາຍຜົນຜະລິດນີ້. ສຳ ລັບສິ່ງນີ້, ພວກເຮົາຈະບໍ່ໃຊ້ຫຍັງເລີຍນອກ ເໜືອ ຈາກງ່າຍດາຍ ສຳ ລັບທັງສູນເລກແລະໂຕເລກເພື່ອໃຫ້ ຈຳ ນວນແລະຕິດຕາມທັງສູນແລະສູນ.

ພວກເຮົາ ກຳ ລັງຈະຫຍິບສາຍແຕ່ລະຈົດ ໝາຍ. ຈົດ ໝາຍ ແຕ່ລະສະບັບຈະເປັນ 0 ຫລື 1 ໃນຮູບແບບຂອງສາຍ. ແລະພວກເຮົາຈະນັບຈັກຈັກເລກສູນແລະມີຈັກຄົນທີ່ຢູ່ໃນສະຕິງທີ່ມອບໃຫ້? ຈຳ ນວນເລກສູນຈະຖືກເກັບໄວ້ໃນສູນເລກສູນແລະ ຈຳ ນວນເລກເກັບມ້ຽນຈະຖືກເກັບໄວ້ເປັນໂດເມນ. ຕົວແປສອງຕົວນີ້ຈະຖືເອົານັບຂອງເລກສູນແລະຕົວເລກຕ່າງໆເຖິງແມ່ນວ່າພວກເຮົາຈະ ດຳ ເນີນການ.

ຫລັງຈາກໄດ້ຮັບການນັບ ຈຳ ນວນທັງ ໝົດ ຂອງເລກສູນແລະອັນທີ່ຢູ່ໃນແຖວ. ພວກເຮົາຈະເລີ່ມຕົ້ນວົງທີ່ມີເງື່ອນໄຂວ່າວົງຈອນດັ່ງກ່າວຈະສືບຕໍ່ໄປຈົນກ່ວາ zeroCount ຫລື onesCount ຈະເປັນ 0. ໃນວົງນັ້ນ, ພວກເຮົາຈະໄດ້ຮັບການລ້ຽວ ສຳ ລັບເລກ ZeroCount ແລະ onesCount ເປັນສ່ວນບຸກຄົນ, ໂດຍມີເງື່ອນໄຂວ່າວົງຈອນຈະສືບຕໍ່ຈົນເຖິງ x ມູນຄ່າບັນລຸໄດ້ໃນວົງຈອນ. ໃນລະຫວ່າງເວລານີ້ພວກເຮົາຈະພິມ '0' ແລະຈະຫຼຸດຄ່າຂອງເລກສູນແລະພິມມັນ x ເທື່ອ. ແລະຫລັງຈາກນັ້ນອີກວົງຈອນ ໜຶ່ງ ຈະຖືກປະຕິບັດ, ເຊິ່ງຈະພິມ '1' y ເທື່ອ. ຫຼັງຈາກນັ້ນ, ສືບຕໍ່ຫຼຸດລົງມູນຄ່າຂອງ onesCount. ດ້ວຍສາຍທີ່ເຫຼືອນີ້ຈະບໍ່ໄດ້ຮັບຜົນກະທົບແລະພວກເຮົາຈະໄດ້ຮັບຜົນຜະລິດທີ່ຕ້ອງການ.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຈັດລຽງ ລຳ ດັບຖານສອງເປັນທາງເລືອກ x ແລະ y ທີ່ເກີດຂື້ນ

#include<iostream>

using namespace std;

void arrangeZeroesAndOnes(string str, int x, int y)
{
    int zeroCount = 0;
    int onesCount = 0;
    int len = str.length();

    for (int i = 0; i < len; i++)
    {
        if (str[i] == '0')
            zeroCount++;
        else
            onesCount++;
    }
    while (zeroCount > 0 || onesCount > 0)
    {
        for (int j = 0; j < x && zeroCount > 0; j++)
        {
            if (zeroCount > 0)
            {
                cout << "0";
                zeroCount--;
            }
        }
        for (int j = 0; j < y && onesCount > 0; j++)
        {
            if (onesCount > 0)
            {
                cout << "1";
                onesCount--;
            }
        }
    }
}
int main()
{
    string str = "01101";
    int x = 1;
    int y = 1;
    arrangeZeroesAndOnes(str, x, y);
    return 0;
}
01011

ລະຫັດ Java ຫາ Rearrange a binary ເປັນເສັ້ນທາງທີ່ເກີດຂື້ນແທນ x ແລະ y

class arrangeBinaryString
{
    static void arrangeZeroesAndOnes(String str, int x, int y)
    {
        int zeroCount = 0;
        int onesCount = 0;
        int len = str.length();

        for (int i = 0; i < len; i++)
        {
            if (str.charAt(i) == '0')
                zeroCount++;
            else
                onesCount++;
        }

        while (zeroCount > 0 || onesCount > 0)
        {
            for (int j = 0; j < x && zeroCount > 0; j++)
            {
                if (zeroCount > 0)
                {
                    System.out.print ("0");
                    zeroCount--;
                }
            }
            for (int j = 0; j < y && onesCount > 0; j++)
            {
                if (onesCount > 0)
                {
                    System.out.print("1");
                    onesCount--;
                }
            }
        }
        System.out.println();
    }
    public static void main (String[] args)
    {
        String str = "01101";
        int x = 1;
        int y = 1;
        arrangeZeroesAndOnes(str, x, y);

    }
}
01011

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

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

O (n) ບ່ອນທີ່ "n" ແມ່ນຄວາມຍາວຂອງຊ່ອຍແນ່. ໃນທີ່ນີ້ພວກເຮົາແລ່ນ loop ເທົ່າກັບຄວາມຍາວຂອງຊ່ອຍແນ່. ສາເຫດທີ່ພວກເຮົາ ຈຳ ເປັນຕ້ອງຈັດແຈງຊ່ອຍແນ່ໃນລັກສະນະສະເພາະ. ພວກເຮົາຕ້ອງໄດ້ພິມຕົວອັກສອນທັງ ໝົດ ທີ່ເຮັດໃຫ້ມັນສັບສົນໃນເວລາເສັ້ນ.

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

ໂອ (1), ເນື່ອງຈາກວ່າພວກເຮົາບໍ່ໄດ້ເກັບຮັກສາສາຍ ໃໝ່. ພວກເຮົາພຽງແຕ່ພິມອົງປະກອບຂອງສາຍ ໃໝ່. ສະນັ້ນການປະຕິບັດງານນີ້ບໍ່ໄດ້ເຮັດໃຫ້ພວກເຮົາມີຊ່ອງຫວ່າງໃດໆ. ແລະເພາະສະນັ້ນຄວາມສັບສົນຂອງພື້ນທີ່ ສຳ ລັບລະບົບ algorithm ເອງແມ່ນຄົງທີ່. ໃນຂະນະທີ່ໂປແກຼມທັງ ໝົດ ຕ້ອງການພື້ນທີ່ O (N) ສຳ ລັບການຈັດເກັບຂໍ້ມູນເຂົ້າ.