8.25 奇安信笔试
两道编程，难度都一般般。对比昨天的华为机试，简直是不能再容易了
第一题，给定有向无环图，0为起点，最后一个点为终点，计算 起点→终点 的总路径数量。输入为二维数组nodes，其中nodes[i]表示第i个节点指向的点。输出路径数量。【拓补排序，途中记录起点到每个节点的路径数即可】
第二天，题目原为“寻找最大的长方形面积”，实际上可以将问题等价为：给定数组arr，寻找两个值 arr[i],arr[j]，使得 min(arr[i],arr[j]) * (j-i)最大。我们要输出这个最大值。【双指针，移动指针的情况需要稍微考究一下】
class Solution: def DagPathNum(self , nodes: List[List[int]]) -> int: n = len(nodes) indegree = [0] * n path_num = [1] + [0] * (n - 1) for i in range(n): for j in nodes[i]: indegree[j] += 1 s = [0] while s: node = s.pop() for nxt in nodes[node]: indegree[nxt] -= 1 path_num[nxt] += path_num[node] if indegree[nxt] == 0: s.append(nxt) return path_num[-1]
a = eval(input()) ans = 0 l, r = 0, len(a) - 1 ans = min(a[0], a[-1]) * (len(a) - 1) while l < r: tmp = min(a[l], a[r]) if a[l] > a[r]: while r > l and a[r] <= tmp: r -= 1 elif a[l] < a[r]: while r > l and a[l] <= tmp: l += 1 else: l += 1 ans = max(ans, min(a[l], a[r]) * (r - l)) print(ans)
