网站用户访问统计,网站html5自适应屏幕大小,网站字体特效,家装设计学校题目 给定一个从1 到 n 排序的整数列表。 首先#xff0c;从左到右#xff0c;从第一个数字开始#xff0c;每隔一个数字进行删除#xff0c;直到列表的末尾。 第二步#xff0c;在剩下的数字中#xff0c;从右到左#xff0c;从倒数第一个数字开始#xff0c;每隔一个…题目 给定一个从1 到 n 排序的整数列表。 首先从左到右从第一个数字开始每隔一个数字进行删除直到列表的末尾。 第二步在剩下的数字中从右到左从倒数第一个数字开始每隔一个数字进行删除直到列表开头。 我们不断重复这两步从左到右和从右到左交替进行直到只剩下一个数字。 返回长度为 n 的列表中最后剩下的数字。 示例 输入:
n 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6输出:
6 思路 1. 递归 边界条件 if (n 1)return 1;
if (n 4)return 2; 递归规律 考虑到边界条件n 4. 由于n9和n8第一次消除之后结果完全一样故后面结果都一致。故把所有n都当做偶数处理 if(n % 2 ! 0)n - 1; 解题思路 2. 暴力破解循环 将[1, n]用列表储存循环判断每次划掉一批数或者将这批数置位0当只有一个数输出。 代码 int lastRemaining(int n) { if (n 1) return 1; if (n 4) return 2; if (n % 2 ! 0)n - 1;
if (n % 4 ! 0)return 4 * lastRemaining(n / 4);
elsereturn 4 * lastRemaining(n / 4) - 2; 转载于:https://www.cnblogs.com/wemo/p/10496189.html
