每日Leetcode—算法（14）

141.环形链表

算法（快慢指针）：

def hasCycle(self, head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

155.最小栈

算法一：

class MinStack:
    def __init__(self):
        self.l = []

    def push(self, x: int) -> None:
        self.l.append(x)

    def pop(self) -> None:
        self.l.pop()

    def top(self) -> int:
        if not self.l:
            return 'error'
        else:
            return self.l[-1]

    def getMin(self) -> int:
        return min(self.l)

算法二：

class MinStack:
    def __init__(self):
        self.stack = []
        self.min = None
        
    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.min or self.min > x:
            self.min = x

    def pop(self) -> None:
        popItem = self.stack.pop()
        if len(self.stack) == 0:
            self.min= None
            return popItem

        if popItem == self.min:
            self.min == self.stack[0]
            for i in self.stack:
                if i < self.min:
                    self.min = i
        return popItem

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min

167. 两数之和 II - 输入有序数组

算法：

def twoSum(self, numbers, target):
    dic = {}           #用字典非常方便
    r = []
    for i in range(len(numbers)):
        if numbers[i] in dic.keys():       #如数组的值在字典中，说明之前的数已经被目标值减出来了
            r.append(dic[numbers[i]] + 1)
            r.append(i+1)
            return r           #返回下标
        dic[target - numbers[i]] = i          #字典的key为减出来的数，
    return None

160.相交链表

算法一：

def getIntersectionNode(self, headA, headB):
    p1 = headA
    p2 = headB
    while p1 != p2:
        p1 = headB if p1 == None else p1.next    #遍历两个链表
        p2 = headA if p2 == None else p2.next
    return p1

分析：该算法是将两个链表当做两条线段p1和p2，因此有p1+p2=p2+p1。例如
p1： A,E,C,H，
p2：B,S,W,C,H，
那么相加后分别为
A,E,C,H,B,S,W,C,H
B,S,W,C,H,A,E,C,H
可以看出，字母重合的地方就是本题所要求的交点。如果没有交点，则会返回None

算法二：

def getIntersectionNode(self, headA, headB):
    lenA, lenB = 0, 0
    pA = headA
    pB = headB
    while pA:      #计算pA的长度
        pA = pA.next
        lenA += 1
    while pB:      #计算pB的长度
        pB = pB.next
        lenB += 1
    if lenA>lenB:      #对较长的链进行裁剪
        for i in range(lenA - lenB):
            pA = pA.next
    if lenB>lenA:      #对较长的链进行裁剪
        for i in range(lenA - lenB):
            pB = pB.next
    while pA!=pB:     #逐一比对
        pA = pA.next
        pB = pB.next
    return pA

分析：该算法利用了相交链表的最后几个数字会重合的特点。首先求出单个链表的长度，对较长的链表进行裁剪，使得两个链表长度一致，例如
p1： A,E,C,H，
p2：B,S,W,C,H，
对p2进行裁剪后得到
p1： A,E,C,H，
p2： S,W,C,H，
最后进行逐一比对，得到相交点，或者None。