TestingCode数据结构挑战

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 [ ]:

贴了一堆代码，到底想问什么问题？

你好，我是有问必答小助手。为了技术专家团更好地为您解答问题，烦请您补充下（1）问题背景详情，（2）您想解决的具体问题，（3）问题相关图片。便于技术专家团更好地理解问题，并给出解决方案。

您可以点击问题下方的【编辑】，进行补充修改问题。