Преформатирайте разтвора на Leetcode


Ниво на трудност Лесно
Често задавани в Microsoft
Низ

Декларация за проблема

В този проблем ни е дадена буквено-цифрова низ т.е. низът има само малки букви (az) и цифри (0-9). От нас се изисква да върнем всякакви пермутации на този низ, в които в него няма последователна азбука или няма последователни цифри. Ако няма такива пермутация е там, тогава трябва да върнем празен низ.

Пример

s = "a0b1c2"
"0a1b2c"

Обяснение:

Няма два съседни знака с един и същи тип в „0a1b2c“.
„A0b1c2“, „0a1b2c“, „0c2a1b“ също са валидни пермутации.

s = "leetcode"
""

Обяснение:

“Leetcode” има само символи, така че не можем да ги разделяме с цифри.

Подход

Нека първо разберем състоянието, при което можем да върнем пермутация.
Да предположим, че ако низът е „abcde“, тогава не можем да направим възможна пермутация от него, в която да няма последователни две азбуки или числа.
По същия начин, ако низът е „12335“, тогава също не можем да направим нищо.
И така, за да направим алтернативен буквено-цифров низ, трябва ли да имаме еднакъв брой цифри и азбуки?
Не, да видим пример „covid2019“, имаме 5 азбуки и 4 цифри.
Все пак имаме възможни отговори, напр. „C2o0v1i9d“.

Преформатирайте разтвора на Leetcode

Сега, ако в същия низ ще има още една азбука, нека “covids2019”, тогава също не бихме могли да формираме някакъв възможен изход.
По този начин тук имаме условие, че разликата в броя на азбуките и броя на цифрите не трябва да надвишава 1.
т.е. abs (count (цифри) -count (азбуки)) <= 1, в противен случай изходът не е възможен.

Нека сега разберем алгоритъма,

алгоритъм

  1. За да създадем алтернативния изход, трябва да направим групиране на азбуки и цифри поотделно.
  2. След това можем да проверим размера на двете групи, ако разликата надвишава 1, връщаме празен низ. Иначе отиваме по-нататък.
  3. Вече можем да проверим размера на двете групи,
    ако размерът на група (група азбуки) е по-голям (с една) от друга (група цифри), тогава трябва да започнем с попълване на символ на по-голяма група на първо място в изходния низ.
    В противен случай характерът на всяка група може да заеме първо място.
    Тук използваме флаг променлива за тази задача. Което не е нищо друго освен завой и за двете групи. Ако знамето е вярно, тогава се придвижваме по-нататък, като поставяме азбуката на текущото място в изходния низ. В противен случай ще сложим цифра.
    Също така при всяко запълване ще обърнем флага, за да запазим редуването между двете групи.
  4. Така че, преди да добавим символите един по един в изхода, ще запазим знамето си вярно, ако азбучната група е с по-голям размер, иначе флагът ще остане невярен.
  5. Сега това е изходен низ и трябва да върнем същото.

изпълнение

Програма за преформатиране на C ++ Leetcode Solution

#include <iostream>
using namespace std;

string reformat(string s) {
        
        string alphas;
        string digs;
        
        for(int i=0;i<s.length();i++){
            char ch=s[i];
            string str=string(1, ch); 
            if(ch>='0' && ch<='9')digs.append(str);
            else alphas.append(str);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=abs(alen-dlen);
        if(diff>1)return "";
        
        string ans;
        
        bool flag=0;
        if(alen-dlen==1)flag=1;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                string str=string(1, alphas[j++]); 
                ans.append(str);
            }else{
                string str=string(1, digs[k++]); 
                ans.append(str);
            }
            flag=!flag;
        }
    
        return ans;
    }


int main() {
  string str="covid2019";
  string ans=reformat(str);
    cout<<ans<<endl;	
  return 0;
}
c2o0v1i9d

Java програма за преформатиране на решението с низови Leetcode

import java.util.*;
class ReformatString{
  public static  String reformat(String s) {
        
        StringBuilder alphas=new StringBuilder();
        StringBuilder digs=new StringBuilder();
        
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch>='0' && ch<='9')digs.append(ch);
            else alphas.append(ch);
        }
        
        int alen=alphas.length();
        int dlen=digs.length();
        
        int diff=Math.abs(alen-dlen);
        if(diff>1)return "";
        
        StringBuilder ans=new StringBuilder();
        
        boolean flag=false;
        if(alen-dlen==1)flag=true;
        
        int j=0,k=0;
        for(int i=0;i<s.length();i++){
            if(flag){
                ans.append(alphas.charAt(j++));
            }else{
                ans.append(digs.charAt(k++));
            }
            flag=!flag;
        }
        return ans.toString();
    }
  
    public static void main(String args[]){
        
    String str="covid2019";
    String ans=reformat(str);
    System.out.println(ans);
    }
}
c2o0v1i9d

Анализ на сложността за преформатиране на разтвора на Leetcode

Сложност във времето

На) : Защото работим линейно върху входния низ. Следователно, сложността във времето ще бъде O (n).

Сложност на пространството 

На) : Трябва да използваме няколко допълнителни низа:

  • а. за азбучна група
  • б. за цифри група
  • ° С. за изход

Размерът на всичко това е най-много дължината на входния низ
Следователно, космическата сложност също е O (n).