week08 作业

用户头像
强哥
关注
发布于: 2020 年 07 月 29 日

作业一:

有两个单向链表(链表长度分别为 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

  • 旋转二叉树恢复平衡

左旋,右旋

  • 红黑(排序)树

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

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

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

  • 跳表

常用算法

  • 穷举算法

  • 递归算法

  • 贪心算法

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

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

  • 动态规划



用户头像

强哥

关注

这个强哥不太弱 2019.08.06 加入

肚子里的货都在文字里了。

评论

发布
暂无评论
week08作业