増加する減少する文字列Leetcodeソリューション


難易度 簡単に
よく聞かれる アクナキャピタル
並べ替え(ソート) 文字列

増加する減少する文字列Leetcodeソリューションの問題は、 文字列 入力として。 入力を変更する必要があります。 または、質問にあるように、並べ替える必要があります。 ここでのソートという用語は、必ずしも単に文字をソートすることを意味するわけではありません。 文字列を特定の順序で並べ替え、最初に文字を厳密に昇順で並べて、文字が増えるまで並べ替えます。 そして、最大の文字に到達すると、使用可能な最大の文字から厳密に降順で文字を配置し始めます。 文字列の文字全体が使用されるまで、このプロセスを繰り返す必要があります。 いつものように、最初にいくつかの例を確認しましょう。

増加する減少する文字列Leetcodeソリューション

s = "aaaabbbbcccc"
"abccbaabccba"

説明:上記のように、ソートされたストリングは特定のパターンに従う必要があります。 最初に、文字は厳密に増加するパターンである必要があり、次に減少するパターンである必要があります。 ここでの出力は同じパターンに従います。 文字列はで始まります a 厳密に増加するパターンに従います c。 それから再び c で終わる a. 入力文字列の文字がなくなるまで、このプロセスが繰り返されます。

s = "rat"
"art"

説明:ソートされた(結果の)ストリングは、最小の文字で始まり、文字がなくなるまで同じパターンに従います。

減少する文字列Leetcodeソリューションを増やすためのアプローチ

Increasing Decreasing String Leetcode Solutionの問題により、指定された入力文字列を特定の方法で並べ替えるように求められました。 パターンは上で詳細に説明されています。 簡単に言うと、入力文字を最初に厳密に昇順で並べ、次に文字がなくなるまで厳密に降順で並べます。 そのため、入力の各文字の数を格納する頻度配列を作成します。 次に、周波数配列内のすべての文字が使い果たされるまで、周波数配列に対してループを実行します。

外側のループは、周波数配列に文字(1より大きい周波数)が含まれるまで実行されます。 内部ループは、一時的な文字列に文字を追加します。 この一時的な文字列は、順番に応じて回答に追加されます。 一時的な文字列が追加される最初のターンである場合、それは同じ増加方法で追加されます。 しかし、それが偶数ターンの場合、応答に追加する前に文字列が逆になります。 周波数配列の文字がなくなった後。 アルゴリズムは、呼び出し元の関数に新しい応答文字列を返します。

コード

減少する文字列Leetcodeソリューションを増加させるためのC ++コード

#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

減少する文字列Leetcodeソリューションを増加させるためのJavaコード

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

複雑さの分析

時間の複雑さ

オン)、 アルゴリズムの外側のループなので、文字が周波数配列に残るまで実行されます。

スペースの複雑さ

オン)、 新しい文字列は、入力と同じ量のスペースを使用するためです。