Сатрро бо аломатҳое тавлид кунед, ки тоқии онро ҳалли Leetcode ҳисоб мекунанд


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад ДиДи
сатр

Изҳороти мушкилот

Дар ин масъала, ба мо дарозӣ дода мешавад. Мо бояд а данд ки ҳамаи аломатҳо шумораи тоқро доранд. Масалан, aaaaab сатри дуруст аст, зеро count (a) = 5 ва count (b) = 1.
Аммо, aaabbc дар ин ҷо сатри дуруст нест, зеро count (b) = 2, ки адади ҷуфт аст.

мисол

n = 4
"pppz"

Шарҳ:

"Pppz" сатри дуруст аст, зеро аломати 'p' се маротиба ва аломати 'z' як маротиба рух медиҳад. Аҳамият диҳед, ки сатрҳои дигари дуруст низ ҳастанд, ба монанди "ohhh" ва "love".

n = 2
"xy"

Шарҳ:

"Xy" сатри дуруст аст, зеро аломатҳои 'x' ва 'y' як маротиба рух медиҳанд. Аҳамият диҳед, ки бисёр сатрҳои дигари эътибор доранд, ба монанди "ag" ва "ur".

усул

Мо метавонем дар ин ҷо ҳиллаеро истифода барем.
Агар дарозии сатр рақами тоқ бошад, мо метавонем як аломатро дар тӯли сохтани данд, ва агар дарозии вуруд ҷуфт бошад, мо метавонем сатре созем, ки танҳо ду аломат дошта бошад.
Як аломате, ки n-1 маротиба рух медиҳад (ин рақами тоқ хоҳад буд, зеро n ҳатто дар инҷост) ва аломати анотер танҳо як маротиба (ки албатта шумораи тоқ аст).

Масалан n = 4, баромади мо aaab хоҳад буд
ва агар n = 3, натиҷаи мо aaa хоҳад буд

Сатрро бо аломатҳое тавлид кунед, ки тоқии онро ҳалли 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 барои тавлиди сатр бо аломатҳое, ки тоқии ҳалли 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 ҳисоб мекунанд

Мураккабии вақт

O (n): Мо ба дарозии танҳо як маротиба додашуда ба таври хаттӣ такрор мешавем. Аз ин рӯ, мукаммали вақт O (n) хоҳад буд.

Мураккабии фазо 

O (n): Мо сатри баромади худро эҷод карда истодаем, аз ин рӯ фазои иловагии дарозии додашударо истифода мебарем. Аз ин рӯ, мураккабии фазо низ O (n) мебошад.