华为2016校招笔试试题（数列删数后剩下的数）

华为2016校招笔试试题一——删数

题目来自牛客网，感谢！

给定数字n，在按序排列的0~n-1中从0起每隔2个数删除1个数，到末尾时循环至开头继续，求最后剩下的数。

输入格式

若干行，每行输入一个n。

输出格式

每行输出对应剩下的数。

输入范例

8

输出范例

6

基础思路以队列存储数据，队首每3个数将2个数接回队尾，删除另一个数，直到队列长度为1为止。

 public static int delMethod1(int n) { Queue<Integer> q = new LinkedList<Integer>(); for (int i = 0; i < n; i++) q.add(i); for (int i = 0; q.size() > 1; i = (i + 1) % 3) { int temp = q.poll(); if (i == 2) continue; q.add(temp); } return q.poll(); } 

如果从数学的角度上考虑这一问题，无妨记$D(·)$为删数操作，$I_n$为$n$个数操作后所余下的数，显然有$I_1=0$。
由于每次删数操作均使数减少一个，因此$D(I_n)$与$I_{n-1}$间存在对应关系。以$n>3$的情况为例，$D(I_n)$跳过$0$、$1$，删去$2$。若此时将$0$、$1$补至队尾，则构成$D(I_n)$与$I_{n-1}$的对应关系：

0	1	2	…	n-3	n-2
3	4	5	…	0	1

从而可得到关系式$I_n=(I_{n-1}+3)\mod n$，简记为$I_n=(I_{n-1}+3)|_{(n)}$。
故$I_n=(((I_1+3)|_{(1)}+3)|_{(2)}+…)|_{(n)}$

此时便有

 public static int delMethod2(int n) { int x = 0; for (int i = 1; i <= n; i++) x = (x + 3) % i; return x; } 

我的代码实现

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; public class DelNum { public static void main(String[] args) { Scanner sc = new Scanner(System.in); List<Integer> list = new ArrayList<Integer>(); String s = null; while (sc.hasNextLine() && !((s = sc.nextLine()).equals(""))) list.add(Integer.parseInt(s)); sc.close(); for (int n : list) System.out.println(delMethod2(n)); } public static int delMethod1(int n) { Queue<Integer> q = new LinkedList<Integer>(); for (int i = 0; i < n; i++) q.add(i); for (int i = 0; q.size() > 1; i = (i + 1) % 3) { int temp = q.poll(); if (i == 2) continue; q.add(temp); } return q.poll(); } public static int delMethod2(int n) { int x = 0; for (int i = 1; i <= n; i++) x = (x + 3) % i; return x; } } 

本文地址：https://blog.csdn.net/Uranum/article/details/107892225