乐趣区

关于字符串:golangleetcode中级二叉树的序列化与反序列化常数时间插入删除和获取随机元素

jiezi

第一题 二叉树的序列化与反序列化

题目

解题思路

本题有两个子问题

第一个为
将二叉树序列化为一个字符串，即为二叉树的遍历
对于树的遍历，有深搜和广搜两种
深搜又按根节点的地位分为先序遍历，中序遍历，后序遍历三种状况
这里咱们规定 应用先序遍历将其转化为字符串序列

这里咱们应用包 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 main

import (
    "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 个元素的信息。

退出移动版