斐波那契

[题目链接](https://www.nowcoder.com/practice/b55722617e204b0ba9d40dd01191fb7b)

思路

给定整数 和数位 ，在前 个斐波那契数中，找出包含数位 次数最多的那个数（若有多个次数相同的，输出最小的）。

斐波那契数列定义如下：

$$

\text{Fib}(n) = \begin{cases} 1 & n = 1, 2 \\ \text{Fib}(n-1) + \text{Fib}(n-2) & n \ge 3 \end{cases}

$$

解法：模拟

直接模拟：

  1. 生成斐波那契数列：从 Fib(1)=1, Fib(2)=1 开始，依次计算到第 项。
  2. 统计每个数中数位 出现的次数：将数转成字符串逐位扫描。
  3. 选取最优答案：遍历时维护当前最大出现次数 maxCnt 及对应的最小数值 ans。若某项的次数严格大于 maxCnt，则更新；若次数相等且该数更小，也更新。

关键细节

  • 题目保证一定存在满足条件的数，因此不需要处理无解情况。
  • 时，Fib(30) = 832040，long long 完全够用，无需大整数。
  • "如果有多个就输出最小的"——斐波那契数列单调不减，但 Fib(1)=Fib(2)=1，因此两个值相同时取第一个即可；遍历时用严格小于来更新最小值即可正确处理。

复杂度分析

  • 时间复杂度：，其中 是最大斐波那契数的十进制位数，对 约为 6 位。
  • 空间复杂度：，存储斐波那契数列。

代码

#include <bits/stdc++.h>
using namespace std;

int countDigit(long long num, int d) {
    string s = to_string(num);
    int cnt = 0;
    for (char c : s) {
        if (c - '0' == d) cnt++;
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, d;
    cin >> n >> d;

    vector<long long> fib;
    if (n >= 1) fib.push_back(1);
    if (n >= 2) fib.push_back(1);
    for (int i = 2; i < n; i++) {
        fib.push_back(fib[i-1] + fib[i-2]);
    }

    int maxCnt = -1;
    long long ans = -1;
    for (long long f : fib) {
        int cnt = countDigit(f, d);
        if (cnt > maxCnt || (cnt == maxCnt && f < ans)) {
            maxCnt = cnt;
            ans = f;
        }
    }

    cout << ans << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int countDigit(long num, int d) {
        String s = Long.toString(num);
        int cnt = 0;
        for (char c : s.toCharArray()) {
            if (c - '0' == d) cnt++;
        }
        return cnt;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();

        List<Long> fib = new ArrayList<>();
        if (n >= 1) fib.add(1L);
        if (n >= 2) fib.add(1L);
        for (int i = 2; i < n; i++) {
            fib.add(fib.get(i-1) + fib.get(i-2));
        }

        int maxCnt = -1;
        long ans = -1;
        for (long f : fib) {
            int cnt = countDigit(f, d);
            if (cnt > maxCnt || (cnt == maxCnt && f < ans)) {
                maxCnt = cnt;
                ans = f;
            }
        }

        System.out.println(ans);
    }
}