2022-04-07:给定一个只由'a'和'b'组成的字符串str,
str中"ab"和"ba"子串都可以消除,
消除之后剩下字符会重新靠在一起,继续出现可以消除的子串...
你的任务是决定一种消除的顺序,最后让str消除到尽可能的短。
返回尽可能的短的剩余字符串。
来自阿里。
答案2022-04-07:
方法一:栈。
方法二:分别求a和b的个数,然后做差,谁多输出谁。这个方法是我另外想的,经过大量测试,准确无误。
时间复杂度:O(N)。
代码用golang编写。代码如下:
package main
import (
"fmt"
"math/rand"
"strings"
"time"
)
func main() {
rand.Seed(time.Now().UnixMilli())
const TOTAL = 10000
sucCount := 0
for i := 0; i < TOTAL; i++ {
s := getRandString()
fmt.Println(s)
ret1 := disappear3(s)
fmt.Println("disappear3 = ", ret1)
ret2 := disappear4(s)
fmt.Println("disappear4 = ", ret2)
if ret1 == ret2 {
sucCount++
}
fmt.Println("---------------------")
}
fmt.Println("成功 = ", sucCount)
}
func disappear3(s string) string {
str := []byte(s)
n := len(str)
// 用数组结构,自己实现栈
stack := make([]int, n)
size := 0
for i := 0; i < n; i++ {
hasA := size != 0 && str[stack[size-1]] == 'a'
hasB := size != 0 && str[stack[size-1]] == 'b'
hasA = hasA || str[i] == 'a'
hasB = hasB || str[i] == 'b'
if hasA && hasB {
size--
} else {
stack[size] = i
size++
}
}
builder := make([]byte, 0)
for i := 0; i < size; i++ {
builder = append(builder, str[stack[i]])
}
return string(builder)
}
func disappear4(s string) string {
n := len(s)
acount := 0
bcount := 0
for i := 0; i < n; i++ {
if s[i] == 'a' {
acount++
} else {
bcount++
}
}
if acount >= bcount {
return strings.Repeat("a", acount-bcount)
} else {
return strings.Repeat("b", bcount-acount)
}
}
func getRandString() string {
n := 5 + rand.Intn(40)
ret := make([]byte, n)
for i := 0; i < n; i++ {
aa := rand.Intn(2)
if aa == 0 {
ret[i] = 'a'
} else {
ret[i] = 'b'
}
}
return string(ret)
}
执行结果如下:
***
[左神java代码](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_01_1_week/Code01_ABDisappear.java)