笔试时间：2024年05月13日

历史笔试传送门：2023秋招笔试合集

第一题

题目：double数

定义double数是位数为偶数且前一半和后一半完全相同的正整数，如: 1212,11,1010 是double数，而313,25,990不是double数。牛牛想知道 [1,n] 内有多少double数。函数传入一个正整数 n ,返回 [1,n] 内double数的个数。

数据范围：1<=n<=10^12

样例输入一

25

样例输出一

2

说明

[1,25] 内的double数有: 11,22，因此答案为2。

样例输入二

2

样例输出二

0

说明

[1,2]内没有double数。

样例输入三

3154354

样例输出三

999

参考题解

对于每一个偶数位长度（如2位、4位、6位等），生成可能的double数。例如：

对于2位数字：生成如11, 22, ..., 99。

对于4位数字：以前两位从10到99，重复它形成如1010, 1111, ..., 9999的数。

我们只需要枚举长度为6的数字即可，所以复杂度是不会爆的。

C++：[此代码未进行大量数据的测试，仅供参考]

class Solution {
public:
    int DoubleNumber(int n) {
        int cnt = 0;
        int i = 1;
        while (true) {
            int st = std::pow(10, i - 1);
            int end = std::pow(10, i) - 1;
            for (int half_num = st; half_num <= end; ++half_num) {
                std::string str_half = std::to_string(half_num);
                std::string str_double = str_half + str_half;
                int double_num = std::stoi(str_double);
                if (double_num > n) {
                    return cnt;
                }
                cnt++;
            }
            i++;
        }

        return cnt;
    }
};

Java：[此代码未进行大量数据的测试，仅供参考]

public class Solution {
    public int DoubleNumber(int n) {
        int cnt = 0;
        int i = 1;
        while (true) {
            int st = (int) Math.pow(10, i - 1);
            int end = (int) Math.pow(10, i) - 1;
            for (int half_num = st; half_num <= end; half_num++) {
                String str_half = Integer.toString(half_num);
                String str_double = str_half + str_half;
                int double_num = Integer.parseInt(str_double);
                if (double_num > n) {
                    return cnt;
                }
                cnt++;
            }
            i++;
        }

        // 这个return理论上是不会被执行的，但为了代码完整性保留
        return cnt;
    }

Python：[此代码未进行大量数据的测试，仅供参考]

class Solution:
    def DoubleNumber(self, n):
        cnt = 0
        i = 1
        while True:
            st = 10 ** (i - 1)
            end = 10 ** i - 1
            for half_num in range(st, end + 1):
                double = int(str(half_num) + str(half_num))
                if double > n:
                    return cnt
                cnt