leetcode-76-Minimum Window Substring

edagarli 发布于2019-07-31 11:10 / 1653人阅读

摘要：逐步逼近法，类似于牛顿迭代法。重点是找到规律，然后将规律加以表示。动态规划，相邻两个位置之间的关系。字符串的叠加，可以增加共性，通过相减可以得到边界位置处符合规律的要求。学会将问题转化为可求的边界问题。

吃透题目：

任何问题的解决在于理解题目，挖掘本质。 
这道题目，从一个string中找包含char的最小子序列，O(n)，要求只能遍历一遍。
每次移动一个index，都尝试找子序列，通过对目标子序列统计数目，与当前的char的数目进行合并，然后子循环while的时候，通过减法操作，达到==0的条件时候，就可以知道这是最短的子序列的边界，同理for循环向后迭代。

相似： kmp算法，保持状态，省略不必要的遍历，从上次移动到的位置i，继续向后移动。

  逐步逼近法，类似于牛顿迭代法。重点是找到规律，然后将规律加以表示。
  动态规划，相邻两个位置之间的关系。

应用：

学会记录状态，没有必要再次重复的位置，通过记录加以过滤。
字符串的叠加，可以增加共性，通过相减可以得到边界位置处符合规律的要求。
学会将问题转化为可求的边界问题。

import collections

class Solution:
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        missing=len(t)
        need=collections.Counter(t)
        i=I=J=0
        # J=len(s)
        for j,c in enumerate(s,1):
            missing-=need[c]>0
            need[c]-=1
            if not missing:
                # tmp1=s[i]
                # tmp3=need[s[i]]
                # tmp2=need[s[i]] < 0
                while (i=0 and j-i<=J-I) or J==0:
                    I=i
                    J=j
        # print("I,J==>",I,J)
        return s[I:J]

if __name__=="__main__":
    S = "ADOBEBCBODEBBANNNNACB"
    T = "ABC"
    S="ab"
    T="a"
    # S="a"
    # T="aa"
    st=Solution()
    out=st.minWindow(S,T)
    print("out==>",out)

GPU云服务器云服务器 Substring SUBSTRING_INDEX java的substring方法 js_substring_substr

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44744.html

Leetcode[76] Minimum Window Substring

LeetCode[76] Minimum Window Substring Given a string S and a string T, find the minimum window in S whichwill contain all the characters in T in complexity O(n). For example, S = ADOBECODEBANC T = AB...

suemi 2019-08-16 10:26 评论0 收藏0
[leetcode] Minimum Window Substring

摘要：使用而不是因为我们需要的是最值，中间值我们不在乎，所以一次收敛到最小。下面来三个需要查重并且记录上次出现的位置，选择以为例，走到用做检查，发现出现过，把移到的下一个。是上个题目的简易版，或者特殊版。这里聊一聊解一类问题，就是满足某一条件的substring最值问题。最开始我们以Minimum Window Substring为例，并整理总结leetcode里所有类似题目的通解。 Gi...

Pines_Cheng 2019-08-14 17:17 评论0 收藏0
实战项目之自动简历

摘要：自动简历项目介绍一个可以自动播放书写过程简历，主要运用原生和的知识点。方法如果展示窗口设置的是或者会自动拉到底部为滚动至底部为滚动至顶部其他参数可选定义缓动动画，或之一。增加简历展示页编写增加编写简历内容的展示窗口。自动简历项目介绍一个可以自动播放书写过程简历，主要运用原生JS和CSS3的知识点。用到的库： prism marked 相关链接预览点我源码点我show...

Eric 2019-08-29 16:44 评论0 收藏0
实战项目之自动简历

摘要：自动简历项目介绍一个可以自动播放书写过程简历，主要运用原生和的知识点。方法如果展示窗口设置的是或者会自动拉到底部为滚动至底部为滚动至顶部其他参数可选定义缓动动画，或之一。增加简历展示页编写增加编写简历内容的展示窗口。自动简历项目介绍一个可以自动播放书写过程简历，主要运用原生JS和CSS3的知识点。用到的库： prism marked 相关链接预览点我源码点我show...

Chao 2019-08-23 12:00 评论0 收藏0