156. Binary Tree Upside Down

# Given a binary tree where all the right nodes are either leaf nodes with a sibling
# (a left node that shares the same parent node) or empty, flip it upside down and
# turn it into a tree where the original right nodes turned into left leaf nodes.
# Return the new ...

class MinStack(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.nums = []
        self.minv = []

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.nums.append(x)
        if len(self.nums) == 1:
            self.minv.append(x)
        else:
            newmin = min(self.minv[-1], x)
            self.minv.append(newmin)

    def pop ...

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left + 1 < right:
            if nums[left] == nums[right]:  # must be a horizontal line on the left
                value = nums[left]
                while nums[left] == value:
                    if left == right:
                        return value # all the ...

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left + 1 < right:
            mid = left + (right - left)/2
            if nums[mid] > nums[left] and nums[mid] < nums[right]:
                return nums[left]
            elif nums[mid] > nums[left]:
                left = mid + 1
            else ...

class Solution(object):
    def maxProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        minproduct = nums[0]
        maxproduct = nums[0]
        totproduct = nums[0]
        for i in range(1, len(nums)):
            copymin = minproduct
            minproduct = min(minproduct * nums[i], maxproduct * nums[i], nums[i])
            maxproduct = max(copymin * nums[i], maxproduct * nums[i], nums ...

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        # s = " ".join(s.split())  # replace interval with only one space. Create a new array! can't use it!
        s = s + ' '  # if not add ' ', the last word can not be extracted
        for i in range(len(s)):
            if s ...

class Solution(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        queue = []
        for item in tokens:
            if item == "*" or item == "/" or item == "+" or item == "-":
                operand2 = queue.pop()
                operand1 = queue.pop()
                result = self.calc(item, operand1, operand2)
                queue.append(result)
            else:
                queue.append(int(item))

        return queue.pop()

    def ...

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head
        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow ...

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        if not head.next:
            return head
        cur = head.next
        beforecur = head
        while cur:
            tmp = head
            beforetmp ...

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        queue = [root]
        result = []
        while queue:
            node = queue.pop()
            result.insert(0 ...

« Page 4 / 22 »

Welcome to Haven's blog

156. Binary Tree Upside Down

155. Min Stack

154. Find Minimum in Rotated Sorted Array II

153. Find Minimum in Rotated Sorted Array

152. Maximum Product Subarray

151. Reverse Words in a String

150. Evaluate Reverse Polish Notation

148. Sort List

147. Insertion Sort List

145. Binary Tree Postorder Traversal

blogroll

social