ធ្វើឱ្យដំណោះស្រាយឡេឡេកូដកូដល្អ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន google
LeetCode ជង់ ខ្សែអក្សរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហា "ធ្វើឱ្យខ្សែអក្សរដ៏អស្ចារ្យ" ខ្សែអក្សរត្រូវបានផ្តល់ឱ្យមានអក្សរតូចនិងអក្សរធំ។ យើងត្រូវធ្វើឱ្យខ្សែនេះល្អដោយយកតួអក្សរដែលនៅជាប់នឹងខ្សែដែលធ្វើឱ្យខ្សែអក្សរមិនល្អ។
ខ្សែអក្សរល្អគឺជាខ្សែដែលមិនមានតួអក្សរជាប់គ្នាពីរដែលតួអក្សរទាំងពីរគឺដូចគ្នាប៉ុន្តែមានករណីខុសគ្នា។ យើងអាចធ្វើប្រតិបត្តិការនេះគ្រប់ពេលដើម្បីធ្វើឱ្យខ្សែអក្សរល្អ។

ឧទាហរណ៍

s = "leEeetcode"
"leetcode"

ការពន្យល់:

ក្នុងជំហ៊ានដំបូងយើងអាចជ្រើសរើសលិបិក្រម ១ និង ២ រឺ ២ និង ៣ ដែលទាំងពីរនឹងកាត់បន្ថយ“ leEeetcode” ទៅ“ leetcode” ។

"abBAcC"
""

ការពន្យល់:

សេណារីយ៉ូដែលអាចមានគឺ៖
ធ្វើឱ្យដំណោះស្រាយឡេឡេកូដកូដល្អ

វិធីសាស្រ្ត

ខ្សែអក្សរដែលបានផ្តល់ឱ្យមានតួអក្សរនៅជិតគ្នាមួយចំនួនដែលដូចគ្នាប៉ុន្តែក្នុងករណីផ្ទុយ។ ដូច្នេះអ្វីដែលយើងត្រូវធ្វើគឺនៅពេលណាដែលយើងជួបតួអក្សរទាំងពីរនេះយើងត្រូវដកវាចេញហើយម្តងទៀតដំណើរការសម្រាប់ខ្សែដែលនៅសល់។

ចំពោះអ្វីដែលយើងអាចធ្វើបានគឺយើងអាចធ្វើវាបានពីតួអក្សរទីមួយនៃខ្សែអក្សរដែលបានផ្តល់ហើយបន្ថែមតួអក្សរទៅខ្សែលទ្ធផលរបស់យើងរហូតទាល់តែវាមិនអាក្រក់។
មុនពេលបន្ថែមតួអក្សរបច្ចុប្បន្នយើងនឹងពិនិត្យមើលប្រសិនបើការបន្ថែមតួអក្សរនេះទៅខ្សែអក្សរ res នឹងធ្វើឱ្យវាអាក្រក់ឬមិនធ្វើដោយប្រៀបធៀបវាជាមួយតួអក្សរចុងក្រោយនៃខ្សែអក្សរ res ។ បើភាពខុសគ្នាអាំងតេក្រាល (ASCII) រវាងតួអក្សរទាំងពីរគឺស្មើនឹង ៣២ ពេលនោះវាគឺជាការរួមបញ្ចូលគ្នាមិនល្អបើមិនដូច្នេះទេវាល្អ។ ផ្អែកលើមូលដ្ឋាននៃការដែលយើងនឹងធ្វើប្រតិបត្តិការដូចខាងក្រោមៈ

  • ប្រសិនបើបន្ថែមតួអក្សរនឹងមិនធ្វើឱ្យអាក្រក់ទេយើងគ្រាន់តែបន្ថែមតួអក្សរនោះទៅ res ។
  • ម៉្យាងទៀតយើងនឹងមិនបន្ថែមទេហើយយើងនឹងដកតួអក្សរចុងក្រោយនៃខ្សែអក្សរ Res ចេញ។

សម្រាប់ក្បួនដោះស្រាយខាងលើយើងអាចប្រើបាន ជង់ រចនាសម្ព័នទិន្នន័យសម្រាប់ជំរុញតួអក្សរដល់ទីបញ្ចប់និងជ្រើសរើសតួអក្សរពីខាងចុង។
នៅក្នុង C ++ យើងក៏អាចប្រើបានដែរ ថ្នាក់ខ្សែអក្សរ ជាជង់នៃតួអក្សរហើយអាចប្រើប្រតិបត្តិការ push_back () និង pop_back () ដូចជាថ្នាក់ជង់។

ការអនុវត្តន៍

កម្មវិធី C ++ សម្រាប់បង្កើតខ្សែអក្សរឡេស៊្រីហ្សិចសូលូសិន

#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"

កម្មវិធីចាវ៉ាសម្រាប់ធ្វើឱ្យខ្សែអក្សរឡេឡេកូដកូដល្អ

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"

ការវិភាគស្មុគស្មាញសម្រាប់ធ្វើឱ្យខ្សែសឺឡេសកូដដំណោះស្រាយដ៏អស្ចារ្យ

ស្មុគស្មាញពេលវេលា

O (n)៖ ដែល n គឺជាប្រវែងនៃខ្សែបញ្ចូល។ ដោយសារតែយើងកំពុងធ្វើឱ្យប្រសើរឡើងតាមរយៈខ្សែនៅក្នុងរង្វិលជុំតែមួយ។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលានឹងក្លាយជាលំដាប់នៃ n ។

ភាពស្មុគស្មាញនៃលំហ 

O (n)៖ យើងកំពុងប្រើជង់ដើម្បីរក្សាទុកលទ្ធផលចុងក្រោយរបស់យើង។ ដូច្នេះទំហំដែលបានប្រើនឹងមានលំដាប់នៃ n ពោលគឺ O (n) ។