华为笔试

又报了华为的软件实习生
上来就笔试 还不能改时间 只能边上课边写 万幸题目还行
1、打乱字符串重新排列方法数 简单的排列
2、给一个字符串 修改k个字符 使得字典序最小
数据量是100000 本来N^2好像是过不了的 但是写了个N^2的好像还行??
对于每一位查找出后面k位的最小值 如果小于当前位 那直接删到对应那个位置就可以
如果大于或等于当前位 那么说明当前位没有优化空间 考虑下一位即可
实际上应该可以用单调栈来优化
3、有限制的一个最短路 每条道路有长度和过路费
求在一定金钱限制下的最短路
先跑一遍spfa出最少金钱 判断可不可达
可达的情况下 dfs找最短路 dfs是顺便传递当前金钱数,利用金钱数选择道路
复杂度感觉挺高的 然后好像能过???
找到原题了 poj1724
题解在这里
原题也过得非常快。。
正解确实好像就是:spfa/dijkstra+dfs/bfs

这两个题感觉都是题目数据太水好像....应该2有O(n)的算法吧 3应该有nlogn的吧
回头再想想

Last modification:April 29th, 2020 at 09:52 pm
如果觉得我的文章对你有用,请随意赞赏