Стварыце радок з персанажамі, якія маюць няцотныя лічбы


Узровень складанасці Лёгка
Часта пытаюцца ў DiDi
Радок

Пастаноўка праблемы

У гэтай праблеме нам дадзена даўжыня. Мы павінны стварыць радок які мае ўсе сімвалы няцотнай колькасці разоў. Напрыклад, aaaaab з'яўляецца сапраўдным радком, таму што count (a) = 5 і count (b) = 1.
Але aaabbc тут не з'яўляецца сапраўдным радком, таму што count (b) = 2, што з'яўляецца цотным лікам.

Прыклад

n = 4
"pppz"

Тлумачэнне:

«Pppz» з'яўляецца сапраўдным радком, бо сімвал «p» сустракаецца тры разы, а сімвал «z» - адзін раз. Звярніце ўвагу, што існуе мноства іншых сапраўдных радкоў, такіх як "ой" і "каханне".

n = 2
"xy"

Тлумачэнне:

"Xy" - сапраўдны радок, бо сімвалы "x" і "y" сустракаюцца адзін раз. Звярніце ўвагу, што ёсць шмат іншых правільных радкоў, такіх як "ag" і "ur".

Падыход

Тут мы можам выкарыстаць хітрасць.
Калі даўжыня радка няцотная, мы можам выкарыстоўваць адзін сімвал для стварэння радок, і калі ўваходная даўжыня роўная цотнай колькасці, мы можам стварыць радок, які мае ўсяго два сімвалы.
Адзін сімвал, які сустракаецца n-1 раз (што будзе няцотнай лічбай, бо n тут нават цотны), а другі сімвал - толькі адзін раз (што, безумоўна, няцотна)

Напрыклад n = 4, наш выхад будзе aaab
і калі n = 3, наш выхад будзе aaa

Стварыце радок з персанажамі, якія маюць няцотныя лічбы
мы проста выкарыстоўваем сімвалы a і b у нашым рашэнні, ёсць больш варыянтаў сімвалаў, калі вы хочаце.

Рэалізацыя

Праграма C ++ для стварэння радка з персанажамі, якія маюць няцотныя лічбы

#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 для стварэння радка з персанажамі, якія маюць няцотныя лічбы

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

Аналіз складанасці для стварэння радка з сімваламі, якія маюць няцотныя лічбы

Складанасць часу

O (n): Мы лінейна ітэруемся для даўжыні, дадзенай толькі адзін раз. Такім чынам, паўната часу будзе O (n).

Касмічная складанасць 

O (n): Мы ствараем нашу выходную радок, таму выкарыстоўваем дадатковы прабел зададзенай даўжыні. Такім чынам, касмічная складанасць таксама роўная O (n).