2022-04-07：给定一个只由'a'和'b'组成的字符串str，str中"ab"和"ba"子串都可以消除

福大大架构师每日一题

发布于 2022-04-13 09:33:16

4260

发布于 2022-04-13 09:33:16

文章被收录于专栏：福大大架构师每日一题

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)
}

执行结果如下：