循环不变量

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

荷兰旗

给定一个包含红色、白色和蓝色,一共 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 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
128
粉丝
19
喜欢
92
收藏
46
排名:98
访问:4.7 万
私信
所有博文