增加減少的字符串Leetcode解決方案


難度級別 容易獎學金
經常問 阿庫納資本
排序

問題“增加減少字符串Leetcode解決方案”指出,我們得到了一個 作為輸入。 我們需要修改輸入。 或者如問題所述,我們需要對其進行排序。 這裡的術語排序並不一定意味著簡單地對字符進行排序。 我們將按照特定的順序對字符串進行排序,然後首先以嚴格的升序排列字母,直到達到遞增的字符為止。 並且,當我們到達最大字符時,我們開始以從最大可用字符開始的嚴格降序排列字母。 我們需要重複此過程,直到使用完整個字符串的字符為止。 因此,像往常一樣,讓我們首先檢查一些示例。

增加減少的字符串Leetcode解決方案

s = "aaaabbbbcccc"
"abccbaabccba"

說明:如上所述,排序後的字符串必須遵循某種模式。 首先,字符必須嚴格按照遞增的方式排列,然後按照遞減的方式排列。 此處的輸出遵循相同的模式。 字符串以 a 並遵循嚴格增加的模式,直到 c。 然後再次從 c 結尾 a. 重複該過程,直到輸入字符串的字母用盡。

s = "rat"
"art"

說明:排序後的(結果)字符串以最小的字符開頭,並遵循相同的模式,直到沒有字符為止。

減少字符串Leetcode解決方案的方法

“增加字符串減少Leetcode解決方案”問題要求我們以某種方式對給定的輸入字符串進行排序。 上面已經詳細描述了該模式。 簡而言之,首先以嚴格的升序排列輸入的字符,然後以嚴格的降序排列,直到沒有剩餘字符為止。 因此,我們創建了一個頻率數組來存儲輸入中每個字符的計數。 然後,我們只需在頻率陣列上運行一個循環,直到耗盡其中的所有字符為止。

外循環運行直到頻率數組中有字符(頻率大於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

複雜度分析

時間複雜度

上), 由於算法中的外循環,一直運行到字符留在頻率數組中為止。

空間複雜度

上), 因為新字符串佔用的空間與輸入所佔用的空間相同。