数据结构 百度搜索优化 ansible architecture cocos2d html5 jquery选择器找子元素 oracle查询所有数据库 rxjava线程切换 matlab颜色代码 hash怎么下载 pythonsocket编程 python3正则表达式 python搭建网站 java基础入门 java开发者 java循环语句 java写入txt文件 java时间类型 java定义 linux安装系统 java项目下载 嵌入式linux驱动程序设计从入门到精通 python封装 wine模拟器 源计划艾克 2700U 任意屏官网 qq魔法卡片登陆 lol无限视野 手机刷机助手 vs2017密钥 汉仪旗黑字体下载 劳动节称号 数据挖掘案例 ie内核修复 未能创建视频预览 苹果手机放大镜怎么关 cad2012激活 文字图片制作软件 怎么调整照片像素
当前位置: 首页 > 学习教程  > python

力扣 leetcode 1208. 尽可能使字符串相等 (python)滑窗 + 双指针

2021/2/7 9:55:33 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

Topic 给你两个长度相同的字符串,s 和 t。 将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。 用于变更字符串的最大预算是 maxCost。在转化字符串…

Topic

给你两个长度相同的字符串,s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串,则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串,则返回 0。

Example_1

输入:s = “abcd”, t = “bcdf”, cost = 3
输出:3
解释:s 中的 “abc” 可以变为 “bcd”。开销为 3,所以最大长度为 3。

Example_2

输入:s = “abcd”, t = “cdef”, cost = 3
输出:1
解释:s 中的任一字符要想变成 t 中对应的字符,其开销都是 2。因此,最大长度为 1。

Example_3

输入:s = “abcd”, t = “acde”, cost = 0
输出:1
解释:你无法作出任何改动,所以最大长度为 1。

Tips

1 <= s.length, t.length <= 10^5
0 <= maxCost <= 10^6
s 和 t 都只含小写英文字母。

Solution_1

我们采用二分法加滑动窗口的方法

首先我们需要对s和t中每一位的消耗进行计算
(消耗即是两个字符的 ASCII 码值的差的绝对值)

之后我们可以遍历消耗序列
计算每一位的前缀和
(从第一位到遍历为的所有消耗和)

但是这样两次遍历计算会导致运行效率低下
运算时间超时
所以需要在第一次计算消耗的同时计算前缀和
在这里可以使用itertools库中的accmulate函数计算前缀和

由于bisect.left二分查找
返回的是放置位置的前一个
所以需要将all_cost向后挪一位

之后继续遍历计算完前缀和的列表
利用前缀和减去最大消耗值
寻找窗口左侧值放置的位置
利用i - pos寻找窗口的长度

最后返回最大窗口长即是结果

Code_1

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        all_cost = [0] + list(itertools.accumulate(abs(ord(a) - ord(b)) for a, b in zip(s, t)))
        max_Length = 0

        for i in range(1, n + 1):
            pos = bisect.bisect_left(all_cost, all_cost[i] - maxCost)
            
            if i - pos > max_Length:
                max_Length = i - pos

        return max_Length

Result_1

在这里插入图片描述

Solution_2

双指针方法(也可看成滑动窗口法)
双指针方法我们就不用前缀和了
(用前缀和也可以处理但是反而增加了麻烦)

第一步同样是先我们需要对s和t中每一位的消耗进行计算
之后设置left和right指针

我们对于窗口中的值设置为num
right指针每向右移动一位
num就加上相应的值

同时如果遇到num比最大消耗还要大的情况
则需要不断右移左指针同时减去all_cost中的值
直至窗口中的消耗值num小于最大消耗
不断返回窗口的较大值

在这里建议两者返回最大值用判断而非max
只用一个判断会比max效率更高

最后返回窗口的最大值max_length即为结果

Code_2

class Solution:
    def equalSubstring(self, s: str, t: str, maxCost: int) -> int:
        n = len(s)
        all_cost =  list(abs(ord(a) - ord(b)) for a, b in zip(s, t))
        max_length = 0
        left = right = 0
        num = 0

        while right < n:
            num += all_cost[right]

            while num > maxCost:
                num -= all_cost[left]
                left += 1
                
            if right - left + 1 > max_length:
                max_length = right - left + 1
                
            right += 1
        
        return max_length

Result_2

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000206.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?