来自域外的视角
0 / 0 / 创建于 4年前 /
pardon110 的个人博客
本文以外观数列为例，添加些许小手段，实现类似单链表
dummy效果，化特殊为普通
引言#
算法边界处理，在域内视角很麻烦，不是漏条件了，就是写了一大堆相似处理逻辑，不甚优雅。
思路#
将特殊的边界情况，转化为普通的元素，直接抹平。
外观数列#
- 双指针
i先行，但末元素无法处理自身，因此末位添加一个字符串位$，合理越界修复 for与for range两个世界，一个索引字节，条件检测会自决可变性，而后者循环副本，rune 值输出
示例返回第 n 个外观数列字符串值
import "bytes"
import "strconv"
func countAndSay( n int ) string {
rs := "1"
var buf bytes.Buffer
for ;n>1;n--{
rs +="$"
for k,i:=0,1;i< len(rs);i++{
if rs[i-1]!=rs[i]{
buf.WriteString(strconv.Itoa(i-k))
buf.WriteByte(rs[i-1])
k=i
}
}
rs = buf.String()
buf.Reset()
}
return rs
}单链表 dummy#
单链表的元素删除，需要通过前驱元素操作，头节点由于不存在前驱，往往需要特殊对待。
用构建 dummy 结点，简化处理逻辑，将头节点当作普通节点操作即可，示例删除倒数第 n 个节点
func removeNthFromEnd( head *ListNode , n int ) *ListNode {
dummy := &ListNode{
Next: head,
}
slow,fast := dummy, dummy
for fast != nil && fast.Next != nil{
n--
if n < 0 {
slow = slow.Next
}
fast = fast.Next
}
slow.Next = slow.Next.Next
return dummy.Next
}
- 快慢指针找到被删除节点的前置节点
- 用哨兵虚拟节点，解决原生链头操作 bug
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：