三个月算法进阶--day31

2020-09-23 约 565 字预计阅读 2 分钟次阅读

判断是否出现过用集合比列表更好

链表同样适用，存储的为结点，可判断结点此前是否被访问过

链表的快慢指针

快两步，慢一步，时间复杂度O(n+k)

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if head == None or head.next == None:
            return False
        slow = head
        fast = head.next
        while slow != fast:
            if fast == None or fast.next == None:
                return False
            slow = slow.next
            fast = fast.next.next
        return True

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False
        ptr1 = head
        ptr2 = head.next
        go = False
        while ptr2:
            if ptr2 == ptr1:
                ans = True
                break
            if go:
                ptr1 = ptr1.next
            ptr2 = ptr2.next
            go = False if go else True
        else:
            ans = False
        return ans

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = head
        fast = head
        while fast:
            fast = fast.next
            if fast:
                fast = fast.next
            if fast == slow:
                return True
            slow = slow.next
        return False

链表的劣势需要灵活应用双指针

无法高效获取长度，无法根据偏移快速访问元素，是链表的两个劣势。

获取倒数第k个元素，获取链表中间元素，判断链表是否存在环

排序之归并排序Merge Sort

1个数据项自然是排好序的

def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    middle = len(lst) // 2
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    merged.extend(right if right else left)
    return merged

分裂的时间复杂度为O(log n)，归并的时间复杂度为O(n)

算法稳定，额外一倍的存储空间

优化：取消切片操作

快速排序

原地排序，左右标交换数据项

def quickSort(alist):
    quickSortHelper(alist, 0, len(alist)-1)

def quickSortHelper(alist, first, last):
    if first < last:
        splitpoint = partition(alist, first, last)
        quickSortHelper(alist, first, splitpoint-1)
        quickSortHelper(alist, splitpoint+1, last)

def partition(alist, first, last):
    pivotvalue = alist[first]
    leftmark = first + 1
    rightmart = last
    done = False
    while not done:
        while leftmark <= rightmart and alist[leftmark] <= pivotvalue:
            leftmark += 1
        while leftmark <= rightmart and alist[rightmart] >= pivotvalue:
            rightmart -= 1
        if rightmart < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmart]
            alist[rightmart] = temp
    temp = alist[first]
    alist[first] = alist[rightmart]
    alist[rightmart] = temp
    return rightmart

极端情况，时间复杂度退化到O(n^2) 优化：中值的选取–“三点取样”

目录