0821滴滴笔试

数据岗

1. 旋转斐波那契数列放进数组中。

2. 输入字符矩阵，判断“CHINA”个数

第一题：

def addValue(matrix, fibList, tr, tc, dr, dc):
    if tr == dr:
        for i in range(tc, dc + 1):
            matrix[tc][i] = fibList.pop()
    elif tc == dc:
        for i in range(tr, dr + 1):
            matrix[i][tc] = fibList.pop()
    else:
        curC = tc
        curR = tr
        while curC != dc:
            matrix[tc][curC] = fibList.pop()
            curC += 1
        while curR != dr:
            matrix[curR][dc] = fibList.pop()
            curR += 1
        while curC != tc:
            matrix[dr][curC] = fibList.pop()
            curC -= 1
        while curR != tr:
            matrix[curR][tc] = fibList.pop()
            curR -= 1


def test01(n):
    if n < 2:
        print(n)
        return
    item1, item2 = 0, 1
    fibonacciList = [1]
    for _ in range(2, n * n + 1):
        ans = item1 + item2
        item1, item2 = item2, ans
        fibonacciList.append(ans)
    res = [[0] * n for _ in range(n)]
    tr, tc = 0, 0
    dr, dc = n - 1, n - 1
    while tr <= dr and tc <= dc:
        addValue(res, fibonacciList, tr, tc, dr, dc)
        tr += 1
        tc += 1
        dr -= 1
        dc -= 1
    for i in range(n):
        for j in range(n):
            print(res[i][j], end=" ")
        print()


if __name__ == '__main__':
    n = int(input())
    test01(n)

第二题

def test02(matrix, china, rows, cols):
    tmp = [True] * rows * cols
    count = 0
    for i in range(rows):
        for j in range(cols):
            res = find(matrix, tmp, rows, cols, i, j, china)
            count += res
    print(count // 4)


def find(matrix, tmp, rows, cols, i, j, path):
    count = 0
    if not path:
        return 1
    index = i * cols + j
    if i < 0 or i >= rows or j < 0 or j >= cols \
            or matrix[index] != path[0] or not tmp[index]:
        return 0
    tmp[index] = False
    # if find(matrix, tmp, rows, cols, i - 1, j, path[1:]) \
    #         or find(matrix, tmp, rows, cols, i + 1, j, path[1:]) \
    #         or find(matrix, tmp, rows, cols, i, j - 1, path[1:]) \
    #         or find(matrix, tmp, rows, cols, i, j + 1, path[1:]):
    #     return True
    count = find(matrix, tmp, rows, cols, i - 1, j, path[1:]) + \
            find(matrix, tmp, rows, cols, i + 1, j, path[1:]) + \
            find(matrix, tmp, rows, cols, i, j - 1, path[1:]) + \
            find(matrix, tmp, rows, cols, i, j + 1, path[1:])
    # if find(matrix, tmp, rows, cols, i - 1, j, path[1:]):
    #     count += 1
    # if find(matrix, tmp, rows, cols, i + 1, j, path[1:]):
    #     count += 1
    # if find(matrix, tmp, rows, cols, i, j - 1, path[1:]):
    #     count += 1
    # if find(matrix, tmp, rows, cols, i, j + 1, path[1:]):
    #     count += 1
    # return True
    tmp[index] = True
    return count


if __name__ == '__main__':
    n = int(input().strip())
    matrix = []
    for i in range(n):
        matrix.extend(input().strip())
    # matrix = list(matrix)
    test02(matrix, "CHINA", n, n)