循环不变量

本文用数组可比性，实现简化哈希计算每个字母出现次数是否相同，兼之快排与滑动窗口思想。

荷兰旗

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。假定使用整数 0、 1 和 2 分别表示红色、白色和蓝色。要求 使用常数空间的一趟扫描算法实现

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

分析

• 结果集显示分三区，以1为基准，小于，等于，大于三区
• 实质是快排的简化版，合理设置循环不变量，交换数组指针，平行赋值

解法

func sortColors(nums []int)  {
    // all in [0, l) = 0
    // all in [l, i) = 1
    // all in [r, len - 1] = 2
    for i,l,r := 0,0,len(nums);i< r; {
        if nums[i] == 0 {
            nums[i],nums[l] = nums[l],nums[i]
            l++
            i++
        }else if nums[i] == 1 {
            i++
        }else {
            r--
            nums[i],nums[r] = nums[r],nums[i]
        }
    }
}

异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

思路

• 异位词只有英文小写字母组成，可用长度为26数组表示
• 用数组代替哈希，进行窗口合理性移动，注意窗口初始化填充

  func findAnagrams(s string, p string) []int {
    ans := []int{}
    arr := [26]int{}     // 26个英文字母，用数组代替哈希
    for i := range p {
        arr[p[i]-'a']++
    }
    for l,r,win := 0,0,[26]int{}; r < len(s);r++ {
        win[s[r] - 'a']++ 
        if r+1 < len(p){ // 防止循环不变量漏算
            continue   // 等待滑动窗口初始化填充
        }
        if win == arr { // 数组具有可比性，简化哈希相同字符出现次数逐一比较
            ans = append(ans, l)
        }
        win[s[l]-'a']--  // 窗口滑动
        l++
    }
    return ans
  }

  其它

• 循环不变量，不重，不漏，不越界
• 开闭区间，交换，自增，自减有序，合理

本作品采用《CC 协议》，转载必须注明作者和本文链接