There is a one-dimensional board with a starting point on the far left side of the board and an end point on the far right side of the board. There are several positions on the board that are connected to other positions, ie if A is connected to B, then when chess falls at position A, you can choose whether to move the chess from A to B. And the connection is one way, which means that the chess cannot move from B to A. Now given the length and connections of the board, and you have a six-sided dice(1-6), output the minimum steps to reach the end point.
"""
有可能有兩多個connecting points
"""
def modernLudo(self, length, connections):
dist = [float('inf')] * (length+1)
route = defaultdict(set)
for con in connections:
route[con[0]].add(con[1])
q = [1]
dist[1] = 0
while q:
d = q.pop(0)
for step in range(1,7):
next = d+step
if next < length and dist[next] > dist[d] + 1:
dist[next] = dist[d]+1
q.append(next)
if d in route:
for next in route[d]:
if dist[next] > dist[d]:
dist[next] = dist[d]
q.append(next)
return dist[-1]
801 Minimum Swap To Make Sequence Increasing
Given A and B, return the minimum number of swaps to make both sequences strictly increasing.
Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
"""
In min swap in ith index comes from in i-1 no swap or i-1 swap
n1, s1: no swap and swap
"""
def minSwap(self, A: List[int], B: List[int]) -> int:
n1, s1 = 0, 1
for i in range(1, len(A)):
n2 = s2 = float("inf")
if A[i-1] < A[i] and B[i-1] < B[i]:
n2 = n1 # both no swap
s2 = s1 + 1 # both swap
if A[i-1] < B[i] and B[i-1] < A[i]:
n2 = min(n2, s1) # i-1 swap
s2 = n1 + 1 # i swap
n1, s1 = n2, s2
return min(n1, s1)
832. Binary Trees With Factors
Given an array of unique integers, each integer is strictly greater than 1.
We make a binary tree using these integers and each number may be used for any number of times.
Each non-leaf node's value should be equal to the product of the values of it's children.
"""
dp[i] = dp[j] * dp[k] j < k < i
Use a hash to record k's index
"""
def numFactoredBinaryTrees(self, A: List[int]) -> int:
n = len(A)
A.sort()
record = {x:i for i, x in enumerate(A)}
dp = [1] * n
for i, x in enumerate(A):
for j in range(i):
if x % A[j] == 0:
y = x / A[j]
if y in record:
dp[i] += dp[j] * dp[record[y]]
return sum(dp) % (10**9 +7)