Golang每日一练(leetDay0102) 数据流中位数、删除无效括号、累加数

package main
import "fmt"
type MedianFinder struct {
    nums []int
}
/** initialize your data structure here. */
func Constructor() MedianFinder {
    return MedianFinder{}
}
func (this *MedianFinder) AddNum(num int) {
    idx := binarySearch(this.nums, num)
    this.nums = append(this.nums[:idx], append([]int{num}, this.nums[idx:]...)...)
}
func (this *MedianFinder) FindMedian() float64 {
    n := len(this.nums)
    if n%2 == 0 {
        return float64(this.nums[n/2-1]+this.nums[n/2]) / 2
    } else {
        return float64(this.nums[n/2])
    }
}
/* Helper function for binary search */
func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}
func main() {
    obj := Constructor()
    obj.AddNum(1)
    obj.AddNum(2)
    median1 := obj.FindMedian()
    obj.AddNum(3)
    median2 := obj.FindMedian()
    fmt.Println(median1)
    fmt.Println(median2)
}

package main
import "fmt"
func removeInvalidParentheses(s string) []string {
  var ans []string
  var visited = make(map[string]struct{})
  queue := []string{s}
  visited[s] = struct{}{}
  found := false
  for len(queue) > 0 {
    size := len(queue)
    for i := 0; i < size; i++ {
      cur := queue[0]
      queue = queue[1:]
      if isValid(cur) {
        ans = append(ans, cur)
        found = true
      }
      if found {
        continue
      }
      for j := 0; j < len(cur); j++ {
        if cur[j] != '(' && cur[j] != ')' {
          continue
        }
        str := cur[0:j] + cur[j+1:]
        if _, ok := visited[str]; !ok {
          queue = append(queue, str)
          visited[str] = struct{}{}
        }
      }
    }
  }
  return ans
}
func isValid(s string) bool {
  cnt := 0
  for i := 0; i < len(s); i++ {
    if s[i] == '(' {
      cnt++
    } else if s[i] == ')' {
      cnt--
      if cnt < 0 {
        return false
      }
    }
  }
  return cnt == 0
}
func main() {
  s1 := "()())()"
  fmt.Println(removeInvalidParentheses(s1))
  s2 := "(a)())()"
  fmt.Println(removeInvalidParentheses(s2))
  s3 := ")("
  fmt.Println(removeInvalidParentheses(s3))
}

package main
import "fmt"
func removeInvalidParentheses(s string) []string {
  left, right := count(s)
  res := make([]string, 0)
  dfs(s, 0, 0, 0, left, right, "", &res)
  return res
}
func dfs(s string, start int, left int, right int, leftRemoved int, rightRemoved int, solution string, solutions *[]string) {
  if start == len(s) {
    if (left-right)*leftRemoved*rightRemoved == 0 && len(solution) > 1 && !in(solution, *solutions) {
      (*solutions) = append((*solutions), solution)
    }
    return
  }
  if s[start] == '(' {
    if leftRemoved > 0 {
      dfs(s, start+1, left, right, leftRemoved-1, rightRemoved, solution, solutions)
    }
    dfs(s, start+1, left+1, right, leftRemoved, rightRemoved, solution+string(s[start]), solutions)
  } else if s[start] == ')' {
    if rightRemoved > 0 {
      dfs(s, start+1, left, right, leftRemoved, rightRemoved-1, solution, solutions)
    }
    if left > right {
      dfs(s, start+1, left, right+1, leftRemoved, rightRemoved, solution+string(s[start]), solutions)
    }
  } else {
    dfs(s, start+1, left, right, leftRemoved, rightRemoved, solution+string(s[start]), solutions)
  }
}
func in(target string, str_array []string) bool {
  for _, ok := range str_array {
    if ok == target {
      return true
    }
  }
  return false
}
func count(s string) (int, int) {
  left, right := 0, 0
  for _, c := range s {
    if c == '(' {
      left++
    }
    if c == ')' {
      if left == 0 {
        right++
      } else {
        left--
      }
    }
  }
  return left, right
}
func main() {
  s := "()())()"
  fmt.Println(removeInvalidParentheses(s))
  s = "(a)())()"
  fmt.Println(removeInvalidParentheses(s))
  s = ")("
  fmt.Println(removeInvalidParentheses(s))
}

package main
import (
  "fmt"
  "strconv"
  "strings"
)
func isAdditiveNumber(num string) bool {
  if len(num) < 3 {
    return false
  }
  n := len(num)
  for i := 1; i <= n/2; i++ {
    for j := 1; j <= (n-i)/2; j++ {
      if num[0] == '0' && i > 1 {
        break
      }
      if num[i] == '0' && j > 1 {
        break
      }
      a, _ := strconv.Atoi(num[:i])
      b, _ := strconv.Atoi(num[i : i+j])
      if isAdditive(num, a, b, i+j) {
        return true
      }
    }
  }
  return false
}
func isAdditive(num string, a int, b int, start int) bool {
  if start == len(num) {
    return true
  }
  sum := a + b
  sumStr := strconv.Itoa(sum)
  if !strings.HasPrefix(num[start:], sumStr) {
    return false
  }
  return isAdditive(num, b, sum, start+len(sumStr))
}
func main() {
  s1 := "112358"
  fmt.Println(isAdditiveNumber(s1))
  s2 := "199100199"
  fmt.Println(isAdditiveNumber(s2))
}