2022.08.30 携程秋招笔试题目 |
您所在的位置：网站首页 › 携程在线测试题答案 › 2022.08.30 携程秋招笔试题目 |
|
算法1
题目描述：给你一个正整数，重排这个正整数的数位，使得它变成偶数，不能有前导0 输入描述：第一行整数q, 接下来的q行，一行一个整数 思路： 这个就需要从后往前走了，在走到开通之前如果能遇到偶数，说明可以满足条件 关于前导0的问题，题目中说明了输入的是正整数，所以数字0出现的位置一定是整数中间，所以只要出现了就交换位置就可以了 代码： n = int(input()) for _ in range(n): s = input() idx = -1 for i in range(len(s) - 1, -1, -1): if int(ord(s[i])-ord('0')) % 2 == 0: idx = i break if idx == -1: print(-1) else: s = list(s) s[idx],s[-1] = s[-1],s[idx] print(''.join(s)) 算法2题目描述：有a个'y',b个'o',c个'u';用这些字母组成一个字符串，you获得2分,oo是1分。问最多可以获得多少分？ 输入输出：第一行一个整数q,代表询问次数，接下来q行，每行三个正整数a,b,c，输出询问答案 思路：这个搞清楚a,b,c之间的关系就行了；首先计算可以组成you的数，那就是x=min(a,b,c) 之后 a-x,b-x,c-x 就看看还能拼成多少个oo啦，此时 o的个数是b-x ooo就可以看成两个 oo也就是2分，所以最后得分 2*x + max(0,b-x-1) 代码： q = int(input()) for _ in range(q): a, b, c = [int(x) for x in input().split(' ')] d = min(min(a, b), c) ans = d * 2 b -= d ans += max(0, b - 1) print(ans) 算法3题目：一棵树，染成了红(r)、绿(g)、蓝(b)，删除一条边，使得剩下的两个连通块恰好有三种颜色，求合法的删除（树指的是不含重边和自环的无向连通图） 输入输出：第一行正整数n(节点数量)、第二行长度为n的字符串(仅包含rgb)，第i个字符表示节点i的颜色，接下来的n-1行，是输入正整数u,v 代表节点u,v之间有一条边连接 思路：无向图；直接深搜；dfs(u,f)划分为两个区域，u和其儿子们放在一个区域计算，因为u和父亲断开，只是断一条边；如果和儿子们断开，可能断开多条边。 代码里有两个dfs 一个dfs用于统计每个节点子树下的rgb出现次数 一个dfs用于看看断开之后是否能满足条件。 def dfs(u, f): # ipdb.set_trace() num[u][mp[color[u]]] = 1 print(str(u)+'_'+ str(f)) for v in G[u]: if v != f: dfs(v, u) for j in range(3): num[u][j] += num[v][j] def dfs2(u, f): global ans for v in G[u]: if v != f: dfs2(v, u) flag = True for j in range(3): if num[v][j] == 0 or num[0][j] == num[v][j]: flag = False if flag: ans += 1 n = int(input()) color = input() G = [[] for i in range(n)] for i in range(n - 1): u, v = [int(x) - 1 for x in input().split()] G[u].append(v) G[v].append(u) # 存储和哪些节点进行相连 mp = {'r': 0, 'b': 1, 'g': 2} num = [[0 for j in range(3)] for i in range(n)] dfs(0, -1) ans = 0 dfs2(0, -1) print(ans)问题4： 描述：平滑值指的是在数组中，任意两个相邻的数的差的绝对值的最大值 [1,2,5,7,8] 的平滑值是3 目前，修改一个位置的数字（改成任意值）或者不修改，数列的平滑值最小应该为多少 思路：分别统计pre shu 【从前往后、从后往前的差值】，然后再一次遍历，去比较改变当前元素的变化。具体看代码吧 n = int(input()) a = [int(x) for x in input().split()] pre = [0] * n suf = [0] * n for i in range(1, n): pre[i] = max(pre[i - 1], abs(a[i] - a[i - 1])) for i in range(n - 2, -1, -1): suf[i] = max(suf[i + 1], abs(a[i] - a[i + 1])) ans = 200000000 for i in range(n): if i == 0 or i == n - 1: if i - 1 >= 0: ans = min(ans, pre[i - 1]) if i + 1 < n: ans = min(ans, suf[i + 1]) else: gap = int(math.ceil(abs(a[i - 1] - a[i + 1]) / 2)) ans = min(ans, max(max(pre[i - 1], suf[i + 1]), gap)) print(ans)笔试情况：算法1、2、4全A，算法3思路没错，猜测python的栈空间的问题，导致报错，通过75% |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |