第一题 二叉树的序列化与反序列化
题目
解题思路
本题有两个子问题
第一个为
将二叉树序列化为一个字符串，即为二叉树的遍历
对于树的遍历，有深搜和广搜两种
深搜又按根节点的地位分为先序遍历，中序遍历，后序遍历三种状况
这里咱们规定 应用先序遍历将其转化为字符串序列
这里咱们应用包strconv实现对根本数据类型的字符串示意的转换
Atoi(string to int)和 Itoa(int to string)
func (Codec) serialize(root *TreeNode) string { sb := &strings.Builder{} var dfs func(*TreeNode) dfs = func(node *TreeNode) { if node == nil { sb.WriteString("null,") return } sb.WriteString(strconv.Itoa(node.Val)) sb.WriteByte(',') dfs(node.Left) dfs(node.Right) } dfs(root) return sb.String()}第二个为
将序列化的字符串从新转化为树
依据先序遍历的规定
字符的第一个元素为根节点
这里应用函数strings.Split函数按指定的分隔符切割字符串，并返回切割后的字符串切片。
不便咱们对字符串进行操作
func (Codec) deserialize(data string) *TreeNode { sp := strings.Split(data, ",") var build func() *TreeNode build = func() *TreeNode { if sp[0] == "null" { sp = sp[1:] return nil } val, _ := strconv.Atoi(sp[0]) sp = sp[1:] return &TreeNode{val, build(), build()} } return build()}具体代码为
package mainimport ( "strconv" "strings")type TreeNode struct { Val int Left *TreeNode Right *TreeNode}type Codec struct{}func Constructor() (_ Codec) { return}func (Codec) serialize(root *TreeNode) string { sb := &strings.Builder{} var dfs func(*TreeNode) dfs = func(node *TreeNode) { if node == nil { sb.WriteString("null,") return } sb.WriteString(strconv.Itoa(node.Val)) sb.WriteByte(',') dfs(node.Left) dfs(node.Right) } dfs(root) return sb.String()}func (Codec) deserialize(data string) *TreeNode { sp := strings.Split(data, ",") var build func() *TreeNode build = func() *TreeNode { if sp[0] == "null" { sp = sp[1:] return nil } val, _ := strconv.Atoi(sp[0]) sp = sp[1:] return &TreeNode{val, build(), build()} } return build()}复杂度剖析
工夫复杂度：O(n)；咱们只拜访每个节点一次，因而工夫复杂度为 O(n)，其中 n 是节点数，即树的大小。
空间复杂度：O(n)；在序列化和反序列化函数中，咱们递归会应用栈空间，故渐进空间复杂度为 O(n)。
第二题 常数工夫插入、删除和获取随机元素
题目
思路
代码
type RandomizedSet struct { m map[int]int nums []int}func Constructor() RandomizedSet { return RandomizedSet{ m: make(map[int]int), nums: []int{}, }}func (this *RandomizedSet) Insert(val int) bool { // val存在，无需插入 if _, ok := this.m[val]; ok { return false } // 若 val 不存在，插入到 nums 尾部， // 并记录 val 对应的索引值 this.nums = append(this.nums, val) this.m[val] = len(this.nums) - 1 return true}func (this *RandomizedSet) Remove(val int) bool { // 若 val 不存在，不必再删除 if _, ok := this.m[val]; !ok { return false } //存在，开始删除操作 // 拿到待删除 val 的索引 index := this.m[val] // 最初一个元素的索引 lastIndex := len(this.nums) - 1 //实现元素替换 // 将最初一个元素对应的索引批改为 index this.m[this.nums[lastIndex]] = index // 替换 val 和最初一个元素 （将 val 索引地位设为最初一个值也可） this.nums[index], this.nums[lastIndex] = this.nums[lastIndex], this.nums[index] // 将数组中最初一个值 val 删除 this.nums = this.nums[0 : len(this.nums)-1] // 删除元素 val 对应的索引 delete(this.m, val) return true}func (this *RandomizedSet) GetRandom() int { return this.nums[rand.Intn(len(this.nums))]}复杂度剖析
工夫复杂度：O(1)，
空间复杂度：O(N)，在动静数组和哈希表别离存储了 N 个元素的信息。