Jonathan's Studio

算法基础(二)数据结构

字数统计: 2.2k阅读时长: 10 min
2020/06/10 3

算法基础(二)数据结构

链表

链表是由数据项组成的一个序列,其中每个数据项被称为节点
链表有两种主要类型:

  • 单链表 每一个节点只包含一个指向链表中下一个节点的指针(引用)。
  • 双链表 每个节点包含两个指针(引用),一个指向前一个节点,一个指向后一个节点。

通常我们用headtail指针来记录链表的头和尾。

代码实现

单链表

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
class ListNode {
var value: Int
var next: ListNode?

init(_ value: Int) {
self.value = value
self.next = nil
}
}

class List {
var head: ListNode?
var tail: ListNode?

//尾插法
func appendToTail(_ value: Int) {
if tail == nil {
tail = ListNode(value)
head = tail
} else {
tail?.next = ListNode(value)
tail = tail?.next
}
}

//头插法
func appendToHead(_ value: Int) {
if head == nil {
head = ListNode(value)
tail = head
} else {
let temp = ListNode(value)
temp.next = head
head = temp
}
}
}

双链表

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
class DoubleNode {
var value : Int
var previous :DoubleNode?
var next:DoubleNode?
init(_ value :Int) {
self.value = value
self.previous = nil
self.next = nil
}
}

class DoubleNodeList{
var head:DoubleNode?
var tail:DoubleNode?

func appendToTail(_ val:Int){
if tail == nil {
tail = DoubleNode(val)
head = tail
}else{
let temp = DoubleNode(val)
tail?.next = temp
temp.previous = tail
tail = temp
}
}

func appendToHead(_ val:Int){
if head == nil {
head = DoubleNode(val)
tail = head
}else{
let temp = DoubleNode(val)
temp.next = head
head?.previous = temp
head = temp
}
}
}

题目练习

给出一个链表和一个值想,要求链表中小于x的值放在左边,大于等于x的放在右边,不改变原有链表
ex:1→5→3→2→4→2 x=3 结果 1→2→2→5→3→4

思路是:一个链表遍历时,小于x的放在一个链表,大于等于x的放在另一个链表,最后拼接。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func partition(head: ListNode?,_ x: Int) -> ListNode? {

let prevDummy = ListNode(0)
let postDummy = ListNode(0)
var prev = prevDummy
var post = postDummy
var node = head

while node != nil {
if node!.value < x {
prev.next = node
prev = node!
} else {
post.next = node
post = node!
}
node = node!.next
}

post.next = nil
prev.next = postDummy.next

return prevDummy.next
}

我们通常传入的参数是ListNode来代表单链表,处理室也能体现出优势,但是需要作出防止生成环的操作。

检测环的方法

这里使用一种方法叫快行指针,就是两个指针访问链表,一前一后。
这里其中的一个的速度是另外一个的两倍,当速度相等时,就说明链表有环了。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isCycle(head: ListNode?) -> Bool {
var slow = head
var fast = head

while fast != nil && fast?.next != nil {
slow = slow?.next!
fast = fast?.next!.next

if slow == fast {
return true
}
}
return false
}

这里需要注意==的运算符,这需要ListNode遵循Equatable协议,那么我们让两个节点比较是否一样呢(不能是比较value),这里通过比较两个节点的内存地址是否相同,我更希望将比较做在ListNode中,让类实现协议并且在==函数中比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class ListNode: Equatable {

static func == (lhs: ListNode, rhs: ListNode) -> Bool {

if Unmanaged.passUnretained(lhs as AnyObject).toOpaque() == Unmanaged.passUnretained(rhs as AnyObject).toOpaque() {
return true
} else {
return false
}
}

var value: Int
var next: ListNode?

init(_ value: Int) {
self.value = value
self.next = nil
}
}

例题分析(使用快行指针)

删除链表中倒数第n个节点。1→2→3 →4 →5 n=2 1→2→3 →5

思路:使用快行指针,但是这里速度不变,一个指在第一个节点,另一个指在第n个节点,这个指针指到最后时,前面一个指针则是要删除的节点。

代码如下:

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
func removeNode(head: ListNode?,backwards: Int) -> ListNode? {

guard backwards > 0 else {
return head
}

let dummy = ListNode(0)
dummy.next = head
var node1:ListNode? = dummy
var node2:ListNode? = dummy
//node2位移
for _ in 0..<backwards {
if node2 == nil {
break
}
node2 = node2?.next
}
while node2?.next != nil && node2 != nil {
node2 = node2?.next
node1 = node1?.next
}

node1?.next = node1?.next?.next
return dummy.next
}

这里使用到Dummy节点的概念,他的作用是作为一个虚拟的头前节点。可以避免处理头节点为空的边界问题。
前一个比较大小的题目我们也是用Dummy节点来优化代码。

栈和队列

在Swift中,没有内设的栈和队列,很多扩展库中使用Generic Type来实现栈和队列。正确的做法是用链表实现,这样可以保证加入或删除的时间复杂度是O(1)。这里推荐使用数组,因为Swift中有提供很多的数组的API可以直接使用。

这里对于栈和队列的概念不再介绍了,因为理解上没有什么突出的。我可以举几个在开发中的例子,APP中的添加撤销操作,栈是首选的数据结构

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
protocol Stack {
associatedtype Element
//关联类型作为协议实现泛型的一种方式

var isEmpty: Bool {get}
var size: Int {get}
var peek: Element? {get}
//栈顶元素

mutating func push(_ newElement: Element)
mutating func pop() -> Element?

}

struct IntegerStack: Stack {
typealias Element = Int
//可以用来对已有的类型进行重命名,这里便用于指明Element的类型

var isEmpty: Bool

var size: Int

var peek: Int?

private var stack = [Element]()

mutating func push(_ newElement: Int) {
stack.append(newElement)
}

mutating func pop() -> Int? {
return stack.popLast()
}

}

这里使用Protocol来制定出通用的栈结构,然后对于IntegerStack实现该协议,他在一定程度上优于继承机制,更具抽象化。

队列

队列是先进先出的结构,在iOS中,GCD和NSOperationQueue就是基于队列实现的。

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
protocol Queue {
associatedtype Element

var isEmpty: Bool {get}
var size: Int {get}
var peek: Element? {get}

mutating func enqueque(_ newElement: Element)
mutating func dequeque() -> Element?
}

struct IntegerQueue: Queue {
typealias Element = Int

var isEmpty: Bool {
return left.isEmpty && right.isEmpty
}

var size: Int {
return left.count + right.count
}

var peek: Element? {
return left.isEmpty ? right.first: left.last
}
private var left = [Element]()

private var right = [Element]()


mutating func enqueque(_ newElement: Int) {
right.append(newElement)
}

mutating func dequeque() -> Int? {
if left.isEmpty {
left = right.reversed()
right.removeAll()
}
return left.popLast()
}

}

例题分析

给出一个文件的绝对路径,要求进行简化,比如”/home/”,简化为”/home”,
“/a/./b/../c/”,简化为”/c”,也就是平常执行cd、pwd命令所得到的路径.

“.”代表当前路径,
“..”代表上一级目录。
这看上去没什么难度的,但是重视边界问题与异常情况。
这里的思路是根据”/”符号进行拆分,生成数组,用栈遍历数组,对于.忽略,对于..进行pop操作。
代码如下:

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
struct StringStack: Stack {
var isEmpty: Bool = true

var size: Int = 0 {
didSet {
if size == 0 {
isEmpty = true
peek = nil
} else {
isEmpty = false
peek = stack.last
}
}
}
var peek: String? = nil

private(set) var stack = [Element]()

mutating func push(_ newElement: String) {
stack.append(newElement)
size = size+1
}

mutating func pop() -> String? {
return stack.popLast()
size = size-1
}

typealias Element = String
}


func simplifyPath(_ path: String) -> String {
var pathStack = StringStack()
let paths = path.components(separatedBy: "/")

for path in paths {
guard path != "." else {
continue
}
if path == ".." {
if pathStack.size > 0 {
pathStack.pop()
}
} else if path != "" {
pathStack.push(path)
}
}
let result = pathStack.stack.reduce("") { (total, dir) in
"\(total)/\(dir)"
}
return result.isEmpty ? "/" : result
}

二叉树

二叉树中,每个节点最多有两个子节点,一般称为左子节点和右子节点,并且二叉树有左右之分,次序不能颠倒
数据结构的代码如下:

1
2
3
4
5
6
7
8
class TreeNode {
var value: Int
var left: TreeNode?
var right: TreeNode?
init(_ value: Int) {
self.value = value
}
}

计算树的最大深度

在二叉树中,节点的层次从根开始定义,根为第一层,节点的最大层次为树的深度。

1
2
3
4
5
6
func maxDepth(root: TreeNode?) -> Int {
guard let root = root else {
return 0
}
return max(maxDepth(root: root.left), maxDepth(root: root.right))+1
}

使用递归算法在代码上最简洁,但是需要避免二叉树成环导致循环程序奔溃。

判断是否为二叉查找树

二叉查找树的特点在于左子树节点的值都小于根节点的值,右子树节点的值都大于根节点的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func isValidBST(root:TreeNode?) -> Bool {
return checkBST(node: root, min: nil, max: nil)
}

private func checkBST(node: TreeNode?, min: Int?, max: Int?) -> Bool {
guard let node = node else {
return true
}

if let min = min,node.value <= min {
return false
}
if let max = max,node.value >= max {
return false
}

return checkBST(node: node.left, min: min, max: node.value) && checkBST(node: node.right, min: node.value, max: max)
}

二叉树本身是由递归定义的,所以,从原理上讲,所有二叉树的题目都可以用递归来解。
二叉树的题目很容易牵涉节点往左还是往右的问题,所以在内部函数时,要想要有两个对应的参数.

二叉树的遍历

最常见的树的遍历有三种,前序、中序和后序遍历,这里用非递归的方法写前序遍历,用栈来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func preorderTRaversal(root: TreeNode?) -> [Int] {
var result = [Int]()
var stack = [TreeNode]()
var node = root

while !stack.isEmpty || node != nil {
if node != nil {
result.append(node!.value)
stack.append(node!)
node = node!.left
} else {
node = stack.removeLast().right
}
}

return result
}
CATALOG
  1. 1. 算法基础(二)数据结构