Review list 3

117. Populating Next Right Pointers in Each Node II

Populating Next Right Pointers in Each Node II - LeetCode

For the code below, the space complexity is O(n)

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if root is None:return root
        nodes = collections.defaultdict(list)
        def bfs(node, layer):
            from collections import deque
            Q = deque([(node,layer)])
            while Q:
                node, layer = Q.popleft()
                nodes[layer].append(node)
                if node.left:Q.append((node.left, layer+1))
                if node.right:Q.append((node.right, layer+1))
        bfs(root, 0)
        for l in nodes:
            for i in range(len(nodes[l])-1):
                nodes[l][i].next = nodes[l][i+1]
        return root

117. Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/discuss/518932/From-an-example-to-understand-the-code

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        upper_tail = root
        while upper_tail:
            dummy_head = Node(-1)
            this_tail = dummy_head
            while upper_tail:
                if upper_tail.left:
                    this_tail.next = upper_tail.left
                    this_tail = upper_tail.left
                if upper_tail.right:
                    this_tail.next = upper_tail.right
                    this_tail = upper_tail.right
                upper_tail = upper_tail.next
            upper_tail = dummy_head.next
        return root

https://leetcode.com/problems/odd-even-linked-list/

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        dummy1 = odd = ListNode(-1)
        dummy2 = even = ListNode(-1)
        tail = head
        while tail:
            odd.next = tail
            even.next =tail.next
            odd = odd.next
            even = even.next
            if even:
                tail = even.next
            else:break
        odd.next = dummy2.next
        return dummy1.next

https://leetcode.com/problems/find-k-closest-elements/

Bisect and by cases. Using deque instead of list can speed up the code from 780ms to 336 ms.

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        i = bisect.bisect_left(arr, x)
        used = 0
        res =collections.deque([])
        if k>=len(arr):return arr
        l, r = i-1, i
        while True:
            if l>=0 and r<len(arr):
                if abs(arr[l]-x)<=abs(arr[r]-x):
                    res.appendleft(arr[l])
                    l -= 1
                    used += 1
                else:
                    res.append(arr[r])
                    r += 1
                    used += 1
                if used ==k:break
            elif l>=0:
                res.appendleft(arr[l])
                used += 1
                l -= 1
                if used ==k:break
            else:
                res.append(arr[r])
                used += 1
                r += 1
                if used ==k:break
        return list(res)

First Missing Positive - LeetCode

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums = [num for num in nums if num>0]
        nums = sorted(set(nums))
        if not nums:return 1
        if nums[0]!=1:return 1
        def good(m):return nums[m]==m+1
        l, r= 0, len(nums)-1
        while l<r:
            m = (l+r+1)//2
            if good(m):l=m
            else:r =m-1
        return l+1+1

The above code time complexity is O(nlogn) +O(logn) as we have sort and binary sort. It is required that we need O(n) time complexity and O(1) space complexity.

A smart solution can be found here

https://leetcode.com/problems/first-missing-positive/discuss/17080/Python-O(1)-space-O(n)-time-solution-with-explanation

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        nums.append(0)
        n = len(nums)
        for i in range(len(nums)): #delete those useless elements
            if nums[i]<0 or nums[i]>=n:
                nums[i]=0
        for i in range(len(nums)): #use the index as the hash to record the frequency of each number
            #print(nums[i])
            nums[nums[i]%n]+=n
        for i in range(1,len(nums)):
            if nums[i]//n==0:
                return i
        return n

https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/

My original naive solution

"""
# Definition for a Node.
class Node:
    def __init__(self, val=None, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    def insert(self, head: 'Node', insertVal: int) -> 'Node':
        if head is None:
            new_head = Node(insertVal)
            new_head.next = new_head
            return new_head
        min_node = tail = head
        max_node = head
        tail = head.next
        while tail!=head:
            if tail.val<min_node.val:
                min_node = tail
            elif tail.val>=max_node.val:
                max_node = tail
            tail = tail.next
        new_node = Node(insertVal)
       # print(min_node.val, max_node.val)
        if max_node.val<=insertVal or min_node.val>=insertVal:
            max_node.next = new_node
            new_node.next = min_node
            return head
        tail = min_node
        while True:
            #print(tail.val)
            if tail.next.val>=insertVal:
                nxt = tail.next
                tail.next = new_node
                new_node.next = nxt
                break
            tail = tail.next
        return head