Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example:

Input:  1---2---3---4---5---6--NULL          
|
7---8---9---10--NULL
|
11--12--NULL
Output: 1-2-3-7-8-11-12-9-10-4-5-6-NULL
"""
# Definition for a Node.
class Node:
    def __init__(self, val, prev, next, child):
        self.val = val
        self.prev = prev
        self.next = next
        self.child = child
"""

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        stack = list()
        cur = head
        
        while cur:
            if cur.child:
                if cur.next:
                    stack += [cur.next]
                cur.next = cur.child
                cur.next.prev = cur
                cur.child = None
           
            if not cur.next and stack:
                temp = stack.pop()
                cur.next = temp
                temp.prev = cur
                
            cur = cur.next
        
        return head

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1    
/ \
2 5
/ \ \
3 4 6

The flattened tree should look like:

1  
\
2
\
3
\
4
\
5
\
6
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        node, stack = root, []
        
        while node:
            if node.right:
                stack.append(node.right)
            node.right = node.left
            node.left = None
            
            if not node.right and stack:
                temp = stack.pop()
                node.right = temp
            
            node = node.right

Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

As you can seen that recursion implementation is pretty easy to achieve, but iteratively achievement might not. Above are two implementations.

# iteratively
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        
        pionner = head
        
        while pionner.next:
            old_head = head
            head = pionner.next
            pionner.next = pionner.next.next
            head.next = old_head
        
        return head
# recursively

来自网易云音乐的评论

有一天我吃完泡面发现洗洁精用光了,我随手用剃须泡洗碗时,会觉得可能要是有一个女朋友就好了。并不是因为有了女朋友就不会吃泡面,也不是因为有了女朋友就会有人帮你洗碗,是我想在洗完碗转身回去时会有个人在那里,等着我一脸神秘地说: “嘿!你猜我刚刚用什么洗的碗?

Daily Temperatures

Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

Solution:
This quiz is a classical application of the stack data structure. Here we can store indexes of each element which is waiting a bigger element in a stack, and calculate the difference between the current index and stored indexes when the current element is bigger than previous elements. The while loop part is really elegant and tricky, in which judging whether the stack is empty and comparing elements.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        ans = [0] * len(T)

        stk = list()

        for c_index, value in enumerate(T):
            while stk and T[stk[-1]] < value:
                p_index = stk.pop()
                ans[p_index] = c_index - p_index
            stk.append(c_index)

        return ans

Circular Queue

class MyCircularQueue:
 
    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        """
        self.head = -1
        self.tail = -1
        self.size = k
        self.queue = [None] * self.size
 
    def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.isFull():
            return False
 
        if self.isEmpty():
            self.head = 0
 
        self.tail = (self.tail + 1) % self.size
        self.queue[self.tail] = value
        return True
 
    def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.isEmpty():
            return False
 
        if self.head == self.tail:
            self.head = -1
            self.tail = -1
            return True
 
        self.queue[self.head] = None
        self.head = (self.head + 1) % self.size
        return True
 
    def Front(self) -> int:
        """
        Get the front item from the queue.
        """
        if self.isEmpty():
            return -1
 
        return self.queue[self.head]
 
    def Rear(self) -> int:
        """
        Get the last item from the queue.
        """
        if self.isEmpty():
            return -1
 
        return self.queue[self.tail]
 
    def isEmpty(self) -> bool:
        """
        Checks whether the circular queue is empty or not.
        """
        return self.head == -1
 
    def isFull(self) -> bool:
        """
        Checks whether the circular queue is full or not.
        """
        return (self.tail + 1) % self.size == self.head

未知疯狂

昨天考完了DS。

这学期还剩一门DP就结束了,但是今天坐在已经没什么人的图书馆里却没有什么复习的心思。

正逢国内的校招季,身边的朋友们也都开始了自己新的旅程。有大四的朋友毕业去找了工作,有的选择了去国外继续深造。研究生的朋友们要不选择了直博,要不就要加入求职大军。

仔细想想,其实我的机会还是蛮多的,但就是怕不能把握住。希望假期里可以想明白这个事情,然后朝着想去的方向奋斗吧。

Miscellaneous

过了周五,这个学期就要告以段落了。

然后接下来就是一周的疯狂复习了,加上考试了。

这段时间一直没有更新blog, 感觉还是应该偶尔记一点流水账的。今天早上起来巨冷,于是坐了Tram去学校,打算好好学几个小时习来着,但是被昨天下载的游戏耽误了好多时间> – <

在Tram上无意看到了昨天在超市买厨房打火机被多收了很多钱,所以下了Tram之后就直奔Caltron的ANZ去问了一下,结果人家并不怎么care这件事,说是直接去找Merchant就好。接着去修车行取了昨天拜托修的自行车,貌似除了链条还有很多问题,估计得我自己订零件修了(车行修车太贵了)

晚上和Angle去吃了晚饭,看了中华剧社的话剧《疯子,你好》,感觉故事很不错,最后的结尾挺让人感动的。把Angle送回家之后,我去找昨天的超市撕逼,结果人家的退款速度简直一气呵成,我也就只能All good了。

下周估计又是一场硬仗了(毕竟感觉这个学期没有好好学习。。),希望考完试可以有一个愉快的新旅程LoL

Piles of Boxes

Several days ago, I’ve joined a Hackathon that sponsored by Facebook.

As qualifying people to this event, they hand out an easy algorithm question. Shortly, you need to calculate how less time to move a bunch of boxes in same heigh.

Here is a solution for reference:


import collections

def box(boxesInPiles):
    sortBoxes = collections.OrderedDict(sorted(collections.Counter(boxesInPiles).items()))
    count = 0
    for index, key in enumerate(sortBoxes):
        count += index * sortBoxes[key]
    return count

print(box([4, 5, 5, 2, 4]))