华为机试（03）

1、获取连通的相邻节点列表

a = list(map(int,input().split()))
a_ids = set()
for i in range(1, len(a)):
    a_ids.add(a[i])

n = int(input())
res = []
for i in range(n):
    neighbor = input().split()
    m = int(neighbor[1])
    for j in range(2,len(neighbor)):
        if int(neighbor[j]) in a_ids:
            res.append(neighbor[0])
            break
print(len(res))
if res:
    print(" ".join(sorted(res)))

2、字符串处理器

res,cursor = "",0
def insert(s):
    global res,cursor
    res = res[:cursor]+s+res[cursor:]
    cursor += len(s)

def delete(l):
    global res,cursor
    if cursor>=l:
        res = res[:cursor-l] + res[cursor:]
        cursor -= l

def move(cnt):
    global res,cursor
    if cnt<0 and abs(cnt)<=cursor:
        cursor -= abs(cnt)
    if cnt>0 and abs(cnt)<=len(res)-cursor:
        cursor += abs(cnt)

def copy():
    global res,cursor
    copy_s = res[:cursor]
    res = res[:cursor]+copy_s+res[cursor:]

while 1:
    try:
        t = input().split()
        if t[0]=="end":
            break
        if t[0]=="insert":
            insert(t[1])
        elif t[0]=="move":
            move(int(t[1]))
        elif t[0]=="delete":
            delete(int(t[1]))
        else:
            copy()
    except:
        break

print(res[:cursor]+"|"+res[cursor:])

5、频率搬移值分配

n = int(input())
leaves = [int(c) for c in input().split()]

treeVals = [0]*(2*n-1)
target = {}

def dfs(node): # node叶子节点的最大值、最小值
    if node >=n-1:
        target[node] = [leaves[node-n+1],leaves[node-n+1]]
        return target[node]
    l,r = dfs(2*node+1),dfs(2*node+2)
    leaveofNode = l+r
    target[node] = [max(leaveofNode),min(leaveofNode)]
    return target[node]

def dfs2(node,sum):
    if node>=2*n-1:return
    treeVals[node] = (target[node][0]+target[node][1])//2-sum
    dfs2(node*2+1,sum+treeVals[node])
    dfs2(node*2+2,sum+treeVals[node])

dfs(0)
dfs2(0,0)
print(" ".join(list(map(str,treeVals))))

6、内存分配

from collections import defaultdict,deque

n = int(input())
taskMemory = list(map(int,input().split()))
next = defaultdict(list)
indegre = [0]*n
for i in range(n):
    tmp = list(map(int,input().split()))
    for j,s in enumerate(tmp):
        if s == 1:
            next[j].append(i)
            indegre[i] += 1

q = deque()
for i in range(n):
    if indegre[i]==0:
        q.append(i)
res = 0
while q:
    size = len(q)
    layerSum = 0
    for _ in range(size):
        node = q.popleft()
        layerSum += taskMemory[node]
        for i in next[node]:
            indegre[i] -= 1
            if indegre[i] == 0:
                q.append(i)
    res = max(res,layerSum)
print(res)

1.每日股票价格

from collections import deque
n = int(input())
stockPrices = list(map(int,input().split()))
dq = deque()
res = [0]*n
for i,curPrices in enumerate(stockPrices):
    while dq and curPrices>stockPrices[dq[-1]]:
        lastIdx = dq.pop()
        res[lastIdx] = i-lastIdx
    dq.append(i)
print(" ".join(map(str,res)))

2.中庸行者

n,m = map(int,input().split())
grid,res = [],0
for i in range(n):
    grid.append(list(map(int,input().split())))

dirs = [[0,1],[0,-1],[1,0],[-1,0]]
visit = [[0]*m for _ in range(n)]
def dfs(x,y,visit,increase):
    pathStep = 0
    for i in range(4):
        nx = x + dirs[i][0]
        ny = y + dirs[i][1]
        if nx<0 or nx>=n or ny<0 or ny>=m or visit[nx][ny]:
            continue
        diff = grid[nx][ny]-grid[x][y]
        nextIncrease = 1 if diff > 0 else -1
        if diff == 0 or increase * nextIncrease > 0:
            continue
        visit[nx][ny] = 1
        pathStep = max(pathStep,dfs(nx,ny,visit,nextIncrease))
        visit[nx][ny] = 0
    return pathStep + 1

for i in range(n):
    for j in range(m):
        visit[i][j] = 1
        res = max(res,dfs(i,j,visit,0))
        visit[i][j] = 0
print(res-1)

# 3 3
# 4 7 8
# 8 6 6
# 2 6 4