【阿里笔试题汇总】[全网首发] 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 = 0
    current_length = 0
    
    for i in range(len(s)):
        if is_vowel(s[i]):
            if i > 0 and is_vowel(s[i-1]):
                current_length = 0
            else:
                current_length += 1
                max_length = max(max_length, current_length)
        else:
            current_length += 1
            
    return max_length

n = 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-over
        String 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 Counter

def main():
    mod = 10 ** 9 + 7
    n = 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 = 0
                while x % i == 0:
                    cnt += 1
                    x //= i
                factors[i] += cnt * x
        if x > 1:
            factors[x] += x
    
    res = 1
    for exp in factors.values():
        res = res * (exp + 1) % mod
    
    print(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 Counter

def dfs(u: int, pre: int, s: Counter):
    global res
    if len(s) > k:
        return
    if len(s) == k:
        res += 1
    for i in g[u]:
        if i != pre:
            s[color[i-1]] += 1
            dfs(i, u, s)
            s[color[i-1]] -= 1
            if 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]] = 1
    dfs(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;
}