- 数据结构和算法结局的是“如何让计算机更快时间，更省空间的解决问题”。因此需要 从执行时间和占用空间两个概念来描述性能问题，二者统称为“复杂度”。
- 分别用时间和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
- 复杂度描述的是算法执行时间（或者用空间）与数据规模之间的增长关系。
- 和性能测试相比，复杂度分析具有：不依赖执行环境、成本低、效率高、易操作、指 导性强的特点
- 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。
算法执行时间与每行代码执行的次数成正比，用 T(n) = O(f(n)) 表示，其中T(n) 表示算法执行总时间，f(n)表示每行代码执行的总次数，n表示数据规模。
以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋 势，所以常量阶、低阶以及系数实际上对这种增长趋势不缠身决定性影响，所以在做 时间复杂度分析时忽略这些项。
- 单段代码看高频：循环
- 多段代码取最大：一段代码中有单循环和嵌套循环，取嵌套循环的复杂度
- 嵌套代码取乘积：比如递归、嵌套循环
- 过个规模使用加法或乘法
多项式阶：随着数据规模的增长，算法执行时间和占用空间按照多项式的比例增长
- O(1) 常数
- O(logn) 对数
- O(n) 线性
- O(nlogn) 线性对数
- O(n^2) 平方
- O(n^3) 立方
非多项式阶：随着数据规模的赠场，算法的执行时间和占用空间暴增，这类算法性能 极差
- O(2^n) 指数
- O(n!) 阶乘
多练，熟能生巧
- 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度
- 最好情况时间复杂度：代码在最好情况下执行的时间复杂度
- 平均时间复杂度：代码在所有情况下执行次数的加权平均值表示
- 均摊时间复杂度：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都 很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关 系，这个时间，我们就将这一组操作放到一起分析，看是否能将较高的时间复杂度那 次操作的耗时，平摊到其他时间复杂度操作较低的操作上。而且，在能够应用均摊时 间复杂度分析的场合，一般均摊时间复杂度就等于较好情况的时间复杂度。 均摊时 间复杂度是一种特殊的平均时间复杂度
- 同一段代码在不同情况下时间复杂度会出现量级差异，为了更全面，更准确的描述 代码的复杂度，引入这四个概念。
- 时间复杂度在不同情况下出现量级差异时才需要区别这四种代码复杂度。大多是情 况下是不需要区别分析他们的。
- 平均时间复杂度 代码在不同情况下复杂度出现量级差异，则用代码所有可能的情况下执行次数加权 平均值表示。
- 均摊时间复杂度 两个条件满足时使用： 1）绝大多是情况下是低级别复杂度，只有极少数情况是高 级别复杂度；2）低级别和高级别复杂度出现具有时序性，均摊结果一般等于低级别 复杂度。
数组是一种 线性表 数据结构。他用一组连续的内存空间，存储一组具有相同类型的数 据。
因为数组用 连续的存储空间和相同的类型 存储数据，所以数组支持随机访问，通过
下标访问数据的时间复杂度为 O(1) 。地址计算公式为
a[i]_address = base_address + i + data_type_size为了保证内存数据的连续性，导致“插入”和“删除”操作比较低效，平均时间复杂度为
O(n) 。
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var hash = [Int: Int]()
for (idx, num) in nums.enumerated() {
let complement = target - num
if let find = hash[complement], find != idx {
return [idx, find]
}
hash[num] = idx
}
return []
}
}
let result = Solution().twoSum([2,7,11,15], 9)
let ans = [1, 0]
print("result: \(result), ans: \(ans) ", result == ans ? "passed!" : "failed")class Solution {
func threeSum_bruteForce(_ nums: [Int]) -> [[Int]] {
var ans = [[Int]]()
let n = nums.count
for i in (0..<n - 2) {
for j in (i + 1)..<n - 1 {
for k in (j + 1)..<n {
if (nums[i] + nums[j] + nums[k] == 0) {
ans.append([nums[i], nums[j], nums[k]])
}
}
}
}
return ans
}
func threeSum(_ nums: [Int]) -> [[Int]] {
if nums.count < 3 { return [] }
var result = [[Int]]()
let nums = nums.sorted()
let count = nums.count
for i in 0..<count {
if nums[i] > 0 { return result }
if i > 0 && nums[i] == nums[i - 1] { continue }
var l = i + 1
var r = count - 1
while l < r {
if (nums[i] + nums[l] + nums[r] == 0) {
result.append([nums[i], nums[l], nums[r]])
while l < r && nums[l] == nums[l + 1] {
l += 1
}
while l < r && nums[r] == nums[r - 1] {
r -= 1
}
l += 1
r -= 1
} else if (nums[i] + nums[l] + nums[r] > 0) {
r -= 1
} else {
l += 1
}
}
}
return result
}
}
let result = Solution().threeSum([-1, 0, 1, 2, -1, 4])
let ans = [[-1, -1, 2], [-1, 0, 1]]
print("result: \(result), ans: \(ans)", result == ans ? "passed!" : "failued")class Solution {
func removeDuplicates(_ nums: inout [Int]) -> Int {
if nums.isEmpty { return 0 }
var i = 0
for j in 1..<nums.count {
if nums[i] != nums[j] {
i += 1
nums[i] = nums[j]
}
}
return i + 1
}
}
var elements = [0,0,1,1,1,2,2,3,3,4]
let result = Solution().removeDuplicates(&elements)
let ans = 5
print("result: \(result), ans: \(ans)", result == ans ? "passed!": "failed")- 链表也是一种 线性结构 。
- 链表的内存结构不是连续的，而是由分散的小块串起来的。
- 链表中的每一个内存块被称为 节点 ，节点除存储数据外，还记录链表的下一个节 点的位置，即 后继 指针。
- 插入、删除复杂度O(1)级别，效率高。
- 不支持随机访问，查找某个元素O(n)级别
- 和数组相比内存消耗大。
- 每个节点只有一个后继指针
- 有两个特殊的节点，头节点和尾节点。首节点位置表示整个链表，尾节点的后继指 针指向null
- 插入和删除节点的时间复杂度为O(1)，查找的时间复杂度为O(n)
- 特殊的单链表，区别在于尾节点的后继指针指向头节点
- 适用于存储有循环特点的数据，比如约瑟夫问题
- 与单链表相比，每个节点除了后继指针外，还有一个指向前一个节点的 前驱指针
- 头节点的前驱指针和尾指针都指向null
- 性能方面，1、需要消耗更多的存储空间；2、插入和删除指定的节点的时间复杂度 为O(1)
- 头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点。
| Array | List | |
|---|---|---|
| insert & delete | O(n) | O(n) |
| random access | O(1) | O(n) |
- 如果申请的空间很大，但是内存不足时会导致申请失败
- 大小固定，如果空间不足则需要扩容，扩容则需要进行数据复制
- 内存空间消耗大，需要额外的空间存放指针信息
- 对链表进行频繁的插入和删除会导致内存频繁的申请和释放，容易造成内存碎片
数组简单已用，在实现上使用连续的内存空间，可以借助CPU缓存机制预读取数组中的 数据，所以访问更高效；而链表在内存中并不是连续存储，所以对CPU缓存不友好，没 有办法预读。如果对内存的使用要求苛刻，就使用数组。
缓存是一种提交数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用， 比如常见的CPU缓存、数据库缓存、浏览器缓存。
缓存的大小是有限的，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保 留，就需要用到缓存淘汰策略。
指的是当缓存被占满时，清理缓存的优先顺序。
- FIFO (First In First Out) 先进先出
- LFU (Least Frenquently Used) 最少使用
- LRU (Least Recently Used) 最近最少使用
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指 针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
- 插入节点是要注意操作顺序
- 删除节点时要记得释放内存
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特 殊处理。引入哨兵节点，不管任何时候，头节点的指针一定会指向这个个哨兵节点。有 哨兵节点的链表叫做 带头链表 ，没有哨兵节点的链表叫做 不带头链表 。
- 如果链表为空，代码能否正常工作
- 如果链表只包含一个节点，代码能否正常工作
- 如果链表只包含两个节点，代码能否正常工作
- 代码逻辑在处理头尾节点的时候，是否能够正常工作
- 其他针对不通过场景的特定边界条件
典型题
- 单链表反转
- 链表中环的检测
- 两个有序链表合并
- 删除链表的倒数第n个节点
- 求链表中的中间节点
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}<<list-node>>
class Solution {
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var pre: ListNode? = nil
var cur = head
var next: ListNode?
while cur != nil {
next = cur?.next
cur?.next = pre
pre = cur
cur = next
}
return pre
}
}
print(Solution().reverseList(nil) as Any)// *对于递归算法，最重要的是明确递归的定义，然后利用明确的定义来实现算法逻辑*
<<list-node>>
class Solution {
/// 输入一个节点 head, 将「以head为起点」的链表反转，并返回反转之后的头节点
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil {
return head
}
let newHead = reverseList(head?.next)
head?.next?.next = head
head?.next = nil
return newHead
}
}<<list-node>>
class Solution {
func reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
if m == 1 {
return revertNTimes(head, n)
}
head?.next = reverseBetween(head?.next, m - 1, n - 1)
return head
}
var successor: ListNode? = nil
/// 反转链表的前N个节点
func revertNTimes(_ head: ListNode?, _ times: Int) -> ListNode? {
if times == 1 {
successor = head?.next
return head
}
let last = revertNTimes(head?.next, times - 1)
head?.next?.next = head
head?.next = successor
return last
}
}<<list-node>>
class Solution {
func reverseBetween(_ head: ListNode?, _ m: Int, _ n: Int) -> ListNode? {
let dummy = ListNode(-1)
var pre: ListNode? = dummy
for _ in 0..<m - 1 {
pre = pre?.next
}
let cur = pre?.next
for _ in m..<n {
let node = cur?.next
cur?.next = node?.next
node?.next = pre?.next
pre?.next = node
}
return dummy.next
}
}<<list-node>>
class Solution {
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy: ListNode? = ListNode(-1)
var cur = dummy
var l1 = l1
var l2 = l2
while l1 != nil && l2 != nil {
if l1!.val <= l2!.val {
cur?.next = l1
cur = cur?.next
l1 = l1?.next
} else {
cur?.next = l2
cur = cur?.next
l2 = l2?.next
}
}
if l1 == nil {
cur?.next = l2
} else {
cur?.next = l1
}
return dummy?.next
}
}
print(Solution().mergeTwoLists(nil, nil) as Any)
class Solution {
func deleteNode(_ head: ListNode?, _ val: Int) -> ListNode? {
if head?.val == val {
return head?.next
}
head?.next = deleteNode(head?.next, val)
return head
}
}------ ------- ------- ------- ------- -------
| dummy+—> | +—> | +—> | +—> | +—> | +—>NULL |
------ ------- ------- ------- ------- -------
^ ^
back front
------ ------- ------- ------- ------- -------
| dummy+—> | +—> | +—> | +—> | +—> | +—>NULL |
------ ------- ------- ------- ------- -------
^ ^ ^
back del front
<<list-node>>
class Solution {
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
if head?.next == nil && n != 0 { return nil }
let dummy = ListNode(-1)
dummy.next = head
var front: ListNode? = dummy
var back: ListNode? = dummy
for _ in 0..<n+1 {
front = front?.next
}
while front != nil {
front = front?.next
back = back?.next
}
let del = back?.next
back?.next = del?.next
del?.next = nil
return dummy.next
}
}class Solution {
func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
// 边界条件，head为空 k == 0 返回head
if head == nil || k == 0 { return head }
let dummy = ListNode(-1)
dummy.next = head
var length = head?.length() ?? 0
var k = k % length
// 求出的k==0也直接返回head
if k == 0 {
return head
}
// 使用双指针找到倒数第k个节点
var back: ListNode? = dummy
var front: ListNode? = dummy
for _ in 0..<k {
front = front?.next
}
while front?.next != nil {
front = front?.next
back = back?.next
}
var rotateHead = back?.next
back?.next = nil
front?.next = head
return rotateHead
}
}
extension ListNode {
/// 计算链表长度
func length() -> Int {
var length = 0
var cur: ListNode? = self
while let node = cur {
length += 1
cur = node.next
}
return length
}
}class Solution {
// RESULT: AC 68ms 5.98%
func deleteDuplicates_doublePointer(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil { return head }
var dummy: ListNode = ListNode(-1)
dummy.next = head
var pre: ListNode? = dummy
var cur = head
while cur != nil {
if cur?.val == cur?.next?.val {
pre?.next = cur?.next
cur = cur?.next
} else {
pre = cur
cur = cur?.next
}
}
return dummy.next
}
// Result: AC 36ms 79.49%
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var node = head
while node?.next != nil {
if node?.val == node?.next?.val {
node?.next = node?.next?.next
} else {
node = node?.next
}
}
return head
}
}力扣 关键条件：
- 排序链表
- 只保留没有重复出现的数字
思路：
- 找到重复出现的数字的头和尾
边界条件：
- 链表头包含重复数字
- 链表尾包含重复数字
- 整个链表都是重复数字
- 链表为空
class Solution {
func deleteDuplicates(_ head: ListNode?) -> ListNode? {
if head == nil { return nil }
var dummy: ListNode? = ListNode(-1)
dummy?.next = head
var pre = dummy
var cur = head
while cur != nil {
if cur?.val != cur?.next?.val {
pre = cur
cur = cur?.next
continue
}
while cur?.val == cur?.next?.val {
cur = cur?.next
}
pre?.next = cur?.next
cur = cur?.next
}
return dummy?.next
}
}力扣 思路
- 在链表中找到第一个大于等于x的节点p
- 在p节点后方找到小于x的节点q，删除q
- 将q插入到p之前
class Solution {
func partition(_ head: ListNode?, _ x: Int) -> ListNode? {
if head == nil || head?.next == nil { return head }
let dummy = ListNode(-1)
dummy.next = head
var p = head
var preInsert: ListNode? = dummy
while let node = p, node.val < x {
preInsert = p
p = p?.next
}
var cur = preInsert
while cur?.next != nil {
if cur!.next!.val < x {
// 被删除的节点
let deleted = cur?.next
// 删除小于x的节点
cur?.next = cur?.next?.next
// 将删除节点插入
deleted?.next = preInsert?.next
preInsert?.next = deleted
// 保证两个分区中每个节点的初始相对位置
preInsert = deleted
} else {
cur = cur?.next
}
}
return dummy.next
}
}备注： 第一次提交未AC，原因是忽略了“保持相对位置”的条件，原因是preInsert节点没有正 确维护，导致插入节点时与原顺序相反。
class Solution {
// 反转链表解法
// 先对两个链表进行反转，将该问题转化为“两数相加”问题，求得结果再反转，就是该题的解
func addTwoNumbers_reverse(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var l1 = reverseList(l1)
var l2 = reverseList(l2)
let dummy = ListNode(-1)
dummy.next = addTwoNumbersI_original(l1, l2) //or addTwoNumbers_optimazed
return reverseList(dummy.next)
}
// 两数相加问题的解
// 两数相加问题的难点在于处理进位，这个方法对进位的处理放在了每次循环中，如果需要进位，则将修改原链表
// 如果原链表下个节点为空，添加一个新的节点，如果存在后继，则将后继的值加上进位。
func addTwoNumbersI_original(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(-1)
var result: ListNode? = dummy
while l1 != nil || l2 != nil {
let sum = (l1?.val ?? 0) + (l2?.val ?? 0)
let val = sum % 10
let newNode = ListNode(val)
result?.next = newNode
// 1)
if sum >= 10 {
if l1?.next == nil {
l1?.next = ListNode(1)
} else {
// 进位的值改为 sum / 10 更准确
// l1?.next?.val += 1
l1?.next?.val += sum / 10
}
}
// 2)
l1 = l1?.next
l2 = l2?.next
result = result?.next
}
return dummy.next
}
// 两数相加问题的解
// 不同与上边一种解法中进位的处理，该实现将进位的处理放到了下一次循环中，在while循环条件判断中
// 添加了是否有进位的判断，如果有进位，就要执行循环。
// 这种实现方式代码更简洁。
func addTwoNumbersI_optimazed(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
let dummy = ListNode(-1)
var result: ListNode? = dummy
var l1 = l1, l2 = l2
var carry = 0
while l1 != nil || l2 != nil || carry > 0 {
var sum = (l1?.val ?? 0) + (l2?.val ?? 0) + carry
result?.next = ListNode(sum % 10)
carry = sum / 10
l1 = l1?.next
l2 = l2?.next
result = result?.next
}
return dummy.next
}
func reverseList(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil { return head }
var newHead = reverseList(head?.next)
head?.next?.next = head
head?.next = nil
return newHead
}
// 使用栈辅助计算
func addTwoNumbers_stack(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
var s1: [Int] = []
var s2: [Int] = []
var l1 = l1, l2 = l2
while let node = l1 {
s1.append(node.val)
l1 = l1?.next
}
while let node = l2 {
s2.append(node.val)
l2 = l2?.next
}
var carry = 0
let dummy = ListNode(-1)
var result: ListNode? = dummy
while !s1.isEmpty || !s2.isEmpty || carry > 0 {
let sum = (s1.popLast() ?? 0) + (s2.popLast() ?? 0) + carry
carry = sum / 10
let newNode = ListNode(sum % 10)
newNode.next = result?.next
result?.next = newNode
}
return dummy.next
}
var addTwoNumbers: (ListNode?, ListNode?) -> ListNode? {
return addTwoNumbers_stack
}
}class Solution {
func swapPairs_iterate(_ head: ListNode?) -> ListNode? {
if head == nil || head?.next == nil { return head }
var first = head
var second = head?.next
first?.next = swapPairs(second?.next)
second?.next = first
return second
}
func swapPairs(_ head: ListNode?) -> ListNode? {
let dummy = ListNode(-1)
dummy.next = head
var pre:ListNode? = dummy
while head != nil && head?.next != nil {
var first = head
var second = head?.next
pre?.next = second
first?.next = second?.next
second?.next = first
pre = first
head = first?.next
}
return dummy.next
}
}class Solution {
func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
var length = 0
var cur = head
while cur != nil {
cur = cur?.next
length += 1
}
if length < k {
return head
}
var tmpHead = head
cur = head
var pre: ListNode? = nil
var n = 0
var tmp: ListNode?
while n < k {
tmp = cur?.next
cur?.next = pre
pre = cur
cur = tmp
n += 1
}
tmpHead?.next = reverseKGroup(tmp, k)
return pre
}
}栈是一种“操作受限”的线性表，栈内的数据只能“后进先出”。
当某个数据集合只涉及在一端插入和删除数据，且满足“后进先出”的特性时，就可以用 栈数据结构，这样可以避免使用“数组”等自由度较高的数据结构可能导致的错误。
protocol Stack {
associatedtype Item
/// 栈是否为空
var isEmpty: Bool { get }
/// 栈内元素的个数
var count: Int { get }
/// 压栈
func push(_ item: Item)
/// 弹栈
func pop() -> Item?
/// 查看栈顶元素
func peek() -> Item?
}栈既可以使用数组实现，也可以使用链表实现，使用数组实现的栈叫做 顺序栈 ， 使 用链表实现的栈叫做 链式栈 。
public class ArrayStack<Item>: Stack {
private var store: [Item] = []
public var isEmpty: Bool {
return store.isEmpty
}
public var count: Int {
return store.count
}
public func push(_ item: Item) {
store.append(item)
}
public func pop() -> Item? {
return store.popLast()
}
public func peek() -> Item? {
return store.last
}
}private class ListNode<Value> {
var val: Value
var next: ListNode?
init(_ val: Value) {
self.val = val
self.next = nil
}
}
public class ListStack<Item>: Stack {
private var head: ListNode<Item>? = nil
public var isEmpty: Bool {
return head == nil
}
public private(set) var count: Int = 0
public func push(_ item: Item) {
let newNode = ListNode(item)
if head == nil {
head = newNode
} else {
newNode.next = head
head = newNode
}
count += 1
}
public func pop() -> Item? {
guard let head = head else {
return nil
}
self.head = head.next
head.next = nil
return head.val
}
public func peek() -> Item? {
return head?.val
}
}这里以“支持动态扩容的顺序栈”为例进行分析
- 出栈操作：O(1) 出栈不涉及内存申请和数据搬移，所以是O(1)的时间复杂度。
- 入栈操作：最好 O(1), 最坏 O(n), 均摊 O(1)
- 函数调用中的应用 – 调用栈
- 栈在表达式求值中的应用 使用两个栈，一个栈存操作数，一个栈存操作符
- 栈在括号匹配中的应用
class Solution {
func isValid(_ s: String) -> Bool {
var stack = [Character]()
for char in Array(s) {
switch char {
case "(": stack.append(")")
case "[": stack.append("]")
case "{": stack.append("}")
default:
if stack.isEmpty || char != stack.removeLast() {
return false
}
}
}
return stack.isEmpty
}
}<<valid-parentheses>>
func test(_ cases: [String], _ ans: [Bool]) {
for pair in zip(cases, ans) {
let result = Solution().isValid(pair.0) == pair.1 ? "passed" : "failed"
print("for case \"\(pair.0)\" " + result)
}
}
let cases = [" ", "()", "{]", "()[]{}", "([)]"]
let ans = [false, true, false, true, false]
test(cases, ans)class MinStack {
private var store = [Int]()
private var min = [Int]()
init() {}
func push(_ x: Int) {
store.append(x)
if min.isEmpty || x <= (min.last ?? 0) {
min.append(x)
}
}
func pop() {
if store.isEmpty { return }
let popped = store.popLast()
if popped == min.last {
_ = min.popLast()
}
}
func top() -> Int {
guard let top = store.last else { fatalError() }
return top
}
func getMin() -> Int {
guard let top = min.last else { fatalError() }
return top
}
}
var result = [String]()
let expected = ["true", "0", "-2"]
var minStack = MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
result.append("\(minStack.getMin() == -3)")
minStack.pop()
result.append("\(minStack.top())")
result.append("\(minStack.getMin())")
print("expected: \(expected), result: \(result)", (result == expected ? "passed" : "failued"))思路:
- 使用两个栈(front, back)实现队列，当有新的元素入列，将元素压入front栈中。
- 如果调用出列操作，先检查back栈是否为空；如果为空，则需要先把front中所有的 元素出栈，压入到back中，然后再调用back的出栈操作即可
需要注意下方实现moveItems的实现，因为是用数组模拟栈，所以应该从后往前遍历数 组元素，并加入到back中。遍历完成之后要将front数组清空。
class MyQueue {
var front: [Int] = []
var back: [Int] = []
/** Initialize your data structure here. */
init() {
}
/** Push element x to the back of queue. */
func push(_ x: Int) {
front.append(x)
}
/** Removes the element from in front of queue and returns that element. */
func pop() -> Int {
if back.isEmpty {
moveItems()
}
return back.removeLast()
}
/** Get the front element. */
func peek() -> Int {
if back.isEmpty {
moveItems()
}
return back.last!
}
/** Returns whether the queue is empty. */
func empty() -> Bool {
return front.isEmpty && back.isEmpty
}
private func moveItems() {
for value in front.reversed() {
back.append(value)
}
front.removeAll()
}
}思路：
- 将字符串按字符入栈
- 如果遇到退格（#），弹出一个字符
- 直至遍历完成，检查两个栈内元素是否相等
class Solution {
func backspaceCompare(_ S: String, _ T: String) -> Bool {
var sStack = stack(from: S)
var tStack = stack(from: T)
return sStack == tStack
}
private func stack(from string: String) -> [Character] {
var stack = [Character]()
for char in Array(string) {
if char == "#" {
stack.popLast()
} else {
stack.append(char)
}
}
return stack
}
}思路:
- 使用栈保存每一轮得分
- 遍历的时候累加得到最后的结果
class Solution {
func calPoints(_ ops: [String]) -> Int {
var roundPoint = [Int]()
var sum = 0
for char in Array(ops) {
let point: Int
if char == "C" {
point = roundPoint.popLast() ?? 0
} else if char == "D" {
point = (roundPoint.last ?? 0) * 2
roundPoint.append(point)
} else if char == "+" {
let pop1 = roundPoint.popLast() ?? 0
let pop2 = roundPoint.popLast() ?? 0
point = pop1 + pop2
roundPoint.append(pop2)
roundPoint.append(pop1)
roundPoint.append(point)
} else {
point = Int(char) ?? 0
roundPoint.append(point)
}
sum += point
}
return sum
}
}该题有两种解法，使用迭代和使用栈
最简单直接的思路是，在nums2中找到nums1中的元素，nums2中的该元素所在的位置开 始遍历数组，记录满足条件的元素。代码 1)。
代码1可以使用hash对查找效率进行优化，如代码2)。
是有单调栈，我们可以先遍历nums2，找到该数组中所有元素的下一个更大元素，并存 入字典，然后遍历num1，在字典中找到“下一个更大元素”，如代码3)s。
class Solution {
var nextGreaterElement: ([Int], [Int]) -> [Int] {
return nextGreaterElement_stack
}
// 1)
func nextGreaterElement_iterate_slow(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
// bounds
if nums1.isEmpty { return [] }
if nums2.isEmpty { return [Int](repeating: -1, count: nums1.count) }
// iterate
var result = [Int](repeating: -1, count: nums1.count)
for i in 0..<nums1.count {
guard let index = nums2.firstIndex(of: nums1[i]) else { continue }
for j in index ..< nums2.count {
if nums2[j] > nums1[i] {
result[i] = nums2[j]
break
}
}
}
return result
}
// 2)
func nextGreaterElement_iterate(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
if nums1.isEmpty { return [] }
var hash = [Int: Int]()
for (idx, num) in nums2.enumerated() {
hash[num] = idx
}
var result = [Int]()
outer: for num in nums1 {
guard let n = hash[num] else { continue }
for i in n..<nums2.count where nums2[i] > num {
result.append(nums2[i])
continue outer
}
result.append(-1)
}
return result
}
// 3)
func nextGreaterElement_stack(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
if nums1.isEmpty { return [] }
var hash: [Int: Int] = [:]
var stack: [Int] = []
for n in nums2 {
while let top = stack.last, n > top {
hash[stack.removeLast()] = n
}
stack.append(n)
}
while let top = stack.popLast() {
hash[top] = -1
}
return nums1.compactMap { n in hash[n] }
}
}遍历数组长度为n的数组，位置为i的元素的下一个更大元素应该在 i+1..<n 和 0..<i 的范围内。
如何模拟循环数组
- 迭代的解题思路所说，对于每个i，使用 i+1..<n 和 0 ..<i 构建一个新的数组， 但是这样每次迭代都要构建新数组，效率不高。
- 在遍历执行前就将数组扩展两倍，这样有些浪费存储空间。
- 对下标使用模运算，模拟循环数组。
var arr = [1,2,3,4,5] var n = array.count var i = 0 while true { print(arr[i % n]) i += 1 }
class Solution {
// 迭代解法 T
func nextGreaterElements_iterate(_ nums: [Int]) -> [Int] {
var ans = [Int](repeating: -1, count: nums.count)
for (idx, num) in nums.enumerated() {
let new = nums[idx+1..<nums.count] + nums[0..<idx]
for greater in new where greater > num {
ans[idx] = greater
break
}
}
return ans
}
func nextGreaterElements_stack(_ nums: [Int]) -> [Int] {
var ans = [Int](repeating: -1, count: nums.count)
var stack = [Int]()
var n = nums.count
for i in (0...2 * (n - 1)).reversed() {
let idx = i % n
let num = nums[idx]
while let top = stack.last, num >= top {
stack.removeLast()
}
ans[idx] = stack.isEmpty ? -1 : stack.top ?? -1
stack.append(num)
}
return ans
}
}思路： 要计算矩形面积必须知道宽和高，高度为第i个元素，要计算宽度我们需要找到第i个元 素对应的左右边界，left和right。 left为i左边第一个小于i的后一个，right为i右边 第一个小于i的前一个。
可以利用一个单调递增的栈来确定i的左右边界
class Solution {
func largestRectangleArea(_ heights: [Int]) -> Int {
if heights.isEmpty { return 0 }
let heights = [0] + heights + [0]
var stack = [Int]()
var result = 0
for (idx, height) in heights.enumerated() {
while let top = stack.last, heights[top] > height {
let popped = stack.removeLast()
result = max(result, (idx - (stack.last ?? 0) - 1) * heights[popped])
}
stack.append(idx)
}
return result
}
}<<largest-rectangle-in-histogram>>
print(Solution().largestRectangleArea([2,1,5,6,2,3]) == 10 ? "passed" : "failed")class Solution {
func trap(_ height: [Int]) -> Int {
var heights = height
var stack: [Int] = []
var sum = 0
for (idx, height) in heights.enumerated() {
while let top = stack.last, heights[top] < height {
var h = heights[top]
stack.removeLast()
if stack.isEmpty {
break
}
let width = idx - (stack.last ?? 0) - 1
let minH = min(heights[stack.last ?? 0], heights[idx])
sum += width * (minH - h)
}
stack.append(idx)
}
return sum
}
}class Solution {
func simplifyPath(_ path: String) -> String {
var stack: [String] = []
let elements = path.split(separator: "/")
for element in elements {
if element == ".." {
_ = stack.popLast()
} else if element == "." || element == "" {
continue
} else {
stack.append(String(element))
}
}
return "/" + stack.joined(separator: "/")
}
}是一种操作受限的线性表数据结构，先进先出是为队列，队列支持两个操作： 入队 (enqueue) 出队(dequeue) 。
public protocol Queue {
associatedtype Item
// 入队
func enqueue(_ item: Item)
// 出队
func dequeue() -> Item?
}有数组实现的队列叫 顺序队列 ，用链表实现的队列叫 链式队列 。
- 在队列的基础上增加阻塞操作，就成了阻塞队列
- 阻塞队列是在队列为空的时候，从队头取数据会被阻塞；队列已满时，要入队会被 阻塞，直到队列中有空闲位置时才能继续入队，然后返回。
- 可以用阻塞队列实现一个典型的“生产者-消费者模型”。
- 在多线程的情况下，还会有多个线程同时操作队列，这时就会存在线程安全的问题。
- 并发队列的简单实现就是在 dequeue和enqueue两个操作上加锁，但是锁的粒度大， 并发度就比较低，同一时刻仅允许一个存或者取操作。
- 基于数组的循环链表利用CAS原子操作，可以实现非常高效的并发队列
递归是一种高效简介的编码技巧，只要是满足“三个条件”的问题，都可以通过递归解决。
- 一个问题的解可以分解为几个问题的解
- 这个问题的解与之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
写出递推公式，找到终止条件 写递归代码的关键就是找到如何将大问题分解为小问 题的规律，并且基于此写出递推公式，然后在推敲终止条件，最后将递推公式和终止条 件翻译成代码。
同时要避免思想上的误区，遇到递归，要把它抽象成一个递推公式，不用想层层的调用 关系，不要试图用人脑去分解递归的每个步骤。
- 警惕推栈溢出
因为函数调用使用栈来保存临时变量，每调用一个函数，都会面临变量封装为栈帧压
入内存栈，等函数返回时才出栈，如果递归求解规模很大，调用层次很深，就会有堆
栈溢出的风险。
可以通过限制最大深度来解决。
- 警惕重复计算
以计算 斐波那契数列 为例，在计算f(6)的过程中，会对中间的值进行多次计算，
这就导致了不必要的开销。
为了避免重复计算，我们可以使用一些缓存手段（散列表）来保存已经求解过的f(k)， 当递归调用到f(k)的时候，就可以直接从缓存中取出结果。
- 其他问题 时间效率低，空间复杂度高。
在实际工作中，我们可以规矩实际情况将递归代码改写为迭代代码，来规避递归带来的 问题。
因为递归是借助栈来实现的，所以我们可以自己在内存堆上实现栈，手动模拟入栈、出 栈过程，这样任何递归都可以改写成看上去不是递归的样子。
- 几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并 排序、计数排序、计数排序、基数排序、桶排序
- 复杂度归类 (按时间复杂度分)
- 冒泡排序、选择排序、插入排序 O(n^2)
- 快速排序、归并排序 O(nlogn)
- 计数排序、基数排序、桶排序 O(n)
- 算法的执行效率
- 最好、最坏、平均时间复杂度
- 时间复杂度的系数、常数和低阶
- 比较次数，交换（或移动）次数 有序度和无序度： 有序度 数组中具有有序关系元素对的个数，数学表达： a[i] <= a[j], i < j , 对于一个完全有序的数组，有序度为n * (n - 1) / 2， 称为 满有序度 。 逆虚度 的定义刚好相反，数学表达为： a[i]>a[j],i<j 逆序度 = 满序度 - 有序度
- 算法的稳定性
- 稳定性的概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元 素原有的先后顺序不变，则该排序算法是稳定的。
- 稳定性的重要性：可针对对象的多种属性进行优先级的排序
- 例子：电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于金额 相同的订单，按照创建订单时间先后进行排序。
- 排序的内存损耗： 原地排序： O(1)的时间复杂度
- 个算法比较
| complex | stable | in place | |
|---|---|---|---|
| bubble | O(n^2) | yes | yes |
| insertion | O(n^2) | yes | yes |
| selection | O(n^2) | no | yes |
| quick | O(nlogn) | no | yes |
| merge | O(nlogn) | yes | no |
| counting | O(k+n) | yes | no |
| bucket | O(n) | yes | no |
| radix | O(d*n) | yes | no |
其中 counting 中的 k 为数据范围， radix中的 d 为唯独
冒泡排序只会操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看 是否满足大小关系要求，如果不满足就让它俩交换。
- 稳定性：冒泡排序是稳定的排序算法
- 空间复杂度：冒泡排序是原地排序算法 O(1)
- 时间复杂度：
- 最好：O(n)
- 最坏：O(n^2)
- 平均：O(n^2)
- 实现：
public func bubbleSort<T>(_ items: inout [T]) where T: Comparable { if items.count <= 1 { return } let n = items.count for i in 0..<n { for j in 0..<(n - i - 1) { if (items[j] > items[j + 1]) { items.swapAt(j, j + 1) } } } }
插入排序将数组分为“已排序区间”和“未排序区间”。初始已排序区间只有一个元素，即 数组的第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，知道未 排序区间为空。
- 稳定性：稳定的
- 空间复杂度：原地排序 O(1)
- 时间复杂度：
- 最好：O(n)
- 最坏：O(n^2)
- 平均：O(n^2) 向数组里插入元素的时间复杂度为O(n) 需要插入n次
- 实现：
public func insertionSort<T>(_ items: inout [T]) where T: Comparable { let n = items.count if n <= 1 { return } for i in 1..<n { var j = i while j > 0 && items[j] < items[j - 1] { items.swapAt(j - 1, j) j -= 1 } } }
选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区 间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。
- 稳定性：不稳定的
- 空间复杂度：原地排序 O(1)
- 时间复杂度：
- 最好：O(n^2)
- 最坏：O(n^2)
- 平均：O(n^2)
- 实现：
public func selectionSort<T>(_ items: inout [T]) where T: Comparable { let n = items.count if n <= 1 { return } for i in 0..<n - 1 { var lowest = i for j in i + 1 ..< n where items[j] < items[lowest] { lowest = j } if i != lowest { items.swapAt(i, lowest) } } }
要排序一个数组，我们先把数组从中间分成前后两个部分，然后对前后两个部分分别排 序，再将两个排好序的数组合并成一个，整个数组就排好序了。使用了 分治 的思想 实现的一种排序算法。
- 稳定性：稳定的
- 空间复杂度：非原地排序算法 O(n)
- 时间复杂度：最好、最坏、平均情况下均为 O(nlogn)
- 实现：
func mergeSort(_ array: [Int]) -> [Int] { guard array.count > 1 else { return array } let middleIndex = array.count / 2 let leftArray = mergeSort(Array(array[0..<middleIndex])) let rightArray = mergeSort(Array(array[middleIndex..<array.count])) return merge(leftArray, rightArray) } func merge(_ left: [Int], _ right: [Int]) -> [Int] { var leftIndex = 0 var rightIndex = 0 var orderd = [Int]() while leftIndex < left.count && rightIndex < right.count { if left[leftIndex] < right[rightIndex] { orderd.append(left[leftIndex]) leftIndex += 1 } else if left[leftIndex] > right[rightIndex] { orderd.append(right[rightIndex]) rightIndex += 1 } else { orderd.append(left[leftIndex]) leftIndex += 1 orderd.append(right[rightIndex]) rightIndex += 1 } } while leftIndex < left.count { orderd.append(left[leftIndex]) leftIndex += 1 } while rightIndex < right.count { orderd.append(right[rightIndex]) rightIndex += 1 } return orderd }
如果要排序数组下标从p到r之间的一组数组，我们选择p到r之间的任意一个数组作为“分 区点(pivot)”。将小于pivot的数据放到左边，将pivot的数据放到右边，将pivot放到中 间，。经过这样的步骤之后，数组p到r就被分为了三个部分，p到q-1的数据都是小于 pivot的，中间是pivot，q+1到r之间的数据都是大于pivot的。 根据递归分治的思想，我们可以用递归排序小表p到q-1的数据和下标从q+1到r的数据， 直到区间缩小为1，就说明所有的数据都有序了。
- 稳定性：不稳定
- 空间复杂度：原地排序 O(1)
- 时间复杂度：大部分情况下O(nlogn) 极少情况下退化为O(n^2)
- 实现：
func quicksort<T: Comparable>(_ a: inout [T]) { quicksortLomuto(&a, low: 0, high: a.count - 1) } func quicksortLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) { if low < high { let p = partitionLomuto(&a, low: low, high: high) quicksortLomuto(&a, low: low, high: p - 1) quicksortLomuto(&a, low: p + 1, high: high) } } func partitionLomuto<T: Comparable>(_ a: inout [T], low: Int, high: Int) -> Int { let pivot = a[high] var i = low for j in low..<high { if a[j] <= pivot { a.swapAt(i, j) i += 1 } } a.swapAt(i, high) return i } var list = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ] quicksort(&list)
快速排序在最坏情况下时间复杂度会退化为O(n^2)，这种退化主要是因为分区点选的不 够合理。理想的分区点是: 被分区点分开的两个分区中，数据数量差不多 ，简单的 分区算法有：
- 三数取中法：从区间的首，尾，中分别取一个数，然后对比大小，取这3个数的中间 值作为分区点。如果排序数组比较大，那”三数取中“可能不够，可能要“五数取中”， “十数取中”。
- 随机法：随机法就是每次从要排序的区间中，随机选择一个元素作为分区点。
将要排序的数据放到几个有序的桶里面，每个痛的数据在单独进行排序。桶内排序完之 后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
- 稳定性： -
- 空间复杂度：O(n)
- 时间复杂度：在适用场景下为线性 O(n)，极端情况下退化为O(nlogn)
- 适用场景
- 要排序的数据需要很容易被划分成m个桶，并且桶与桶之间有着天然的大小顺序
- 数据在个桶之间的分布比较均匀
- 桶排序还适合用在 外部排序 中
当要排序的n个数据，所处的防伪并不大的时候，比如最大值是k，我们就可以把数据划 分成k个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。
- 稳定性：可以稳定的
- 空间复杂度：O(n)
- 时间复杂度：O(n)
- 适用场景：如果排序数据范围k比要排序的数据n大很多，就不适合适用计数排序了。 而且，计数排序只能给非负整数排序，如果排序的数据是其他类型的，要将其在不改 变相对大小的情况下，转化为非负整数。
func countingSort(_ array: [Int]) -> [Int] {
guard array.count > 0 else { return [] }
let maxElement = array.max() ?? 0
// 计数
var countArray = [Int](repeating: 0, count: maxElement + 1)
for element in array {
countArray[element] += 1
}
// 累加
for index in 1 ..< countArray.count {
let sum = countArray[index] + countArray[index - 1]
countArray[index] = sum
}
// 排序
var sortedArray = [Int](repeating: 0, count: array.count)
for element in array {
countArray[element] -= 1
sortedArray[countArray[element]] = element
}
return sortedArray
}Swift使用稳定的，适应性的归并排序，时间复杂度为O(n log n)
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过个区 间中间的元素对比，将带查找的区间缩小为之前的一半，直到找到要查找的元素，或者区 间被缩小为0. 时间复杂度 O(logn)
- 推出循环的条件 应该是 low <= high，而不是 low < high
- mid 的取值
一般写为
(low+high) / 2, 如果low和high很大的话，两者之和可能会溢出。可 以写为low + (high - low) / 2, 跟进一步优化的话可以将出发操作改为位移操 作。 - low和high的更新 low = mid + 1, high = mid - 1，要特别注意相应的 +1 和 -1 操作，直接让high， low等于mid的话，容易进入死循环。
- 二分查找依赖顺序表结构
- 二分查找针对的是有序数据
- 数据量太小不适合二分查找 运行时间可能与线性查找差距不大
- 数据量太大不适合二分查找 数据可能无法一次装入数组
func bsearch(_ nums: [Int], _ n: Int) -> Int {
var low = 0
var high = nums.count - 1
while low <= high {
let mid = low + ((high - high) >> 1)
if nums[mid] == n {
return mid
} else if nums[mid] > n {
high = mid - 1
} else {
low = mid + 1
}
}
return -1
}
let nums = [8, 11, 19, 23, 27, 33, 45, 55, 67]
print(bsearch(nums, 33) == 5)
print(bsearch(nums, 34) == -1) func bsearch(_ nums: [Int], _ n: Int) -> Int {
return bsearch(nums, n, low: 0, high: nums.count - 1)
}
func bsearch(_ nums: [Int], _ n: Int, low: Int, high: Int) -> Int {
if low > high { return -1 }
let mid = low + ((high - low) >> 1)
if nums[mid] == n {
return mid
} else if nums[mid] > n {
return bsearch(nums, n, low: low, high: mid - 1)
} else {
return bsearch(nums, n, low: mid + 1, high: high)
}
}
let nums = [8, 11, 19, 23, 27, 33, 45, 55, 67]
print(bsearch(nums, 33) == 5)
print(bsearch(nums, 34) == -1)func bsearch(from nums: [Int], firstEqualTo n: Int) -> Int {
var low = 0
var high = nums.count - 1
while low <= high {
let mid = low + ((high - low) >> 1)
if nums[mid] > n {
high = mid - 1
} else if nums[mid] < n {
low = mid + 1
} else {
if (mid == 0 || nums[mid - 1] != n) {
return mid
} else {
high = mid - 1
}
}
}
return -1
}
print(bsearch(from: [1,3,4,5,6,8,8,8,11,18], firstEqualTo: 8) == 5)func bsearch(from nums: [Int], lastEqualTo n: Int) -> Int {
var low = 0
var high = nums.count - 1
while low <= high {
let mid = low + ((high - low) >> 1)
if nums[mid] > n {
high = mid - 1
} else if nums[mid] < n {
low = mid + 1
} else {
if mid == nums.count - 1 || nums[mid + 1] != n {
return mid
} else {
low = mid + 1
}
}
}
return -1
}
print(bsearch(from: [1,3,4,5,6,8,8,8,11,18], lastEqualTo: 8) == 7)func bsearch(from nums: [Int], firstGreaterThanOrEqualTo n: Int) -> Int {
var low = 0
var high = nums.count - 1
while low <= high {
let mid = low + ((high - low) >> 1)
if nums[mid] >= n {
if mid == 0 || nums[mid - 1] < n {
return mid
}
high = mid - 1
} else {
low = mid + 1
}
}
return -1
}
print(bsearch(from: [3,5,6,8,9,10], firstGreaterThanOrEqualTo: 7) == 3)func bsearch(from nums: [Int], lastLessThanOrEqualTo n: Int) -> Int {
var low = 0
var high = nums.count - 1
while low <= high {
let mid = low + ((high - low) >> 1)
if nums[mid] <= n {
if mid == nums.count - 1 || nums[mid + 1] > n {
return mid
}
low = mid + 1
} else {
high = mid - 1
}
}
return -1
}
print(bsearch(from: [3,5,6,8,9,11], lastLessThanOrEqualTo: 7) == 2)对于但链表来说，即使内部存储的数据是有序的，要查找一个元素也需要从头到尾遍历 一边数组，复杂度为O(n)。又不能像数组那样使用二分查找，我们可以对链表建立一级 “索引”，每两个节点取一个节点到上一级，抽出来节点叫作“索引”或者“索引层”。
┌───┬┐ ┌───┬┐ ┌─────┐
layer2 │ 1 │├─────────────────────────────▶│ 7 │├────────────────────▶│ nil │
└───┴┘ └───┴┘ └─────┘
│ │
│ │
┌─▼─┬┐ ┌───┬┐ ┌─▼─┬┐ ┌───┬┐ ┌─────┐
layer1 │ 1 │├───────────▶│ 4 │├───────────▶│ 7 │├───────────▶│10 │├──▶│ nil │
└───┴┘ └───┴┘ └───┴┘ └───┴┘ └─────┘
│ │ │ │
│ │ │ │
┌─▼─┬┐ ┌───┬┐ ┌─▼─┬┐ ┌───┬┐ ┌─▼─┬┐ ┌───┬┐ ┌─▼─┬┐ ┌─────┐
layer0 │ 1 │├──▶│ 3 │├──▶│ 4 │├──▶│ 5 │├──▶│ 7 │├──▶│ 8 │├──▶│10 │├──▶│ nil │
└───┴┘ └───┴┘ └───┴┘ └───┴┘ └───┴┘ └───┴┘ └───┴┘ └─────┘
┌────┐ ┌────┬────┐ ┌─────┐
│ │──────────────────────▶│ │ │──────────────────────────────────────────────────────────────────────────────────────────▶│ │
├────┤ │ ├────┤ ┌────┬────┐ │ │
│ │──────────────────────▶│ │ │─────────────────────────────────────────────────────────────────────────▶│ │ │─────▶│ │
├────┤ │ 7 ├────┤ ┌────┬────┐ │ ├────┤ │ nil │
│ │──────────────────────▶│ │ │──────────────────────▶│ │ │───────────────────────────────────────▶│ 37 │ │─────▶│ │
├────┤ ┌────┬────┐ │ ├────┤ ┌────┬────┐ │ 19 ├────┤ ┌────┬────┐ ┌────┬────┐ │ ├────┤ │ │
│ │─────▶│ 3 │ │─────▶│ │ │─────▶│ 11 │ │─────▶│ │ │─────▶│ 22 │ │─────▶│ 26 │ │─────▶│ │ │─────▶│ │
└────┘ └────┴────┘ └────┴────┘ └────┴────┘ └────┴────┘ └────┴────┘ └────┴────┘ └────┴────┘ └─────┘
时间复杂度O(logn) 每两个节点抽取一个节点作为上一级节点的索引，那第一级索引的节点大概是n/2，第二 级索引的节点大概是n/4，第三纪索引的节点大概是n/8。那么第k级索引的节点个数是第 k-1级索引节点个数的1/2，那么第k级索引的节点个数是n/2^k。
每两个节点抽取一个节点做索引的空间复杂度为： 2/n + 4/n + 8/n + … + 8 + 4 + 2 = n - 2
没三个节点抽取一个节点做索引的空间复杂度： n/3 + n/9 + n/12 + … + 9 + 3 + 1 = n/2
总体空间复杂度为O(n)，但每个几个抽取节点当作索引没有量级上的差异，但是可以起 到优化效果。
在实际软件开发中，可以不用太在意索引占用的存储空间。因为原始链表可能存了很大 的数据对象，而索引只需要存储关键值和几个指针。
单向链表的插入操作很高效，只需要O(1)的时间复杂度，但是为了保证链表的有序性， 找到要插入的位置需要O(n)的时间复杂度。得益于跳表高效的搜索效率，找到要插入的 位置只需要O(logn)的复杂度
如果要删除的节点在索引中也有出现，我们除了要删除链表中的节点，索引中的节点也 要删除。
当我们不停的往跳表中插入数据而不更新索引是，很有可能某两个索引节点间存在大量 数据，最后导致跳表退化为单链表。为了避免复杂度退化，我们需要某种手段来维护跳 表的索引。 我们可以使用一个 随机函数 来决定这个节点插入到哪几级索引中，比如随机函数生 成了值K，那我们就把索引插入到第1级到第K级这K级索引中。
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩 展，由数组演化而来。可以说，如果没有数组，就没有散列表。
通过元素的键生成散列值的函数叫散列函数。散列函数的三个基本要素：
- 散列函数计算得到的散列值是一个非负整数。
- 如果
key1==key2，那么hash(key1)==hash(key2) - 如果 key1!=key2, 那么 hash(key1)!=hash(key2)
什么叫散列冲突 解决散列冲突的方法有两种 开放寻址法 链表法
开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一个空闲位置，将其 插入。重新探测空闲位置也有很多方法，其中比较简单的一个叫做： 线性探索
当我们向散列表中插入数据时，如果发现位置已经被占用，那么就一个一个向后找， 知道找到为止，如果找到最后都没有找到空闲，就从头开始找，知道找到为止。
我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列 值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后 依次查找。如果遍历到数组中的空闲位置，还没有找到，就说明要查找的元素并没有 在散列表中。
删除元素时，当我们找到要删除的元素，不能直接将这个位置的值置空，这样会导致 查找函数失效。而是要将这个位置标记为deleted，当探测到deleted继续找下一个。
这种探测方法存在很大问题，就是随着插入的数据越来越的，散列冲突发生的概率就 越来越大，空闲位置越来越少，线性探测的时间就越来越久。
对于开放寻址解决冲突的方法，除了线性探测之外，还有二次探测和双重探测。不管采用 那种方法，当新型链表中的元素越来越多，散列冲突的概率也越来越大。
在散列表中，每个桶或者槽对应一条链表，所有散列值相同的元素我们放到相同槽位对 应的散列表中。
插入的时候，只需要通过散列函数计算出对应的散列槽位，将其插入到对应的链表中即 可。
查找和删除的时候需要通过散列函数计算出对应的槽位，然后便利链表查找或者删除。
一个好的散列表
- 散列函数设计不能太复杂。太复杂的散列函数会消耗太多的计算资源
- 散列函数生成的值要尽可能随机并且分布均匀。这样才能最小化散列冲突，即便出现 散列冲突，因为分布均匀，不会出现某个槽里数据特别多的问题.
一般情况下，我们们会保证哈希表中有一定比列的空闲槽位。我们使用 装载因子 来表 示空位的多少。
散列表的装载因子 = 填入表中元素的个数 / 散列表的长度
装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率也就越大。
当装载因子过大时，我们可以对散列表进行动态扩容。我们可以将散列表扩容为原先的 2倍，将原散列表的元素重新计算散列值插入新的散列表。随着数据的删除，装载因子 会不断变小，当缩小到某一个值时，我们可以进行动态缩容。
装载因子的阈值设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求 很高，可以降低装载因子的阈值；相反，可以提高装载因子的阈值。
我们可以将扩容穿插在插入过程中，分批完成。
当装载因子触达阈值之后，我们对散列表进行扩容，但是不进行数据搬移。当有新数据 插入是，我们将新数据插入到新的散列表中，同时将旧散列表中的一个数据搬移至新的 散列表。 查找删除元素是，先在新散列表中进行查找，如果未找到，则到旧散列表中进行查找。
开放寻址法的优点是
- 散列表的数据都存放在数组中，可以利用CPU缓存机制加快查询速度。
- 序列化简单
开放寻址法的缺点
- 删除数据比较麻烦，需要特殊标记已经删掉的数据。
- 所有数据都存储在一个数组中，冲突代价更高。
当数据量比较小、装载因子小的时候，适合开放寻址法
优点
- 对内存的利用率比开放寻址法要更高
- 对大装载因子容忍度更高
缺点
- 可能消耗更多内存
- 无法利用CPU的缓存机制，查找效率偏低
可以对链表法进行改造，实现一个更加高效的散列表。可以讲链表换为其他更高效的数 据结构，例如：跳表，红黑树。这样即使出现散列冲突，即使出现散列碰撞攻击，查找 效率也为O(logn)。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且比起开 放寻址法，它更加灵活，支持更多的优化策略
- 父节点
- 子节点
- 兄弟节点
- 根节点
- 叶子节点
- 高度
- 深度
- 层
每个节点最多只有两个节点，左子节点和右子节点
叶子节点在最底层，除了叶子节点之外，每个节点都有左右两个子节点
叶子节点都在最底下两层，最后一层的叶子节点靠左排列，并且除了最后一层，其他层 的节点个数都达到最大
- 基于指针的二叉链式存储
- 基于顺序表的存储
每个节点有三个字端：值，指向左节点的指针，指向右节点的指针
class TreeNode<Value> {
let value: Value
var left: TreeNode?
var right: TreeNode?
init(_ value: Value) {
self.value = value
}
}使用数组(tree)存储树中的节点，对于在位置i的节点
- 根节点：0
- 左子节点： i * 2 + 1
- 右子节点： i * 2 + 2
- 父节点： ( i - 1 ) / 2
顺序存储方式适合用来存储完全二叉树，一般二叉树使用顺序方式存储会造成数组空 洞，浪费存储空间
前序遍历，中序遍历，后续遍历
根节点 -> 左子树 -> 右子树
<<TreeNode>>
func preorderTraversal(_ root: TreeNode<Value>?) -> [Value] {
guard let root = root else { return [] }
return [root.value] + preorderTraversal(root.left) + preorderTraversal(root.right)
}func preorderTraversal<Value>(_ root: TreeNode<Value>?) -> [Value] {
guard let root = root else { return [] }
var result = [Value]()
var stack = [root]
while !stack.isEmpty {
let node = stack.removeLast()
result.append(node.vale)
if let left = node?.left {
stack.append(left)
}
if let right = node?.right {
stack.append(right)
}
}
return result
}左子树 -> 根节点 -> 右子树
左子树 -> 右子树 -> 根节点
堆是一种特殊的树，只要满足两点要求，就是一个堆
- 堆是一个完全二叉树
- 堆中的每个节点的值都必须大于等于（或小于等于）其子树中的每个节点的值。
- 大顶堆：每个节点的值都大于等于其每个子节点的值
- 小顶堆：每个节点的值都小于等于其每个子节点的值
由于堆是一个完全二叉树，所以使用数组来存储非常方便，且节省空间。只使用下标就 可以找到一个节点的左右子树。
根节点存储在数组[1]的位置，那么下标为 i * 2 的节点就是左子节点； i * 2 + 1就 是节点的右子节点。i / 2 就是父节点。
如果我们向堆中插入，或者从堆中删除一个元素，堆的结构会被破坏，我们需要调整 结构，使其在操作后依然是个堆，该过程称为堆化。
堆化有两种：从下往上 从上往下
插入元素后，需要继续满足堆的两个特性：完全二叉树，每个节点的值都大于等于 （或小于等于）其每个子节点的值。
可以使用 从下往上 的堆化过程，先将元素插入到数组的最后，然后与父节点比较 大小，如果不满足子节点小于等于父节点的关系，就互换节点，一直重复这个过程， 知道父子节点满足堆要求的大小关系。
堆顶元素存储的就是堆中的最大值或者最小值。
以大顶堆为例，当我们删除堆顶元素后，就需要把第二大的元素放到堆顶，第二大的 元素肯定出现在左右节点中。然后迭代的删除第二大节点，以此类推，直到叶子节点 被删除。这种方法有可能出现数组中的空洞。
可以用另一种方法，还以大顶堆为例，将堆中的最后一个元素放到第一个，然后进行 一次 从上到下 的堆化，可以避免出现数组空洞，肯定满足完全二叉树的特性。
一个包含n个节点的完全二叉树，树的高度不会超过 log2 n。堆化的时间复杂度跟树 的高度成正比，也就是O(log n)。插入和删除堆顶元素的主要逻辑就是堆化，所以， 往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(log n)。
堆排序是原地排序算法，时间复杂度是稳定的 O(n log n)。
堆排序分为两步 建堆 排序
建堆有两种方法
核心逻辑就是向堆中插入元素。假设起初堆中只包含下标为1的元素，然后一次将2到 n的元素插入到堆中，这样就组成了堆。
对于大顶堆，数组的第一个元素就是堆顶，也就是数组的最大元素，把它跟数组最后 一个元素交换，最大元素就放到了下标为N的位置。将剩下的 n - 1 个元素重新构建 成堆。堆化后，我们再取堆顶元素，放到下标是 n - 1 的位置，一直重复这个过程， 直到最后堆中剩下一个元素。
包括建堆和排序两个操作，建堆操作的时间复杂度是O(n)，排序的时间复杂度是O(n log n), 所以整体时间复杂度是 O(nlogn)
堆排序是原地排序算法
堆排序不是稳定的
优先级队列与普通队列先进先出的性质不同，而是按照优先级来确定出队顺序，优先级 高的先出队。
一个堆可以看作是一个优先级队列，往优先级队列插入一个元素就相当于向堆中插入一 个元素，从队列中取出优先级最高的元素就相当于取出堆顶元素。