chapter2

Documentation

Index

• type BFSLevelTraversal
  • func NewBFSLevelTraversal() *BFSLevelTraversal
  • func (bfs *BFSLevelTraversal) LevelOrder(root *module.TreeNode) [][]int
• type BSTreeFLCA
  • func (bst *BSTreeFLCA) LowestCommonAncestor(root, p, q *module.TreeNode) *module.TreeNode
• type BTreeFLCA
  • func (bt *BTreeFLCA) LowestCommonAncestor(root, p, q *module.TreeNode) *module.TreeNode
• type BinarySqrt
  • func (bs *BinarySqrt) MySqrt(x float64, accuracy int) float64
• type BitQueens
  • func (bq *BitQueens) TotalNQueens(n int) int
• type BracketGenerator
• type CountDepth
• type DCCountDepth
  • func (dc *DCCountDepth) MaxDepth(root *module.TreeNode) int
  • func (dc *DCCountDepth) MinDepth(root *module.TreeNode) int
• type DFSQueens
  • func NewDFSQueens() *DFSQueens
  • func (dq *DFSQueens) SolveNQueens(n int) [][]string
• type DPProduct
  • func (dpp *DPProduct) MaxProduct(nums []int) int
• type DefinitionVerifyBST
  • func (dv *DefinitionVerifyBST) IsValidBST(root *module.TreeNode) bool
• type DivideConquerPow
  • func (dc *DivideConquerPow) MyPow(x float64, n int) float64
• type DpLIS
  • func (dl *DpLIS) LengthOfLIS(nums []int) (res int)
• type FindLowestCommonAncestor
• type InOrderVerifyBST
  • func (iov *InOrderVerifyBST) IsValidBST(root *module.TreeNode) bool
• type IteratePow
  • func (ip *IteratePow) MyPow(x float64, n int) float64
• type LIS
• type LevelTraversal
• type Pow
• type Product
• type Queens
• type QueensII
• type RecursionBG
  • func (rbg *RecursionBG) GenerateParenthesis(n int) []string
• type RecursionProduct
  • func (rp *RecursionProduct) MaxProduct(nums []int) int
• type Sqrter
• type VerifyBST

Types

type BFSLevelTraversal

type BFSLevelTraversal struct {
	// contains filtered or unexported fields
}

1. BFS O(n)

func NewBFSLevelTraversal

func NewBFSLevelTraversal() *BFSLevelTraversal

func (*BFSLevelTraversal) LevelOrder

func (bfs *BFSLevelTraversal) LevelOrder(root *module.TreeNode) [][]int

type BSTreeFLCA

type BSTreeFLCA struct {
}

235 二叉搜索树 根据大小判断

func (*BSTreeFLCA) LowestCommonAncestor

func (bst *BSTreeFLCA) LowestCommonAncestor(root, p, q *module.TreeNode) *module.TreeNode

type BTreeFLCA

type BTreeFLCA struct {
}

236 普通二叉树

func (*BTreeFLCA) LowestCommonAncestor

func (bt *BTreeFLCA) LowestCommonAncestor(root, p, q *module.TreeNode) *module.TreeNode

type BinarySqrt

type BinarySqrt struct {
}

1. 二分法

func (*BinarySqrt) MySqrt

func (bs *BinarySqrt) MySqrt(x float64, accuracy int) float64

规律: 误差判断 -> m - x/m

type BitQueens

type BitQueens struct {
	// contains filtered or unexported fields
}

1. 位运算 (最快) 用位运算实现

func (*BitQueens) TotalNQueens

func (bq *BitQueens) TotalNQueens(n int) int

type BracketGenerator

type BracketGenerator interface {
	GenerateParenthesis(n int) []string
}

22 括号生成

type CountDepth

type CountDepth interface {
	MinDepth(root *module.TreeNode) int
	MaxDepth(root *module.TreeNode) int
}

104/111 二叉树的最大/最小深度

type DCCountDepth

type DCCountDepth struct {
}

111

func (*DCCountDepth) MaxDepth

func (dc *DCCountDepth) MaxDepth(root *module.TreeNode) int

func (*DCCountDepth) MinDepth

func (dc *DCCountDepth) MinDepth(root *module.TreeNode) int

type DFSQueens

type DFSQueens struct {
	// contains filtered or unexported fields
}

func NewDFSQueens

func NewDFSQueens() *DFSQueens

func (*DFSQueens) SolveNQueens

func (dq *DFSQueens) SolveNQueens(n int) [][]string

type DPProduct

type DPProduct struct {
}

func (*DPProduct) MaxProduct

func (dpp *DPProduct) MaxProduct(nums []int) int

type DefinitionVerifyBST

type DefinitionVerifyBST struct {
}

2. 递归 利用定义: 左子树(max) <= 当前节点 < 右子树(min) O(n)

func (*DefinitionVerifyBST) IsValidBST

func (dv *DefinitionVerifyBST) IsValidBST(root *module.TreeNode) bool

type DivideConquerPow

type DivideConquerPow struct {
}

3. 分治 原理类似: 计算 2^8 = 2*2*2*2*2*2*2*2

2*2   = 4    2 * 2              2次
4*4   = 16   2*2 * 2*2          4次
16*16 = 256  2*2*2*2 * 2*2*2*2  8次
总共需要3次计算

func (*DivideConquerPow) MyPow

func (dc *DivideConquerPow) MyPow(x float64, n int) float64

type DpLIS

type DpLIS struct {
}

2. DP O(n^2) 定义 DP[i]: 选择第 i 个元素时的最长上升子序列 Max(DP[0], ..., DP[i-1]) = DP[j] DP[i] = DP[j] + 1

func (*DpLIS) LengthOfLIS

func (dl *DpLIS) LengthOfLIS(nums []int) (res int)

type FindLowestCommonAncestor

type FindLowestCommonAncestor interface {
	// 感觉题目给 p, q 的指针不太合理, 应该使用 int
	LowestCommonAncestor(root, p, q *module.TreeNode) *module.TreeNode
}

235/236(二叉搜索树/二叉树) 的最近公共祖先 说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

type InOrderVerifyBST

type InOrderVerifyBST struct {
	// contains filtered or unexported fields
}

1. 递归 中序遍历的结果是升序的. 这里只保存前驱节点的值, 而不必保存中序遍历的完整结果. O(n)

func (*InOrderVerifyBST) IsValidBST

func (iov *InOrderVerifyBST) IsValidBST(root *module.TreeNode) bool

type IteratePow

type IteratePow struct {
}

迭代

func (*IteratePow) MyPow

func (ip *IteratePow) MyPow(x float64, n int) float64

type LIS

type LIS interface {
	LengthOfLIS(nums []int) int
}

300 最长上升子序列

type LevelTraversal

type LevelTraversal interface {
	LevelOrder(root *module.TreeNode) [][]int
}

102 层遍历二叉树

type Pow

type Pow interface {
	MyPow(x float64, n int) float64
}

50 实现 pow(x, y)

type Product

type Product interface {
	MaxProduct(nums []int) int
}

152 乘积最大子序列

type Queens

type Queens interface {
	SolveNQueens(n int) [][]string
}

51

type QueensII

type QueensII interface {
	TotalNQueens(n int) int
}

52 N皇后

type RecursionBG

type RecursionBG struct {
	// contains filtered or unexported fields
}

3. 改进方法2

• 生成时按照一定规则

规律是一个一个往后添加 "(/)"

func (*RecursionBG) GenerateParenthesis

func (rbg *RecursionBG) GenerateParenthesis(n int) []string

type RecursionProduct

type RecursionProduct struct {
	// contains filtered or unexported fields
}

1. 暴力 Recursion 每个数字进行抉择: 乘, 不乘

func (*RecursionProduct) MaxProduct

func (rp *RecursionProduct) MaxProduct(nums []int) int

type Sqrter

type Sqrter interface {
	MySqrt(x, accuracy int) float64
}

69 Sqrt(x)

type VerifyBST

type VerifyBST interface {
	IsValidBST(root *module.TreeNode) bool
}

98 验证二叉搜索树