鱼C论坛

 找回密码
 立即注册
查看: 2930|回复: 28

Python:每日一题 376

[复制链接]
发表于 2020-4-15 13:32:05 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 zltzlt 于 2020-4-15 13:36 编辑

今天的题目:


给定两个字符串 word1 和 word2,找到使得 word1 和 word2 相同所需的最小操作数,每一个操作可以删除任意一个字符串中的一个字符

示例:

输入:word1 = "sea", word2 = "eat"
输出:2
解释:第一步将 "sea" 变为 "ea",第二步将 "eat" 变为 "ea" 。


欢迎大家一起答题!

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-4-15 13:36:32 | 显示全部楼层
本帖最后由 蒋博文 于 2020-4-15 14:56 编辑
def fun376(word1, word2):
    len1 = len(word1)
    len2 = len(word2)

    dp = [[0 for i in range(len2 + 1)] for j in range(len1 + 1)]
    dp[0][0] = 0
    for i in range(1,len2 + 1):
        dp[0][i] = dp[0][i - 1] + 1
    for i in range(1,len1 + 1):
        dp[i][0] = dp[i-1][0] + 1
        for j in range(1,len2 + 1):
            if word1[i-1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j] + 1,dp[i][j - 1] + 1)
    return dp[len1][len2]

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 13:40:05 | 显示全部楼层
本帖最后由 kinkon 于 2020-4-15 14:31 编辑
def f376(word1, word2):
    
    n1, n2 = len(word1), len(word2)
    dp = [0] * (n2 + 1)
    for i in range(n1 + 1):
        temp = [0] * (n2 + 1)
        for j in range(n2 + 1):
            if i == 0 or j == 0:
                temp[j] = i + j
            elif word1[i - 1] == word2[j - 1]:
                temp[j] = dp[j - 1]
            else:
                temp[j] = min(dp[j], temp[j - 1]) + 1
        dp = temp[:]
        #print(dp)

    return dp[n2]

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 14:00:14 | 显示全部楼层
占楼
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-4-15 14:06:03 | 显示全部楼层
@zltzlt 想问一下两个字符串是不是一样长?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 14:57:49 | 显示全部楼层
kinkon 发表于 2020-4-15 14:06
@zltzlt 想问一下两个字符串是不是一样长?

应该是可以不一样长的吧。反正我这样写的。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 15:17:25 | 显示全部楼层
蒋博文 发表于 2020-4-15 14:57
应该是可以不一样长的吧。反正我这样写的。

嗯嗯,我也是这样想的,字符串一样长的话会简单些
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 15:42:21 | 显示全部楼层
本帖最后由 TJBEST 于 2020-4-15 21:14 编辑

采用了一种算法,因为本人不太精通算法,不知道有没有成套的系统
我通过数学的数组递归得出的结论
f(i,j)表示从word1取前i元素构成字符串str1,word2取前j元素构成字符串str2时,可以从str1和str2中找到相同的子列的长度的最大值。(子列定义为:从字符串中选择若干字符并将他们按照在原有字符串的顺序拼接在一起组成的新字符串)
当word1[i-1]==word2[j-1] 显然为f(i,j)=f(i-1,j-1)+1
当word1[i-1]!=word2[j-1] 可知f(i-1,j)和f(i,j-1)至少有一个和f(i,j)相等且根据定义可知 f(i-m,j-n)<= f(i,j)(m,n都是非负数)存在。所以f(i,j)=min{f(i-1,j),f(i,j-1)}
最后的结果两个字符串总长度 减去 两倍保留的长度(保留的长度即f(len(word1),len(word2),删完剩下的字符串长度)
上面的推导不是三言两语说明白的,语言能力有限
def fun376(word1,word2):
    M1 = len(word1)
    M2 = len(word2)
    previous = [0]*(M2+1)
    for i in range(1,M1+1):
        now = [0]
        for j in range(1,M2+1):
            if word1[i-1]==word2[j-1]:
                now.append(previous[j]+1)
            else:
                now.append(max(previous[j],now[-1]))
        previous = now[:]
    return M1+M2-previous[-1]*2

评分

参与人数 1荣誉 +4 鱼币 +4 收起 理由
zltzlt + 4 + 4

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 15:44:16 | 显示全部楼层
楼主, word里的字符可以重复出现吗
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-15 17:03:27 | 显示全部楼层
旅途Z 发表于 2020-4-15 15:44
楼主, word里的字符可以重复出现吗

可以
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-15 17:03:39 | 显示全部楼层
kinkon 发表于 2020-4-15 14:06
@zltzlt 想问一下两个字符串是不是一样长?

不是一样长的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 18:01:32 | 显示全部楼层
本帖最后由 风魔孤行者 于 2020-4-15 18:23 编辑
def f(word1,word2):
    a = len(word1)+len(word2)
    new_word = ''
    for each in range(len(word1)):
        word3 = word1[each:]
        word4 = word2
        new = ''
        for m in word3:
            if m in word4:
                word4 = word4[word4.find(m)+1:]
                new += m
        if len(new) > len(new_word):
            new_word = new
    return a-len(new_word)*2

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 20:47:01 | 显示全部楼层
本帖最后由 March2615 于 2020-4-15 22:04 编辑

整理思路用了好久
# 解题思路:word1和word2剩余的一定是两者共有的word3(不一定连续,但一定在两遍都出现)
# 字符串的增删改操作 -> 动态规划
# 动态转移方程:
# 遍历word1和2,
# 一个字母如果在两个里面都有,则在word3中也有
# 否则,要么在1没有,要么在2没有
# 建立一个二维数组dp[len(word1)][len(word2)]
# dp[i][j]表示遍历word1[i]和word2[j]时word3的长度
# 若字母在两个里面都有,则 -> dp[i][j] = dp[i-1][j-1] + 1
# 否则,word3长度是dp[i-1][j]和dp[i][j-1]的较大值 -> dp[i][j] = max(dp[i-1][j], dp[i][j-1])
def daily376(word1: str, word2: str) -> int:
    l1, l2 = len(word1), len(word2)
    dp = [[0 for _ in range(l2 + 1)] for _ in range(l1 + 1)]
    for i in range(1, l1 + 1):
        for j in range(1, l2 + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return l1 + l2 - 2 * dp[l1][l2]
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-15 20:50:57 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-15 20:51:23 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-15 20:52:12 | 显示全部楼层
TJBEST 发表于 2020-4-15 15:42
采用了一种算法,因为本人不太精通算法,不知道有没有成套的系统
我通过数学的数组递归得出的结论
f(i,j) ...

解答错误

输入:word1 = "ab", word2 = "a"
输出:3
预期结果:1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-15 20:52:54 | 显示全部楼层

解答错误

输入:
word1 = "intention", word2 = "execution"
输出:10
预期结果:8
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 21:15:12 | 显示全部楼层
zltzlt 发表于 2020-4-15 20:52
解答错误

输入:word1 = "ab", word2 = "a"

已修改,见8楼@zltzlt
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2020-4-15 21:28:26 | 显示全部楼层
TJBEST 发表于 2020-4-15 21:15
已修改,见8楼@zltzlt

解答错误

输入:word1 = "food", word2 = "money"
输出:5
预期结果:7
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-4-15 21:39:53 | 显示全部楼层
本帖最后由 TJBEST 于 2020-4-15 21:41 编辑
zltzlt 发表于 2020-4-15 21:28
解答错误
输入:word1 = "food", word2 = "money"


@zltzlt
多改了一个-1,这次应该对了。
def fun376(word1,word2):
    M1 = len(word1)
    M2 = len(word2)
    previous = [0]*(M2+1)
    for i in range(1,M1+1):
        now = [0]
        for j in range(1,M2+1):
            if word1[i-1]==word2[j-1]:
                now.append(previous[j-1]+1)
            else:
                now.append(max(previous[j],now[-1]))
        previous = now[:]
    return M1+M2-previous[-1]*2

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
zltzlt + 2 + 2

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-20 16:33

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表