为期一周，本周难度会比较大，所以不再设置附加题
周一：回溯
面试题 04.09. 二叉搜索树序列
周三：字典树
211. 添加与搜索单词 - 数据结构设计
周五：线段树
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);
*/