首页 > 3.27 网易4道笔试题
头像
煎饼果子w
编辑于 2021-04-17 10:25
+ 关注

3.27 网易4道笔试题

第一题: 二叉树最短路径

dfs+栈,和leetcode题 面试题34. 二叉树中和为某一值的路径 类似。

第二题:远离污染工厂问题

bfs遍历,和leetcode题 1162. 地图分析 类似

第三题:满减优惠问题

给定一系列商品价格[x,y,z,...]和满减价格T以及优惠y,需要从商品中找出某几件商品,满足凑够T元的同时超出的部分最少(最大化满减收益),将该价格减去优惠后输出。

dp动态规划,类似0-1背包问题,这里有一篇解答 促销中“满X优惠”问题的两种解法:动态规划和枚举法

第四题:魔鬼字符串

给定长度相同都为n的字符串s0和s1,找出在它们字典序中间、并且不包含b的所有字符串的数量。

题中给了个例子:

Input:
2
aa
da

Output:
51

意思大概就是在aada字典序之间的字符串有

aa,ab,ac,ad,...,az // 25个, ab不符合,因为里面含有b
ba,bb,...,bz, // 0个, 都不符合,因为是b开头
ca,cb,...,cz, // 25个, cb不符合,含有b
da # 1个

总共是有25+0+25+1=51个符合要求的魔鬼字符串。

没来得及做,只有一个dfs思路,不知是否可行。

来自评论区补充:
此题同leetcode题 1397. 找到所有好字符串,使用数位DP,非常有难度

全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐