Эки Байланышкан Тизменин кесилиш чекитин алуу үчүн функцияны жаз  


Кыйынчылык деңгээли жеңил
Көп суралган Accolite Amazon DE Shaw Factset Goldman Sachs MakeMyTrip MAQ Microsoft Qualcomm Snapdeal виза Zopper
Байланышкан тизме

Маселени билдирүү  

"Эки Байланышкан Тизменин кесилиш чекитин алуу функциясын жаз" маселеси сизге эки байланышкан тизме берилгенин билдирет. Бирок алар көз карандысыз байланышкан тизмелер эмес. Алар кандайдыр бир учурда туташып турат. Эми ушул эки тизменин кесилишкен жерин табуу керек.

мисал  

Эки Байланышкан Тизменин кесилиш чекитин алуу үчүн функцияны жаз

1 -> 2
      \
        5 -> 6
      /
3 -> 4
Point of intersection: 5

Түшүндүрмө: Кириште көрсөтүлгөн эки шилтеме тизмеси бар, алар 1, 2, 5, 6 жана 3, 4, 5, 6. Алардын экөө тең түйүнгө бириктирилген, алардын мааниси 5ке барабар. Ошентип, жыйынтык 5 болуп саналат.

жакындоо  

Маселе жөнөкөй. Экөө бар байланышкан тизмелер бирок алар кандайдыр бир мезгилде бириктирилген же өз ара байланыштуу. Биригүү чекитине чейин, эки шилтеме берилген тизмелердин ар башка түйүндөрү бар жана кошулуу түйүнүнөн кийин. Алар бир тизме менен көрсөтүлгөн. Ошентип, маселе мындай түйүндү (же чекитти) кантип тапсак болот? Көйгөйгө жооптор / чечимдер көп болушу мүмкүн. Бирок эң жөнөкөй жолу - байланышкан тизмелердин узундугун табуу. Чечим жөнөкөй болгон сайын, убакыттын өтүшүнө жетиштүү натыйжа бербейт. Бирок бул жерде андай эмес. Бул чечим натыйжалуу жана жөнөкөй.

түшүндүрүү

Бул чечимде, биз эки байланышкан тизмелердин узундугун табабыз. Андан кийин узунураак байланышкан тизменин башын алдыга жылдырабыз (lenA - lenB) түйүндөр. Бул жерде lenA жана lenB тиешелүүлүгүнө жараша А жана В тизмесинин узундугун билдирет. Бирок эмне үчүн биз муну жасадык?

ошондой эле
Санды он алтылыктын Leetcode чечимине айландыруу

Жалпы байланышкан тизменин узундугун z деп эсептесеңиз, узунураак тизменин узундугун x + z жана кыска тизмектелген тизмедеги y + z. Ошентип, ушул убакка чейин биз көчүп келгенбиз lenA - lenB узунураак байланышкан тизмеде. Ушул (x + z - (y + z)) = x - y. Демек, биз турган түйүн дагы узун болгонго чейин, биз узунураак байланышкан тизмеден өттүк y бириктирүүчү түйүндөн кыска тизмектелген тизмектин башчысы. Андан кийин биз эки шилтеме берилген тизмелер боюнча бир эле мезгилде жылып, учурдагы эки түйүндүн тең экендигин текшеребиз. Эгер ошондой болсо, анда биз кесилиш чекитин таптык. Бирок, эгерде биз байланышкан тизмелердин аягына чейин ушул сыяктуу пункттарды таппасак. Андан кийин бул алардын кесилиш чекитинин жоктугун билдирет.

Ошентип, эки Байланышкан Тизменин кесилиш чекитин алуу функциясын ушундайча жазабыз.

коду  

Байланышкан эки тизмектин кесилишин табуу үчүн C ++ коду

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

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

int length(ListNode *tmp){
    int cnt =  0;
    while(tmp != NULL){
        cnt++;
        tmp = tmp->next;
    }
    return cnt;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = length(headA);
    int lenB = length(headB);
    
    if(lenA > lenB){
        int cnt = lenA - lenB;
        while(cnt--)
            headA = headA->next;
    } else {
        int cnt = lenB - lenA;
        while(cnt--)
            headB = headB->next;
    }
    while(headA != NULL && headB != NULL){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  ListNode *headB = create(3);
  headB->next = create(4);
  headA->next->next = headB->next->next = create(5);
  headA->next->next->next = headB->next->next->next = create(6);

  cout<<"Intersection at node: ";
  cout<<getIntersectionNode(headA, headB)->data<<endl;
}
Intersection at node: 5

Байланышкан эки тизменин кесилишин табуу үчүн Java коду

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static int length(ListNode tmp){
        int cnt =  0;
        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        return cnt;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        if(lenA > lenB){
            int cnt = lenA - lenB;
            while(cnt-- > 0)
                headA = headA.next;
        } else {
            int cnt = lenB - lenA;
            while(cnt-- > 0)
                headB = headB.next;
        }
        while(headA != null && headB != null){
            if(headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;        
    }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    ListNode headB = create(3);
    headB.next = create(4);
    headA.next.next = headB.next.next = create(5);
    headA.next.next.next = headB.next.next.next = create(6);

    System.out.print("Intersection at node: ");
    System.out.print(getIntersectionNode(headA, headB).data);
  }
}
Intersection at node: 5

Комплекстик анализ  

Убакыт татаалдыгы

O (N), анткени биз байланышкан тизмелердеги түйүндөрдүн ар бирине так бир жолу чуркадык. Эгерде кесилиш чекити бар болсо, анда ошол түйүнгө жеткенде биз аны кайтарабыз. Башка ар бир түйүн бир жолу гана өтөт. Бул убакыттын татаалдыгы сызыктуу экендигин далилдейт.

ошондой эле
Байланышкан тизме цикли

Космостун татаалдыгы

O (1), Бул алгоритм туруктуу мейкиндикти гана ээлей турган шилтеме берилген тизмелердин узундугу.