饿了么笔试 饿了么笔试题 0412
笔试时间:2024年04月12日
历史笔试传送门:2023秋招笔试合集
第一题
题目:小红的质数合数
小红有一个数组,她想知道这个数组不同的质数和不同的合数共有多少个。合数是指在大于1的整数中除了能被1和本身整除外,还能被其他数(O除外)整除的数。
输入描述
第一行输入一个整数n(1<= n<=2 x 10^5)表示数组长度。
第二行输入n个整数表示数组ai。
输出描述
输出一个整数。
样例输入
3
20 2 4
样例输出
3
参考题解
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <unordered_set> using namespace std; int main() { int n; cin >> n; unordered_set<int> st; for (int i = 0; i < n; ++i) { int a; cin >> a; if (a > 1) { st.emplace(a); } } cout << st.size(); }
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); HashSet<Integer> set = new HashSet<>(); for (int i = 0; i < n; ++i) { int a = scanner.nextInt(); if (a > 1) { set.add(a); } } System.out.println(set.size()); } }
Python:[此代码未进行大量数据的测试,仅供参考]
n = int(input()) st = set() for _ in range(n): a = int(input()) if a > 1: st.add(a) print(len(st))
第二题
题目:小苯的数组查询
小苯有一个长度为n的数组α。它定义了一个函数:
f(l,r) = al|al + 1|ar。
(|表示位运算中的按位或运算)
现在他有q次询问,每次询问他都会给出一个区间[l,r],以及一个正整数k,他想知道在区间中是否存在一个右端点r',使得f(l, r')请你帮帮他处理每次询问吧。
输入描述
输入包含若干行。 第一行两个正整数n,q(),分别表示数组α的长度和小苯的询问次数。
第二行n个正整数,表示数组α的每个元素。
接下来q行,每行三个正整数l,r,k
输出描述
输出包含q行,每行一个整数,如果存在符合条件的,请输出最小的一个,如果不存在输出一个-1。
样例输入
5 5
3 2 3 3 6
1 2 3
1 5 7
1 4 7
2 2 2
2 3 7
样例输出
1
5
-1
2
-1
说明
第一个询问,区间[1.2]中,选择r=1,区间[1,1]的f值为3,因此输出1。
参考题解
比较典型的题目,遇到按位或运算,可以考虑前缀和,因为bit的数目是递增的,可以先统计每个数位上1的数目的前缀和;然后对于每一次询问,采用二分查找来找到最左边符合条件的索引。在二分查找中,利用前缀和数组构建当前区间所有元素按位或的和,判断其与k的大小关系,从而收缩左右边界。
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <vector> using namespace std; using ll = long long; int main() { int n, q; cin >> n >> q; vector<int> a(n); vector<vector<int>> S(n + 2, vector<int>(32, 0)); for (int i = 0; i < n; ++i) { cin >> a[i]; S[i + 1] = S[i]; for (int j = 0; j < 32; ++j) S[i + 1][j] += (a[i] >> j & 1); } for (int i = 0; i < q; ++i) { ll left, right, k; cin >> left >> right >> k; left--, right--; ll cur = 0, l = left, r = right; while (l <= r) { ll mid = (l + r) / 2; cur = 0; for (int j = 0; j < 32; ++j) { int c = S[mid + 1][j] - S[left][j]; if (c) cur |= (1 << j); } if (cur >= k) r = mid - 1; else l = mid + 1; } cur = 0; for (int j = 0; j < 32; ++j) { int c = S[l + 1][j] - S[left][j]; if (c) cur |= (1 << j); } if (cur == k && l + 1 <= right + 1) cout << l + 1 << "\n"; else cout << "-1\n"; } }
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int q = scanner.nextInt(); int[] a = new int[n]; int[][] S = new int[n + 2][32]; for (int i = 0; i < n; ++i) { a[i] = scanner.nextInt(); System.arraycopy(S[i], 0, S[i + 1], 0, 32); for (int j = 0; j < 32; ++j) S[i + 1
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。