Skip to end of metadata
Go to start of metadata

You are viewing an old version of this page. View the current version.

Compare with Current View Page History

« Previous Version 3 Current »

滑动窗口

模板

int left = 0, right = 0;

while (right < nums.size()) {
    // 增大窗口
    window.addLast(nums[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.removeFirst(nums[left]);
        left++;
    }
}
// 滑动窗口算法伪码框架
func slidingWindow(s string) {
    // 用合适的数据结构记录窗口中的数据,根据具体场景变通
    // 比如说,我想记录窗口中元素出现的次数,就用 map
    // 如果我想记录窗口中的元素和,就可以只用一个 int
    var window = ...

    left, right := 0, 0 // 把索引左闭右开区间 [left, right) 称为一个「窗口」
    for right < len(s) {
        // c 是将移入窗口的字符
        c := rune(s[right])
        window[c]++
        // 增大窗口
        right++
        // 进行窗口内数据的一系列更新
        ...

        // *** debug 输出的位置 ***
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时,可能导致超时
        fmt.Println("window: [",left,", ",right,")")
        // ***********************

        // 判断左侧窗口是否要收缩
        for left < right && window needs shrink { //replace "window needs shrink" with actual condition
            // d 是将移出窗口的字符
            d := rune(s[left])
            window[d]--
            // 缩小窗口
            left++
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

Minimum Window Substring 最小覆盖子串

https://leetcode.com/problems/minimum-window-substring/

func minWindow(s string, t string) string {
    T := toWindow(t)
    
    initialResult :=  "x" + s
    result := initialResult
    
    var window [52]int
    l, r := 0, 0
    for r < len(s) {
        windowAdd(&window, s[r])
        r++
        
        // fmt.Println("window: [",l,", ",r,")", s[l:r], "->", result)
        
        for l < r && windowContains(window, T) {
            if r - l < len(result) {
                result = s[l:r]
            }
            
            windowRemove(&window, s[l])
            l++
        }
    }
    
    if result == initialResult {
        return ""
    }
    
    return result
}

func toIndex(c byte) int {
    if c >= 'A' && c <= 'Z' {
        return int(c - 'A')
    } else if c >= 'a' && c <= 'z' {
        return 26 + int(c - 'a')
    } else {
        panic("Invalid character")
    }
}

func toWindow(s string) (w [52]int) {
    for _, r := range s {
        w[toIndex(byte(r))]++
    }
    return
}

func windowAdd(window *[52]int, c byte) {
    (*window)[toIndex(c)]++
}
func windowRemove(window *[52]int, c byte) {
    (*window)[toIndex(c)]--
}

func windowContains(window1, window2 [52]int) bool { // window1 contains all window2
    for i := range window1 {
        if window1[i] < window2[i] {
            return false
        }
    }
    return true
}
  • No labels