Problem 1.Rabbit go home
Rabbit located at top left most,home is at bottom right most.Cells with width M,height N. in the cells snake ,one cell only habitat one snake.how many path possible? rabbit go right or down direction.
Problem 2. Stone weight
serveral stone weight is known,how to find a pair with given difference.eg.A-B=diff,(A,B) and (B,A) is same pair.
程序二很容易理解，约定题目二的代码给出O(n)复杂度的程序。
Behind,this is a demos .
Problem 1 Rabbit goes home
A & B
O(M * N) achieved
In [1]:
import numpy as np
snake_coord=((0,2),(3,3))means there are snakes at（0，2），（3，3）
In [7]:
def countPath(m,n,snake_coord):
grid = getGrid(m,n,snake_coord)
return uniquePathsWithsnakes(grid)
def getGrid(m: int, n:int, snake_coord):
grid = np.zeros((n,m))
for o in snake_coord:
grid[o[0]][o[1]]=1
return grid
def uniquePathsWithsnakes(snakeGrid):
# if there is a snake at the start point, no path available
if snakeGrid[0][0] == 1 or snakeGrid[-1][-1] == 1:
return 0
m, n = len(snakeGrid), len(snakeGrid[0])
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
dp[i][j] = 1
elif snakeGrid[i][j] == 1:
dp[i][j] = 0
else:
dp[i][j] = (dp[i - 1][j] if i > 0 else 0) + (dp[i][j - 1] if j > 0 else 0)
# print((i, j), ":", dp[i][j])
return dp[-1][-1]
C
In [5]:
countPath(4,3,[(0,1)]) #uncomment line 28,print((i, j), ":", dp[i][j])
(0, 0) : 1 (0, 1) : 0 (0, 2) : 0 (0, 3) : 0 (1, 0) : 1 (1, 1) : 1 (1, 2) : 1 (1, 3) : 1 (2, 0) : 1 (2, 1) : 2 (2, 2) : 3 (2, 3) : 4
Out[5]:
4
In [8]:
countPath(4,3,[(1,1),(1,2)])
Out[8]:
2
Problem 2 Find stone pairs
A
Write a function F that:
- inputs:
- an array of int
- output: find an element pair in the array whose difference is D
In [9]:
def findPairs(nums, d):
#nums: list[int], k: int
if d<0:
return 0
saw = set()
diff = set()
for i in nums:
if i-d in saw:
diff.add((i,i-d))
if i+d in saw:
diff.add((i, i+d))
saw.add(i)
return diff
B
O(N) achieved
In [10]:
nums = [2,3,3,5,8,9,2] d = 1 tmp_lst = list(findPairs(nums, 1)) tmp_lst
Out[10]:
[(3, 2), (9, 8), (2, 3)]
C
In [23]:
a = [sorted(o)[0] for o in list(findPairs(nums, 1))] b = zip(a, tmp_lst) print([value for key,value in dict(b).items()])
[(2, 3), (9, 8)]
In [ ]:
