题目链接

幸运数字

题目描述

一个“幸运数”是指在十进制表示下，只含有数字 6 和 8 的正整数。

给定一个区间 ，求这个区间内（包含 和 ）幸运数的个数。

约束：。

解题思路

本题要求在高达 的区间内计数特定模式的数字。如果直接遍历区间内的每一个数再判断其是否为幸运数，时间复杂度会非常高，无法通过。

正确的思路是，幸运数的结构非常特殊，数量也很稀疏。我们可以不“检查”，而是“生成”所有符合条件的幸运数，然后再看有多少个落在给定区间内。

算法流程：

  1. 生成所有幸运数：

    • 我们可以使用广度优先搜索 (BFS) 的思想，通过队列来生成所有小于等于 的幸运数。

    • 初始状态：队列中放入第一批幸运数，即 6 和 8。

    • 扩展过程：

      a. 创建一个列表 lucky_numbers 用来存储所有生成的幸运数。

      b. 当队列不为空时，从队首取出一个数 current。

      c. 将 current 添加到 lucky_numbers 列表中。

      d. 从 current 扩展出两个新的数：current * 10 + 6 和 current * 10 + 8。

      e. 如果新生成的数不超过上限 ()，就将其加入队列末尾。

    • 这个过程会按从小到大的顺序生成所有幸运数。

  2. 计数：

    • 当生成过程结束后，lucky_numbers 列表就包含了所有小于等于 的幸运数。

    • 读入区间的左右边界 和 。

    • 遍历 lucky_numbers 列表，统计其中满足 a <= num <= b 的数字 num 的个数。

  3. 输出结果：

    • 输出最终的统计个数。

    • 关于题目中提到的“非法入参”，根据约束条件 ，输入的参数总是合法的，所以无需特殊处理。

代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
using ll = long long;

vector<ll> lucky_numbers;

void generate_lucky_numbers() {
    queue<ll> q;
    q.push(6);
    q.push(8);
    lucky_numbers.push_back(6);
    lucky_numbers.push_back(8);

    while (!q.empty()) {
        ll current = q.front();
        q.pop();

        ll next6 = current * 10 + 6;
        if (next6 <= 1000000000) {
            lucky_numbers.push_back(next6);
            q.push(next6);
        }

        ll next8 = current * 10 + 8;
        if (next8 <= 1000000000) {
            lucky_numbers.push_back(next8);
            q.push(next8);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    generate_lucky_numbers();
    
    int a, b;
    while (cin >> a >> b) {
        int count = 0;
        for (ll num : lucky_numbers) {
            if (num >= a && num <= b) {
                count++;
            }
        }
        cout << count << endl;
    }

    return 0;
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static ArrayList<Long> luckyNumbers = new ArrayList<>();

    public static void generateLuckyNumbers() {
        Queue<Long> queue = new LinkedList<>();
        queue.add(6L);
        queue.add(8L);
        luckyNumbers.add(6L);
        luckyNumbers.add(8L);

        while (!queue.isEmpty()) {
            long current = queue.poll();

            long next6 = current * 10 + 6;
            if (next6 <= 1000000000L) {
                luckyNumbers.add(next6);
                queue.add(next6);
            }

            long next8 = current * 10 + 8;
            if (next8 <= 1000000000L) {
                luckyNumbers.add(next8);
                queue.add(next8);
            }
        }
    }

    public static void main(String[] args) {
        generateLuckyNumbers();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            int count = 0;
            for (long num : luckyNumbers) {
                if (num >= a && num <= b) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }
}

import sys
from collections import deque

def generate_lucky_numbers():
    """
    生成所有小于等于 10^9 的幸运数
    """
    lucky_nums = []
    q = deque([6, 8])
    lucky_nums.extend([6, 8])

    while q:
        current = q.popleft()
        
        next6 = current * 10 + 6
        if next6 <= 1000000000:
            lucky_nums.append(next6)
            q.append(next6)
            
        next8 = current * 10 + 8
        if next8 <= 1000000000:
            lucky_nums.append(next8)
            q.append(next8)
            
    return lucky_nums

LUCKY_NUMBERS = generate_lucky_numbers()

def solve():
    for line in sys.stdin:
        try:
            a, b = map(int, line.strip().split())
            count = 0
            for num in LUCKY_NUMBERS:
                if a <= num <= b:
                    count += 1
            print(count)
        except (IOError, ValueError):
            continue

solve()

算法及复杂度

  • 算法：广度优先搜索 (BFS) 生成 + 线性扫描

  • 时间复杂度：，其中 是小于等于 的幸运数的总数。 是一个固定的、与输入 无关的较小常数（）。生成所有幸运数的时间和后续扫描计数的时间都与 成正比，因此总时间复杂度可以认为是常数时间 。

  • 空间复杂度：。需要一个列表来存储所有生成的幸运数。