有N张卡片,标号为从1到N。第一轮抽取到奇数位时,将卡片扔掉,偶数位保留;第二轮扔掉剩下来的奇数位。以此类推,最后剩下的卡片标号为?
1. 列表实现
private static int retrieveLastViaList(int n) {
LinkedList<Integer> list = new LinkedList<Integer>(); // 构建列表
for (int i = 1; i <= n; i++) { // 第一轮
if (i % 2 == 0) {
list.add(i); // 存放卡片
}
}
boolean bOdd = true; // 奇数位标志
Iterator<Integer> iter = list.iterator();
while (true) {
if (!iter.hasNext()) { // 到卡片尾部了,开始下一轮
iter = list.iterator();
bOdd = true; // 重置奇数位标志
}
Integer cur = iter.next();
if (list.size() == 1) { // 卡片只有一张了,是我们需要的
return cur;
}
if (bOdd) { // 奇数位
iter.remove(); // 扔掉卡片
bOdd = false; // 切换偶数位
} else { // 偶数位
bOdd = true; // 切换奇数位
}
}
}
2. 数组实现
private static int retrieveLastViaArray(int n) {
int[] arr = new int[n]; // 构建数组
for (int i = 1; i <= n; ++i) {
arr[i - 1] = i; // 存放卡片
}
int cur = 1; // 当前卡片
int rem = n; // 剩余卡片数
boolean bOdd = true; // 奇数位标志
while (true) {
if (rem == 1) { // 只剩一张卡片
while (arr[cur - 1] == 0) { // 该卡片已丢弃,定位下一张可用的卡片
cur++;
if (cur > n) { // 超过卡片尾部
cur = 1;
}
}
return cur; // 返回该卡片标号
}
while (arr[cur - 1] == 0) { // 该卡片已丢弃,定位下一张可用的卡片
cur++;
if (cur > n) { // 超过卡片尾部,开始下一轮
bOdd = true; // 重置奇数位标志
cur = 1;
}
}
if (bOdd) { // 奇数位
arr[cur - 1] = 0; // 置0,表示丢弃
rem--; // 剩余卡片减一
bOdd = false; // 切换到偶数位
} else { // 偶数位
bOdd = true; // 切换到奇数位
}
cur++;
if (cur > n) { // 超过卡片尾部,开始下一轮
bOdd = true; // 重置奇数位标志
cur = 1;
}
}
}
逻辑方面,数组比列表复杂,因为数组创建后,长度无法改变,通过置0表示扔掉该卡片。
性能方面,数组比列表要好很多。
分享到:
相关推荐
### 线性时间选择中位数算法 #### 实验目的 1. **掌握线性时间选择的基本算法及其应用:** 线性时间选择算法是一种可以在平均或最坏情况下达到线性时间复杂度的选择算法,它主要用于在无序数组中找到第k小的元素。...
平时作业 数字卡片的识别 输入:9个,笔划通过小块时,输出为“1”,否则为“0”; 输出:1个,当超过阈值时...奇偶数字卡片识别利用单层感知器学习算法,求解上述“奇偶辨认”例题(即:让机器自动求解权值和阈值)。
其中,Crpto-1算法是Mifare Classic卡中用于数据加密的一种专有算法,它为卡片的数据安全提供了基础保障。本资源包含的是Crpto-1加密算法的源码,可用于理解算法原理或开发与Mifare Classic兼容的读写设备。 Crpto-...
g_p算法,关于求解嵌入关联维数的matlab的算法
6位数,共有几种排列组合的算法,java实现
第九章聚焦于“中位数和顺序统计量”,这些概念在数据分析、数据挖掘以及算法设计中扮演着重要角色。中位数是数据集中间的平衡点,而顺序统计量则涉及对数据集中的特定位置值的查询。我们将深入探讨这两个概念及其C#...
好久没有上传资料了,这是我前几年开发51单片机时写得多位数除法的一个算法。前两天用了一下。感觉还是那么好用。所以发上来供大家参考。 此算法为汇编,被除数、除数和商的位数都不限,商的小数点后转换为十进制后...
**基于OpenCV的中位切分算法详解** 中位切分算法是一种经典的图像分割方法,尤其适用于处理二值图像或灰度图像。该算法通过反复将像素集合按灰度值进行排序并切分,达到分割图像的目的。在计算机视觉和图像处理领域...
滤波算法集合(中位数、中位数平均、平均、加权平均、一阶加权、正太分布)
有n张卡片排成一行,并且有n个不同的数字写在卡片上(每张卡片上一个),使得卡片呈降序排列状态 现在允许你交换任何一对卡片的位置,只要它们之间只有一张卡片即可 对于什么样的n值,在这样一组操作序列以后,能...
以下是一些关于手写数字识别的基本概念、常用算法以及如何在C语言中实现这些算法的关键知识点: 1. **预处理**: 在识别手写数字之前,通常需要对图像进行预处理。这包括二值化(将图像转换为黑白)、降噪(去除...
算法讲解084【必备】数位dp-上
数位dp与ac自动机算法
3.7 禁位排列 习 题 第四章 鸽巢原理 4.1 鸽巢原理 4. 2 鸽巢原理的推广形式 4. 3 ramsey数 4.4 ramsey数的性质 4.5 ramsey定理 习 题 第五章 母函数 5.1 母函数概念 5.2 幂级数型母函数 5.3 ...
模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+代码实现)模型算法大全(20+种常用算法模型+...
8. 5 数字非相干双△△DLL跟踪算法及VLSI结构 8. 5. 1 非相干双△DLL跟踪算法描述 8. 5. 2 环路参数设计及部分单元部件的VLSI结构 8. 5. 3 数字式非相干双△DLL的VLSI结构 8. 6 窄相关DLL原理及性能 8. 6. 1 窄相关...
电梯调度算法是优化高层建筑内电梯运行效率的关键技术,它涉及到多门学科,如计算机科学、控制理论和人工智能。在给定的压缩包文件中,包含了一系列关于电梯调度算法的资料,涵盖了强化学习、LOOK调度、最短寻道、...
粒子群算法(Particle Swarm Optimization, PSO)与遗传算法(Genetic Algorithm, GA)是两种在优化问题中广泛应用的全局搜索方法。它们都是基于自然选择和群体智能的启发式算法,能够有效地解决复杂多模态优化问题...
标题中的“灰狼优化算法和粒子群优化算法比较”指的是在优化问题中,对两种流行的启发式算法——灰狼优化算法(Grey Wolf Optimizer, GWO)与粒子群优化算法(Particle Swarm Optimization, PSO)的性能进行分析和...
对二进制的数字数据,在需要按位取反时,可以直接使用该函数。是效率最优算法。