Monthly Archives: September 2019

Path In Zigzag Labelled Binary Tree

Posted on by
Reply

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]
from math import log

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        ans = [label]
        
        def findParent(label):
            level =  math.floor(math.log(label,2))            
            diff = math.ceil((label - 2**level + 1) / 2)       
            parent = 2**(level) - diff
            return parent
            
        while label != 1:
            label = findParent(label)
            ans.append(label)
            
        return ans[::-1]

Remove Duplicates from Sorted Array

Posted on by
Reply

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.











Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.





Example 1:





Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.





Example 2:





Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.





class Solution:
    def removeDuplicates(self, nums: List[int]):
        if not nums:
            return 0

        newTail = 0

        for i in range(1, len(nums)):
            if nums[i] != nums[newTail]:
                newTail += 1
                nums[newTail] = nums[i]

        return newTail + 1

					

		
		
	


				
					
	

		

						
Permutations II

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			

Given a collection of numbers that might contain duplicates, return all possible unique permutations.





Example:





Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]





class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.result = []

        def perm(data, begin, end):
            if begin == end:
                self.result += [[item for item in data]]
            else:
                i = begin
                for j in range(begin, end):
                    data[i], data[j] = data[j], data[i]
                    perm(data, begin + 1, end)
                    data[i], data[j] = data[j], data[i]
                    
        perm(nums, 0, len(nums))

        return self.result

					

		
		
	


				
					
	

		

						
Permutation Sequence

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			

The set [1,2,3,...,n] contains a total of n! unique permutations.





By listing and labeling all of the permutations in order, we get the following sequence for n = 3:





  1. "123"
  2. "132"
  3. "213"
  4. "231"
  5. "312"
  6. "321"





Given n and k, return the kth permutation sequence.





Note:





  • Given n will be between 1 and 9 inclusive.
  • Given k will be between 1 and n! inclusive.





Example 1:





Input: n = 3, k = 3
Output: "213"






Example 2:





Input: n = 4, k = 9
Output: "2314"





class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        res, nums = "", list(range(1, n + 1))

        k -= 1

        for n in range(n, 0, -1):
            index, k = divmod(k, math.factorial(n-1))
            res += str(nums.pop(index))

        return res

					

		
		
	


				
					
	

		

						
Lowest Common Ancestor with N nodes

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			

Similar with finding lowest common ancestor of two nodes, we can extend this function to N nodes.





The method buildTree in the solution is in order to building a tree instantly by given strings.





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


class Solution:
    def buildTree(self, inorder, postorder):
        if not inorder or not postorder:
            return None

        while postorder:
            if postorder[-1] not in inorder:
                postorder.pop()
            else:
                break

        if len(postorder) == 1:
            return TreeNode(postorder[0])

        else:
            node = TreeNode(postorder[-1])
            in_index = inorder.index(postorder[-1])
            node.left = self.buildTree(inorder[:in_index], postorder[:-1])
            node.right = self.buildTree(inorder[in_index + 1:], postorder[:-1])
            return node

    def find(self, root, nodes):
        if not root:
            return None
        else:
            if root.val in nodes:
                return root

            left = self.find(root.left, nodes)
            right = self.find(root.right, nodes)

            if left and right:
                return root

            return right if not left else left


if __name__ == "__main__":
    obj = Solution()
    root = obj.buildTree([6, 5, 7, 2, 4, 3, 0, 1, 8], [6, 7, 4, 2, 5, 0, 8, 1, 3])
    nodes = [0, 1, 8]
    result = obj.find(root, nodes)
    print(result.val)


					

		
		
	


				
					
	

		

						
House Robber III

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.





Determine the maximum amount of money the thief can rob tonight without alerting the police.





Example 1:





Input: [3,2,3,null,3,null,1]      
  3     
 / \    
2   3     
 \   \       
  3   1 
Output: 7  
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.





Example 2:





Input: [3,4,5,1,3,null,1]      
      3     
     / \    
    4   5   
   / \   \   
  1   3   1 
Output: 9 
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.





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

class Solution:
    def rob(self, root: TreeNode) -> int:
        def superrob(node):
            # returns tuple of size two (now, later)
            # now: max money earned if input node is robbed
            # later: max money earned if input node is not robbed
            
            # base case
            if not node: return (0, 0)
            
            # get values
            left, right = superrob(node.left), superrob(node.right)
            
            # rob now
            now = node.val + left[1] + right[1]
            
            # rob later
            later = max(left) + max(right)
            
            return (now, later)
            
        return max(superrob(root))

					

		
		
	


				
					
	

		

						
Courage

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			

I wanted you to see what real courage is, instead of getting the idea that courage is a man with a gun in his hand. It’s when you know you’re licked before you begin anyway and you see it through no matter what. You rarely win, but sometimes you do.

					

		
		
	


				
					
	

		

						
Next Permutation

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.





If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).





The replacement must be in-place and use only constant extra memory.





Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.





1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1




 Continue reading →					

		
		
	


				
					
	

				
					
	

		

						
Trapping Rain Water

			
						

				Posted on   by  			

			
						

				Reply			

					


				

			

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.











The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!




 Continue reading →