首页 > 3.30 SAP VT实习生-2022研发岗 2道笔试题
头像
煎饼果子w
编辑于 2021-04-17 18:00
+ 关注

3.30 SAP VT实习生-2022研发岗 2道笔试题

第一题:错别字

签到题

1. 题目描述

小王在抄会议记录,但他手比较抖,有一些单词出现了错误,现在让你统计他抄的记录中所有不同情况错误出现的次数,共有三种情况:

  • 连续抄错一个单词的次数
  • 连续抄错两个单词的次数
  • 连续抄错三个及以上单词的次数

这里抄错的定义是:只要两个单词不是完全一致,包括缺少/增加字母、改变字母大小写,都算是抄错。
注意:小王只会抄错,不会漏抄或者多抄(说人话就是两个字符串单词的个数是相等的)。

输入输出样例:

Input:
17
Hello everyone let us discuss the problem and I believe you are smart enough to solve it
HELLO everyone lat is discus the probelm and i beelieve u r smart through two solve it
Output:
2 1 2

输入表示会议记录一共有17个单词,单词之间由空格分隔,接下来是原文和小王的记录,
输出表示连续抄错一个单词的有2次,连续抄错两个单词的有1次,连续抄错三个及以上单词的有2次。

如果用一个表示是否抄错的数组表示,即为 (1表示该单词抄错了)

[1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0]

一下就能看出来答案。

2. 解法

两趟遍历,(也可以优化为一趟遍历)

# -*- encoding: utf-8 -*-

"""
@Author : Soarkey
@Date   : 2021/3/30
@Desc   : 错别字
"""

if __name__ == '__main__':
    while True:
        try:
            n = int(input())
            s1 = input().split(' ')
            s2 = input().split(' ')

            error = [0] * (n + 1)  # 多加1位保证最后一个是错误的情况能被cover住
            for i in range(n):
                if s1[i] != s2[i]:
                    error[i] = 1

            print(error)

            one_error = 0
            two_error = 0
            more_than_two_error = 0

            k = 0  # 表示连续k个错误
            for i in range(n + 1):
                if error[i] == 1:
                    k += 1
                else:
                    if k == 1:
                        one_error += 1
                    if k == 2:
                        two_error += 1
                    if k >= 3:
                        more_than_two_error += 1
                    k = 0

            print(f'{one_error} {two_error} {more_than_two_error}')

        except EOFError:
            break

第二题:乌龟快跑

1.题目描述

给定一个n*n的有向图,共有m条有向边,边的权值代表了该条边上的兔子数量,乌龟要从起始点s爬到终点t,但是只允许走x步(即经过x条边),题目数据保证满足约束条件的情况下一定存在从起点到终点的路径。

乌龟经过每一条边都会被该条边上的兔子(数量为该边权值)嘲讽,请问这个玻璃心乌龟该走哪条路,能够最小化受到的嘲讽,输出该条路径上兔子最多的边的兔子数量。

(说人话就是从能到达终点的路径中找到最短的路径,输出该条路径上边的最大权值)

输入输出样例

Input:
5 6 1 5 2
1 5 100
1 2 10
2 5 5
1 3 3
3 4 2
4 5 1
Output:
10

输入第一行为n,m,s,t,x,接下来的m行为有向边的(起点,终点,权值)该输入构成的图为:

输入输出样例

可以看出从起点2到终点5的满足步长为2的路径有红色和蓝色两条边,其中最短的路径为红色路径,该路径上最大的权值为10

2. 解法

图论问题,用dfs遍历

# -*- encoding: utf-8 -*-

"""
@Author : Soarkey
@Date   : 2021/3/30
@Desc   : 乌龟兔子
"""

if __name__ == '__main__':
    while True:
        try:
            n, m, s, t, x = tuple(map(lambda x: int(x), input().split()))
            graph = [[0 for j in range(n + 1)] for i in range(n + 1)]
            for _ in range(m):
                a, b, v = tuple(map(lambda x: int(x), input().split()))
                graph[a][b] = v
            # print(graph)
            path = []
            vis = [False for i in range(n + 1)]
            rabbits = []
            min_rabbits = 9999999

            def dfs(i, depth):
                global vis, t, x, graph, min_rabbits, rabbits
                if i == t:
                    # 找到
                    # print(rabbits)
                    min_rabbits = min(min_rabbits, max(rabbits))
                    return
                if depth >= x:
                    # 超过步长
                    return

                for j in range(len(graph[i])):
                    if not vis[j] and graph[i][j] > 0:
                        vis[j] = True
                        rabbits.append(graph[i][j])
                        dfs(j, depth + 1)
                        rabbits.pop()
                        vis[j] = False

            dfs(s, 0)
            print(min_rabbits)

        except EOFError:
            break

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

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

近期精华帖

热门推荐