20211013华为机试分享

第一题100分

小明家有很大的房子，有很多房间。先输入roomA，然后输入roomB，再输入门的个数N。
接着输入N行门，意味着可以从一个房间（第一个数字）到另一个房间（第二个数字）。
请问从roomA到roomB最短的要经过几个门
输入：
1
5
5
1 2
2 3
3 4
2 5
4 5

这道题很像leetcode的课程表，就是要注意一个房间可能可以到达多个房间，所以字典value是list

import sys
from collections import defaultdict
if __name__ == "__main__":
    # 读取第一行的n
    # 都是string
    roomA = input().strip()
    roomB = input().strip()
    N =  int(input().strip())

    # 保存门
    doors=defaultdict(list)
    # 保存路径
    visited=[]
    # 保存答案
    res=[]
    path=[]
    for i in range(N):
        door=input().strip().split()
        door1,door2=door[0],door[1]

        doors[door1].append(door2)
        doors[door2].append(door1)

    def dfs(room1):
        # 到达终点
        if room1==roomB:
            # 取消注释可以看路径
            #path.append(visited.copy())
            res.append(len(visited))
            return
        elif room1 in visited:
            return
        else:
            # 刚刚进入room1
            visited.append(room1)
            to_visit=doors[room1]

            for room in to_visit:
                dfs(room)
            visited.pop()
    dfs(roomA)
    # res元素最短长度
    #print(res)
    #print(path)
    print(min(res))

第二题200分

一个m*n的陆地板块，中间有湖，湖是不能走的。
先输入m n，再输入起点坐标，终点坐标。
然后输入湖的个数n。
下面n行输入湖的坐标。
需要输出从起点到终点的最短路径的数量和最短路径所经过的距离
输入：
5 5
0 1
5 5
1
2 1

这道题看起来简单，实际上要注意一下路径数量会非常多。需要用堆去优化结果，另外还需要在visited已经长于之前搜索过的路径的时候提前中止。
还有，可能不能到达所以需要输出0 0

import heapq
if __name__ == "__main__":
    m,n=input().strip().split()
    m,n=int(m),int(n)

    line=input().strip().split()
    Start=(int(line[0]),int(line[1]))

    line=input().strip().split()
    End=(int(line[0]),int(line[1]))

    line=input().strip()
    Lakes_num=int(line)
    Lakes=set()
    for i in range(Lakes_num):
        line=input().strip().split()
        Lakes.add( (int(line[0]),int(line[1])) )

    visited=set()
    visited.add(Start)
    res=[]
    #Paths=[]
    direcs=[[0,1],[0,-1],[1,0],[-1,0]]

    def dfs(pos):
        if pos==End:
            #Paths.append(visited.copy())
            val=len(visited)
            if not res:
                heapq.heappush(res, val)
            else:
                cur_min=heapq.heappop(res)
                if val<cur_min:
                    heapq.heappush(res, val)
                elif val==cur_min:
                    heapq.heappush(res, val)
                    heapq.heappush(res, val)
                else:
                    heapq.heappush(res, cur_min)
            return
        elif res and len(visited)>res[0]:
            return
        else:
            x0,y0=pos[0],pos[1]
            for dx,dy in direcs:
                x,y=x0+dx,y0+dy
                if 0<=x<m and 0<=y<n and (x,y) not in visited and (x,y) not in Lakes:
                    visited.add((x,y))
                    dfs((x,y))
                    visited.remove((x,y))
    if m*n==0:
        print("0 0")
        exit()
    elif m==1 or n==1 and Lakes_num!=0:
        print("0 0")
        exit()
    else:
        dfs(Start)
        if not res:
            print("0 0")
        else:
            MIN=res[0]
            ans=0
            while res:
                tmp=heapq.heappop(res)
                if tmp==MIN:
                    ans+=1
                else:
                    break
            print(ans,MIN-1)
            #print(Paths)

第三题 300分

（我没做出来！）
搜到了leetcode原题：编码最短长度的字符串：
给定一个 非空 字符串，将其编码为具有最短长度的字符串。

编码规则是：k[encoded_string]，其中在方括号 encoded_string 中的内容重复 k 次。

注：

k 为正整数
如果编码的过程不能使字符串缩短，则不要对其进行编码。如果有多种编码方式，返回 任意一种 即可

    string encode(string s) {
        vector<vector<string>> d(s.size(),vector<string>(s.size(),""));
        return dfs(s,0,s.size()-1,d);
    }

    string dfs(const string s,int i,int j,vector<vector<string>>& d){
        if(i > j) return "";
        string& ans=d[i][j];
        if(ans.size()) return ans;
        int len = j-i+1;
        ans=s.substr(i,len);
        if(len < 5) return ans;
        int p=(ans+ans).find(ans,1);
        if(p < len){
            ans=to_string(len/p)+"["+dfs(s,i,i+p-1,d)+"]";
        }
        for(int k=i;k<j;++k){
            string c=dfs(s,i,k,d);
            string e=dfs(s,k+1,j,d);
            if(c.size()+e.size() < ans.size()){
                ans=c+e;
            }
        }
        return ans;
    }