ສ້າງສາຍສະຕິງດ້ວຍຕົວລະຄອນທີ່ມີວິທີການແກ້ໄຂຄີກກັບ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ດີຈີດີ
string

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

ໃນບັນຫານີ້, ພວກເຮົາມີຄວາມຍາວ. ພວກເຮົາຕ້ອງສ້າງກ string ທີ່ມີຕົວອັກສອນທັງ ໝົດ ເປັນ ຈຳ ນວນຄັ້ງທີ່ຄີກ. ຕົວຢ່າງ, aaaaab ແມ່ນສາຍທີ່ຖືກຕ້ອງເພາະວ່ານັບ (a) = 5 ແລະນັບ (ຂ) = 1.
ແຕ່, aaabbc ບໍ່ແມ່ນສາຍທີ່ຖືກຕ້ອງຢູ່ທີ່ນີ້ເພາະວ່າການນັບ (ຂ) = 2 ເຊິ່ງແມ່ນຕົວເລກແມ້ກະທັ້ງ.

ຍົກຕົວຢ່າງ

n = 4
"pppz"

ຄໍາອະທິບາຍ:

“ pppz” ແມ່ນສາຍທີ່ຖືກຕ້ອງເນື່ອງຈາກຕົວອັກສອນ 'p' ເກີດຂື້ນສາມຄັ້ງແລະຕົວອັກສອນ 'z' ເກີດຂື້ນ ໜຶ່ງ ຄັ້ງ. ໃຫ້ສັງເກດວ່າມີສາຍເຊືອກທີ່ຖືກຕ້ອງອື່ນໆອີກເຊັ່ນ: "ໂອ້" ແລະ "ຮັກ".

n = 2
"xy"

ຄໍາອະທິບາຍ:

“ xy” ແມ່ນສາຍທີ່ຖືກຕ້ອງເນື່ອງຈາກຕົວອັກສອນ 'x' ແລະ 'y' ເກີດຂື້ນຄັ້ງດຽວ. ໃຫ້ສັງເກດວ່າມັນມີຫລາຍສາຍທີ່ຖືກຕ້ອງອື່ນໆເຊັ່ນ "ag" ແລະ "ur".

ວິທີການ

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

ຕົວຢ່າງ n = 4, ຜົນຜະລິດຂອງພວກເຮົາຈະເປັນ aaab
ແລະຖ້າ n = 3, ຜົນຜະລິດຂອງພວກເຮົາຈະບໍ່ໄດ້ຮັບ

ສ້າງສາຍສະຕິງດ້ວຍຕົວລະຄອນທີ່ມີວິທີການແກ້ໄຂຄີກກັບ Leetcode
ພວກເຮົາພຽງແຕ່ ນຳ ໃຊ້ຕົວອັກສອນ a ແລະ b ໃນການແກ້ໄຂຂອງພວກເຮົາ, ມີຕົວເລືອກຕົວລະຄອນຫລາຍກວ່າຖ້າທ່ານຕ້ອງການ.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບສ້າງສາຍເຊືອກທີ່ມີຕົວລະຄອນທີ່ມີວິທີແກ້ໄຂຄີກົ້ທີ່ມີລະຫັດ Leetcode

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

string generateTheString(int n) 
{
    string str;
    if(n%2==0)
    {
        for(int i=0;i<n-1;i++)  str.push_back('a');
        str.push_back('b');
    }
    else
    {
        for(int i=0;i<n;i++)  str.push_back('a');
    }
    return str;
}

int main() 
{
    int n=5;
    cout<<  generateTheString(n)   << endl;
    return 0; 
}
aaaaa

Java Program ສຳ ລັບສ້າງສາຍເຊືອກທີ່ມີຕົວລະຄອນທີ່ມີວິທີແກ້ໄຂຄີກົ້ທີ່ມີລະຫັດ Leetcode

class Rextester 
{
    public static String generateTheString(int n) 
    {
        StringBuilder sb=new StringBuilder();

        if(n%2==0)
        {
            for(int i=0;i<n-1;i++)sb.append('a');
            sb.append('b');
        }
        else
        {
            for(int i=0;i<n;i++)sb.append('a');
        }

        return sb.toString();
    }

    public static void main(String[]args)
    {
        int length=5;
        System.out.println(generateTheString(length));
    }
}
aaaaa

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

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

ໂອ (n): ພວກເຮົາ ກຳ ລັງປ່ຽນເສັ້ນຊື່ ສຳ ລັບຄວາມຍາວທີ່ໃຫ້ພຽງແຕ່ຄັ້ງດຽວ. ສະນັ້ນ, ເວລາປະສົມປະສານຈະເປັນ O (n).

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

ໂອ (n): ພວກເຮົາ ກຳ ລັງສ້າງລະບົບສາຍສົ່ງຜົນຜະລິດຂອງພວກເຮົາ, ດັ່ງນັ້ນພວກເຮົາ ກຳ ລັງໃຊ້ພື້ນທີ່ພິເສດຂອງຄວາມຍາວທີ່ໃຫ້. ເພາະສະນັ້ນ, ຄວາມສັບສົນໃນອະວະກາດກໍ່ແມ່ນ O (n).