Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: вежбе - XIII недеља

Задатак 1

За дат почетак повезане листе, одредити да ли повезана листа има петљу. Повезана листа има петљу ако можемо да дођемо до неког чвора поново пратећи следеће чворове. Вратити True ако постоји петља у повезној листи, у супротном вратити False.

Решење - $O(N)$ меморија
# Дефиниција чвора листе:
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def hasCycle(self, head):
        skup_vidjenih = set()

        curr = head
        while curr:
            if curr in skup_vidjenih:
                return True
            else:
                skup_vidjenih.add(curr)

            curr = curr.next
        
        return False

# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
##head.next.next.next.next = head.next

#print(head.hasCycle(head))
Решење - $O(1)$ меморија
# Дефиниција чвора листе:
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

    def hasCycle(self, head):
        slow, fast = head, head


        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                return True

        return False

# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)
#head.next.next.next.next = head.next

#print(head.hasCycle(head))

Задатак 2

За дат почетак повезане листе, вратити чвор у средини повезане листе. Ако повезана листа има паран број чворова, вратити други у средини.

Решење - један пролаз кроз листу
# Дефиниција чвора листе.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


def middleNode(self, head):
	slow, fast = head, head

	while fast and fast.next:

	    slow = slow.next
	    fast = fast.next.next

	return slow
        
Решење - два пролаза кроз листу
# Дефиниција чвора листе.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


def middleNode(self, head):
	# тражимо дужину листе
        curr = head
        duzina = 0
        while curr:
            duzina+=1
            curr=curr.next

        # прелазимо до половине листе
        curr = head
        for i in range(duzina//2):
            curr=curr.next

        return curr

Задатак 3

За дат почетак сортиране повезане листе, избацити чворове тако да се свака вредност појављује само једном, и вратити нови почетак.

Решење без $dummy$ чвора
# Дефинисија чвора листе:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def deleteDuplicates(self, head):
        curr = head
        while curr and curr.next:
            if curr.val == curr.next.val:
                curr.next = curr.next.next
            else:
                curr = curr.next
        
        return head
    
# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(4)
#head.next.next.next = ListNode(6)
#head.next.next.next.next = ListNode(6)

#head = ListNode(2, ListNode(4, ListNode(4, ListNode(6, ListNode(6)))))

#newHead = head.deleteDuplicates(head)

#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
Решење са $dummy$ чвором
# Дефинисија чвора листе:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def deleteDuplicates(self, head):
        dummy = ListNode(float('inf'),head)

        prev, curr = dummy, head

        while curr:
            if prev.val == curr.val:
                prev.next = curr.next
            else:
                prev = prev.next

            curr = curr.next

        return dummy.next
    
    
# Тест пример:    
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(4)
#head.next.next.next = ListNode(6)
#head.next.next.next.next = ListNode(6)

#newHead = head.deleteDuplicates(head)

#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)


Задатак 4

За дат почетак повезане листе, избрисати н-ти чвор са краја листе, и вратити нови почетак листе.

Решење - два пролаза кроз листу
# Дефиниција чвора листе:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def removeNthFromEnd(head,n):

    curr = head
    duzina = 0
    while curr:
        duzina+=1
        curr = curr.next

    dummy = ListNode(0,head)
    prev, curr = dummy, head

    for i in range(duzina - n):
        prev = curr
        curr = curr.next

    prev.next = curr.next
        
    return dummy.next

# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)

#newHead = removeNthFromEnd(head, 2)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)

Решење - један пролаз кроз листу
# Дефиниција чвора листе:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head,n):
    fast = head
        
    for i in range(n):
        fast = fast.next


    dummy = ListNode(val=0,next=head)
    prev, curr= dummy, head

    while fast:
        prev = curr
        curr = curr.next
        fast = fast.next

        
    prev.next = curr.next

    return dummy.next

# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)

#newHead = removeNthFromEnd(head, 2)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)

Задатак 5

За дата два почетка повезаних листи, вратити први њихов заједнички чвор. Уколико немају заједнички чвор, вратити None.

Решење - $O(N)$ меморија
# Дефиниција чвора листе.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

def getIntersectionNode(headA, headB):

        # пролазимо кроз листу А и чувамо све чворове у скуп
        skup_vidjenih = set()
        while headA:
            skup_vidjenih.add(headA)
            headA = headA.next

        # пролазимо кроз листу B и када наиђемо на чвор који је у скупу
        # то је први заједнички
        while headB:
            if headB in skup_vidjenih:
                return headB
            skup_vidjenih.add(headB)
            headB = headB.next

        return None
Решење - $O(1)$ меморија
# Дефиниција чвора листе.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

ddef getIntersectionNode(headA, headB):

        # израчунај дужину листе A
        lA, curr = 0, headA
        while curr:
            lA+=1
            curr=curr.next
        
        # израчунај дужину листе B
        lB, curr = 0, headB
        while curr:
            lB+=1
            curr=curr.next
        

        # за дужи, head пребаци за разлику места
        if lA > lB:
            for i in range(lA-lB):
                headA = headA.next
                
        if lA < lB:
            for i in range(-(lA-lB)):
                headB = headB.next
        
        # крећемо од новог head-a и старог head-a
        # скачемо за једно место
        # и када су једнаки, ту се секу
        while headA and headB:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
            
        return None

Задатак 6

За дат почетак повезане листе, вратити почетак изокренуте листе.

Рекуризвно решење
# Дефиниција чвора листе:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverseList(head):
    if head ==None or head.next == None:
        return head

    newHead = head.next
    if head.next:
        newHead = reverseList(head.next)
        head.next.next = head

    head.next = None

    return newHead

# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)

#newHead = reverseList(head)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
#print(newHead.next.next.next.val)
Итеративно решење
# Дефиниција чвора листе:
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverseList(head):
    prev, curr = None, head
    while curr:
        tmp = curr.next
        curr.next = prev

        prev = curr
        curr = tmp

    return prev

# Тест пример:
#head = ListNode(2)
#head.next = ListNode(4)
#head.next.next = ListNode(6)
#head.next.next.next = ListNode(8)

#newHead = reverseList(head)
#print(newHead.val)
#print(newHead.next.val)
#print(newHead.next.next.val)
#print(newHead.next.next.next.val)

Задатак 7

За дат почетак повезане листе, вратити True ако је листа палиндром у супротном вратити False.

Решење
# Дефинисија чвора листе.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

def isPalindrome(self, head):

        # nadjemo polovinu
        slow,fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        #od polovine do kraja izokrenemo
        prev, curr = None, slow
        while curr:
            tmp = curr.next
            curr.next = prev
            prev = curr
            curr = tmp
            
        # gledamo cvor po cvor od pocetka i kraja
        # i uporedjujemo vrednosti
        left, right = head, prev
        while left and right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next        
        return True