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

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

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，非常有难度