幸运数字问题 —— Java实现

题目描述

小雅同学认为6,8是她的幸运数字,而其他数字均不是,一个幸运数是指在十进制表示下只含有幸运数字的数。给定你一个区间（a,b）a和b之间（其中包括a和b幸）运数的个数。

输入描述

输入两个整数a和b，a的取值范围在1和1000000000之间（其中包括1和1000000000），b的取值范围在a和1000000000之间（其中包括a和1000000000）。

输出描述

返回a和b之间的幸运数个数，如果入参不合法，请输出-1

时间、空间要求

时间限制：1秒空间限制：32768K

示例

输入

1 10

输出

说明

6,8,6666,88888,6668888,68686688均为幸运数字，当a=1，b=10函数返回值为2。

解题思路

首先一看数量级，如果用遍历，然后挨个判断显然是不行的，肯定会超出时间限制，通过数学枚举找规律发现：这就是一个全排列问题，100 - 1000 的幸运数的在1- 10的所有幸运数的基础上跟‘6’和‘8’全排一下组成百位级别的幸运数，以此类推。换句话说，每个区间内的幸运数是已知的（总共2^ i个，i为数的位数，比如个位数（i == 1），就是从‘6’、 ‘8’中选i个数全排列组成一个整数），怎样得到每个区间的幸运数n？就是通过上一个区间迭代得到。这样将一个时间复杂度为O（N）（而且要去判断该数是否是幸运数，这个复杂度系数应该会很大！！！）变为了复杂度O(logN).

代码

package string;

/**
 * 幸运数字
 * 最佳时间43ms，时间复杂度O(logN)
 * 特别注意的是，某几个+=操作，通过寄存器简单的加减指令，可以优化20ms左右，这也是让我更加注重让自己的代码尽量清爽简洁，以便于提升！
 */
import java.util.Scanner;
public class ImprovedLuckyNum {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int INF = 1000000000;
        int[] before = new int[512];
        int[] after = new int[512];
        if (a < 1 || a > INF || a > b) {
            System.out.println(-1);
        } else {
            int sum = 0;
            for (int i = 1; i <= 9; i++) {  
                int length = (int)Math.pow(2, i); // 这个区段有多少个这样的数
                // 判断超过范围即可退出了
                if (Math.pow(10, i) > b) {
                    break;
                }
                if (i == 1) {
                    after[0] = 6;
                    after[1] = 8;
                } else {
                    int b_l = (int)Math.pow(2, i - 1); // 表示before数组的包含有效值的长度
                    for (int k = 0; k < b_l; k++) {
                        after[k] = before[k] * 10 + 6;
                        after[k + b_l] = before[k] * 10 + 8;
                    }
                }
                
                // 寻找合适的数
                for (int j = 0; j < length; j++) {
                    if (after[j] >= a && b >= after[j]) {
                        sum++;
                    }
                    // 记得更新before数组，用于迭代
                    before[j] = after[j];
//                  after[j] = INF + 1;
                }
            }
            System.out.println(sum);
        }
    }
}

运行结果

时间在50ms左右，空间使用在10000k左右，基本上快赶上C/C++的时间了（C/ C++时间大概在30ms左右）
另外：减少一些寄存器指令也可以起到一定的优化效果，10ms左右

最后编辑于：2019.01.17 12:34:33