首页 > 技术交流 > 华为7.28笔试

华为7.28笔试

头像
石郎 #华为机试#
编辑于 2021-08-01 06:08:36 APP内打开
赞 5 | 收藏 34 | 回复4 | 浏览7009
1. 先把不符合要求的去掉,然后按照策略排序,选择前n个,最后再按编号排序,Python代码:
import sys
# sys.setrecursionlimit(1000000)
m = int(sys.stdin.readline().strip(' ').strip('
').strip(' '))
arr = []
for _ in range(m):
    idx,cpuCount,memSize,cpuArch,supportNP = list(map(int,sys.stdin.readline().strip(' ').strip('
').strip(' ').split(',')))
    arr.append([idx,cpuCount,memSize,cpuArch,supportNP])
n,strategy,cpuCount,memSize,cpuArch,supportNP = list(map(int,sys.stdin.readline().strip(' ').strip('
').strip(' ').split(' ')))
remaid_arr= []
for i in range(m):
    if arr[i][1]>= cpuCount and arr[i][2]>=memSize:
        if (cpuArch==9&nbs***bsp;cpuArch==arr[i][3]) and (supportNP==2&nbs***bsp;supportNP==arr[i][4]):
            remaid_arr.append(arr[i].copy())

if strategy==1:
    remaid_arr = sorted(remaid_arr,key=lambda x:[x[1],x[2],x[0]])
else:
    remaid_arr = sorted(remaid_arr,key=lambda x:[x[2],x[1],x[0]])
remaid_arr = remaid_arr[:n]
res = [v[0] for v in remaid_arr]
res = sorted(res)
t = len(res)
res.insert(0,t)
print(" ".join(list(map(str,res))))

2. 拓扑排序
import sys
# sys.setrecursionlimit(1000000)
m = int(sys.stdin.readline().strip(' ').strip('
').strip(' '))
n = int(sys.stdin.readline().strip(' ').strip('
').strip(' '))
z = int(sys.stdin.readline().strip(' ').strip('
').strip(' '))

arr = []
graph = [[] for _ in range(m+1)]
cnt_in = [0]*(m+1)
cnt_out = [0]*(m+1)
for _ in range(z):
    i,j = list(map(int,sys.stdin.readline().strip(' ').strip('
').strip(' ').split(' ')))
    arr.append([i,j])
    cnt_in[j]+=1
    cnt_out[i]+=1
    graph[i].append(j)

length = [-1]*(m+1)
for i in range(1,m+1):
    def dfs(idx):
        if len(graph[idx])==0:
            length[idx] =0
            return 0
        if length[idx]>=0:
            return length[idx]
        res = 0
        for to in graph[idx]:
            res = max(res,1+dfs(to))
        length[idx] = res
        return res
    dfs(i)

res = 0
book =  [0]*(m+1)
book[0]=1
while True:
    tn = n
    temp_book = [0]*(m+1)
    flag = True
    for _ in range(tn):
        temp_idx = 0
        for i in range(1,m+1):
            if book[i]==0 and temp_book[i]==0 and cnt_in[i]==0 and (temp_idx==0&nbs***bsp;length[temp_idx]<length[i]):
            # if book[i]==0 and temp_book[i]==0 and cnt_in[i]==0 and (temp_idx==0&nbs***bsp;cnt_out[temp_idx]<cnt_out[i]):
                temp_idx =i

        if temp_idx==0:
            break
        flag = False
        book[temp_idx] = 1
        for to in graph[temp_idx]:
            cnt_in[to]-=1
            temp_book[to]=1
    if flag:
        break
    res+=1

print(res)

3. 求路径,需要保证经过图上所以能到达的点,一次且仅一次。我是暴力做的,Python过不了,但是C++可以😂。
Python代码(AC 60%):
import sys
# sys.setrecursionlimit(1000000)
m,n = list(map(int,sys.stdin.readline().strip(' ').strip('
').strip(' ').split(' ')))
# n = int(sys.stdin.readline().strip(' ').strip('
').strip(' '))
# z = int(sys.stdin.readline().strip(' ').strip('
').strip(' '))


graph = []
line_num = 1
start,end = [], []
for i in range(m):
    line = list(map(int,sys.stdin.readline().strip(' ').strip('
').strip(' ').split(' ')))
    graph.append(line)
    for j in range(n):
        v = line[j]
        if v ==0 :
            line_num+=1
        elif v==1:
            start = [i,j]
        elif v==2:
            end = [i,j]
res = [0]
nex = [[0,1],[1,0],[0,-1],[-1,0]]
book = [[0 for _ in range(n)] for _ in range(m)]
def dfs(x,y,temp_line_num,m,n,line_num):
    if x==end[0] and y ==end[1]:
        if temp_line_num== line_num:
            res[0]+=1
        return

    book[x][y]  = 1
    for k in range(len(nex)):
        newx,newy = nex[k][0]+x,nex[k][1]+y
        if 0<=newx<m and 0<=newy<n and book[newx][newy] == 0 and (graph[newx][newy]==1&nbs***bsp;graph[newx][newy]==0&nbs***bsp;graph[newx][newy]==2  ):
            dfs(newx,newy,temp_line_num+1,m,n,line_num)
    book[x][y]= 0

dfs(start[0],start[1],0,m,n,line_num)
print(res[0])


C++(AC 100%):
#include <iostream>
#include <vector>
using namespace std;
int graph[41][41];
int book[41][41];
int res,sx,sy,ex,ey;
int nex[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x,int y,int temp_line_num,int m ,int n ,int line_num){
    if (x==ex and y==ey){
        if (temp_line_num == line_num){
            res+=1;
        }
        return;
    }
    book[x][y] = 1;
    int newx,newy;
    for (int i = 0; i < 4; ++i) {
        newx= nex[i][0]+x;
        newy = nex[i][1]+y;
        if (0<= newx && newx<m && 0<=newy && newy<n &&book[newx][newy] == 0 && (graph[newx][newy]==1 || graph[newx][newy]==0 || graph[newx][newy]==2)){
            dfs(newx,newy,temp_line_num+1,m,n,line_num);
        }
    }
    book[x][y] =0;
    return;
}
int main() {
    int t;
    int a,b,n,m,line_num=1;
    cin>>m>>n;

    for (int i = 0; i <m ; ++i) {
        for (int j = 0; j <n ; ++j) {
            cin>>graph[i][j];
            if (graph[i][j]==0){
                line_num+=1;
            }
            else if (graph[i][j]==1){
                sx= i;
                sy = j;
            } else if (graph[i][j]==2){
                ex= i;
                ey = j;
            }
        }
    }

    dfs(sx,sy,0,m,n,line_num);
    cout<<res<<endl;

//    std::cout << "Hello, World!" << std::endl;
    return 0;
}


4条回帖

回帖
加载中...
话题 回帖

推荐话题

相关热帖

技术交流近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐