2024京东春招3.2笔试真题解析

第三题是个sql题，就不贴了，整体难度不大，第二题需要学一下欧拉筛/线性筛

T1 字符串查找

塔子哥是一个善于寻找快乐的人。

对于一个字符串，塔子哥认为它是“快乐的”当且仅当其包含以下任意一个连续子串:

• cheerful
• glad
• happy
• pleased

对于输入的字符串，请你判断这个字符串是否是“快乐的”。

输入描述

本题中，每个测试点包含多组测试数据。

第一行一个整数 ，表示数据的组数。

对于每组数据:

输入仅一行，包含一个字符串。

数据保证字符串的长度不超过10000，且仅由小写字母构成。

输出描述

对于每组数据，如果 是“快乐的”，请输出Yes，否则请输出No。

示例1

输入

2
happydays
saddays

输出

Yes
No

思路：枚举

由于字符串的长度不超过，因此我们可以枚举每一个位置，来判断以开头的子串是否可以构成满足题目条件的字符串之一，如果可以，则输出Yes，否则循环遍历完之后，输出No

Java

import java.util.*;
// 注意类名必须为Main
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        sc.nextLine();
        String[] happyList={"cheerful","glad","happy","pleased"};
        for(int i=0;i<num;i++){
            String tmpString=sc.nextLine();
            boolean flag=false;
            for(int j=0;j<tmpString.length();j++){
                for(String tmpHappy:happyList){
                    if(j+tmpHappy.length()<tmpString.length()){
                        if(tmpHappy.equals(tmpString.substring(j,j+tmpHappy.length()))){
                            flag=true;
                            break;
                        }
                    }
                }
                if(flag){
                    break;
                }
            }
            if(flag){
                System.out.println("Yes");
            }
            else{
                System.out.println("No");
            }
        }
    }
}

Python

t = int(input())
arr = ["cheerful", "glad", "happy","pleased"]
for _ in range(t):
    s = input()
    flag = False
    for i in arr:
        if i in s:
            flag = True
            break
    if flag:
        print("Yes")
    else:
        print("No")

T2 素数三元组

塔子哥希望你找出满足,且A,B,C均小于等于N的素数三元组（A,B,C)的数量。

素数三元组：A,B,C都是素数。

输入描述

输入的第一行给出正整数N。

输出描述

一行中输出答案。

示例1

输入

8

输出

3

说明

2,2,2

7,2,3

2,7,3

思路：筛质数

首先，我们需要筛选出以内的所有素数，其实总数量约为左右

然后问题就变成了两数之和的变型，但是我们如果暴力枚举,总复杂度为，也会超时

因此可以考虑枚举，对应的复杂度应为

我们先枚举,再去枚举，然后把所有的素数存入哈希表中，因此只需要判断哈希表中是否有B即可

整体时间复杂度为，其中，不会超时

Java

import java.util.*;
class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        List<Integer> primes = new ArrayList<>();
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }
        isPrime[0] = isPrime[1] = false;
        
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                primes.add(i);
                for (int j = 2 * i; j <= n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        Set<Integer> s = new HashSet<>(primes);
        int cnt = 0;
        for (int i = 0; i < primes.size(); i++) {
            int x = primes.get(i) * primes.get(i);
            if (x > primes.get(primes.size() - 1) * 2) {
                break;
            }
            for (int j = 0; j < primes.size(); j++) {
                int y = x - primes.get(j);
                if (s.contains(y)) {
                    cnt++;
                }
            }
        }
        
        System.out.println(cnt/2+1);
    }
}

Python

n = int(input())
primes = []
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
for i in range(2, n+1):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, n+1, i):
            is_prime[j] = False
s = set(primes)
cnt = 0
for i in range(len(primes)):
    x = primes[i] * primes[i]
    if x > primes[-1] * 2:
        break
    for j in range(len(primes)):
        y = x - primes[j]
        if y in s:
            cnt += 1
print(cnt)