首页 > 华为09-06笔试 部份题解(期望步数)
头像
Yasu0
编辑于 2020-09-20 00:36
+ 关注

华为09-06笔试 部份题解(期望步数)

三面都过了,泡池子中,求offer


第一题简单题
第二题题目真读不懂 乱写
第三题概率+dp 测试用例比较弱

  1. n 个个字符串,一个数字, 一个匹配字符串,每个字符串中的字符小于那个数字就作为特征值 , 然后判断和匹配字符串的特征值相同(或者包含关系)的字符串 .
    ex. 字符串 数字 -> 特征
    "239123" "3" -> "212"
    这题比较简单,注意读入,输出和包含关系(用contains不要用equals)就行
  1. 编辑距离?完全不懂,感觉给的用例都是错的。

"This is a book!" 和 "This is book!" 差值为 1
"This is a book!" 和 "This is book" 差值也为 1 ??? (符号差一,单词差一,不应该2吗)

"This is a book!" 和 "This is a duck" 差值为 2
"is This a book!" 和 "is this a book?" 差值为 1 ??? (说了符号和单词一样的算)

直接hashmap乱写一通,顺序都不考虑了,拿了40%, 放弃

  1. m*n 矩阵,求从左上角到右下角的步数期望,每个格子往下往右原地不动的概率分别为PD,PR,PS.
    dp[i][j] 表示 从(i,j)到终点的期望步数
    dp[i][j] = 1 + PD * dp[i+1][j] + PR * dp[i][j+1]  + PS * dp[i][j] 
    dp[i][j] = ( 1 + PD * dp[i+1][j] + PR * dp[i][j+1] ) / (1 - PS)
    (i,j) 只依赖 i+1 and j+1 ,满足动态规划的性质
  • 从下往上
    • 从右往左
      • dp就ok

本来以为有很奇怪的出界的case,提交看看就过了

三面都过了,等池子中

全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐