TalkGo 算法之美第三期系列三

为期一周,本周难度会比较大,所以不再设置附加题

周一:回溯

面试题 04.09. 二叉搜索树序列

周三:字典树

211. 添加与搜索单词 - 数据结构设计

周五:线段树

307. 区域和检索 - 数组可修改
func BSTSequences(root *TreeNode) (ans [][]int) {
	if root == nil {
		ans = append(ans, []int(nil))
		return
	}

	comb := make([]int, 0)

	// nodes数组存放下一个能插入的节点
	nodes := make([]*TreeNode, 0)
	nodes = append(nodes, root)

	var traceBack func()
	traceBack = func() {
		if len(nodes) <= 0 {
			ans = append(ans, append([]int(nil), comb...))
			return
		}
		for i := 0; i < len(nodes); i++ {
			// 拷贝nodes用于回退还原
			copyNodes := make([]*TreeNode, len(nodes))
			copy(copyNodes, nodes)

			// 删除nodes中的node节点
			node := nodes[i]
			nodes = append(nodes[:i], nodes[i+1:]...)

			comb = append(comb, node.Val)
			if node.Left != nil {
				nodes = append(nodes, node.Left)
			}
			if node.Right != nil {
				nodes = append(nodes, node.Right)
			}
			traceBack()
			// 回退
			comb = comb[:len(comb)-1]
			// 还原nodes
			nodes = copyNodes
		}
	}
	traceBack()
	return
}

队列中放置可选择的结点,每次从队列中随机选择一个,并把孩子加入到队列中。

var vis map[int]bool
var ans [][]int
var queue []*TreeNode
var cnt int

func nodeCnt(t *TreeNode) int {
	if t==nil {return 0}

	return 1+nodeCnt(t.Left)+nodeCnt(t.Right)
}

func dfs(queueEnd int, selectArr []int) {
	if len(selectArr) == cnt{
		ans = append(ans, selectArr)
		return
	}

	// 所有在队列中的都是没有前置依赖,可以选择。
	for i:=0;i<queueEnd ;i++  {
		node := queue[i]
		if vis[node.Val] {continue}// 已经被选择过了
		vis[node.Val] = true // 标记已选
		addNodeCnt := 0
		if node.Left!=nil {
			queue[queueEnd+addNodeCnt] = node.Left
			addNodeCnt++
		}
		if node.Right !=nil {
			queue[queueEnd+addNodeCnt] = node.Right
			addNodeCnt++
		}

		dfs(queueEnd+addNodeCnt, append(append([]int{}, selectArr...), node.Val))

		vis[node.Val] = false
	}
}

func Init(n int) {
	vis = map[int]bool{}
	ans = [][]int{}
	queue = make([]*TreeNode, n+10)
}


func BSTSequences(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{[]int{}}
	}
	cnt = nodeCnt(root)
	Init(cnt)
	queue[0] = root
	dfs(1, []int{})
	return ans
}

211


type Trie struct {
	isEnd bool
	child map[byte]*Trie
}

type WordDictionary struct {
	root *Trie
}

/** Initialize your data structure here. */
func Constructor() WordDictionary {

	trie := &Trie{child: make(map[byte]*Trie, 0)}

	return WordDictionary{root: trie}
}

/** Adds a word into the data structure. */
func (this *WordDictionary) AddWord(word string) {

	wLen := len(word)
	cur := this.root
	for i := 0; i < wLen; i++ {

		next, ok := cur.child[word[i]]
		if ok {
			cur = next
		} else {
			next = &Trie{child: make(map[byte]*Trie, 0)}
			cur.child[word[i]] = next
		}

		cur = next
	}

	cur.isEnd = true

}

/** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
func (this *WordDictionary) Search(word string) bool {

	return this.root.Search(word)
}

func (this *Trie) Search(word string) bool {

	wLen := len(word)
	cur := this
	for i := 0; i < wLen; i++ {

		next, ok := cur.child[word[i]]
		if ok {
			cur = next
			continue
		}

		if 'a' <= word[i] && word[i] <= 'z' {
			return false
		}

		//如果是 .
		for _, c := range cur.child {

			if c.Search(word[i+1:]) {
				return true
			}

		}

		return false

	}

	return cur.isEnd

}

1赞

307
简单版本线段树,单点更新,范围查询

type node struct {
	l, r                  int // 代表树结点代表的区间范围
	leftChild, rightChild *node
	sum                   int // 区间总和
}

type SegmentTree struct {
	nodes []node // 事先申请结点,加事内存分配
	root  int    //根结点编号
}

// 初始化线段树,分配内存大小, 构造树型
func (tree *SegmentTree) Init(l, r int) {
	tree.nodes = make([]node, (r-l+1)*4)
	tree.root = 1 //
	tree.buildNode(l, r, tree.root)
}

// 构造树型
func (tree *SegmentTree) buildNode(l, r, root int) *node {
	if l > r {
		return nil
	}

	mid := (l + r) >> 1
	tree.nodes[root].l, tree.nodes[root].r = l, r
	tree.nodes[root].sum, tree.nodes[root].sum = 0, 0
	if l == r {
		return &tree.nodes[root]
	}
	// 构造左右子树
	tree.nodes[root].leftChild = tree.buildNode(l, mid, root<<1)
	tree.nodes[root].rightChild = tree.buildNode(mid+1, r, root<<1|1)
	return &tree.nodes[root]
}

func (tree *SegmentTree) UpdatePoint(x, val int) {
	tree.update(x, x, val, tree.root)
}

func (tree *SegmentTree) update(l, r, val, root int) {
	if l > tree.nodes[root].r || r < tree.nodes[root].l {
		return
	}

	if l <= tree.nodes[root].l && tree.nodes[root].r <= r {
		tree.nodes[root].sum = val
		return
	}

	tree.update(l, r, val, root<<1)
	tree.update(l, r, val, root<<1|1)

	// 更新完孩子,更新自己
	tree.nodes[root].sum = tree.nodes[root<<1].sum + tree.nodes[root<<1|1].sum
}

func (tree *SegmentTree) QueryRange(l, r int) int {
	return tree.query(l, r, tree.root)
}

func (tree *SegmentTree) query(l, r, root int) int {
	if l > tree.nodes[root].r || r < tree.nodes[root].l {
		return 0
	}

	if l <= tree.nodes[root].l && tree.nodes[root].r <= r {
		return tree.nodes[root].sum
	}

	return tree.query(l, r, root<<1) + tree.query(l, r, root<<1|1)
}

type NumArray struct {
	tree *SegmentTree
}

func Constructor(nums []int) NumArray {
	na := NumArray{}
	na.tree = &SegmentTree{}
	na.tree.Init(0, len(nums))
	for i, v := range nums {
		na.Update(i, v)
	}

	return na
}

func (this *NumArray) Update(index int, val int) {
	this.tree.UpdatePoint(index, val)
}

func (this *NumArray) SumRange(left int, right int) int {
	return this.tree.QueryRange(left, right)
}

/**
 * Your NumArray object will be instantiated and called as such:
 * obj := Constructor(nums);
 * obj.Update(index,val);
 * param_2 := obj.SumRange(left,right);
 */