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

295. 数据流的中位数 Find-median-from-data-stream

中位数是有序整数列表中的中间值。如果列表的大小是奇数，中位数是列表最中间的那个数；如果列表的大小是偶数，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [1,2,3,4] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类：

• MedianFinder() 初始化 MedianFinder 对象。
• void addNum(int num) - 从数据流中添加一个整数到数据结构中。
• double findMedian() - 返回目前所有元素的中位数。

示例：

**输入:**
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
**输出:**
[null, null, null, 1.5, null, 2.0]
**解释:**
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

进阶:

1. 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
2. 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

代码：

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

输出：

1.5
2

301. 删除无效的括号 Remove Invalid Parentheses

给你一个由若干括号和字母组成的字符串

s

，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

示例 1：

**输入：**s = "()())()"
**输出：**["(())()","()()()"]

示例 2：

**输入：**s = "(a)())()"
**输出：**["(a())()","(a)()()"]

示例 3：

**输入：**s = ")("
**输出：**[""]

提示：

• 1 <= s.length <= 25
• s 由小写英文字母以及括号 '(' 和 ')' 组成
• s 中至多含 20 个括号

代码1：BFS

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

代码2：DFS

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

输出：

[(())() ()()()]
[(a())() (a)()()]
[]

306. 累加数 Additive Number

累加数 是一个字符串，组成它的数字可以形成累加序列。

一个有效的 累加序列 必须** 至少 **包含 3 个数。除了最开始的两个数以外，序列中的每个后续数字必须是它之前两个数字之和。

给你一个只包含数字

'0'-'9'

的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回

true

；否则，返回

false

。

说明：累加序列里的数，除数字 0 之外，不会 以 0 开头，所以不会出现

1, 2, 03

或者

1, 02, 3

的情况。

示例 1：

**输入：**"112358"
**输出：**true 
**解释：**累加序列为: 1, 1, 2, 3, 5, 8 。
1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

示例 2：

**输入**："199100199"
**输出：**true 
**解释：**累加序列为: 1, 99, 100, 199。
1 + 99 = 100, 99 + 100 = 199

提示：

• 1 <= num.length <= 35
• num 仅由数字（0 - 9）组成

进阶：你计划如何处理由过大的整数输入导致的溢出?

代码：

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

输出：

true
true

🌟 每日一练刷题专栏 🌟

✨持续，努力奋斗做强刷题搬运工！

👍 点赞，你的认可是我坚持的动力！

🌟 收藏，你的青睐是我努力的方向！

✎ 评论，你的意见是我进步的财富！

☸ 主页：https://hannyang.blog.csdn.net/

Rust每日一练 专栏

（2023.5.16~）更新中...

Golang每日一练 专栏

（2023.3.11~）更新中...

Python每日一练 专栏

（2023.2.18~2023.5.18）暂停更

C/C++每日一练 专栏

（2023.2.18~2023.5.18）暂停更

Java每日一练 专栏

（2023.3.11~2023.5.18）暂停更