Sorry, your browser cannot access this site
This page requires browser support (enable) JavaScript
Learn more >

方法一:二分

  • 时间复杂度:O(logN)
  • 空间复杂度:O(1)

注意点:

  1. mid*mix > x的时候容易溢出,改成mid > x/mid
  2. mid := (l+r)>>1的时候也容易溢出,改成mid := l + (r-l)>>1
不保留小数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//不保留小数
func Sqrt(x int) int {

if x <= 0 {
return 0
}

l, r := 1, x-1
for l <= r {
mid := l + (r-l)>>1
if mid > x/mid {
r = mid - 1
} else if mid < x/mid { //Tips:写成x/mid用来确认不会溢出
l = mid + 1
} else {
return mid
}
}

return r
}

求两棵树的第一个交点

首先判断两棵树是否相交,可以根据判断两个链表是否相交扩展而来,如果相交的话,将第1个链表的末尾指向第1个链表的头部将会成环,因此借鉴这种思路

自己的思路如下:KlYSSU

验证两棵树是否相交

思路:Morris先序遍历,遍历第1棵树的时候将叶节点的左指针指向root1,然后遍历root2,如果发现某一个节点左指针指向第1个树根,说明相交,包含了两个树中有一个是子树的情况

时间复杂度:O(N)
空间复杂度:O(1)

Morris遍历:

优点:不同于我们之前递归遍历或者借助栈来进行树的遍历,因为Morris遍历可以在保证时间复杂度依然为O(N)的情况下可以将空间复杂度降低为O(1)

假设当前节点为cur,最一开始来到树根,什么时候停呢,当cur来到nil的时候就停止

  1. 如果当前节点没有左子树,直接向右移动
  2. 如果当前节点有左子树,找到当前节点左子树的最右节点mostRight
    1. 如果mostRight的右指针指向null,那么mostRight.Right=Cur,cur=cur.Left
    2. 如果mostRight的右指针指向cur,那么mostRight.Right=nil,cur=cur.Right

遍历之后发现一个问题:任何一个节点,只要有左孩子Morris遍历的时候会遍历两次,也就是有左树的节点,左树不为空,首先遍历当前节点,然后遍历左树,遍历之后再回到当前节点,所以当前节点会遍历两次。因为用这个就可以知道是第一次来到自己还是第二次来到自己。

Morris先序遍历:

第一次遍历到该节点的时候直接打印(没有左子树的节点会遍历到一次,有左子树的节点会遍历到两次,但是我们第一次就应该打印)

Morris先序遍历代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func MorrisPreOrderTraverse(root *TreeNode) []int {
if root == nil {
return nil
}

var mostRight *TreeNode
cur := root
var ret []int
for cur != nil {
//如果当前节点没有左子树
if cur.Left == nil { //当前节点向右移动 (只有没有左子树的节点会走这一步)
ret = append(ret, cur.Val)
cur = cur.Right
} else { //找到当前节点左子树的最右节点
mostRight = cur.Left

for mostRight.Right != nil && mostRight.Right != cur {
mostRight = mostRight.Right
}
//此时mostRight就是当前节点左子树的最右节点
if mostRight.Right == nil { //说明是第一次来到
ret = append(ret, cur.Val)
mostRight.Right, cur = cur, cur.Left
} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
mostRight.Right, cur = nil, cur.Right
}
}
}

return ret
}

二叉树树形结构,但是树中每个节点的分支最多只有两个,我们叫做二叉树 二叉搜索树(BST)!> 二叉搜索树又叫二叉排序树,或二叉查找树。它或者是一颗空树或者是具有下列性质的二叉树: 若它的左子树不为空,则左子树上的所有节点的值均小于它的根节点的值 若它的右子树不为空,则右子树上的所有节点的值均大于它的根节点的值 它的左右子树也分别是二叉排序树 平衡二叉树(AVL)!> 平衡二叉...

前言

在旋转数据中搜索值包括两个系列的题型:搜索旋转点(也就是最小值)以及搜索我们给定的目标值。关于旋转排序数组的定义这里就不再赘述

套路总结

套路总结

sCRjwC

注意:方法一二代码较为简单,这里就不再赘述了

方法三

上图中的方法三,我们以LeetCode 240为例

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/** ✅
* @Author: yirufeng
* @Date: 2020/12/7 11:41 上午
* @Desc:
* 方法一:暴力
* 方法二:从右上角或者左下角每次排除一行或者一列
* 方法三:每一行二分搜索
* 方法四:采用二分
思路:获取当前搜索矩阵的中心点,然后排出左上角或者右下角的矩阵
如下是方法四代码
**/
func searchTarget(matrix [][]int, x1, y1, x2, y2, target int) bool {
//递归可能越界
if x1 > x2 || y1 > y2 {
return false
}

//之前这个if语句块没有写会死循环,
//注意点:避免x1,y1,x2,y2相等时调用searchTarget(matrix, x1, y1, xMid, yMid, target)死循环
if x1 == x2 && y1 == y2 {
if matrix[x1][y1] == target {
return true
}
return false
}

//得到中心点坐标
xMid, yMid := x1+(x2-x1)>>1, y1+(y2-y1)>>1
if matrix[xMid][yMid] > target { //排除右下角
return searchTarget(matrix, x1, y1, xMid, yMid, target) ||
searchTarget(matrix, x1, yMid+1, xMid-1, y2, target) ||
searchTarget(matrix, xMid+1, y1, x2, yMid-1, target)
} else if matrix[xMid][yMid] < target { //排除左上角
return searchTarget(matrix, x1, yMid+1, xMid, y2, target) ||
searchTarget(matrix, xMid+1, y1, x2, yMid, target) ||
searchTarget(matrix, xMid+1, yMid+1, x2, y2, target)
}
return true

}

func searchMatrix(matrix [][]int, target int) bool {
if len(matrix) == 0 || len(matrix[0]) == 0 {
return false
}
return searchTarget(matrix, 0, 0, len(matrix)-1, len(matrix[0])-1, target)
}

前言

序列化:二叉树被记录成文件的过程叫做序列化

反序列化:通过文件内容重建原来二叉树的过程叫做反序列化

基于递归的遍历

步骤

  1. 以某个节点X为头结点的子树中,分析答案有哪些可能性,并且这种分析是以X的左子树,X的右子树,和X整棵树的角度来考虑可能性的
  2. 根据第一步分析的可能性,列出所需要的信息,例如在二叉树是否平衡中,左子树和右子树都需要知道各自是否平衡,以及高度这两个信息。
  3. 根据第二步信息汇总,定义自己的信息结构体
  4. 设计递归函数,递归函数是处理以X为头结点的情况相爱的答案,包括设计递归函数的base case,默认直接得到左树和右树所有的信息,以及把可能性左整合,并且返回第三步的信息结构这4个小步骤。

了解布隆过滤器

什么是布隆过滤器?

一个布隆过滤器精确地代表了一个集合。并不像哈希表那样存储原始信息,而是存储原始信息的压缩信息以节省空间,但牺牲了一定的准确度。

布隆过滤器的作用

可以精确地判断一个元素是否在这个集合中。注意只是精确代表和精确判断,到底有多精确,取决于我们自己的设计。想做到完全正确是不可能的,布隆过滤器的优势在于使用很少的空间就可以将准确率做到很高的程度。