2020-08-27

# 234. 回文链表
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None or head.next is None:
            return True
        # 计算长度
        length = 0
        cur = head
        while cur:
            length += 1
            cur = cur.next

        # 取出后半部分
        length1 = length // 2 if length % 2 == 0 else (length-1) // 2
        new = head
        while length1 > 0:
            new = new.next
            length1 -= 1

        # 反转后半部分
        prev = None
        while new:
            temp = new.next
            new.next = prev
            prev = new
            new = temp

        # 与前半部分逐项对比
        prev_c, head_c = prev, head
        while prev_c:
            if prev_c.val != head_c.val:
                return False
            prev_c = prev_c.next
            head_c = head_c.next
        return True

# 141. 环形链表
class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                return True
        return False

# 25. K 个一组翻转链表
class Solution:
    # 翻转一个子链表，并且返回新的头与尾
    def reverse(self, head: ListNode, tail: ListNode):
        prev = tail.next
        p = head
        while prev != tail:
            nex = p.next
            p.next = prev
            prev = p
            p = nex
        return tail, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        hair = ListNode(0)
        hair.next = head
        pre = hair

        while head:
            tail = pre
            # 查看剩余部分长度是否大于等于 k
            for i in range(k):
                tail = tail.next
                if not tail:
                    return hair.next
            nex = tail.next
            head, tail = self.reverse(head, tail)
            # 把子链表重新接回原链表
            pre.next = head
            tail.next = nex
            pre = tail
            head = tail.next

# 206. 反转链表
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head 
        while cur:
            temp = cur.next 
            cur.next = pre 
            pre = cur 
            cur = temp
        return pre

# 103. 二叉树的锯齿形层次遍历
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []
        if root is None:
            return levels
        import collections
        bfs = collections.deque([root])
        flag = 0 #默认从左到右
        while len(bfs) > 0:
            level_size = len(bfs)
            levels.append([])
            if flag == 0:
                for _ in range(level_size):
                    node = bfs.popleft()
                    levels[-1].append(node.val)
                    if node.left is not None:
                        bfs.append(node.left)
                    if node.right is not None:
                        bfs.append(node.right)
                flag = 1
            else:
                for _ in range(level_size):
                    node = bfs.pop()
                    levels[-1].append(node.val)
                    if node.right is not None:
                        bfs.appendleft(node.right)
                    if node.left is not None:
                        bfs.appendleft(node.left)
                flag = 0
        return levels

# 2. 两数相加
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        a = ListNode() # 保留完整的链表
        l3 = a  # 保留完整的链表
        c = 0  # 进位
        while l1 or l2:
            x=l1.val if l1 else 0  # 没有下一节点时取0
            y=l2.val if l2 else 0
            tmp = x+y
            if tmp+c <10:
                l3.next = ListNode(tmp+c)
                c=0  # 不进位，清零
            else:
                l3.next = ListNode(tmp+c-10)
                c=1  # 进位，进1
            # print(tmp)
            # print(l1)
            # print(l2)
            if l1:
                l1 = l1.next  # 进入链表的下一节点
            if l2:
                l2 = l2.next  # 进入链表的下一节点
            l3 = l3.next
        if c==1:
            l3.next = ListNode(1)  # 最后一个进位增加一个末尾节点，元素为1
        return a.next  # a的第一个是0，因此去头节点

# 15. 三数之和
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        
        n=len(nums)
        res=[]
        if(not nums or n<3):
            return []
        nums.sort()
        res=[]
        for i in range(n):
            if(nums[i]>0):
                return res
            if(i>0 and nums[i]==nums[i-1]):
                continue
            L=i+1
            R=n-1
            while(L<R):
                if(nums[i]+nums[L]+nums[R]==0):
                    res.append([nums[i],nums[L],nums[R]])
                    while(L<R and nums[L]==nums[L+1]):
                        L=L+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res

# 69. x 的平方根
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left, right = 0, x + 1
        # [left, right)
        while left < right:
            mid = left + (right - left) // 2
            if mid ** 2 == x:
                return mid
            if mid ** 2 < x:
                left = mid + 1
            else:
                right = mid
        return left - 1

# 这个问题其实就是求f(x)=num - x ^ 2的零点。

# 已知牛顿法递推公式：Xn+1 = Xn - f(Xn)/f'(Xn).

# 带入f'(x) = -2x.

# 得：
# Xn+1 = Xn +(num - Xn ^ 2)/2Xn
# = (num + Xn ^ 2) / 2Xn
# = (num / Xn + Xn) / 2.

# 用代码表示则为num = (num + x / num) / 2.

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        num = x
        while num * num > x:
            num = (num + x // num) // 2
        return num

# 3. 无重复字符的最长子串
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 使用一个辅助变量来暂时存储匹配的子串
        ans = ''
        tep = ''
        for i in s:
            # 遍历，若不重复则记录该字符
            if i not in tep:
                tep += i
            # 如果遇到了已经存在的字符，则找到该字符所在位置，删除该字符，并保留该位置之后的子串，并把当前字符加入到最后，完成更新
            else:
                tep = tep[tep.index(i)+1:]
                tep += i   
            # 如果是当前最长的，就替换掉之前存储的最长子串
            if len(tep) > len(ans): 
                    ans = tep 
        return len(ans)

# 20. 有效的括号
class Solution:
    def isValid(self, s: str) -> bool:
        dic = {')':'(',']':'[','}':'{'}
        stack = []
        for i in s:
            if stack and i in dic:
                if stack[-1] == dic[i]: stack.pop()
                else: return False
            else: stack.append(i)
            
        return not stack

# 143. 重排链表
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        # 如果为空，返回None
        if not head:
            return None
        # 找到链表的中间节点
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # re_node记录的是后面需要反转链表的头结点，这里奇数节点和偶数节点时的操作是一样的，反转半部分的链表
        re_node = slow.next
        slow.next = None
        dumm = None
        while re_node:
            temp = re_node.next
            re_node.next = dumm
            dumm = re_node
            re_node = temp

        # 开始按照要求合并两个链表
        res = ListNode(0)
        p = res
        while head or dumm:
            if head and dumm:
                # 连接节点
                temp_h = head.next
                temp_d = dumm.next
                p.next = head
                p = p.next
                p.next = dumm
                p =p.next
                head = temp_h
                dumm = temp_d
            else:# 这里是奇数个节点时候，其实也就是会有一个节点需要连接在最后面
                p.next = head
                p = p.next
                head = head.next
        head = res.next

# 162. 寻找峰值
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        l=0
        r=len(nums)-1
        while(l<r):
            mid=(l+r)//2
            if(nums[mid]>nums[mid+1]):
                r=mid
            else:
                l=mid+1
        return l

# 215. 数组中的第K个最大元素
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        return sorted(nums)[-k]

class Solution:
    def findKthLargest(self, A: List[int], k: int) -> int:

        def partition(left, right, pivot_idx):
            pivot_value = A[pivot_idx]
            new = left
            A[pivot_idx], A[right] = A[right], A[pivot_idx]
            for i in range(left, right):
                if A[i] > pivot_value:
                    A[i], A[new] = A[new], A[i]
                    new += 1
            A[new], A[right] = A[right], A[new]
            return new
        
        left, right = 0, len(A)-1
        while left <= right:
            pivot_idx = random.randint(left, right)
            new = partition(left, right, pivot_idx)
            if new == k-1:
                return A[new]
            elif new > k-1:
                right = new - 1
            else:
                left = new + 1 

# 124. 二叉树中的最大路径和
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        self.max_depth = float(-inf)
        def largest_path(root):
            if root is None:
                return float(-inf)
            m_l = largest_path(root.left)
            m_r = largest_path(root.right)
            self.max_depth = max(max(0, m_l) + max(0, m_r) + root.val, m_l, m_r, self.max_depth)
            return max(m_l, m_r, 0) + root.val
        
        largest_path(root)
        return self.max_depth

# 105. 从前序与中序遍历序列构造二叉树 
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        # 实际上inorder 和 postorder一定是同时为空的，因此你无论判断哪个都行
        if not preorder:
            return None
        root = TreeNode(preorder[0])

        i = inorder.index(root.val)
        root.left = self.buildTree(preorder[1:i + 1], inorder[:i])
        root.right = self.buildTree(preorder[i + 1:], inorder[i+1:])

        return root

# 113. 路径总和 II
class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        res = []
        if not root: 
            return []
        
        def dfs(track, root, sum):
            if not root:
                return
            if not root.left and not root.right and root.val == sum:
                track += [root.val]
                res.append(track)
            
            dfs(track + [root.val], root.left, sum - root.val)
            dfs(track + [root.val], root.right, sum - root.val)
        
        dfs([], root, sum)
        return res

# 160. 相交链表


# 114. 二叉树展开为链表

# 146. LRU缓存机制

# 128. 最长连续序列

# 102. 二叉树的层序遍历