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代码
