Delete Nodes And Return Forest

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest.  You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

  • The number of nodes in the given tree is at most 1000.
  • Each node has a distinct value between 1 and 1000.
  • to_delete.length <= 1000
  • to_delete contains distinct values between 1 and 1000.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:    
    def delNodes(self, root, to_delete):
        """
        :type root: TreeNode
        :type to_delete: List[int]
        :rtype: List[TreeNode]
        """
        self.forests = []
        self.delete = to_delete
        
        node = self.divideAndConquer(root)
        
        if node:
            self.forests.append(node)
        
        return self.forests
    
    def divideAndConquer(self, node):
        
        if not node:
            return None
        
        left = self.divideAndConquer(node.left)
        right = self.divideAndConquer(node.right)
        
        if node.val not in self.delete:
            node.left = left
            node.right = right
            return node
        else:
            if left:
                self.forests.append(left)
            if right:
                self.forests.append(right)
                
            return None

Minimum Knight Moves

In an infinite chess board with coordinates from -infinity to +infinity, you have a knight at square [0, 0].

A knight has 8 possible moves it can make, as illustrated below. Each move is two squares in a cardinal direction, then one square in an orthogonal direction.

Return the minimum number of steps needed to move the knight to the square [x, y].  It is guaranteed the answer exists.

Example 1:

Input: x = 2, y = 1
Output: 1
Explanation: [0, 0] → [2, 1]

Example 2:

Input: x = 5, y = 5
Output: 4
Explanation: [0, 0] → [2, 1] → [4, 2] → [3, 4] → [5, 5]
class Solution:
    def minKnightMoves(self, x: int, y: int) -> int:
        x, y = abs(x), abs(y)
        
        q = collections.deque([(0,0,0)])
        seen = set([(0,0)])

        while q:
            s_x, s_y, s = q.popleft()
            if (s_x, s_y) == (x,y):
                return s

            d = []
            for dx, dy in [(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2)]:
                n_x = s_x + dx
                n_y = s_y + dy
                if -2 <= n_x <= x and -2 <= n_y <= y:
                    d.append((n_x,n_y))

            d.sort(key=lambda e: abs(x-e[0]) + abs(y-e[1]))

			# only enqueue towards the 2 directions closest to the x,y
            for n_x,n_y in d[:2]:
                if (n_x, n_y) not in seen:
                    q.append((n_x,n_y,s+1))
                    seen.add((n_x,n_y))

Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Note: A leaf is a node with no children.

Example:

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        def getNumbers(root, previous, result):
            if not root:
                return
            
            current = previous*10 + root.val
            
            if not root.left and not root.right:
                result[0] += current
            
            getNumbers(root.left, current, result)
            getNumbers(root.right, current, result)
            
        ans = [0]
        getNumbers(root, 0, ans)
        return ans[0] 

Decode ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
class Solution:
    def numDecodings(self, s: str) -> int:        
        if s[0] == '0': return 0
        
#         N = len(s)
#         dp = [1 for i in range(N+1)]
        
        for i in range(1, len(s)):
            if s[i] == '0':
                # dp[i] = 0
                b = 0
            if int(s[i-1:i+1]) <= 26:
                # dp[i+1] = dp[i] + dp[i-1]
                c = b+a
            else:
                # dp[i+1] = dp[i]
                c = b
            a=b
            b=c
            
        return dp[-1]

Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from functools import lru_cache

class Solution:
    def generateTrees(self, n):
        if n == 0: return []
        
        @lru_cache(maxsize=None)
        def generate(start, end):
            ans = []
            
            if start > end: return [None]

            for i in range(start, end+1):
                for left_node in generate(start, i-1):
                    for right_node in generate(i+1, end):
                        node = TreeNode(i)
                        node.left = left_node
                        node.right = right_node
                        ans.append(node)

            return ans

        return generate(1, n)

2 Keys Keyboard

Initially on a notepad only one character ‘A’ is present. You can perform two operations on this notepad for each step:

  1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
  2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n ‘A’ on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n ‘A’.

Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Note:

  1. The n will be in the range [1, 1000].
from functools import lru_cache

class Solution:
    def minSteps(self, n: int) -> int:
        
#         @lru_cache(None)
#         def operation(notepad, current):
#         def operation(notepad, current):
#             if len(current) <= n:
#                 if len(current) == n:
#                     return 0

#                 # no notepad
#                 t1 = (operation(current, current) if not notepad else 0x7777777) + 1

#                 # paste from notepad
#                 t2 = (operation(notepad, current + notepad) if notepad else 0x7777777) + 1

#                 # update notepad
#                 t3 = (operation(current, current) if notepad and notepad != current else 0x7777777) + 1

#                 return min(t1, t2, t3)

#             else:
#                 return 0x7777777

#         result = operation(0, "A")

#         return result

        if n == 1: 
            return 0
        
        for i in range(2,n+1):
            if n % i == 0: 
                return i + self.minSteps(int(n/i))

Find K-th Palindrome Number of N Digits

Given N and K, output K-th Palindrome that has N digits.

Input: N = 2, K = 3
Output: [3, 3]
Explanation: [1,1] => [2,2] => [3, 3]

Input: N = 3, K = 5
Output: [1, 4, 1]
Explanation: [1, 0, 1] => [1, 1, 1] => [1, 2, 1] => [1, 3, 1] => [1, 4, 1]

Input: N = 5, K = 201
Output: [3, 0, 0, 0, 3]
Explanation: … => [2, 9, 8, 9, 2] => [2, 9, 9, 9, 2] => [3, 0, 0, 0, 3]

def func(n, k, ans):
    if n > 0:
        segment = 10 ** ((n - 1) // 2)
        element, next_k = divmod(k, segment)
        ans.append(element)
        func(n - 2, next_k, ans)


def generate(n, k):
    ans = []
    func(n, k - 1, ans)

    ans[0] += 1

    if n % 2:
        return ans[:-1] + ans[::-1]
    else:
        return ans + ans[::-1]


if __name__ == "__main__":
    result = generate(5, 201)
    print(result)

Pow(x, n)

mplement pow(xn), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        
        if n < 0:
            return 1 / self.myPow(x, -n)
        
        if n % 2:
            return x * self.myPow(x, n-1)
        
        return self.myPow(x*x, n/2)

Stone Game II

Alex and Lee continue their games with piles of stones.  There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i].  The objective of the game is to end with the most stones. 

Alex and Lee take turns, with Alex starting first.  Initially, M = 1.

On each player’s turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M.  Then, we set M = max(M, X).

The game continues until all the stones have been taken.

Assuming Alex and Lee play optimally, return the maximum number of stones Alex can get.

Example 1:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alex takes one pile at the beginning, Lee takes two piles, then Alex takes 2 piles again. Alex can get 2 + 4 + 4 = 10 piles in total. If Alex takes two piles at the beginning, then Lee can take all three piles left. In this case, Alex get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

Constraints:

  • 1 <= piles.length <= 100
  • 1 <= piles[i] <= 10 ^ 4

The king of concise code reigns!

from functools import lru_cache

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        
        N = len(piles)
        
        for i in range(N - 2, -1, -1):
            piles[i] += piles[i + 1]
            
        @lru_cache(None)
        def dp(i, m):
            if i + 2 * m >= N: 
                return piles[i]
            
            return piles[i] - min(dp(i + x, max(m, x)) for x in range(1, 2 * m + 1))
        
        return dp(0, 1)