Վավեր Palindrome Leetcode լուծում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon խնձոր Bloomberg facebook Microsoft Պատգամախոս Վայֆայեր
String Երկու ցուցիչ

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

Տրված ա լարային, մենք պետք է որոշենք, արդյոք դա պալինդրոմ է ՝ հաշվի առնելով միայն այբբենական թվերը, այսինքն ՝ միայն թվերը և այբուբենները: Մենք նաև ստիպված ենք անտեսել այբուբենի նիշերի դեպքերը:

Օրինակ

"A man, a plan, a canal: Panama"
true

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

«AmanaplanacanalPanama» - ն գործող պալինդրոմ է:

"race a car"
false

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

«Raceacar» - ը պալինդրոմ չէ:

Միամիտ մոտեցում (համեմատելով հակադարձի հետ)

Ստուգելու համար, թե արդյոք պարանը պալինդրոմ է, թե ոչ, մենք կարող ենք պարզապես հետ շեղել այն և համեմատել այն բուն տողի հետ: Հակադարձելուց հետո, եթե այն մնում է հավասար, ապա տրված տողը պալինդրոմ է:
Այս խնդրում մենք պետք է անտեսենք բոլոր նիշերը, բացի այբուբեններից և թվերից: Այսպիսով, դրա համար մենք կարող ենք զտել տրված տողը և զտված տողը պահպանել նոր փոփոխականի մեջ ՝ հեռացնելով բոլոր անցանկալի նիշերը: Եկեք օրինակ վերցնենք.

Վավեր Palindrome Leetcode լուծում

 

 

 

 

Մենք կարող ենք տեսնել, որ զտված տողը և հակադարձված զտված տողը հավասար չէ, ուստի այն վավեր պալինդրոմ չէ:

Իրականացում Palindrome Leetcode լուծման համար

C ++ ծրագիր

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

bool isAlphaNum(char c)
{
    if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
        return true;
    return false;
}
    
char lowerCase(char c)
{
    if(65<=c && c<=90)
        return c+32;
    else 
        return c;
}
    
bool isPalindrome(string s) 
{
    string input;

    for(char c:s)
    {
        if(isAlphaNum(c))
            input+= lowerCase(c);
    }

    string reversed=input;
    reverse(reversed.begin(),reversed.end());

    if(input==reversed) return true;
    else return false;

}

int main() 
{
    string s="A man, a plan, a canal: Panama";
    if(isPalindrome(s))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

Java ծրագիր

import java.lang.*;

class Rextester
{  
    static boolean isAlphaNum(char c)
    {
        if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
            return true;
        else
            return false;
    }
    
    static char lowerCase(char c)
    {
        if(65<=c && c<=90)
            return (char)(c+32);
        else 
            return c;
    }
    
    public static boolean isPalindrome(String s) 
    {
       StringBuffer buf= new StringBuffer();
        
       for(char c: s.toCharArray())
       {
           if(isAlphaNum(c))
               buf.append(lowerCase(c));
       }
        
        String input,reversed;
        input= buf.toString();
        reversed= buf.reverse().toString();
        
        if(input.equals(reversed))
            return true;
        else 
            return false;
        
    }
    
    public static void main(String args[])
    {
       String s="A man, a plan, a canal: Panama";
       System.out.println(isPalindrome(s));   
    }
}
true

Բարդության վերլուծություն Palindrome Valid կոդերի լուծման համար

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

Վրա): n տրված տողի երկարությունն է: Մենք պետք է գծերը կրկնենք գծային գծով: Ուստի ժամանակի բարդությունը կլինի O (n):

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

Վրա): Մեզ պետք է O (n) լրացուցիչ տարածք զտված լարը և հակադարձ տողը պահելու համար:

Օպտիմիզացված մոտեցում (օգտագործելով երկու ցուցիչ)

Վերը նշված մոտեցման մեջ մենք զտեցինք տրված տողը և ավելորդ տարածք օգտագործեցինք այն պահելու համար: Կարող ենք նաև օգտագործել երկու ցուցիչ ՝ ստուգելու համար, արդյոք դա պալինդրոմ է, թե ոչ, և անհրաժեշտ չէ այն զտել կամ պահպանել ՝ ստեղծելով լրացուցիչ հիշողություն:

1. Այն, ինչ մենք կարող ենք անել, վերցնել ցուցիչի երկու փոփոխական, Սկիզբ և վերջ և մատնանշեք դրանք մուտքային լարի երկու ծայրերով:
2. Այժմ տեղափոխեք այն Սկիզբ ցուցիչ աջ, այնպես որ այն մատնանշում է այբբենական թվանշանը: Նմանապես տեղափոխվել վերջ ցուցիչը ձախից, այնպես որ այն նաև մատնանշում է այբբենական թվանշանը:
3. Այժմ ստուգեք ՝ արդյոք երկու նիշերն էլ նույնն են, թե ոչ (անտեսելով դեպքերը).

  • Եթե ​​դա հավասար չէ, ապա մենք գիտենք, որ տողը վավեր պալինդրոմ չէ, ուստի կեղծ վերադարձ:
  • Այլևս շարունակեք հաջորդ կրկնությունը և կրկնել երկու ցուցիչները տեղափոխելու նույն գործընթացը `մինչև հաջորդ ալֆանային թվանշանը նշելու համար սկսել.

4. Օղակի ավարտից հետո նշվում է, որ լարը պալինդրոմ է, ուստի վերադառնում է true:

Իրականացում Palindrome Leetcode լուծման համար

C ++ ծրագիր

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

bool isAlphaNum(char c)
{
    if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
        return true;
    return false;
}
    
char lowerCase(char c)
{
    if(65<=c && c<=90)
        return c+32;
    else 
        return c;
}
    
bool isPalindrome(string s) 
{
        int start=0,end=s.size()-1;
        
        while(start<end)
        {
            while(start<end && !isAlphaNum(s[start])) start++;
            while(start<end && !isAlphaNum(s[end])) end--;
           
            if(lowerCase(s[start])!=lowerCase(s[end]))  return false; 
            
            start++;
            end--;
        }
        
        return true;

}

int main() 
{
    string s="A man, a plan, a canal: Panama";
    if(isPalindrome(s))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

Java ծրագիր

import java.lang.*;

class Rextester
{  
    static boolean isAlphaNum(char c)
    {
        if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
            return true;
        else
            return false;
    }
    
    static char lowerCase(char c)
    {
        if(65<=c && c<=90)
            return (char)(c+32);
        else 
            return c;
    }
    
    public static boolean isPalindrome(String s) 
    {
       int start=0,end=s.length()-1;
        
        while(start<end)
        {
            while(start<end && !isAlphaNum(s.charAt(start))) start++;
            while(start<end && !isAlphaNum(s.charAt(end))) end--;
           
            if(lowerCase(s.charAt(start))!=lowerCase(s.charAt(end)))  
                return false; 
            
            start++;
            end--;
        }
        
        return true;
        
    }
    
    public static void main(String args[])
    {
       String s="A man, a plan, a canal: Panama";
       System.out.println(isPalindrome(s));   
    }
}
true

Բարդության վերլուծություն Palindrome Valid կոդերի լուծման համար

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

Վրա): Մենք լարի յուրաքանչյուր նիշ ենք այցելում միայն մեկ անգամ: Ուստի ժամանակի բարդությունը O (n) է:

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

O (1): Մեզ այստեղ լրացուցիչ հիշողության կարիք չկա: