// [0,0,1,1,1,2,2,3,3,4] => [0,1,1,...] => .. => [0, 1, 2, 3, 4]
func removeDuplicates_invariant(nums []int) int {
ln := len(nums)
if ln < 2 {
return ln
}
// 循环不变量 nums[0..j] 没有重复元素
// j 是刚刚赋值完的元素的下标
j := 0
for i := 1; i < ln; i++ {
if nums[i] != nums[j] { // 找到不重复的元素 [0,0,1]
j++
nums[j] = nums[i] // [0,1,..] j 指向第一个不重复的元素
}
}
return j + 1
}
// [0,1,0,3,12] => [1,3,12,0,0]
func moveZeroes(nums []int) {
ln := len(nums)
if ln < 2 {
return
}
// 循环不变量：nums[0..j] 非零，且保持顺序，j 指向马上要赋值的元素
// nums(j..i) = 0
j := -1
for i := 0; i < ln; i++ {
if nums[i] != 0 {
j++
nums[j] = nums[i]
}
}
for i := j+1; i < ln; i++ {
nums[i] = 0
}
}
92. Reverse Linked List II
要求在一轮遍历中将第 m 个节点到第 n 个节点逆转，关键是从逆转操作中抽象出「循环不变式」建立虚拟头节点并应用头插法
循环不变式子代码 ( pre 为反转区间的前一节点即图中的 1
单向链表的重排操作上应该是单向顺序 1->3 再 2->4
tmp := pre.Next // 2, 3 遍历右边界前各节点
pre.Next = cur.Next // 1->3, 1->4 分别断开各节点的前指
cur.Next = cur.Next.Next // 2->4, 2->5 (2 作为游标不断往后指
pre.Next.Next = tmp // 3->2, 4->3
后序遍历的数组最后一个元素代表的即为根节点。知道这个性质后，我们可以利用已知的根节点信息在中序遍历的数组中找到根节点所在的下标，然后根据其将中序遍历的数组分成左右两部分，左边部分即左子树，右边部分为右子树，针对每个部分可以用同样的方法继续递归下去构造。
func buildTree(inorder []int, postorder []int) *TreeNode {
idxMap := map[int]int{}
for i, v := range inorder {
idxMap[v] = i
}
var build func(int, int) *TreeNode
build = func(inorderLeft, inorderRight int) *TreeNode {
// 无剩余节点
if inorderLeft > inorderRight {
return nil
}
// 后序遍历的末尾元素即为当前子树的根节点
val := postorder[len(postorder)-1]
postorder = postorder[:len(postorder)-1]
root := &TreeNode{Val: val}
// 根据 val 在中序遍历的位置，将中序遍历划分成左右两颗子树
inorderRootIndex := idxMap[val]
// 循环不变量为左右区间 [left, root-1], [root+1, right]
// 由于我们每次都从后序遍历的末尾取元素，所以要先遍历右子树再遍历左子树
root.Right = build(inorderRootIndex+1, inorderRight)
root.Left = build(inorderLeft, inorderRootIndex-1)
return root
}
return build(0, len(inorder)-1)
}
遵循左闭右开：可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。