阿里淘天笔试 阿里淘天笔试题 0515
笔试时间:2024年05月15日
历史笔试传送门:2023秋招笔试合集
第一题
题目:小红的子序列排列
小红拿到了一个数组,她想知道该数组有多少个子序列是排列。由于答案过大,请对10^9+7取模。排列是一个长度为k的数组,其中1到k都恰好出现一次。例如[2,3,1]是排列,而[1,3,3]、[1,5,2,3]则不是排列。子序列指数组取若干元素(可以不连续)按原数组顺序形成的新数组。
输入描述
第一行输入一个正整数n,代表小红拿到的数组。第二行输入n个正整数ai,代表数组中的元素。
1<=n<=10^5
1<=ai<=10^9
输出描述
一个整数,代表子序列是排列的数量。
样例输入一
3
1 2 1
样例输出一
4
说明:有两个[1]子序列,1个[1,2]子序列,1个[2,1]子序列
样例输入二
1
2
样例输出二
0
参考题解
数学题。可以组成最长的排列取决于n,而n范围是10w,因此我们只需要枚举n即可。
如果存在2的排列数假设为x,那么假设存在y个3,那么此时3的排列数是x*y,利用这个性质即可快速求解。
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <vector> #include <unordered_map> using namespace std; const int MOD = 1000000007; int main() { int n; cin >> n; vector<int> nums(n); for(int i = 0; i < n; ++i) { cin >> nums[i]; } unordered_map<int, int> cnt; for(int num : nums) { cnt[num]++; } long long res = 0; long long pro = 1; for(int i = 1; i <= 100000; ++i) { if(cnt.find(i) == cnt.end()) break; res = (res + cnt[i] * pro) % MOD; pro = (pro * cnt[i]) % MOD; } cout << res << endl; return 0; }
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { private static final int MOD = 1000000007; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] nums = new int[n]; for (int i = 0; i < n; i++) { nums[i] = scanner.nextInt(); } Map<Integer, Integer> cnt = new HashMap<>(); for (int num : nums) { cnt.put(num, cnt.getOrDefault(num, 0) + 1); } long res = 0; long pro = 1; for (int i = 1; i <= 100000; i++) { if (!cnt.containsKey(i)) break; res = (res + cnt.get(i) * pro) % MOD; pro = (pro * cnt.get(i)) % MOD; } System.out.println(res); } }
Python:[此代码未进行大量数据的测试,仅供参考]
from collections import Counter n = int(input()) nums = list(map(int, input().split())) MOD = 1000000007 cnt = Counter(nums) res = 0 pro = 1 for i in range(1, 100001): if i not in cnt: break res = (res + cnt[i]*pro) % MOD pro = (pro*cnt[i])%MOD print(res)
第二题
题目:小红的01串字串计算
小红拿到了一个01串,她想知道有多少个字符串作为连续子串在01串中出现了至少k次?
输入描述
第一行输入两个正整数n,k,代表字符串长度、子串的至少出现次数。
第二行输入一个长度为n的、仅由'0'和'1'组成的字符串。
1<=k<=n<=400
输出描述
一个整数,代表出现了至少k次的字符串数量。
样例输入
6 2
010100
样例输出
5
说明:"0"、"1"、"01"、"10"、"010"这五个字符串都出现了至少2次。
参考题解
枚举。题目的数据比较小,因此直接枚举所有的子串,判断子串的出现次数是否满足>=k即可。
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <string> #include <set> using namespace std; int main() { int n, k; cin >> n >> k; string s; cin >> s; set<string> ans; for (int i = 0; i < n; ++i) { for (int j = i + 1; j <= n; ++j) { string sub = s.substr(i, j - i); int cnt = 0; for (int l = 0; l < n; ++l) { if (l + j - i > n) break;
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
持续收录字节、腾讯、阿里、美团、美团、拼多多、华为等笔试题解,包含python、C++、Java多种语言版本,持续更新中。