Bağlı bir Strinq siyahısının Palindrom təşkil etdiyini yoxlayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Capital One Cisco Facebook google Ağır IXL microsoft Nutanix Kahin Paytm Snapchat Über Yandex
Bağlı siyahı Əlaqəli siyahı SimBaxılıb 233

Problem bəyanat

"Bağlı bir Strinq siyahısının Palindrom təşkil edib etmədiyini yoxlayın" problemində biz verdik əlaqəli siyahı simli məlumatların idarə olunması. Verilənlərin palindrom təşkil edib etmədiyini yoxlamaq üçün bir proqram yazın.

misal

ba->c->d->ca->b
1

Explanation: Yuxarıdakı nümunədə “bacdcab” sətrinin palindrom olduğunu görə bilərik

Yanaşma

Hər bir qovşaqda bir simli olan əlaqəli bir siyahı verilir. Bağlı siyahıdakı məlumatların palindrom əmələ gətirdiyini yoxlamalıyıq. Bir simli a palindrom geriyə kimi eyni irəli oxuyarsa. Məsələn, “bacdcab” rəqəmi palindromdur. Bağlı bir siyahı, irəli və geriyə keçərkən eyni elementlər sırasına sahib olduqları halda palindromlar əmələ gətirir.

Alqoritm

  1. Boş bir simli başladın.
  2. Bağlı siyahıdan keçin və əlaqəli siyahıda olan bütün elementləri həmin sətirdə saxlayın.
  3. Müvafiq birinci və son simvolların bərabər olub olmadığını yoxlamaq üçün əlaqəli siyahıdan keçin. Bir nöqtədə bərabər deyilsə, bu palindrom meydana gətirməyəcəkdir.

Həyata keçirilməsi

Bağlı bir Strinq siyahısının Palindrome təşkil etdiyini yoxlamaq üçün C ++ Proqramı

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

class MyLinkedList {
public:
    struct ListNode {
        ListNode *next;
        string val;
        ListNode(string a): next(NULL), val(a){}
    };
    ListNode *head;

    MyLinkedList():head(NULL) {
    }
    
    void addAtHead(string val) {
        ListNode *node = new ListNode(val);
        node->next = head;
        head = node;
    }
    
    bool isPlalindrome(){
    	string str = "";
    	ListNode* ptr = head;
    	while(ptr){
    		str+=ptr->val;
    		ptr = ptr->next;
    	}
    	int n = str.size();
    	for(int i=0;i<n/2;i++){
    		if(str[i]!=str[n-i-1]){
    			return false;
    		}
    	}
    	return true;
    }

    void print_list(){
    	ListNode* node = head;
    while(node){
      cout<<node->val<<" ";
      node = node->next;
    }
        cout<<endl;
  }
};

int main(){
  MyLinkedList *list = new MyLinkedList();
  list->addAtHead("b");
  list->addAtHead("ca");
  list->addAtHead("d");
  list->addAtHead("c");
  list->addAtHead("ba");
  
  cout<<list->isPlalindrome();
}

Bağlı bir Strinq siyahısının Palindrome təşkil etdiyini yoxlamaq üçün Java Proqramı

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

public class Main{
  
  public static void main (String[] args) throws java.lang.Exception{
    
    MyLinkedList obj = new MyLinkedList();
    obj.addAtHead("b");
    obj.addAtHead("ca");
    obj.addAtHead("d");
    obj.addAtHead("c");
    obj.addAtHead("ba");
    
    System.out.println(obj.isPalindrome());
  }
  
  public static class MyLinkedList {
    
      class Node{
          Node next = null;
          String val = "";
          
          public Node(String val){
              this.val = val;
          }
      }
      
      private Node head;
      private int size;

      public MyLinkedList() {
          this.head = null;
          this.size = 0;
      }
      
      
      public void addAtHead(String val) {
          Node node = new Node(val);
          if(this.size == 0){
              this.head = node;
          }
          else{
              node.next = this.head;
              this.head = node;
          }
          this.size++;
      }
      
    public boolean isPalindrome(){
      String str="";
      Node curr = head;
      while(curr!=null){
        str+=curr.val;
        curr = curr.next;
      }
      
      int n = str.length();
      for(int i=0;i<n/2;i++){
        if(str.charAt(i)!=str.charAt(n-i-1)){
          return false;
        }
      }
      return true;
    }

    public void printList(){
      Node curr = head;
      while(curr!=null){
        System.out.print(curr.val+" ");
        curr = curr.next;
      }
      System.out.println("");
    }
      
  }
}
1

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara n verilmiş əlaqəli siyahıda mövcud olan qovşaq sayıdır. Buradakı bütün dəyərləri bir sətrə əlavə edirik və palindrom vəziyyəti üçün bu sətri yoxlayırıq.

Kosmik Mürəkkəblik

O (n) çünki verilmiş bir sətir siyahısının bütün qovşaqlarının dəyərlərini birləşdirərək meydana gələn bir sətirdən istifadə edirik.

Translate »