Создание строки с символами, имеющими нечетные числа Решение Leetcode


Сложный уровень Легко
Часто спрашивают в 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

Создание строки с символами, имеющими нечетные числа Решение 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).