4.3 阿里实习笔试

def count(arr):
    def isValid(index):
        pivot = arr[index]
        left, right = float("inf"), float("-inf")
        # find left
        for i in range(index):
            if arr[i] - pivot > 0 and arr[i] < left:
                left = arr[i]
        # find right
        for j in range(index + 1, len(arr)):
            if arr[j] - pivot < 0 and arr[j] > right:
                right = arr[j]
        return left % right == 0

    res = 0
    if len(arr) < 2:
        return 0
    for i in range(1, len(arr) - 1):
        if isValid(i):
            res += 1
    return res



if __name__ == '__main__':
    n = int(input())
    arr = [int(i) for i in input().split(' ')]
    print(count(arr))

import heapq


class Node:
    def __init__(self, i, j, cost):
        self.i = i
        self.j = j
        self.cost = cost

    def __lt__(self, other):
        return self.cost < other.cost

    def __eq__(self, other):
        return self.cost == other.cost


def minPath(grid):
    m, n = len(grid), len(grid[0])
    visited = [[False for _ in range(n)] for _ in range(m)]
    heap = []
    for j in range(n):
        heapq.heappush(heap, Node(0, j, grid[0][j]))

    while heap:
        cur = heapq.heappop(heap)
        i, j, cost = cur.i, cur.j, cur.cost

        if i == m - 1:
            return cost
        elif visited[i][j]:
            continue
        else:
            visited[i][j] = True
            for a, b in [[1, 0], [-1, 0], [0, -1], [0, 1]]:
                x = i + a
                y = j + b
                if m > x >= 0 and n > y >= 0:
                    heapq.heappush(heap, Node(x, y, cost + grid[x][y]))
    return


if __name__ == '__main__':
    # a = input().split(" ")
    # n, m = int(a[0]), int(a[1])
    #
    # matrix = []
    # for i in range(n):
    #     row = [int(i) for i in input().split(" ")]
    #     matrix.append(row)

    matrix1 = [[8, 9, 9, 9, 9, 1],
               [1, 1, 1, 9, 1, 1],
               [1, 9, 1, 1, 1, 9],
               [1, 9, 9, 9, 9, 9]]

    matrix2 = [[3, 1, 3],
               [3, 1, 3],
               [3, 1, 3]]
    assert minPath(matrix1) == 11
    assert minPath(matrix2) == 3