首页 > 今晚小米的笔试题第二题
头像
零K同学
发布于 2021-06-11 20:30
+ 关注

今晚小米的笔试题第二题

int getSimilarity(string str2, string str1) {
	int len1 = str1.size(),len2 = str2.size();
    vector<vector<int>> dp(len1 + 1,vector<int>(len2 + 1,0));
    for(int i=1;i<=len1;++i) {
        dp[i][0] = i;
    }
    for(int j = 1;j<=len2;++j) {
        dp[0][j] = j;
    }
    for(int i=1;i<=len1;++i) {
        for(int j=1;j<=len2;++j) {
            //相同,啥也不做
            if(str1[i-1] == str2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            }
            else {
                dp[i][j] = min (
                	dp[i][j-1] + 1,
                    min (
                    	dp[i-1][j] + 1,
                        dp[i-1][j-1] + 1
                    )
                );
            }
        }
    }
	return dp[len1][len2];
今晚(2021-06-11:19:00)小米笔试有朋友做了么?编程题第二题,用动态规划这样写为什么只能AC80%。很疑惑。有没有大佬解答一下。
这题和 leetcode72 题 应该是差不多的。

全部评论

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

推荐话题

相关热帖

近期热帖

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

近期精华帖

热门推荐