Решение Leetcode с возрастающей убывающей строкой


Сложный уровень Легко
Часто спрашивают в Акуна Капитал
Сортировка строка

В решении проблемы «Увеличение убывающей строки с кодом Leetcode» говорится, что нам дается строка как вход. Нам нужно изменить ввод. Или, как говорится в вопросе, нам нужно его отсортировать. Термин «сортировка» здесь не обязательно означает просто сортировку символов. Мы будем отсортировать строку в определенном порядке, сначала расположив буквы в строго возрастающем порядке, пока не дойдем до возрастающего символа. И когда мы достигаем самого большого символа, мы начинаем располагать буквы в строго убывающем порядке, начиная с самого большого доступного символа. Нам нужно повторять этот процесс, пока не будут использованы все символы строки. Итак, как обычно, давайте сначала проверим несколько примеров.

Решение Leetcode с возрастающей убывающей строкой

s = "aaaabbbbcccc"
"abccbaabccba"

Объяснение: Как указано выше, отсортированная строка должна следовать определенному шаблону. Сначала символы должны быть строго возрастающими, а затем убывающими. Вывод здесь соответствует той же схеме. Строка начинается с a и следует строго возрастающей схеме, пока c. Затем снова начиная с c заканчивается a. Процесс повторяется до тех пор, пока не закончатся буквы входной строки.

s = "rat"
"art"

Объяснение: Отсортированная (результирующая) строка начинается с наименьшего символа и следует тому же шаблону, пока не останется никаких символов.

Подход для увеличения решения Leetcode с убывающей строкой

Задача «Увеличение убывающей строки» Leetcode Solution попросила нас отсортировать заданную строку ввода определенным образом. Выкройка подробно описана выше. Короче говоря, расположите входные символы сначала в строго возрастающем порядке, а затем в строго убывающем порядке, пока не останется никаких символов. Итак, мы создаем частотный массив для хранения количества каждого символа во входных данных. Затем мы просто запускаем цикл по массиву частот, пока все символы в нем не будут исчерпаны.

Внешний цикл выполняется до тех пор, пока в массиве частот не появятся символы (частота больше 1). Внутренний цикл добавляет символ во временную строку. Эта временная строка добавляется к ответу в зависимости от хода. Если временная строка добавляется впервые, она добавляется таким же возрастающим образом. Но если это четный ход, то перед добавлением к ответу строка переворачивается. После исчерпания символов в частотном массиве. Алгоритм возвращает новую строку ответа вызывающей функции.

Код:

Код C ++ для увеличения решения Leetcode с убывающей строкой

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

string sortString(string s) {
    vector<int> frq(26, 0);
    for(auto x: s)
        frq[x-'a']++;
    int par = false;
    string ans = "";
    bool can = false;
    do{
        can = false;
        string ss = "";
        for(int i=0;i<26;i++)
            if(frq[i]){
                ss += (char)(i+'a');
                frq[i]--;
                can |= (frq[i] > 0);
            }
        if(par == true)
            reverse(ss.begin(), ss.end());
        par ^= 1;
        ans += ss;
    } while(can);
    return ans;
}

int main()
{
    cout<<sortString("aaaabbbbcccc");
}
abccbaabccba

Код Java для увеличения решения Leetcode с убывающей строкой

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static String sortString(String s) {
        ArrayList<Integer> frq = new ArrayList<Integer>();
        for(int i=0;i<26;i++)
            frq.add(0);
        for(int i=0;i<s.length();i++)
            frq.set(s.charAt(i)-'a', frq.get(s.charAt(i)-'a')+1);
        int par = 0;
        StringBuilder ans = new StringBuilder();
        boolean can = false;
        do{
            can = false;
            StringBuilder ss = new StringBuilder();
            for(int i=0;i<26;i++)
                if(frq.get(i)>0){
                    ss.append((char)(i+'a'));
                    frq.set(i, frq.get(i)-1);
                    can |= (frq.get(i) > 0);
                }
            if(par == 1)
                ss.reverse();
            par ^= 1;
            ans.append(ss);
        } while(can == true);
        return ans.toString();
    }
    
  public static void main (String[] args) throws java.lang.Exception
  {
    System.out.print(sortString("aaaabbbbcccc"));
  }
}
abccbaabccba

Анализ сложности

Сложность времени

НА), поскольку внешний цикл в алгоритме выполняется до тех пор, пока символы не останутся в массиве частот.

Космическая сложность

НА), потому что новая строка занимает столько же места, сколько занимает ввод.