有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表示扔掉该卡片。
性能方面,数组比列表要好很多。
分享到:
相关推荐
2位数*3位数=4位数的算法 2位数*3位数=4位数的算法 java代码
线性时间选择,中位数算法,利用按每5个元素分组,分别找出其中位数,再递归找出
计算机图形学算法卡片 栏栅求余算法 AEL算法 中点法画直线 八点画圆
经典算法5(十进制整数的数位提取算法,逆序、正序输出).c
实现数字签名算法以及验证数字签名算法的正确性。本程序经本人验证
1)利用C\C++语言实现DSA算法。 2)DSA中的Hash函数采用SHA算法。 (1)消息填充:因为我们存储的时候是以字节为单位存储的,所以消息的长度(单位:位)一定是 8 的倍数。而我们填充的时候也一定是 8 位、8 位...
计算机图形学(倪明田著)的图形学基本算法卡片,方便大家查询
总结数位DP算法.doc
算法训练 数位分离 时间限制:1.0s 内存限制:512.0MB 问题描述 编写一个程序,输入一个1000 以内的正整数,然后把这个整数的每一位数
快速记忆算法小卡片图文算法!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
平时作业 数字卡片的识别 输入:9个,笔划通过小块时,输出为“1”,否则为“0”; 输出:1个,当超过阈值时...奇偶数字卡片识别利用单层感知器学习算法,求解上述“奇偶辨认”例题(即:让机器自动求解权值和阈值)。
python实现的介数中心算法
LRU算法LRU算法LRU算法LRU算法
PPT图片结合文字讲述数位dp
java 优先数调度 处理器调度 java设计一个按优先数调度算法实现处理器调度的程序。
这是一个不错的算法,21位的花朵数只用30多秒,容易理解
6位数,共有几种排列组合的算法,java实现
包涵三个RSA算法,c++是实现,数字签名的合集,三个独自的程序,可以独自编译运行,VC6.0下编译
g_p算法,关于求解嵌入关联维数的matlab的算法
条件中位数算法用于无失效数据的可靠性估算,本程序是主函数,将数据带入即可计算