【春招笔试】2024-05-07-阿里文娱-三语言题解
大家好这里是清隆学长 ，一枚热爱算法的程序员
✨ 本系列打算持续跟新阿里文娱近期的春秋招笔试题汇总～
感谢大家的订阅➕ 和 喜欢
✨ 笔试合集传送们 -> 春秋招笔试合集
01.时间复杂度判断
题目描述
K小姐刚开始学习编程时，经常会遇到时间超限的问题。她希望你能帮忙判断她的程序是否会超时。
已知计算机每秒可以执行 次计算。如果程序的计算次数大于等于 ，则判定为超时，输出 TLE；否则，请求出最内层循环中代码的计算次数。
输入格式
第一行包含一个正整数 （），表示嵌套 for 循环的层数。
第二行包含 个空格分隔的正整数 （），表示每个 for 循环的重复次数。
输出格式
如果最内层循环的计算次数大于等于 ，则输出 TLE，否则输出最内层循环的计算次数。
样例输入
3
1000 1000 1000
样例输出
TLE
数据范围
题解
本题考察了程序的时间复杂度计算。对于嵌套的 for 循环，最内层循环的计算次数等于所有外层循环的重复次数的乘积。
我们可以先读入循环层数 以及每层循环的重复次数 ，然后将所有 相乘，即可得到最内层循环的计算次数。如果计算次数大于等于 ，则输出 TLE，否则输出计算次数即可。
时间复杂度为 ，空间复杂度为 。
参考代码
- Python
N = int(input())
M = list(map(int, input().split()))
ans = 1
for x in M:
ans *= x
if ans >= 10**8:
print("TLE")
exit(0)
if ans >= 10**8:
print("TLE")
else:
print(ans)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int[] M = new int[N];
for (int i = 0; i < N; i++) {
M[i] = sc.nextInt();
}
long ans = 1;
for (int x : M) {
ans *= x;
if (ans >= 1e8)
{
System.out.println("TLE");
System.exit(0);
}
}
if (ans >= 1e8) {
System.out.println("TLE");
} else {
System.out.println(ans);
}
}
}
- Cpp
#include <iostream>
using namespace std;
int main() {
int N;
cin >> N;
long long ans = 1;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
ans *= x;
if(ans >= 1e8)
return cout << "TLE\n", 0;
}
if (ans >= 1e8) {
cout << "TLE" << endl;
} else {
cout << ans << endl;
}
return 0;
}
02.K小姐的阶乘中的零计数
问题描述
K小姐在做数学作业时，遇到了一个关于阶乘数字的问题。她需要找出一个数 的阶乘中所有包含的数字0的总数。这并不仅仅是末尾的0，而是整个数中所有出现的0。
输入格式
输入包含一个整数 。
输出格式
输出一个整数，表示 的阶乘中数字0的总数。
样例输入
7
样例输出
2
数据范围
题解
计算一个正整数 的阶乘，并统计阶乘结果中所有0的数量。考虑到 的最大值为15，计算阶乘是可行的，因为 只有1307674368000
参考代码
- Python
import sys
input = lambda: sys.stdin.readline().strip()
n = int(input())
factorial = 1
for i in range(1, n + 1):
factorial *= i
count_of_zeros = str(factorial).count('0')
print(count_of_zeros)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long factorial = 1;
for (int i = 1; i <= n; i++) {
factorial *= i;
}
String factorialStr = Long.toString(factorial);
int countOfZeros = 0;
for (char c : factorialStr.toCharArray()) {
if (c == '0') {
countOfZeros++;
}
}
System.out.println(countOfZeros);
scanner.close();
}
}
- Cpp
#include <iostream>
int main() {
int n;
std::cin >> n;
long long factorial = 1;
for (int i = 1; i <= n; i++) {
factorial *= i;
}
std::string factorialStr = std::to_string(factorial);
int countOfZeros = 0;
for (char c : factorialStr) {
if (c == '0') {
countOfZeros++;
}
}
std::cout << countOfZeros << std::endl;
return 0;
}
03.神奇数字
题目描述
LYA 定义了一个神奇数字 ，其要满足 ，其中 都为质数。于是 LYA 想知道在 中有多少个这样的神奇数字呢，请你告诉 LYA。
输入格式
第一行为 ，表示有 组数据。
接下来有 行，每行为一个整数 。
输出格式
输出为 行，每行为一组答案。
样例输入
3
28
33
47
样例输出
1
2
3
数据范围
题解
本题可以使用预处理 + 二分查找的方法来解决。
首先，预处理出所有可能的神奇数字。由于 都是质数，我们可以先用埃氏筛法筛选出 内的所有质数，存入数组 中。
然后，我们使用三重循环枚举所有可能的 ，计算出对应的神奇数字 ，并将其加入到集合 中。注意，为了避免重复计算，我们需要保证 ，虽然有三重循环，但有大量剪枝，总计算次数在 左右。
接下来，将集合 中的元素转移到数组 中，并对 进行排序。
最后，对于每个询问 ，我们使用二分查找在数组 中查找不超过 的元素个数，即为答案。
时间复杂度 ，空间复杂度 。
参考代码
- Python
import sys
input = lambda: sys.stdin.readline().strip()
import bisect
prime = []
N = 10 ** 6 + 1
st = [False] * N
for i in range(2, N):
if not st[i]:
prime.append(i)
for j in range(i, N, i):
st[j] = True
v = []
s = set()
n = len(prime)
for a in prime:
if a * a >= N:
break
for b in prime:
if a * a + b ** 3 >= N:
break
for c in prime:
val = a ** 2 + b ** 3 + c ** 4
if val >= N:
break
s.add(val)
v = sorted(s)
t = int(input())
for _ in range(t):
x = int(input())
idx = bisect.bisect_right(v, x)
print(idx)
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
int N = 1000001;
boolean[] st = new boolean[N];
List<Integer> prime = new ArrayList<>();
for (int i = 2; i < N; i++) {
if (!st[i]) prime.add(i);
for (int j = i; j < N; j += i) st[j] = true;
}
Set<Long> s = new HashSet<>();
int n = prime.size();
for (int a : prime) {
if ((long) a * a >= N) break;
for (int b : prime) {
if ((long) a * a + (long) b * b * b >= N) break;
for (int c : prime) {
long val = (long) a * a + (long) b * b * b + (long) c * c * c * c;
if (val >= N) break;
s.add(val);
}
}
}
List<Long> v = new ArrayList<>(s);
Collections.sort(v);
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
int m = v.size();
while (t-- > 0) {
int x = scanner.nextInt();
int L = 0, R = m;
while(L < R)
{
int mid = L + R >> 1;
if(v.get(mid) > x) R = mid;
else
L = mid + 1;
}
System.out.println(L);
}
}
}
- Cpp
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
using namespace std;
using ll = long long;
const int N = 1e6 + 1;
bool st[N];
vector<int> prime;
int main() {
for (int i = 2; i < N; i++) {
if (!st[i]) prime.push_back(i);
for (int j = i; j < N; j += i) st[j] = true;
}
unordered_set<int> s;
int n = prime.size();
for (auto a : prime) {
if (1ll * a * a >= N) break;
for (auto b : prime) {
if (1ll * a * a + b * b * b >= N) break;
for (auto c : prime) {
ll val = 1ll * a * a + b * b * b + c * c * c * c;
if (val >= N) break;
s.insert(val);
}
}
}
vector<int> v(s.begin(), s.end());
sort(v.begin(), v.end());
int t;
cin >> t;
while (t--) {
int x;
cin >> x;
int idx = upper_bound(v.begin(), v.end(), x) - v.begin();
cout << idx << "\n";
}
return 0;
}
类似资料：