首页 > 试题广场 >

奇数位丢弃

[编程题]奇数位丢弃
  • 热度指数：14118 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
对于一个由 0..n 的所有数按升序组成的序列，我们要进行一些筛选，每次我们丢弃去当前所有数字中第奇数位个的数。重复这一过程直到最后剩下一个数。请求出最后剩下的数字。

数据范围：  ，本题有多组输入

输入描述:
每组数据一行一个数字，为题目中的n(n小于等于1000)。


输出描述:
一行输出最后剩下的数字。
示例1

输入

500

输出

255
算法知识视频讲解
添加回答
Java
Dandaalayyaa头像 Dandaalayyaa
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) { 
            int n = in.nextInt();
            System.out.println((int)(Math.pow(2,Math.floor(Math.log(n)/Math.log(2)))-1));
        }
    }
}
发表于 2023-05-18 03:51:12 回复(0)
Java
牛客773335897号头像 牛客773335897号 
//數學規律
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in) ;
		while(sc.hasNext()){
        int n=sc.nextInt();
		int m=0;
		int sum=0;
		while(n>1) 
        {
			n=n/2;
			m++;
			sum=sum+(int)Math.pow(2, m-1);
		}
		System.out.println(sum);
        }
    }
}

发表于 2021-08-12 21:06:23 回复(0)
Java
牛客49495154号头像 牛客49495154号 
  public static void main(String[] args) { int size = 5000;
        LinkedList<Integer> integers = intToLList(size);
        LinkedList<Integer> integers2 = new LinkedList<>(); while (integers.size() != 1) { for (int i = 0; i < integers.size(); i++) { if ((i+1)%2 != 0) {
                    integers2.add(integers.get(i));
                }
            } for (Integer integer : integers2) {
                integers.remove(integer);
            }
        }
        System.out.println(integers.get(0));
    } private static LinkedList<Integer> intToLList(int n) {
        LinkedList<Integer> integers = new LinkedList<>(); for (int i = 0; i <= n; i++) {
            integers.add(i);
        } return integers;
    }
发表于 2020-09-19 22:38:27 回复(0)
Java
京东内推君头像 京东内推君

思路：数学推导

以 n = 37 为例，即 0 ~ 37

  • 第一次删除：time = 1,开始位置 base = 0,每次位置新增为 up=2，删除的值为：
    0 2 4 6 8 10 12 14 16 18 20 22 24 26 28...
  • 第二次删除：time = 2,开始位置 base = 1,每次位置新增为 up = 4，删除的值为：
    1 5 9 13 17 21 25 29...
  • 第三次删除：time = 3,开始位置 base = 3,每次位置新增 up = 8,删除的值为：
    3 11 19 27 35
    ..... 
import java.util.Scanner;

/**
 * @author GJXAIOU
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int inputValue = scanner.nextInt();
            if (inputValue == 0) {
                System.out.println(0);
            }
            int[] values = new int[inputValue + 1];
            for (int i = 0; i < values.length; i++) {
                values[i] = i;
            }

            // time 表示第几次运行删除
            int time = 1;
            // 每次删除的第一个数
            int base = 0;
            // 每次删除时候递增的间隔
            int up = 2;
            // 还有多少值没有检查替换
            int left = values.length;
            while (left > 1) {
                for (int i = base; i < values.length; i += up) {
                    values[i] = 0;
                    left--;
                }
                base = (int) (base + Math.pow(2, time - 1));
                // 进行下一次
                time++;
                // 每次运行删除间隔都是 2 的倍数
                up *= 2;
            }

            for (int i = 0; i < values.length; i++) {
                if (values[i] != 0) {
                    System.out.println(values[i]);
                }
            }
        }
    }
}
发表于 2020-06-23 16:33:19 回复(0)
Java
hshorse168头像 hshorse168 
import java.util.*;

public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<=n;i++)
                list.add(i);
            while(list.size() > 1){
                for(int i=0; i < list.size();i++)
                    list.remove(i);
            }
            System.out.println(list.get(0));
        }
    }
}

发表于 2019-04-16 20:22:29 回复(1)
Java
若相熙头像 若相熙 
import java.util.Scanner;
// 找规律每次删除后的第一个数为2^times  - 1然后算出 times 即可
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int total = n + 1;
            int times = 0;
            while (total != 1) {
                total /= 2;
                times++;
            }
            System.out.println(String.format("%.0f", Math.pow(2, times) - 1));
        }


    }
}


发表于 2019-04-08 14:27:48 回复(0)
Java
blingblingbling2018010612头像 blingblingbling2018010612 
//一开始以为是约瑟夫环问题，后来自己试了连个例子，不太像。
//每次去除奇数位只留下原来的个数的一半，m次后只剩下一个数
//假设将剩下的数看做1，则在原来的序列中他是2^m，m=logn
//不知道说的明白不，贴出来给大家一个思路吧




import java.util.Scanner;

public class Main {

    public static void main(String[] args){

        Scanner in =new Scanner(System.in);

        while(in.hasNext()){

            int n=in.nextInt();

            int m = (int)(Math.log(n)/Math.log(2));

            System.out.println((int)(Math.pow(2,m))-1);

        }

    }

}

发表于 2018-04-19 10:57:23 回复(0)
Java
no_and_life头像 no_and_life 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        while(input.hasNext()) {
            int n=input.nextInt();
            int len=0;
            while(n>1) {
                n=n>>1;
                len++;
            }
            System.out.println((1<<len)-1);
        }
        input.close();
    }
}
编辑于 2018-04-13 00:10:32 回复(0)
Java
dong1234头像 dong1234 
求大神解疑惑。本地运行答案都对，为什么在这里却没有输出。 import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double tmp = Math.log(n)/Math.log(2);
        double count = Math.floor(tmp);
		System.out.println((int)Math.pow(2,count)-1);
        
    }
}


发表于 2017-07-26 10:38:43 回复(0)
Java
珍爱生命，远离加班头像 珍爱生命，远离加班
public class Main{
    
    
    public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String str = "";
while ((str = bf.readLine()) != null) {
int n = Integer.valueOf(str);
System.out.println(deleteAllOdd02(n));
}
bf.close();

}
    
    
    public static int deleteAllOdd02(int n) {
int i = 1;
while (true) {

if (Math.pow(2, i) - 1 > n) {
break;
}
i++;
}
return (int) (Math.pow(2, i - 1) - 1);

}
    
}
发表于 2017-07-25 18:20:16 回复(0)
Java
牛客2796735号头像 牛客2796735号 
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int n = in.nextInt();
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i <= n; i++)
                list.add(i);
            while (list.size() > 1){
                for (int j = 0; j < list.size(); j++)
                    list.remove(j);
            }
            System.out.println(list.get(0));
        }
    }
}
发表于 2017-07-04 15:29:00 回复(0)
Java
华仔17头像 华仔17
import java.util.Scanner;

public class JiShu{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
String str = sc.nextLine();
double n = Double.parseDouble(str);
int m = (int)(Math.log(n)/Math.log(2));
System.out.println((int)(Math.pow(2,m)-1));

}
}
}
发表于 2017-03-12 18:59:04 回复(0)
Java
java的神秘男友script头像 java的神秘男友script 
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        while(in.hasNext()){
            int n =in.nextInt();
            int num=0;
            int s=1;
            for(int i=0;num<n;i++ ){
                num=2*s-2;
                s*=2;
            }
            System.out.println(num/2);
        }
    }
}


学会找规律
发表于 2017-03-09 01:09:29 回复(0)
Java
王小叶头像 王小叶 
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<=n;i++){
                list.add(i);
            }
            while(list.size()>1){
                for(int i=0;i<list.size();i=i+1){//注意不是i+2，因为删除了右边的前移
               		list.remove(i);
                }
            }
            System.out.println(list.get(0));
        }
    }
}

编辑于 2017-03-06 18:58:02 回复(0)
Java
C r 7头像 C r 7 
用一个辅助的数组，1代表死，2代表活。不断地挑出筛选过的数组，不断递归。 import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n = in.nextInt();
			int[] arr = new int[n+1];
			//初始化数组
			for(int i=0;i<n+1;i++){
				arr[i] = i;
			}
			while(arr.length!=1){
				arr=getNewArr(arr);
			}
			System.out.println(arr[0]);
		}
	}
	public static int[] getNewArr(int[] arr){
		if(arr == null){
			return null;
		}
		//标志数组，初始化为0，1为死，2为活
		int[] vice = new int[arr.length];
		int[] result = new int[arr.length/2];
		for(int i=0;i<vice.length;i++){
			//如果是双数位，令他死置为1
			if(i%2==0){
				vice[i] = 1;
			}else{
				vice[i] = 2;
			}
		}
		//result数组的标志
		int num = 0;
		for(int i=0;i<arr.length;i++){
			if(vice[i] == 2){
				result[num++] = arr[i];
			}
		}
		
		return result;
	}
}


发表于 2016-09-13 16:13:17 回复(0)
Java
詆調壹點头像 詆調壹點 
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			List<Integer> list = new ArrayList<Integer>();
			for (int i = 0; i <= n; i ++ )
				list.add(i);
			while (list.size() != 1) {
				// 从0开始list移除一次,i再加一次,i始终指向奇数位
				for (int i = 0; i < list.size(); i = i + 1)
					list.remove(i);
			}
			System.out.println(list.get(0));
		}
	}
}

编辑于 2017-03-20 12:57:53 回复(13)
Java
writeless头像 writeless
import java.util.Scanner;
public class Main {
    public  static void  main(String[] a){
        Scanner s=new Scanner(System.in);
         while (s.hasNextInt()){ 
        int n=s.nextInt();
        int k=1;
        while(n>0){
            n/=2;
            k*=2;
        }
        System.out.println(k/2-1);
       } 
    }
}
发表于 2016-08-13 15:04:44 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 数组 安卓工程师 运维工程师 链表 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 2016 美团 模拟 测试开发工程师 大数据开发工程师 Java工程师
来自：美团2016研发工程师...
难度：
21条回答 28610浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号