首页 > 京东笔试,8月27日,Java
头像
Pugu
编辑于 2020-08-28 11:35
+ 关注

京东笔试,8月27日,Java

第一题,求仅由2,3,5组成的数从小到大的第个数是啥()。
为了简化,我们称呼这种数为“漂亮数”。
即是在2、3、5、22、23、25、32、33、35、222、……里面找第“漂亮数”

一句话:转成3进制计算!

思路:
  1. 先得到第个数是几位数的。我们可以很容易想到,位数为“漂亮数”个数为,那么我们就构建一个数组:,分别表示位数为1、2、3……的“漂亮数”个数。我们对求累加和,得到,表示到某一位数位置前面共有多少个“漂亮数”因为,所以长度为6就足够了。然后为了得到位数,我们从头开始一次判断,如果大于,则表示1位数的“漂亮数”个数凑不到,说明。之后继续比较……,直到某个位置有,此时我们就得到了
  2. 再在位数里面找我们要找的数是第几个。就先简短省略了。。。

上代码:
public class Main {

    public static final int N = 7;

    public static final int[] cusums = new int[N];

    public static final int[] mapping = new int[10];

    static {
        int pow = 3;
        cusums[0] = 0;
        cusums[1] = 3;
        for (int i = 2; i < N; i++) {
            pow *= 3;
            cusums[i] = cusums[i - 1] + pow;
        }

        mapping[0] = 2;
        mapping[1] = 3;
        mapping[2] = 5;
    }

    public static int numberN(int n) {

        int k = 0;

        // 求第n个数的位数,记为k,并得到在k位数里面它排在第几个,最多循环7次
        while (n >= cusums[k]) {
            k++;
        }
        n -= cusums[k - 1];


        // 建立k位数的三进制数组
        int[] nums = new int[k];


        // 求在k位里面的第n个排列(表示为三进制数),最多循环7次
        int p = 0;
        while (n > 0) {
            nums[p] = n % 3;
            n = n / 3;
            p++;
        }

        // 将三进制表示的数组转为2,3,5组成的数
        int res = 0;
        for (int i = k - 1; i >= 0; i--) {
            res = res * 10 + mapping[nums[i]];
        }


        return res;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 1000; i++) {
            System.out.println(numberN(i));
        }
    }
}


全部评论

(1) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐