ချိတ်ဆက်စာရင်း Cycle


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accolite အမေဇုံ MAQ Samsung
ချိတ်ဆက်စာရင်း ညွှန်ပြချက်နှစ်ခု

မာတိကာ

ပြProbleနာဖော်ပြချက်

“ ချိတ်ဆက်ထားသောစာရင်းသံသရာ” ပြproblemနာကသင်အားဆက်နွယ်သောစာရင်းတစ်ခုပေးထားသည်ဟုဖော်ပြသည်။ ၎င်းတွင်ကွင်းဆက်များပါ ၀ င်သလားရှာဖွေသည်မဟုတ်လော

ချိတ်ဆက်စာရင်း Cycle

 သံသရာနှင့်အတူချိတ်ဆက်စာရင်း

နမူနာ

1->2->3
No Loop

ရှင်းလင်းချက် ဆက်စပ်စာရင်း ဘာလို့လဲဆိုတော့အဲဒီလိုလုပ်မယ်ဆိုရင် node တစ်ခုတည်းကိုပဲညွှန်ပြမယ့်နှစ်ခုမရှိတော့ဘူး။ သို့မဟုတ်ပါက၎င်း၏ node နောက်တစ်ခုအဖြစ် Null ရှိသည့်မည်သည့် node မှရှိမည်မဟုတ်ပါ။

1->2->3->4
   ^     |
   |_____|
Yes there exists a loop

ရှင်းလင်းချက်။ ဟုတ်ကဲ့၊ loop တစ်ခုရှိတယ်။ ဘာလို့လဲဆိုတော့ value 1 ရှိ node နှင့် value 4 သည် node သည်တူညီတဲ့ node 2 ကိုညွှန်ပြသောကြောင့်ဖြစ်သည်။

Hashing နည်းလမ်းကိုအသုံးပြုခြင်း

algorithm

1. Initialize a hash table of type Node.
2. Start traversing the list. While node of the list is not null check if the current value is already stored in the hash table, if yes return true.
3. Else store it in the hash table and increment the pointer of the hash table.
4. Return false.

ငါတို့ဒီမှာ hash table ကိုသုံးနေတယ် HashSet ချိတ်ဆက်ထားသည့်စာရင်းတွင်ကွင်းဆက်ရှိမရှိကိုရှာဖွေရန်။ ကျွန်ုပ်တို့၏ခင်းကျင်းချက်တွင်ထပ်တူများပါရှိပါကရှာဖွေရန်လိုအပ်သည့်အခါတွင်လည်းအလားတူနည်းလမ်းကိုအသုံးပြုသည်။ ကျွန်ုပ်တို့ HashSet ကို အသုံးပြု၍ ကျွန်ုပ်တို့လိုချင်သောတန်ဖိုးကိုထပ်မံမပြောသင့်ပါ။ အဘယ်ကြောင့်ဆိုသော် HashSet သည်မည်သည့် element တစ်ခု၏ဥပမာတစ်ခုတည်းကိုသာသိုလှောင်ရန်ခွင့်ပြုသည်။ ဤလုပ်ဆောင်ချက်သည်ကျွန်ုပ်တို့၏အသုံးပြုမှုကိစ္စနှင့်ကိုက်ညီသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် HashSet ကို အသုံးပြု၍ ချိတ်ဆက်ထားသောစာရင်းကိုနှစ်ကြိမ်ထပ်ခါထပ်ခါရှာပါကစစ်ဆေးရန်သွားသည်။ ချိတ်ဆက်ထားသောစာရင်းတွင်ကွင်းဆက်တစ်ခုရှိနေသည်ကိုကျွန်ုပ်တို့သိသည်။ ဒါပေမယ့်ကျနော်တို့ချိတ်ဆက်စာရင်းဖြတ်သန်းသွားနိုင်လျှင်တူညီသော node ကိုနှစ်ကြိမ်မရှာဘဲ။ ဒြပ်စင်တစ်ခုမျှထပ်ခါတလဲလဲမရှိကြောင်းနှင့်ဆက်နွယ်နေသောစာရင်းတွင်ကွင်းဆက်မရှိပါ။

ကုဒ်

ချိတ်ဆက်ထားသောစာရင်းသံသရာကိုရှာဖွေရန် C ++ ပရိုဂရမ်

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    struct Node* next; 
}; 
  
void push(struct Node** head_ref, int new_data){ 
    struct Node* new_node = new Node; 
  
    new_node->data = new_data; 
  
    new_node->next = (*head_ref); 
  
    (*head_ref) = new_node; 
} 
  
bool detectCycle(struct Node* h){ 
    unordered_set<Node*> s; 
    while (h != NULL) { 
        if (s.find(h) != s.end()) 
            return true; 
  
        s.insert(h); 
  
        h = h->next; 
    } 
  
    return false; 
} 
  
int main(){ 
    struct Node* head = NULL; 
  
    push(&head, 20); 
    push(&head, 4); 
    push(&head, 15); 
    push(&head, 10); 
  
    head->next->next->next->next = head; 
  
    if(detectCycle(head)) 
        cout << "Loop found"; 
    else
        cout << "No Loop"; 
  
    return 0; 
}
Loop found

Linked list သံသရာကိုရှာဖွေရန် Java Program

import java.util.*;
  
class Cycle{ 
  
    static Node head;
    static class Node { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    static public void push(int new_data){ 
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
    } 
  
    static boolean detectCycle(Node h){ 
        HashSet<Node> s = new HashSet<Node>(); 
        while(h != null){ 
            if(s.contains(h)) 
                return true; 
  
            s.add(h); 
  
            h = h.next; 
        } 
  
        return false; 
    } 
  
    public static void main(String[] args){ 
        Cycle list = new Cycle(); 
  
        list.push(20); 
        list.push(4); 
        list.push(15); 
        list.push(10); 
  
        list.head.next.next.next.next = list.head; 
  
        if(detectCycle(head)) 
            System.out.println("Loop found"); 
        else
            System.out.println("No Loop"); 
    } 
}
Loop found

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) n သည်ပေးထားသောစာရင်းတွင်ထည့်သွင်းထားသော node များ၏နံပါတ်ဖြစ်သည်။ ကျွန်ုပ်တို့သည် HashSet (သို့) unordered_set ကိုအသုံးပြုပြီး O (1) ကိုသွင်းခြင်းနှင့်ရှာဖွေခြင်းကိုကျွန်ုပ်တို့အချိန် linear ရှုပ်ထွေးမှုရရှိရန်ခွင့်ပြုထားသည်။

အာကာသရှုပ်ထွေးမှု

အို (N) ဘာလို့လဲဆိုတော့ကျွန်တော်တို့က HashSet ကိုသုံးပြီးအဆိုးဆုံးကိစ္စကတော့ N node တွေထည့်ရမယ်။

Floyd's Cycle-Finding Algorithm

ခြေလှမ်းများ

  1. နှေးနှေးမြန်မြန်နှစ်ခုထောက်ပြသုံးပါ။
  2. နှေးသော pointer ကို node 1 ဖြင့်ရွှေ့။ အဆင့်တစ်ခုစီတွင် 2 ကိုအစာရှောင်ပါ။
  3. အကယ်၍ pointer နှစ်ခုလုံးသည်မည်သည့်နေရာ၌မဆိုတွေ့ဆုံကြလျှင်၊

algorithm

1. Initialize two pointers fast and slow as head of the list.
2. Traverse while fast or slow is not null. Increment slow by 1 node and fast by 2 nodes.
3. Check at each traversal if slow equals to fast, print "Loop found" and return 1.
4. Else return 0 and print "No loop".

ကုဒ်

ချိတ်ဆက်ထားသောစာရင်းသံသရာကိုရှာဖွေရန် C ++ ပရိုဂရမ်

#include <bits/stdc++.h> 
using namespace std; 
  
class Node{ 
public: 
    int data; 
    Node* next; 
}; 
  
void push(Node** head_ref, int new_data){ 
    Node* new_node = new Node(); 
  
    new_node->data = new_data; 
  
    new_node->next = (*head_ref); 
  
    (*head_ref) = new_node; 
} 
  
int detectCycle(Node* list){ 
    Node *slow = list, *fast = list; 
  
    while (slow && fast && fast->next) { 
        slow = slow->next; 
        fast = fast->next->next; 
        if (slow == fast) { 
            cout << "Found Loop"; 
            return 1; 
        } 
    } 
    return 0; 
} 
  
int main(){ 
    Node* head = NULL; 
  
    push(&head, 20); 
    push(&head, 4); 
    push(&head, 15); 
    push(&head, 10); 
  
    head->next->next->next->next = head; 
    if(!detectCycle(head))
        cout<<"No Loop"; 
  
    return 0; 
} 
Loop found

Linked list သံသရာကိုရှာဖွေရန် Java Program

class Cycle{ 
  
    Node head; 
  
    class Node { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    public void push(int new_data){ 
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
    } 
  
    int detectCycle(){ 
        Node slow = head, fast = head; 
        while (slow != null && fast != null && fast.next != null) { 
            slow = slow.next; 
            fast = fast.next.next; 
            if (slow == fast) { 
                System.out.println("Found loop"); 
                return 1; 
            } 
        } 
        return 0; 
    } 
  
    public static void main(String args[]){ 
        Cycle list = new Cycle(); 
  
        list.push(20); 
        list.push(4); 
        list.push(15); 
        list.push(10); 
  
        list.head.next.next.next.next = list.head; 
  
        if(list.detectCycle()==0)
             System.out.println("No loop");  
    }  
}
Loop found

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ဘယ်မှာ N သည်ပေးထားသောစာရင်းထဲတွင်ထည့်သွင်း node များ၏အရေအတွက်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာအပိုအာကာသကိုသုံးခဲ့တယ် ဒီမှာ node တစ်ခုချင်းစီနှင့်ပတ်သက်ပြီးမည်သည့်အပိုသတင်းအချက်အလက်မျှမသိမ်းဆည်းပါ။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်စဉ်ဆက်မပြတ်အာကာသရှုပ်ထွေးရှိသည်။

ချိတ်ဆက်ထားသောစာရင်းဒေတာဖွဲ့စည်းပုံကိုပြုပြင်မွမ်းမံခြင်းမရှိဘဲသွားရောက်ကြည့်ရှု node များ

ဆက်နွယ်စာရင်းသံသရာ detect လုပ်ဖို့ Algorithm

1. Initialize an extra node.
2. Traverse through the list while the head is not null. If head->next is null i.e. there is no cycle, return false.
3. Else if head->next is equal to the extra node, return true.
4. Create a node to store the pointer of the next node.
5. Store extra node in a pointer to the next node.
6. Update the head to the next node.
7. Return false.

ဤတွင်ကျွန်ုပ်တို့သည်ယာယီ node တစ်ခုကိုဖန်တီးခဲ့ပြီး node အားလုံးကိုဤ node အသစ်သို့ညွှန်ပြသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်အချိန်ကာလတစ်ခုအတွင်း၌ယာယီ node ကိုညွှန်ပြပြီးသော node တစ်ခုကိုတွေ့မိလျှင်။ နောက်ဆက်နွယ်နေသောစာရင်းတွင်သံသရာတစ်ခုမပါ ၀ င်သော loop တစ်ခုရှိသေးသည်ကိုကျွန်ုပ်တို့သိသည်။

ကုဒ်

ချိတ်ဆက်ထားသောစာရင်းသံသရာကိုရှာဖွေရန် C ++ ပရိုဂရမ်

#include <iostream> 
using namespace std; 
  
struct Node{ 
    int key; 
    struct Node* next; 
}; 
  
Node* newNode(int key){ 
    Node* temp = new Node; 
    temp->key = key; 
    temp->next = NULL; 
    return temp; 
} 
  
bool detectCycle(Node* head){ 
  
    Node* temp = new Node; 
    while (head != NULL) { 
  
        if(head->next == NULL){ 
            return false; 
        } 
  
        if(head->next == temp){ 
            return true; 
        } 
  
        Node* nex = head->next; 
  
        head->next = temp; 
  
        head = nex; 
    } 
  
    return false; 
} 
  
int main(){ 
    Node* head = newNode(1); 
    head->next = newNode(2); 
    head->next->next = newNode(3); 
    head->next->next->next = newNode(4); 
    head->next->next->next->next = newNode(5); 
  
    head->next->next->next->next->next = head->next->next; 
  
    bool found = detectCycle(head); 
    if(found) 
        cout << "Loop Found"; 
    else
        cout << "No Loop"; 
  
    return 0; 
}
Loop found

Linked list သံသရာကိုရှာဖွေရန် Java Program

class Cycle{ 
  
    static class Node { 
        int key; 
        Node next; 
    }; 
  
    static Node newNode(int key){ 
        Node temp = new Node(); 
        temp.key = key; 
        temp.next = null; 
        return temp; 
    } 
  
    static void printList(Node head){ 
        while (head != null) { 
            System.out.print(head.key + " "); 
            head = head.next; 
        } 
        System.out.println(); 
    } 
  
    static boolean detectCycle(Node head){ 
  
        Node temp = new Node(); 
        while (head != null) { 
  
            if(head.next == null){ 
                return false; 
            } 
  
            if (head.next == temp) { 
                return true; 
            } 
  
            Node nex = head.next; 
  
            head.next = temp; 
  
            head = nex; 
        } 
  
        return false; 
    } 
  
    public static void main(String args[]){ 
        
        Node head = newNode(1); 
        head.next = newNode(2); 
        head.next.next = newNode(3); 
        head.next.next.next = newNode(4); 
        head.next.next.next.next = newNode(5); 
  
        head.next.next.next.next.next = head.next.next; 
  
        boolean found = detectCycle(head); 
        if (found) 
            System.out.println("Loop Found"); 
        else
            System.out.println("No Loop"); 
    } 
}
Loop found

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ဘယ်မှာ N သည်ပေးထားသောစာရင်းထဲတွင်ထည့်သွင်း node များ၏အရေအတွက်သည်။

အာကာသရှုပ်ထွေးမှု

အို (၁) ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာအပိုအာကာသကိုသုံးခဲ့တယ် ဤတွင်ကျွန်ုပ်တို့သည်အခြား node များအားလုံးညွှန်ပြသည့်တစ်ခုတည်းသော node အသစ်တစ်ခုကိုဖန်တီးခဲ့သည်။