Category Archives: Leetcode

Remove Zero Sum Consecutive Nodes from Linked List

Posted on by
Reply

Firstly, I can’t help myself to say: “Lee, you are a fucking genius!”

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list.  You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        
        prefix = 0
        seen = collections.OrderedDict()
        
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur = cur.next
            
        return dummy.next

Printing a pyramid matrix

Posted on by
Reply

How to print a pyramid matrix like that:

n = 2
[1, 1, 1]
[1, 2, 1]
[1, 1, 1]

n = 3
[1, 1, 1, 1]
[1, 2, 2, 1]
[1, 2, 2, 1]
[1, 1, 1, 1]

n = 4
[1, 1, 1, 1, 1]
[1, 2, 2, 2, 1]
[1, 1, 3, 2, 1]
[1, 2, 2, 2, 1]
[1, 1, 1, 1, 1]
def func(N):
    N += 1
    matrix = [[1 for _ in range(N)] for _ in range(N)]
    cnt = 0

    while cnt < N:
        # UP
        for i in range(cnt, N - cnt - 1):
            matrix[cnt][i] = cnt + 1

        # RIGHT
        for i in range(cnt, N - cnt - 1):
            matrix[i][N - cnt - 1] = cnt + 1

        # DOWN
        for i in range(N - cnt - 1, cnt, -1):
            matrix[N - cnt - 1][i] = cnt + 1

        # LEFT
        for i in range(N - cnt, cnt, -1):
            matrix[N - cnt - 1][cnt] = cnt + 1

        cnt += 1

    return matrix


if __name__ == "__main__":
    matrix = func(N=4)

    for line in matrix:
        print(line)

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))

					

		
		
	


				
					
	

		

						
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 →