数据结构面试题.md

链表和数组的区别是什么？插入和查询的时间复杂度分别是多少？

查看答案

数组是一个连续的内存空间，链表可以在内存的任何位置。数组查找比链表快，链表插入和删除比数组快。数组空间大小固定，链表空间大小不固定。

数组的插入复杂度o(n),链表是o(1)。数组查询的复杂度是o(n),链表是o(1)。

哈希表是如何实现的？如何解决地址冲突？

查看答案

哈希表其实是一个数组，数组的每一个元素是一个哈希字典。哈希字典通过内存地址的Hash值作为Key来存储。解决地址冲突方法有

• 开放定址法 开放定址法可以分为三种
  • 线性探测(顺序查找下一个单元)
  • 二次探测(左右两侧相互查找)
  • 随机探测(随机查找下一个单元)
• 再哈希法（通过修改Hash函数再次生成一个不重复的Hash值）
• 链地址法
• 建立公共溢出区

如何检测链表中是否有环？

查看答案

• 顺序查找 每次出现新节点 就查询之前的所有节点看是否有重复的节点ID
• 通过哈希表 按照顺序查找 把出现的节点存在hash表中 之后新出的节点在hash表查看是否存在重复的节点ID
• 创建两个指针都指向头节点 指针1一次移动一个节点 指针2每次移动两个节点 如果两个指针指向的节点ID一样则证明有环

简单说明 单向链表\双向链表\循环链表

查看答案

单项链表只有一个头比如火车，双向链表有两个头部，比如高铁和轻轨，地铁。循环链表，是头部和尾部相连。比如蛇环，

集合结构 线性结构 树形结构 图形结构

查看答案

• 集合结构是一个集合中存在很多的元素，元素和元素之间没有任何的联系。
• 线性结构是所有元素都在一条线上，可以是直线也可以是曲线。
• 树形结构也就是元素存在一对多的关系。
• 图形结构就好比一张蜘蛛网，多对多的关系。

数据结构的存储

查看答案

数据结构的储存有两种方式

• 顺序储存 数组
• 链式储存 链表

什么是二叉搜索树？时间复杂度是什么？

查看答案

二叉搜索树特点是左侧节点小于右侧节点，右侧节点大于父节点。时间复杂度o(log2(n))

求二叉树的最大深度

查看答案

• 循环递归

class Solution {
    func maxDepth(treeNode:TreeNode?) -> Int {
        guard let treeNode = treeNode else {
            return 0
        }
        let leftDepth = maxDepth(treeNode: treeNode.left)
        let rightDepth = maxDepth(treeNode: treeNode.right)
        return max(leftDepth, rightDepth) + 1
    }
}

• 迭代

class Solution {
    func maxDepth(treeNode:TreeNode?) -> Int {
        guard let treeNode = treeNode else {
            return 0
        }
        var stack:[(TreeNode?,Int)] = [(treeNode,1)]
        var maxDepth = 1
        while stack.count > 0 {
            let root = stack.removeFirst()
            let currentDepth = root.1
            guard let node = root.0 else {
                continue
            }
            maxDepth = max(maxDepth, currentDepth)
            stack.append((node.left,currentDepth + 1))
            stack.append((node.right,currentDepth + 1))
        }
        return maxDepth
    }
}

判断二叉树是否是平衡二叉树

查看答案

平衡二叉树定义是空树或者是左右节点的深入相差1

class Solution {
    func isBalanced(treeNode:TreeNode?) -> Bool {
        guard let treeNode = treeNode else {
            return false
        }
        if treeNode.left == nil && treeNode.right == nil {
            return true
        }
        let leftDepth = maxDepth(treeNode: treeNode.left)
        let rightDepath = maxDepth(treeNode: treeNode.right)
        let value = leftDepth - rightDepath
        return value == 1 || value == -1
    }
    func maxDepth(treeNode:TreeNode?) -> Int {
        guard let treeNode = treeNode else {
            return 0
        }
        var stack:[(TreeNode?,Int)] = [(treeNode,1)]
        var maxDepth = 1
        while stack.count > 0 {
            let root = stack.removeFirst()
            let currentDepth = root.1
            guard let node = root.0 else {
                continue
            }
            maxDepth = max(maxDepth, currentDepth)
            stack.append((node.left,currentDepth + 1))
            stack.append((node.right,currentDepth + 1))
        }
        return maxDepth
    }
}

单链表反转

查看答案

单链表反转