【阿里笔试题汇总】[全网首发] 2024-04-29-阿里国际春招笔试题-三语言题解(CPP/Python/Java)

本文主要是介绍【阿里笔试题汇总】[全网首发] 2024-04-29-阿里国际春招笔试题-三语言题解(CPP/Python/Java)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

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

⌚️ 春招笔试也是接近尾声，没有拿到offer的小伙伴们抓紧啦～

文章目录

- 💞 01.卢小姐的连续音节挑战
- - 问题描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 💓 02.K小姐的魔法药水
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 💖 03.彩色项链
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 写在最后
- 📧 清隆这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下清隆领取，会在飞书进行同步的跟新。

💞 01.卢小姐的连续音节挑战

问题描述

卢小姐最近在学习外语，她注意到在某些语言中，元音不能连续出现。现在，她有一串由不同字母组成的字符序列，她想找出一个最长的连续子序列，使得在这个子序列中没有两个相邻的元音。元音定义为 “a”, “e”, “i”, “o”, “u” 这五个字母，其他所有字母都被视为辅音。

输入格式

第一行包含一个正整数 $n$ ，代表卢小姐拿到的字符序列的长度。

第二行包含一个长度为 $n$ 的字符串，代表卢小姐拿到的字符序列。

输出格式

输出一个整数，代表卢小姐可以得到的最长子序列的长度。

样例输入

7
aeiobcd

样例输出

数据范围

$\leq n \leq 200000$

题解

可以遍历整个字符串，同时跟踪当前连续子序列的长度。当遇到元音时，需要检查前一个字符是否也是元音。如果是，就重置当前子序列的长度；如果不是，就继续增加当前子序列的长度，并更新最大长度。

参考代码

Python

def is_vowel(char):return char.lower() in 'aeiou'def max_consecutive_substring(s):max_length = 0current_length = 0for i in range(len(s)):if is_vowel(s[i]):if i > 0 and is_vowel(s[i-1]):current_length = 0else:current_length += 1max_length = max(max_length, current_length)else:current_length += 1return max_lengthn = int(input().strip())
s = input().strip()
print(max_consecutive_substring(s))

Java

import java.util.Scanner;public class Main {public static boolean isVowel(char ch) {return "aeiou".indexOf(Character.toLowerCase(ch)) != -1;}public static int maxConsecutiveSubstring(String s) {int max_length = 0, current_length = 0;for (int i = 0; i < s.length(); i++) {if (isVowel(s.charAt(i))) {if (i > 0 && isVowel(s.charAt(i - 1))) {current_length = 0;} else {current_length++;max_length = Math.max(max_length, current_length);}} else {current_length++;}}return max_length;}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();in.nextLine(); // Consume newline left-overString s = in.nextLine();System.out.println(maxConsecutiveSubstring(s));in.close();}
}

#include <iostream>
#include <string>
using namespace std;bool isVowel(char ch) {string vowels = "aeiou";return vowels.find(tolower(ch)) != string::npos;
}int maxConsecutiveSubstring(string s) {int max_length = 0, current_length = 0;for (int i = 0; i < s.length(); i++) {if (isVowel(s[i])) {if (i > 0 && isVowel(s[i - 1])) {current_length = 0;} else {current_length++;max_length = max(max_length, current_length);}} else {current_length++;}}return max_length;
}int main() {int n;cin >> n;string s;cin >> s;cout << maxConsecutiveSubstring(s) << endl;return 0;
}

💓 02.K小姐的魔法药水

题目描述

K小姐是一位魔法师，她发明了一种神奇的魔法药水。这种药水的效果取决于配方中的魔法材料。每种材料都有一个魔力值 $a_i$ ，药水的最终魔力等于所有材料魔力值的乘积，即 $f(a_1) \times f(a_2) \times \ldots \times f(a_n)$ ，其中 $f(x) = x^x$ 。

现在，K小姐准备了 $n$ 种魔法材料，她想知道最终药水的魔力有多少种不同的因子。由于答案可能很大，请对 $10^9+7$ 取模。

输入格式

第一行包含一个正整数 $n$ ，表示魔法材料的种类数。

第二行包含 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ ，表示每种魔法材料的魔力值。

输出格式

输出一个整数，表示最终药水魔力的因子个数对 $10^9+7$ 取模的结果。

样例输入

3
1 2 3

样例输出

数据范围

$\le n \le 2 \times 10^5$
$\le a_i \le 2 \times 10^5$

题解

本题可以通过分解质因数的方法来求解。

首先，对于每个魔力值 $a_i$ ，计算 $f(a_i) = a_i^{a_i}$ 。然后将所有的 $f(a_i)$ 进行质因数分解，统计每个质因子的指数之和。最终答案等于所有质因子指数加一的乘积。

具体步骤如下：

遍历每个魔力值 $a_i$ ：
- 对 $a_i$ 进行质因数分解，对于每个质因子 $p$ ，计算 $a_i$ 中 $p$ 的指数 $c n t$ ，将 $cnt \times a_i$ 累加到 $p$ 的总指数中。
将所有质因子的总指数加一，并累乘得到最终答案。
将答案对 $10^9+7$ 取模。

时间复杂度为 $\sqrt{a_i})$ ，空间复杂度为 $O(a_i)$ 。

参考代码

Python

import sys
from collections import Counterdef main():mod = 10 ** 9 + 7n = int(sys.stdin.readline())a = list(map(int, sys.stdin.readline().split()))factors = Counter()for x in a:for i in range(2, int(x ** 0.5) + 1):if x % i == 0:cnt = 0while x % i == 0:cnt += 1x //= ifactors[i] += cnt * xif x > 1:factors[x] += xres = 1for exp in factors.values():res = res * (exp + 1) % modprint(res)if __name__ == '__main__':main()

Java

import java.io.*;
import java.util.*;public class Main {private static final int MOD = (int) 1e9 + 7;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();Map<Integer, Integer> factors = new HashMap<>();for (int x : a) {for (int i = 2; i <= Math.sqrt(x); i++) {if (x % i == 0) {int cnt = 0;while (x % i == 0) {cnt++;x /= i;}factors.put(i, factors.getOrDefault(i, 0) + cnt * x);}}if (x > 1) {factors.put(x, factors.getOrDefault(x, 0) + x);}}long res = 1;for (int exp : factors.values()) {res = res * (exp + 1) % MOD;}System.out.println(res);}
}

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
using ll = long long;const int MOD = 1e9 + 7;int main() {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}unordered_map<int, long long> factors;for (int x : a) {for (int i = 2; i * i <= x; i++) {if (x % i == 0) {int cnt = 0;while (x % i == 0) {cnt++;x /= i;}factors[i] +=1ll * cnt * x;}}if (x > 1) {factors[x] += x;}}ll res = 1;for (auto [p, exp] : factors) {res = res * (exp + 1) % MOD;}cout << res << endl;return 0;
}

💖 03.彩色项链

题目描述

LYA 有一条由 $n$ 个珠子组成的项链,每个珠子都有一个颜色,用一个大写字母表示。现在 LYA 想知道,在这条项链上一共有多少种不同的简单路径,恰好包含 $k$ 种颜色的珠子。

一个简单路径指的是项链上的一段连续的珠子序列,且任意两个珠子之间至多只有一条边相连。

输入格式

第一行包含两个正整数 $n$ 和 $k$ ,分别表示项链的珠子数和需要的颜色数。

第二行是一个长度为 $n$ 的字符串,表示项链上每个珠子的颜色。

接下来 $n - 1$ 行,每行两个整数 $u, v$ ,表示编号为 $u$ 和 $v$ 的珠子之间有一条边相连。

输出格式

输出一个整数,表示满足条件的简单路径的数目。

样例输入

样例输出

数据范围

$\leq n \leq 10^3$
$\leq k \leq 26$
字符串中只包含大写字母
数据保证给出的是一棵树

题解

本题可以用 DFS 来解决。我们从每个点出发,进行一次 DFS 遍历,过程中维护当前路径上出现的颜色种类数。如果超过了 $k$ 种,就直接返回;如果恰好为 $k$ 种,就将答案加 $1$ 。

注意到每条路径都会被计算两次,因为它的两个端点都会作为起点进行一次 DFS。所以最后的答案需要除以 $2$ 。特殊地,如果 $k = 1$ ,不需要除以 $2$ 。

时间复杂度 $O(n^2)$ ,空间复杂度 $O (n)$ 。

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()
from collections import Counterdef dfs(u: int, pre: int, s: Counter):global resif len(s) > k:returnif len(s) == k:res += 1for i in g[u]:if i != pre:s[color[i-1]] += 1dfs(i, u, s)s[color[i-1]] -= 1if s[color[i-1]] == 0:del s[color[i-1]]n, k = map(int, input().split())
color = input()
g = [[] for _ in range(n+1)]for _ in range(n-1):a, b = map(int, input().split())g[a].append(b)g[b].append(a)res = 0
for i in range(1, n+1):cnt = Counter()cnt[color[i-1]] = 1dfs(i, -1, cnt)if k != 1:res //= 2
print(res)

Java

import java.io.*;
import java.util.*;public class Main {static int n, k;static String color;static List<Integer>[] g;static int res;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String[] str = br.readLine().split(" ");n = Integer.parseInt(str[0]);k = Integer.parseInt(str[1]);color = br.readLine();g = new List[n+1];for (int i = 1; i <= n; i++) {g[i] = new ArrayList<>();}for (int i = 0; i < n-1; i++) {str = br.readLine().split(" ");int a = Integer.parseInt(str[0]);int b = Integer.parseInt(str[1]);g[a].add(b);g[b].add(a);}for (int i = 1; i <= n; i++) {Map<Character, Integer> cnt = new HashMap<>();cnt.put(color.charAt(i-1), 1);dfs(i, -1, cnt);}if (k != 1) {res /= 2;}System.out.println(res);}static void dfs(int u, int pre, Map<Character, Integer> cnt) {if (cnt.size() > k) {return;}if (cnt.size() == k) {res++;}for (int i : g[u]) {if (i != pre) {char c = color.charAt(i-1);cnt.put(c, cnt.getOrDefault(c, 0)+1);dfs(i, u, cnt);cnt.put(c, cnt.get(c)-1);if (cnt.get(c) == 0) {cnt.remove(c);}}}}
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;int n, k;
string color;
vector<int> g[N];
int res;void dfs(int u, int pre, unordered_map<char, int>& cnt) {if (cnt.size() > k) {return;}if (cnt.size() == k) {res++;}for (int i : g[u]) {if (i != pre) {char c = color[i-1];cnt[c]++;dfs(i, u, cnt);if (--cnt[c] == 0) {cnt.erase(c);}}}
}int main() {cin >> n >> k;cin >> color;for (int i = 0; i < n-1; i++) {int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}for (int i = 1; i <= n; i++) {unordered_map<char, int> cnt;cnt[color[i-1]] = 1;dfs(i, -1, cnt);}if (k != 1) {res /= 2;}cout << res << endl;return 0;
}