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. 判断链表是否有环
  2. 链表有环的情况下找到环的入口节点
  3. 判断两个链表是否相交
  4. 相交的情况下找到相交时候的第一个节点

对应的7种情况

6aSs8P

解决代码

执行测试命令:go test -v intersection_test.go intersection.go -test.run TestIntersection

解决代码
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package InterviewCoding

/**
* @Author: yirufeng
* @Date: 2021/11/25 8:21 上午
* @Email: yirufeng@foxmail.com
* @GitHub: https://www.github.com/sivanWu0222
* @Desc:
**/

type LinkedListNode struct {
Val int
Next *LinkedListNode
}

/*
题目:返回两个链表相交的节点
步骤:
1. 明确题目中的意思,两个链表有无环,是否一定相交(如果不一定的话,我们需要判断是否相交,只有在相交的情况下我们才可以返回相交的第一个节点)
2. 分情况进行讨论:
2.1 有环
2.1.1 一定相交:
直接找到相交的节点即可
2.1.2 不一定相交:
首先判断是否相交
相交的时候,找到相交的第一个节点并返回
2.2 无环
2.2.1 一定相交:
2.2.2 不一定相交:
首先判断是否相交
相交的时候,找到相交的第一个节点并返回
2.3 1个有环1个无环,说明一定不会相交,直接返回Nil就可以了
*/

//返回两个链表的相交节点,如果不相交返回Nil,否则返回相交的第一个节点
func Intersection(l1, l2 *LinkedListNode) *LinkedListNode {
//如果有一个为空,直接说明不相交
if l1 == nil || l2 == nil {
return nil
}

//判断两个链表是否有环,如果有环就返回环的起始节点
startOfl1Ring, startOfl2Ring := startNodeOfRing(l1), startNodeOfRing(l2)
//如果1个有1个没有,说明白不相交,直接返回nil
if ((startOfl1Ring == nil) && (startOfl2Ring != nil)) || ((startOfl1Ring != nil) && (startOfl2Ring == nil)) {
return nil
}

var ret *LinkedListNode
if startOfl1Ring != nil { //如果有环
ret = findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring)
} else { //如果没有环:此时就转换为我们正常的题解了
ret = findIntersectionNodeWhenBothNoCycle(l1, l2)
}

return ret
}

//当两个链表都没有环的时候,找到两个链表的相交节点(可能相交,可能不相交)
//三种解法去找出第一个相交的节点
func findIntersectionNodeWhenBothNoCycle(l1, l2 *LinkedListNode) *LinkedListNode {
//1. 获得第1个链表第2个链表的长度以及各自链表的最后一个节点
l1Length, l2Length := 1, 1
l1LastNode, l2LastNode := l1, l2
for l1LastNode.Next != nil {
l1Length, l1LastNode = l1Length+1, l1LastNode.Next
}
for l2LastNode.Next != nil {
l2Length, l2LastNode = l2Length+1, l2LastNode.Next
}

//判断各自最后一个节点是否相等,如果不相等,说明不相交,直接返回nil
if l1LastNode != l2LastNode {
return nil
}

//先走长度差
l1LastNode, l2LastNode = l1, l2
if l1Length > l2Length {
for i := 0; i < l1Length-l2Length; i++ {
l1LastNode = l1LastNode.Next
}
} else {
for i := 0; i < l2Length-l1Length; i++ {
l2LastNode = l2LastNode.Next
}
}

//然后一起走,如果中途相等直接返回
for l1LastNode != l2LastNode {
l1LastNode, l2LastNode = l1LastNode.Next, l2LastNode.Next
}

return l1LastNode
}

//当两个链表都有环的时候,找到两个链表的相交节点(可能相交,可能不相交(各自有一个自己的环))
func findIntersectionNodeWhenBothHaveCycle(l1, l2, startOfl1Ring, startOfl2Ring *LinkedListNode) *LinkedListNode {
//判断两个链表是否有环的时候我们可以找到链表有环时候环的第一个节点
//如果两个环的起始节点都相同,此时问题转变为l1的起始节点到自己拥有环的开始节点和l2的起始节点到自己拥有环的开始节点的第一个相交节点
if startOfl1Ring == startOfl2Ring {
l1Temp, l2Temp := l1, l2
//转变为求两个无环单链表的相交节点
var l1TempLength, l2TempLength int

for l1Temp != startOfl1Ring {
l1Temp, l1TempLength = l1Temp.Next, l1TempLength+1
}

for l2Temp != startOfl2Ring {
l2Temp, l2TempLength = l2Temp.Next, l2TempLength+1
}

//长的先走
if l1TempLength > l2TempLength {
for i := 0; i < l1TempLength-l2TempLength; i++ {
l1Temp = l1Temp.Next
}
} else {
for i := 0; i < l2TempLength-l1TempLength; i++ {
l2Temp = l2Temp.Next
}
}

//此时一起走
for l1Temp != l2Temp {
l1Temp, l2Temp = l1Temp.Next, l2Temp.Next
}
return l1Temp

} else { //如果两个环的起始节点不同,让其中一个环开始走,走到起始节点为止,如果中途会出现和另外一个环起始节点相同,说明相交,否则各自成环
l1Temp := startOfl1Ring.Next
for l1Temp != startOfl1Ring {
if l1Temp == startOfl2Ring {
return startOfl2Ring
}
l1Temp = l1Temp.Next
}
}

return nil
}

//返回链表是否有环,如果有的话直接返回true,否则返回false
func startNodeOfRing(head *LinkedListNode) *LinkedListNode {
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast, slow = fast.Next.Next, slow.Next
//说明此时相遇,表明有环
if fast == slow {
break
}
}

//这里是第二个注意点,这里不仅仅要判断fast是否为空,还要判断fast.Next是否为空,
//因为让链表停止上面for循环的有两个条件:1. fast为空 2. fast.Next为空
//判断一下是因为fast为空或者fast.Next为空还是fast==slow退出的
if fast == nil || fast.Next == nil {
return nil
}

//走到这里说明有环,此时让fast指向head,然后fast与slow每次都走一步,一起相遇的时候返回即可
fast = head
for fast != slow {
fast, slow = fast.Next, slow.Next
}
return fast
}
测试代码
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
package InterviewCoding

import (
"testing"
)

/**
* @Author: yirufeng
* @Date: 2021/11/25 11:05 上午
* @Email: yirufeng@foxmail.com
* @GitHub: https://www.github.com/sivanWu0222
* @Desc:
**/

//测试两个链表
func TestIntersection(t *testing.T) {
//模拟场景
//1.1 两个不带环且不相交的链表
l1, l2 := constructTwoLinkedListWithoutCycleAndNotIntersection()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}

//1.2 两个不带环但是相交的链表:LeetCode原题
//已修复,由于&&写成了||
l1, l2 = constructTwoLinkedListWithoutCycleButIntersection()
if Intersection(l1, l2) == nil {
t.Log(Intersection(l1, l2))
t.Fatalf("expect to have intersection node.")
}

//2. 1个链表有环,1个无环
l1, l2 = constructTwoLinkedListButOneHasCycle()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}
//3. 两个链表都有环
//3.1 两个链表都有环,但是两个链表的环都是各自的
l1, l2 = constructTwoLinkedBothHasOwnCycle()
if Intersection(l1, l2) != nil {
t.Fatalf("expect no intersection node.")
}

//3.2.1 两个链表都有环,并且两个链表是相交的,且交点在进入环之前
//todo: 有问题
l1, l2 = constructTwoLinkedListBothHasCycleAndIntersection()
if Intersection(l1, l2) == nil {
t.Fatalf("expect to have intersection node.")
}
//3.2.2 两个链表都有环,并且两个链表是相交的,且交点在环上
l1, l2 = constructTwoLinkedListBothHasCycleAndIntersectionII()
if Intersection(l1, l2) == nil {
t.Fatalf("expect to have intersection node.")
}
}

//两个不带环但是相交的链表
func constructTwoLinkedListWithoutCycleButIntersection() (l1, l2 *LinkedListNode) {
node := &LinkedListNode{Val: 5}
l1, l2 = &LinkedListNode{Val: 3}, &LinkedListNode{Val: 4, Next: &LinkedListNode{Val: 6, Next: node}}
l1.Next, l2.Next = node, node
return l1, l2
}

//两个不带环且不相交的链表
func constructTwoLinkedListWithoutCycleAndNotIntersection() (l1, l2 *LinkedListNode) {
l1, l2 = &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 4}}, &LinkedListNode{Val: 5, Next: &LinkedListNode{Val: 6}}
return l1, l2
}

//构造两个链表1个有环1个无环
func constructTwoLinkedListButOneHasCycle() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
node.Next, node2.Next = node2, node
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表的环都是各自的
func constructTwoLinkedBothHasOwnCycle() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 2}, &LinkedListNode{Val: 3}
node.Next, node2.Next = node2, node
node3, node4 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node3.Next, node4.Next = node4, node3
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: node3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表都是相交的且相交的起点位于环的入口之前
func constructTwoLinkedListBothHasCycleAndIntersection() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node.Next, node2.Next = node2, node
node3 := &LinkedListNode{Val: 6, Next: node}
l1, l2 = &LinkedListNode{Val: 1, Next: node3}, &LinkedListNode{Val: 3, Next: node3}
return l1, l2
}

//构造两个都有环的链表,但是两个链表都是相交的且相交的起点位于环上
func constructTwoLinkedListBothHasCycleAndIntersectionII() (l1, l2 *LinkedListNode) {
node, node2 := &LinkedListNode{Val: 4}, &LinkedListNode{Val: 5}
node.Next, node2.Next = node2, node
l1, l2 = &LinkedListNode{Val: 1, Next: node}, &LinkedListNode{Val: 3, Next: &LinkedListNode{Val: 6, Next: node2}}
return l1, l2
}

前言

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

第一道题

ZWdEW0

前言

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

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

问题1

问题描述:递归的过程中,传递了一个切片作为参数,每次我们都需要对切片切取首元素,之后递归回来的时候发现切片中的元素还是没有切取首元素,是一个很严重的逻辑错误

问题解决:我们递归函数使用切片作为参数的时候,我们直接传入切片的地址。因为切片每次删除元素,地址也会改变。当切片增加元素引起扩容,地址也会发生改变,而如果只传入切片我们只是引用最开始的时候的切片的地址,因此会发现切片没有任何改变。

例如我们自己写的二叉树序列化和反序列化代码:在最开始只是传递一个切片,但是后来传递切片的地址进去发现代码逻辑正常运行。

代码
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
49
//方法一:使用先序遍历进行序列化和反序列化
//进行序列化
func PreorderSerialize(root *TreeNode) string {
if root == nil {
return "#!"
}

var ret string

ret += strconv.Itoa(root.Val) + "!"
ret += PreorderSerialize(root.Left)
ret += PreorderSerialize(root.Right)
return ret
}

//进行反序列化
func PreorderDeserialize(ret string) *TreeNode {
strs := strings.Split(ret, "!")

//注意点:由于切片在执行过程中有可能会因为增加和删除元素而造成切片不是原来那个切片,但是我们递归回去的时候还是指向原来的切片,因此会有问题
//所以这里我们传递的是切片的地址
//因为切片扩容可能会生成一个新的底层数组,并且由于切片移除了元素,因此对应的头部地址一定会改变,所以会造成地址的改变
root := ReconstructTreeFromPreorder(&strs)
return root
}

//根据我们分割后的字符串建立二叉树
func ReconstructTreeFromPreorder(strs *[]string) *TreeNode {
if (*strs)[0] == "#" {
(*strs) = (*strs)[1:]
return nil
}

//首先将该值对应的字符串转换为int
val, _ := strconv.Atoi((*strs)[0])
//建立一个针对于该值的节点
node := &TreeNode{
Val: val,
}

//去掉我们建立过的节点的值
(*strs) = (*strs)[1:]
//之后进行递归建立左右子树
node.Left = ReconstructTreeFromPreorder(strs)
node.Right = ReconstructTreeFromPreorder(strs)

return node
}

了解布隆过滤器

什么是布隆过滤器?

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

布隆过滤器的作用

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

题目描述

使用一个固定长度大小的数组实现栈

思路

思路:使用一个index进行指向当前可以插入元素的位置
  1. 使用一个index指向下次栈中加入元素的位置
  2. 如果要弹出元素,需要判断index是否大于1,如果大于弹出index-1位置的元素,index减去1,否则不可以弹出。
  3. 如果要加入元素,直接加入到index指向的位置,之后index++

题目描述

使用一个固定长度大小的数组实现队列

思路

思路:使用start指向队头,end指向队尾的下一个位置
  1. 我们加了一个标志位empty区分start等于end的两种情况,一种是队列中没有元素,另外一种是队列元素满。
  2. 如果要弹出元素,需要判断end是否等于start,如果empty为真且start等于end,说明不可以弹出,否则可以弹出元素。
  3. 如果要加入元素,直接加入到end指向的位置,之后end需要判断是否处于最后一个位置,如果是则跳转到数组第1个位置,否则end++。同时判断是否满元素来更新empty

题目描述

给定一个数组,求如果排序之后,相邻两数的最大差值,要求时 间复杂度O(N),且要求不能用非基于比较的排序

注意不基于比较哦

思路

思路:桶排序
  1. 假设数组长度为n,准备n+1个桶
  2. 遍历该数组,将最小值放入到第1个位置,将最大值放入到最后一个位置
  3. 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中,
  4. 最后这n+1个桶中至少有一个空桶,说明桶内的数值差不是最大差值,我们去桶间找最大差值
  5. 对于每个桶,我们都保存了每个桶的最小值和最大值,从第2个桶开始,每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差,过程中我们动态更新最大差值