Golang每日一练(leetDay0102) 删除无效的括号、累加数

这篇具有很好参考价值的文章主要介绍了Golang每日一练(leetDay0102) 删除无效的括号、累加数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Golang每日一练(leetDay0102) 删除无效的括号、累加数

目录

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

进阶:

  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/ 

Golang每日一练(leetDay0102) 删除无效的括号、累加数

Rust每日一练 专栏

(2023.5.16~)更新中...

Golang每日一练(leetDay0102) 删除无效的括号、累加数

Golang每日一练 专栏

(2023.3.11~)更新中...

Golang每日一练(leetDay0102) 删除无效的括号、累加数

Python每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Golang每日一练(leetDay0102) 删除无效的括号、累加数

C/C++每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Golang每日一练(leetDay0102) 删除无效的括号、累加数

Java每日一练 专栏

(2023.3.11~2023.5.18)暂停更文章来源地址https://www.toymoban.com/news/detail-497527.html

到了这里,关于Golang每日一练(leetDay0102) 删除无效的括号、累加数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Golang每日一练(leetDay0052)

    目录 153. 寻找旋转排序数组中的最小值 Find Minimum In Rotated Sorted Array  🌟🌟 154. 寻找旋转排序数组中的最小值 II Find Minimum In Rotated Sorted Array II  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 已知一个长度为

    2024年02月02日
    浏览(37)
  • Golang每日一练(leetDay0116) 路径交叉、回文对

    目录 335. 路径交叉 Self-crossing  🌟🌟🌟 336. 回文对 Palindrome Pairs  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个整数数组  distance   。 从  X-Y  平面上的点  (0,0)  开始,先向北

    2024年02月12日
    浏览(38)
  • Golang每日一练(leetDay0049) 二叉树专题(9)

    目录 144. 二叉树的前序遍历 Binary-tree Preorder Traversal  🌟 145. 二叉树的前序遍历 Binary-tree Postorder Traversal  🌟 对比: 94. 二叉树的中序遍历 Binary-tree Inorder Traversal  🌟 146. LRU缓存 LRU Cache  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一

    2024年02月04日
    浏览(41)
  • Golang每日一练(leetDay0098) 生命、Nim、猜数字游戏

    目录 289. 生命游戏 Game Of Life  🌟🌟 292. Nim 游戏 Nim Game  🌟 299. 猜数字游戏 Bulls and Cows  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 生命游戏   是英国数学家约翰·何顿·康威在 1970 年发

    2024年02月09日
    浏览(38)
  • Golang每日一练(leetDay0065) 位1的个数、词频统计

    目录 191. 位1的个数 Nnumber of 1-bits  🌟 192. 统计词频 Word Frequency  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为

    2024年02月06日
    浏览(64)
  • Golang每日一练(leetDay0061) 表列序号、阶乘后的零

    目录 171. Excel 表列序号 Excel Sheet Column Number  🌟 172. 阶乘后的零 Factorial Trailing Zeroes  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个字符串  columnTitle  ,表示 Excel 表格中的列名称。返回  该列名称对

    2024年02月04日
    浏览(73)
  • Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列

    目录 332. 重新安排行程 Reconstruct Itinerary  🌟🌟🌟 334. 递增的三元子序列 Increasing Triplet Subsequence 🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一份航线列表  tickets  ,其中  tickets[i]

    2024年02月16日
    浏览(42)
  • Golang每日一练(leetDay0095) 第一个错误的版本、完全平方数

    目录 278. 第一个错误的版本 First Bad Version  🌟 279. 完全平方数 Perfect Squares  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你

    2024年02月09日
    浏览(49)
  • Golang每日一练(leetDay0118) 扁平化嵌套列表迭代器、整数拆分

    目录 341. 扁平化嵌套列表迭代器 Flatten Nested List Iterator  🌟🌟 343. 整数拆分 Integer Break  🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给你一个嵌套的整数列表  nestedList  。每个元素要么是

    2024年02月16日
    浏览(45)
  • Golang每日一练(leetDay0075) 打家劫舍II、最短回文串

    目录 213. 打家劫舍 II House Robber ii  🌟🌟 214. 最短回文串 Shortest Palindrome  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的

    2024年02月06日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包