反直觉正循环删除
0 / 0 / 创建于 4年前 /
pardon110 的个人博客
反直觉的正向循环
(i++)删除元素，看似不可取，但在某些时候恰到好处。
正向删除可变循环对象，往往会产生不可期结果。
但采取类似回拔复位修正行为，来消除其副作用，在合适的时机，地点使用，会有情理之中的巧妙。
问题#
给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。
你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。
在执行完所有删除操作后，返回最终得到的字符串。
输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/remove-al...
分析#
- 本文用切片模拟栈的操作（list 容器太重，麻烦）
- 一个充作计数器栈，一个为可变的字节切片栈
- 在循环体内，字节切片栈发生修改时，修正循环变量 i 差值
实现#
func removeDuplicates(s string, k int) string {
cnt :=[]int{}
stack :=[]byte(s)
for i:=0;i<len(stack);i++{
if i==0 || stack[i]!=stack[i-1]{
cnt = append(cnt,1)
}else{
top := cnt[len(cnt)-1]
cnt = cnt[:len(cnt)-1]
if top+1==k{
stack = append(stack[:i-k+1],stack[i+1:]...)
i-=k
}else{
cnt = append(cnt,top+1)
}
}
}
return string(stack)
}整理字符串#
一个由大小写英文字母组成的字符串 s
输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""链接：leetcode-cn.com/problems/make-the-...
解析#
- 同等字母字符大小写差值 32
- 回拔一个删除位 2，执行顺序 自增，条件判定
- 注意数组可能存在的越界情况
上码#
func makeGood(s string) string {
rs :=[]byte(s)
for i:=0;i<len(rs);i++{
if i>0 && (rs[i]+32 ==rs[i-1] || rs[i]==rs[i-1]+32){
if i+1 == len(rs){
rs = rs[:i-1]
}else{
rs = append(rs[:i-1],rs[i+1:]...)
}
i-=2
}
}
return string(rs)
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号