Պատրաստիր լարը մեծ Leetcode լուծում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Google
ալգորիթմները կոդավորում հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions Գրապահոց String

Խնդիրի հայտարարություն  

«Դարձիր լարը մեծ» խնդրում տրված տողը բաղկացած է փոքր և մեծ տառերից: Մենք պետք է այս լարը լավ դարձնենք ՝ հեռացնելով հարակից նիշերը լարը վատթարացնող լարում:
Լավ տողը մի լար է, որը չունի երկու հարակից նիշ, որտեղ երկու նիշերն էլ նույնն են, բայց տարբեր գործերի: Լարը լավացնելու համար մենք կարող ենք ցանկացած անգամ կատարել այս գործողությունը:

Օրինակ

s = "leEeetcode"
"leetcode"

Բացատրությունը.

Առաջին քայլում մենք կարող ենք ընտրել ինդեքս 1-ը և 2-ը կամ 2-ը և 3-ը, երկուսն էլ «leEeetcode» - ը կիջեցնեն «leetcode»:

"abBAcC"
""

Բացատրությունը.

Հնարավոր սցենարներն են.
Պատրաստիր լարը մեծ Leetcode լուծում

Մոտեցում  

Տրված տողն ունի հարակից բնույթ, որոնք նույնն են, բայց հակառակ դեպքում: Այսպիսով, ինչ մենք պետք է անենք, երբ այս երկու նիշերը բախվեն, մենք պետք է հեռացնենք երկուսն էլ և նորից կրկնենք մնացած տողի գործընթացը:

Դրա համար այն, ինչ կարող ենք անել, այն է, որ մենք կարողանանք կրկնել տրված տողի առաջին նիշից և նիշը կցել մեր արդյունքի տողին, մինչև դա վատ չէ:
Ընթացիկ նիշը կցելուց առաջ մենք ստուգելու ենք, թե արդյոք այս նիշը res տողին ավելացնելը կդարձնի դա վատ, թե ոչ `համեմատելով res տողի վերջին նիշի հետ: Եթե ​​ինտեգրալ տարբերություն (ascii) այդ երկու նիշերի միջեւ հավասար է 32-ի, ապա դա վատ համադրություն է, այլապես լավ է: Դրա հիման վրա մենք կատարելու ենք հետևյալ գործողությունը.

  • եթե նիշին կցելը վատ չի լինի, մենք պարզապես այդ նիշը կցում ենք res- ին:
  • Այլապես, մենք չէինք կցի և կվերացնենք res տողի վերջին նիշը:
Տես նաեւ,
Թիվը վերածեք տասնվեցական Leetcode լուծման

Վերոնշյալ ալգորիթմի համար մենք կարող ենք օգտագործել բուրգ տվյալների կառուցվածքը նիշը մինչև վերջ մղելու և վերջից նիշը դուրս բերելու համար:
C ++ - ում մենք կարող ենք նաև օգտագործել լարային դաս որպես նիշերի բուրգ և կարող է օգտագործել push_back () և pop_back () գործողությունները, ինչպիսիք են stack class:

Իրականացման  

C ++ ծրագիրը ՝ String- ի հիանալի Leetcode լուծումը դարձնելու համար

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

string makeGood(string s) {

    string goodString;

    for(char ch:s)
    {
        if((!goodString.empty()) && abs(goodString.back()-ch)==32)  
            goodString.pop_back();
        else  
            goodString.push_back(ch);
    }

    return goodString;
}

int main() 
{
    string s = "leEeetcode";
    
    cout<<makeGood(s)<<endl;

  return 0; 
}
"leetcode"

Java ծրագիրը լարային հիանալի Leetcode լուծումը դարձնելու համար

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

class Rextester
{  
    public static String makeGood(String s) {

        Stack<Character> stack= new Stack<Character>();

        for(int i=0;i<s.length();i++)
        {
            if((!stack.isEmpty()) && Math.abs(stack.peek()-s.charAt(i))==32 )
                stack.pop();
            else
                stack.push(s.charAt(i));
        }

        char res[]= new char[stack.size()];
        
        for(int i=res.length-1;i>=0;i--) 
            res[i]= stack.pop();

        return new String(res);

    }
    
    public static void main(String args[])
    {
        String s = "leEeetcode";

        System.out.println(makeGood(s));
        
    }
}
"leetcode"

Բարդության վերլուծություն տողը մեծ Leetcode լուծումը դարձնելու համար  

Timeամանակի բարդություն

Վրա) : Որտեղ n է մուտքային տողի երկարությունը: Քանի որ մենք լարով անցնում ենք մեկ օղակի մեջ: Հետևաբար, ժամանակի բարդությունը կլինի n- ի կարգ:

Տիեզերական բարդություն 

Վրա) : Մենք օգտագործում ենք բուրգ ՝ մեր վերջնական արդյունքը պահելու համար: Հետևաբար, օգտագործված տարածությունը կլինի n- ի կարգ, այսինքն ՝ O (n):