首页 > 华为3.31机试AK题解
头像
老萌新
编辑于 2021-04-18 10:24
+ 关注

华为3.31机试AK题解

第一题:
直接开一个26长度的结构体数组(结构体有队伍名字'a-z',得分)。然后读入字符串,按照题意计算对应的字母的得分,累加到对应数组位置上,比如'a'的对应位置是0,z是25。最后按照得分第一关键字从高到低,名字第二关键字从低到高排序就可以了。

第二题:
1.假如a说有x个人和他一样颜色,那么a的颜色至多能容纳(x+1)个人。
2.假如a说x,b说y,那么a和b的颜色一定不一样,为什么呢?举个例子,有两种颜色分别为1,2。假设分布为 1 1 2 2 2 ,其中a为1颜***为2颜色,那么a会说1,b会说2。假设b为1颜色,那么b也会说1。
3.前两点得出的结论就是说,其实每个人相当于买了一栋楼,楼里的房间个数为(x+1),自己先占了一间,然后这栋楼还可以住和他说一样的数字——也就是x的人。注满即止。如果有(x+2)个人说了x,那么就得新买一栋楼。
4.所以答案很显然了,直接求出说x的人数,然后求这些说x的人数至少得住几栋楼,那么就是  ceil (cnt(x) / (x+1))。 其中ceil是向上取整。
5.用4的方法对每个x累加即可。

第三题:
贪心是错的,暴力回溯会超时,正解是dp。
dp的话其实也有几种思路,其中一种就是评论区老哥发的leetcode上的一道类似题的官方解法https://leetcode-cn.com/problems/freedom-trail/。感兴趣的自己去看,他的复杂度是O(n^2m)的。
在这里讲下我的做法吧,复杂度是O(nm)的。
首先:用start表示游标起始位置,n表示字符数组长度,m表示匹配串长度。a表示字符数组,b表示匹配串。
1.前面的表示以及dp转移其实和leetcode题解是相似的。
2.dp[i][j]表示现在游标指在a的i位置,匹配了b的j个字符,所用的最少的移动次数。
3.初始化dp[i][j]=INF(也就是正无穷,1e7以上就行,我用的1e8)
4.那么dp[start][0] = 0。其余的dp[i][0] = min(abs(i-start),n-abs(i-start) ) 也就是向左或者向右取最小的步数。
5.转移方程:
(1) dp[i][j] = dp[i][j-1]  if a[i] == b[j] (也就是不用移动游标了,因为当前的i就可以匹配了)
(2) dp[i][j] = min(dp[i][j],dp[i+1][j])  这个i和i+1记得取模,这里就不写了
(3) dp[i][j] = min(dp[i][j],dp[i-1][j])  这个i和i-1记得取模,这里就不写了
6.过程:
  1. 枚举j
  2. 遍历a,如果a[i]==b[j],那么用(1)号方程转移
  3. 从后往前遍历两轮用(2)号方程转移
  4. 从前往后遍历两轮用(3)号方程转移
  5. 最后答案就是min dp[i][m] (i in 0 to n-1)

全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐