🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新阿里文娱近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。

🎬 01.时间复杂度判断

题目描述

K小姐刚开始学习编程时，经常会遇到时间超限的问题。她希望你能帮忙判断她的程序是否会超时。

已知计算机每秒可以执行 $10^8$ 次计算。如果程序的计算次数大于等于 $10^8$，则判定为超时，输出 TLE；否则，请求出最内层循环中代码的计算次数。

输入格式

第一行包含一个正整数 $N$（$1\le N\le 100$），表示嵌套 for 循环的层数。

第二行包含 $N$ 个空格分隔的正整数 $M_i$（$1\le M_i\le 10000$），表示每个 for 循环的重复次数。

输出格式

如果最内层循环的计算次数大于等于 $10^8$，则输出 TLE，否则输出最内层循环的计算次数。

样例输入

3
1000 1000 1000

样例输出

TLE

数据范围

• $1\le N\le 100$
• $1\le M_i\le 10000$

题解

本题考察了程序的时间复杂度计算。对于嵌套的 for 循环，最内层循环的计算次数等于所有外层循环的重复次数的乘积。

我们可以先读入循环层数 $N$ 以及每层循环的重复次数 $M_i$，然后将所有 $M_i$ 相乘，即可得到最内层循环的计算次数。如果计算次数大于等于 $10^8$，则输出 TLE，否则输出计算次数即可。

时间复杂度为 $O(N)$，空间复杂度为 $O(1)$。

参考代码

• Python

N = int(input())
M = list(map(int, input().split()))ans = 1
for x in M:ans *= xif 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小姐在做数学作业时，遇到了一个关于阶乘数字的问题。她需要找出一个数 $n$ 的阶乘中所有包含的数字0的总数。这并不仅仅是末尾的0，而是整个数中所有出现的0。

输入格式

输入包含一个整数 $n$。

输出格式

输出一个整数，表示 $n$ 的阶乘中数字0的总数。

样例输入

7

样例输出

2

数据范围

$1\le n\le 15$

题解

计算一个正整数 $n$ 的阶乘，并统计阶乘结果中所有0的数量。考虑到 $n$ 的最大值为15，计算阶乘是可行的，因为 $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 定义了一个神奇数字 $num$，其要满足 $num=a^2+b^3+c^4$，其中 $a,b,c$ 都为质数。于是 LYA 想知道在 $1\sim n$ 中有多少个这样的神奇数字呢，请你告诉 LYA。

输入格式

第一行为 $t$，表示有 $t$ 组数据。

接下来有 $t$ 行，每行为一个整数 $n$。

输出格式

输出为 $t$ 行，每行为一组答案。

样例输入

3
28
33
47

样例输出

1
2
3

数据范围

• $1<t<10^5$
• $1\le n<10^6$

题解

本题可以使用预处理 + 二分查找的方法来解决。

首先，预处理出所有可能的神奇数字。由于 $a,b,c$ 都是质数，我们可以先用埃氏筛法筛选出 $1\sim 10^6$ 内的所有质数，存入数组 $prime$ 中。

然后，我们使用三重循环枚举所有可能的 $a,b,c$，计算出对应的神奇数字 $val$，并将其加入到集合 $s$ 中。注意，为了避免重复计算，我们需要保证 $a^2+b^3+c^4<10^6$，虽然有三重循环，但有大量剪枝，总计算次数在 $3\times 10^5$ 左右。

接下来，将集合 $s$ 中的元素转移到数组 $v$ 中，并对 $v$ 进行排序。

最后，对于每个询问 $n$，我们使用二分查找在数组 $v$ 中查找不超过 $n$ 的元素个数，即为答案。

时间复杂度 $O(t\log n)$，空间复杂度 $O(n)$。

参考代码

• Python

import sys
input = lambda: sys.stdin.readline().strip()
import bisectprime = []
N = 10 ** 6 + 1
st = [False] * Nfor 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:breakfor b in prime:if a * a + b ** 3 >= N:breakfor c in prime:val = a ** 2 + b ** 3 + c ** 4if val >= N:breaks.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;elseL = 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;
}

写在最后

📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 清隆领取，会在飞书进行同步的跟新。