03-28 11:16 已编辑广东技术师范大学运营发布于北京

关注

笔试真题解析2 | 最近刷了一套京东笔试真题，感觉还不错

题目来源：2024年京东春招技术通用岗位第一批笔试

1. 快乐字符串

题目描述

题目链接：快乐字符串

判断一个字符串是否包含以下任意一个连续子串："cheerful"、"glad"、"happy"、"pleased"。
如果包含，则这个字符串被认为是"快乐的"。

解题思路

这是一个简单的字符串匹配问题，我们可以：

对每个输入字符串，检查是否包含任意一个目标子串
使用字符串的find函数或者暴力匹配都可以解决

代码实现

#include <iostream>
#include <string>
using namespace std;

bool isHappy(string& s) {
    string happy_words[] = {"cheerful", "glad", "happy", "pleased"};
    for (const string& word : happy_words) {
        if (s.find(word) != string::npos) {
            return true;
        }
    }
    return false;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        cout << (isHappy(s) ? "Yes" : "No") << endl;
    }
    return 0;
}

复杂度分析

时间复杂度： $O(n \cdot m)$ ，其中 $n$ 是输入字符串长度， $m$ 是所有快乐词的总长度
空间复杂度： $O(1)$ ，只使用了常数额外空间

2. 特殊的科学计数法

题目描述

题目链接：特殊的科学计数法

将一个正整数转换为科学计数法形式 $(a.b * 10^c)$ ，其中数值部分需要四舍五入到小数点后一位。

解题思路

计算数字的位数，确定指数 $c$
提取首位和第二位数字，进行四舍五入处理
格式化输出结果

代码实现

#include <iostream>
#include <string>
using namespace std;

string to_scientific(string s) {
    int length = s.length();
    
    // 获取第一个数字
    int first = s[0] - '0';
    
    // 获取第二个数字并四舍五入
    int second = 0;
    if (length > 1) {
        second = s[1] - '0';
        if (length > 2 && (s[2] - '0') >= 5) {
            second++;
            if (second == 10) {
                first++;
                second = 0;
                if (first == 10) {
                    first = 1;
                    second = 0;
                    length++; // 位数增加1
                }
            }
        }
    }
    
    return to_string(first) + "." + to_string(second) + "*10^" + to_string(length-1);
}

int main() {
    string n;
    cin >> n;
    cout << to_scientific(n) << endl;
    return 0;
}

复杂度分析

时间复杂度： $O(\log n)$ ，其中 $n$ 是输入的数字
空间复杂度： $O(\log n)$ ，用于存储数字的字符串表示

3. 素数对

题目描述

题目链接：素数对

给定一个正整数 $n$ ，找出所有满足以下条件的三元组 $(p1,p2,p3)$ 的个数：

$p1$ 、 $p2$ 、 $p3$ 均为质数
$1 \leq p1,p2,p3 \leq n$
$p1+p2=p3^2$

解题思路

首先使用埃氏筛法筛选出不超过 $n$ 的所有素数
枚举每个素数 $p3$ ，计算其平方 $p3^2$
对于每个 $p3$ ，枚举另一个素数 $p1$ ，然后计算 $p2 = p3^2 - p1$
如果 $p2$ 也是素数且在范围内，就找到了一组合法解
优化：
- 使用静态数组预处理素数，避免动态内存分配
- 当 $p3^2 - p1$ 超出范围时可以提前终止内层循环

代码实现

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
static const int MAX = 500005;
bool isPrime[MAX];

void makePrime() {
    for (int i = 0; i < MAX; i++)
        isPrime[i] = true;

    isPrime[0] = false;
    isPrime[1] = false;

    int n = sqrt(MAX);
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i])
            continue;
        for (int j = i * 2; j < MAX; j += i)
            isPrime[j] = false;
    }
}

int main() {
    int N;
    cin >> N;
    vector<ll> p;
    makePrime();
    for (int i = 2; i <= N; i++) {
        if (isPrime[i])
            p.push_back(i);
    }
    int ans = 0;
    for (int i = 0; i < p.size(); i++) {
        for (int j = 0; j < p.size(); j++) {
            ll t = p[i] * p[i] - p[j];
            if (t < 1 || t > N)
                break;
            if (isPrime[t]) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

时间复杂度： $O(p^2)$ ，其中 $p$ 是不超过 $n$ 的素数个数。对于每个素数 $p3$ ，我们需要枚举所有可能的 $p1$
空间复杂度： $O(\sqrt{MAX})$ ，其中 $MAX$ 是预定义的最大值500005。主要用于存储素数筛选结果

4. 循环节

题目描述

题目链接：循环节

计算 $1/n$ 的小数表示中循环节的长度。

解题思路

模拟长除法的过程
使用哈希表记录余数出现的位置
当余数重复出现时，就找到了循环节

代码实现

#include <bits/stdc++.h>
#define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define all(x) (x).begin(),(x).end()
#define inf 1e18

using namespace std;

typedef long long llint;
typedef long long ll;
typedef pair<llint, llint> P;

ll T;
ll n, mod;

llint modpow(llint a, llint n)
{
    if(n == 0) return 1;
    if(n % 2){
        return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
    }
    else{
        return modpow((a*a)%mod, n/2) % mod;
    }
}

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

    cin >> T;
    while(T--){
        cin >> n;

        while(n % 5 == 0) n /= 5;
        while(n % 2 == 0) n /= 2;

        if(n == 1){
            cout << 1 << endl;
            continue;
        }

        int res = n, t = n;
        for(int i = 2; i*i <= t; i++){
            if(t % i == 0){
                res = res / i * (i-1);
                for(; t % i == 0; t /= i);
            }
        }
        if(t != 1) res = res / t * (t-1);

        ll ans = inf; mod = n;
        for(llint i = 1; i*i <= n; i++){
            if(res % i == 0){
                if(modpow(10, i) == 1) chmin(ans, i);
                if(modpow(10, res/i) == 1) chmin(ans, res/i);
            }
        }
        cout << ans << endl;
    }

    return 0;
}