哈希主打

最小覆盖子串

http://www.nowcoder.com/questionTerminal/c466d480d20c4c7c9d322d12ca7955ac

非典型滑动窗口思想

  1. 建立目标哈希

  2. 有序列表内容迭代过程重构待比哈希

  3. 比较通过则重置循环变量,初始化待比哈希

  4. 循环迭代提跳出

    func minWindow( S string ,  T string ) string {
    tm := make(map[byte]int,0)
    for i:=0;i<len(T);i++{
        tm[T[i]]++
    }
    
    minStr :=""
    ssm := make(map[byte]int,0)
    for i,k:=0,-1;i<len(S);i++{
        if _,ok:=tm[S[i]];ok {
            if k ==-1 {
                k = i
            }
           ssm[S[i]]++
        }
        if  k != -1 && cmpMap(tm,ssm){
            if k >len(S)-len(T){
                break
            }
            cur :=S[k:i+1]
            if len(minStr)>len(cur) || len(minStr)==0 {
                minStr = cur
            }
            i=k
            k=-1
            ssm = make(map[byte]int,0)
        }
    }
    return minStr
    }
    func cmpMap(t, s map[byte]int)bool {
     if len(t) != len(s){
         return false
     }
     for k,v :=range s {
         if v < t[k] {
             return false
         }
     }
     return true
    }
全部评论

相关推荐

牛客5655:其他公司的面试(事)吗
点赞 评论 收藏
分享
头像
11-09 12:17
清华大学 C++
out11Man:小丑罢了,不用理会
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-27 10:48
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务