51nod--1087 1 10 100 1000

题目描述

题目来源： Ural 1209
基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注
1,10,100,1000…组成序列1101001000…，求这个序列的第N位是0还是1。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行1个数N。（1 <= N <= 10^9)
Output
共T行，如果该位是0，输出0，如果该位是1，输出1。
Input示例
3
1
2
3
Output示例
1
1
0

解题思想

/*
找规律+打表
例如：1101001000
map[i]表示第i个1所在的位置(下标从0开始)，
map[0] = 1;
map[1] = 2;
map[2] = 4;
map[3] = 7;
不难发现：规律已经出现了：map[i] = map[i-1] + i;(i>0)
map[0] = 1;(i==0)
总体解题思路：t个数据，先求出其中的最大值为max，然后开辟一个打表数组map[sqrt(max*2)],为甚吗开
这么大？假如现在n的长度为1e9，
第一个是
序号 a1 1 长度 1
a2 10 2
a3 100 3
an … n
总长度=n(n+1)/2 = max;
n个序号有n个1，map数组只是存每个1的位置，即1 的个数，但是题目给的是总长度，所以我们开的数组大小
就是求n，n = sqrt(max*2)-1
最后就是打表，查表，输出
*/

代码

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[] a = new int[T];
        int max = Integer.MIN_VALUE;
        for(int i=0; i<T; ++i){
           a[i] = sc.nextInt();
           if(a[i] > max)
              max = a[i];
        }
        int Max =(int) Math.sqrt(max*2);
        int[] map = new int[Max+1];
        //打表
        map[0] = 1;
        for(int i=1; i<=Max; ++i)
            map[i] = map[i-1] + i;
            //查表
        for(int i=0; i<T; ++i){
            if(find(a[i],map))
               System.out.println("1");
            else
               System.out.println("0");
        }
    }
    //二分查找
    public static boolean find(int k, int[] map){
        //在有序数组map里面查找k
        int left = 0;
        int right = map.length-1;
        int mid = -1;
        while(left <= right){
            mid = left + (right-left)/2;
            if(k < map[mid]){
                right = mid-1;
            }else if(map[mid] < k){
                left = mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
}