Algorithms_基础数据结构(04)_线性表之链表_单向循环链表&约瑟夫环问题

简介: Algorithms_基础数据结构(04)_线性表之链表_单向循环链表&约瑟夫环问题

20191216220326136.png


大纲图


20191229231819317.png

链表的经典面试题目

如何设计一个LRU缓存淘汰算法

tip:单向链表


约瑟夫问题


N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。

举个例子: 假设N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。

现在问你最后留下的人是谁?

比如N=6,M=5 ,留下的就是1

1 2 3 4 5 6 => 6 1 2 3 4 => 6 1 2 3 =>1 2 3 => 1 3 => 1


tips: 单向循环链表


结构


20200108141801697.png


相比单向链表(单向链表的tail节点next指针指向null) , 单向循环链表无非就是把尾结点的next指针重新指向head节点而已。


代码实现也相对简单,多一步操作, 思路可参考 Algorithms_基础数据结构(02)_线性表之链表_单向链表 ,这里我们直接使用单向循环链表来解决个经典的算法问题吧。


分析


20200108195715989.png


20200108195736496.png


相关文章
|
1月前
|
存储 C语言
数据结构中的线性表链式存储介绍及其基本操作
链式存储是线性表的一种重要存储方式,它通过节点和指针的结构,实现了灵活的动态存储管理。本文介绍了单向链表的基本操作,并提供了相应的C语言代码示例。理解和掌握链表的操作对学习和应用数据结构具有重要意义。希望这篇博客能帮助你更好地理解线性表的链式存储。
37 2
|
21天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
27 5
|
21天前
|
存储 测试技术
【数据结构】操作受限的线性表,队列的具体实现
【数据结构】操作受限的线性表,队列的具体实现
21 4
|
29天前
|
存储 算法
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
【单向链表】数据结构——单向链表的介绍与代码实现&笔记
|
21天前
|
Java
单向环形链表-约瑟夫问题(java)
单向环形链表-约瑟夫问题(java)
8 0
|
21天前
|
存储 算法 前端开发
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
13 0
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
【循环链表】数据结构——单向循环链表和双向循环链表操作&笔记
|
1月前
|
存储 算法
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
数据结构和算法学习记录——特殊线性表之队列-队列的概念、队列结构体类型定义 、基本接口函数、初始化函数、销毁队列函数、入队列函数、判断队列是否为空、出队列函数、读取队头队尾的数据 、计算队列数据个数
18 0
|
20天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)