2938. 区分黑球与白球

区分黑球与白球

• 难度: medium
• 原始链接: https://leetcode.cn/problems/separate-black-and-white-balls
• 标签: 双指针

解法一: 双指针

go

func minimumSteps(s string) int64 {
  n := len(s)
  bytes := []byte(s)
  left := n - 1
  right := n - 1
  ans := int64(0)
  for {
    for right >= 0 && bytes[right] == '1' {
      right--
    }
    left = min(left, right-1)
    for left >= 0 && bytes[left] == '0' {
      left--
    }
    if left < 0 {
      break
    }
    bytes[left], bytes[right] = bytes[right], bytes[left]
    ans += int64(right - left)
  }
  return ans
}

解法二: 逆向思维

go

func minimumSteps(s string) int64 {
  ans := int64(0)
  sum := 0
  for _, ch := range s {
    if ch == '1' {
      sum++
    } else {
      ans += int64(sum)
    }
  }
  return ans
}