目录
295. 数据流的中位数 Find-median-from-data-stream 🌟🌟🌟
301. 删除无效的括号 Remove Invalid Parentheses 🌟🌟🌟
306. 累加数 Additive Number 🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
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
进阶:
- 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
- 如果数据流中 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）暂停更文章来源地址https://www.toymoban.com/news/detail-531877.html |
文章来源：https://www.toymoban.com/news/detail-531877.html到了这里，关于Golang每日一练(leetDay0102) 数据流中位数、删除无效括号、累加数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
