week08 作业

作业一：

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也可能不合并。

现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。

请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。

HashMap<String> hashMapOne;

while(headOne != null) {

hashMapOne.put(headOne);

headOne = headOne.next;

}

bool found =false;

while(headTwo != null) {

if(hashMapOne.ContainKey(headTwo)) {

found = true;

return headTwo;

}

}

return none;



空间复杂度O(n),时间复杂度O(1)



总结

算法复杂度

• 时间复杂度

并不是计算程序具体运行的事件，而是算法执行语句的次数

• 空间复杂度

一个算法在运行过程中临时占用存储空间大小的量度

• NP问题

数据结构

• 数组

连续空间相同数据类型，根据下标访问数据，时间复杂度为O(1)

• 链表

可以使用零散内存空间存储数据，查找链表数据，需要遍历，查找复杂度是O(N)

• Hash表

实现快速访问数据，增删数据，时间复杂度O(1)

由于Hash冲突的存在，hash表存储的是指针

数组和链表都是线性表

• 栈

栈在线性表的基础上加了操作限制条件：后进先出。线程栈，栈帧的概念。

• 队列

操作受限的线性表，先进先出，典型应用场景：生产者消费者；阻塞等待的线程被放入队列

• 队列搜索好友中关系最近的有钱人可以用队列实现

• 树

• 二叉排序树

左子树上所有节点的值均小于或等于它的根节点的值

右子树所有节点的值均大于或等于它的根节点的值

• 平衡二叉（排序）树

从任何节点出发。左右子树深度之差的绝对值不超过1

• 旋转二叉树恢复平衡

左旋，右旋

• 红黑（排序）树

每个节点只有两种颜色；红色和黑色。根节点是黑色的。每个叶子节点都是黑色的空节点

根节点到叶子节点。不会出现两个连续的红色节点

从任何一个节点触发，到叶子节点，这条陆金尚都有相同数目的黑色节点

• 跳表

常用算法

• 穷举算法

• 递归算法

• 贪心算法

当前最优解不一定是整体最优解，得到的是较优解

迪杰斯特拉算法（最快路径）对贪心算法进行改进

• 动态规划