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)
