【阿里笔试题汇总】2024-04-08-阿里国际春招笔试题(第一套)-三语言题解(CPP/Python/Java)

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

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

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

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

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

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

文章目录

- 01.K小姐的完全平方数
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 02.K小姐的魔法石板
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 03.K小姐的幸运数字
- - 题目描述
  - 输入格式
  - 输出格式
  - 样例输入
  - 样例输出
  - 数据范围
  - 题解
  - 参考代码
- 写在最后
- 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

01.K小姐的完全平方数

题目描述

K小姐拿到一个正整数 $x$ ，她希望通过以下两个操作将 $x$ 变为完全平方数：

如果 $x$ 是质数，则将其减 $1$ 。
否则，将其除以自己最小的质因数。

请问 K小姐需要操作多少次才能将 $x$ 变为完全平方数？

输入格式

输入包含一个正整数 $x$ ，表示初始的数。

输出格式

输出一个整数，表示 K小姐需要操作的次数。

样例输入

样例输出

样例输入

样例输出

数据范围

$\le x \le 10^9$

题解

本题可以通过模拟 K小姐的操作过程来解决。

首先，我们需要预处理出 $1$ 到 $10^5$ 范围内的所有质数，可以使用埃氏筛法来实现。对于大于 $10^5$ 的数，可以通过遍历 $2$ 到 $\sqrt{x}$ 的所有数来判断其是否为质数。

接下来，我们从 $x$ 开始，不断执行 K小姐的操作，直到 $x$ 变为完全平方数为止。在操作过程中，我们需要记录操作的次数。

对于当前的数 $x$ ，如果它是质数，则将其减 $1$ ，操作次数加 $1$ 。否则，我们找到 $x$ 最小的质因数，将 $x$ 除以该质因数，操作次数加 $1$ 。

重复上述过程，直到 $x$ 变为完全平方数，即可得到 K小姐需要操作的次数。

判断一个数是否为完全平方数，可以通过求其平方根，然后判断平方根的平方是否等于原数来实现。

时间复杂度为 $O(\sqrt{x})$ ，其中 $x$ 为输入的数。

参考代码

Python

from math import sqrtN = 100010
primes = set()
st = [False] * Ndef get_primes():for i in range(2, N):if not st[i]:primes.add(i)for j in range(i + i, N, i):st[j] = Truedef is_square(x):t = int(sqrt(x))return t * t == xdef is_prime(x):for i in range(2, int(sqrt(x)) + 1):if x % i == 0:return Falsereturn Truedef solve(n):cnt = 0while not is_square(n):if (n <= 1e5 and n in primes) or is_prime(n):n -= 1cnt += 1else:for p in primes:if n % p == 0:n //= pcnt += 1breakreturn cntget_primes()
n = int(input())
print(solve(n))

Java

import java.util.*;public class Main {static final int N = 100010;static Set<Integer> primes = new HashSet<>();static boolean[] st = new boolean[N];static void getPrimes() {for (int i = 2; i < N; i++) {if (!st[i]) {primes.add(i);for (int j = i + i; j < N; j += i) {st[j] = true;}}}}static boolean isSquare(int x) {int t = (int) Math.sqrt(x);return t * t == x;}static boolean isPrime(int x) {for (int i = 2; i * i <= x; i++) {if (x % i == 0) {return false;}}return true;}static int solve(int n) {int cnt = 0;while (!isSquare(n)) {if ((n <= 1e5 && primes.contains(n)) || isPrime(n)) {n--;cnt++;} else {for (int p : primes) {if (n % p == 0) {n /= p;cnt++;break;}}}}return cnt;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);getPrimes();int n = sc.nextInt();System.out.println(solve(n));}
}

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
set<int> primes;
bool st[N];void init() {for (int i = 2; i < N; i++) {if (!st[i]) {primes.insert(i);for (int j = i + i; j < N; j += i) {st[j] = true;}}}
}bool isSquare(int x) {int t = sqrt(x);return t * t == x;
}bool isPrime(int x) {for (int i = 2; i * i <= x; i++) {if (x % i == 0) {return false;}}return true;
}int solve(int n) {int cnt = 0;while (!isSquare(n)) {if ((n <= 1e5 && primes.count(n)) || isPrime(n)) {n--;cnt++;} else {for (auto p : primes) {if (n % p == 0) {n /= p;cnt++;break;}}}}return cnt;
}int main() {init();int n;cin >> n;cout << solve(n) << endl;return 0;
}

02.K小姐的魔法石板

题目描述

K小姐有一个神奇的石板，上面有 $n$ 个格子，每个格子里有一颗魔法石，第 $i$ 个格子里的魔法石价值为 $a_i$ 。K小姐可以从第 $1$ 个格子出发，每次跳跃到前面的某个格子上。但是，K小姐的跳跃距离必须是一个斐波那契数（斐波那契数列： $\dots$ ，第三项开始，每一项等于前两项之和）。K小姐想知道，如果她必须跳到第 $n$ 个格子，那么她最多可以收集到多少价值的魔法石？

输入格式

第一行输入一个整数 $n$ ，表示石板上格子的数量。

第二行输入 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个格子里魔法石的价值 $a_i$ 。

输出格式

输出一个整数，表示 K小姐最多可以收集到的魔法石的总价值。

样例输入

3
1 2 3

样例输出

样例输入

3
1 -2 3

样例输出

数据范围

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

题解

本题可以使用动态规划来解决。设 $d p [i]$ 表示跳到第 $i$ 个格子时可以收集到的最大魔法石价值。那么我们有以下状态转移方程：

$\max_{j \in fib} (dp[i-j] + a[i])$

其中， $f ib$ 表示斐波那契数列。

我们可以预处理出前 $n$ 个斐波那契数，然后使用记忆化搜索或者动态规划来计算 $d p$ 数组的值。最终的答案即为 $d p [n]$ 。

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

参考代码

Python

import sys
input = lambda: sys.stdin.readline().strip()
from functools import cachedef solve():n = int(input())a = list(map(int, input().split()))fib = [1, 1]while fib[-1] < n:fib.append(fib[-1] + fib[-2])@cachedef dp(i):if i == 0:return a[0]res = -float('inf')for f in fib:if i - f >= 0:res = max(res, dp(i - f) + a[i])return resreturn dp(n - 1)print(solve())

Java

import java.io.*;
import java.util.*;public class Main {static int n;static int[] a;static List<Integer> fib = new ArrayList<>();static long[] memo;public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));n = Integer.parseInt(br.readLine());a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();fib.add(1); fib.add(1);while (fib.get(fib.size() - 1) < n) {fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));}memo = new long[n];Arrays.fill(memo, -1);System.out.println(dp(n - 1));}static long dp(int i) {if (i == 0) {return a[0];}if (memo[i] != -1) {return memo[i];}long res = Long.MIN_VALUE;for (int f : fib) {if (i - f >= 0) {res = Math.max(res, dp(i - f) + a[i]);}}return memo[i] = res;}
}

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;
int n;
int a[N];
vector<int> fib;
long long memo[N];long long dp(int i) {if (i == 0) {return a[0];}if (memo[i] != -1) {return memo[i];}long long res = LLONG_MIN;for (int f : fib) {if (i - f >= 0) {res = max(res, dp(i - f) + a[i]);}}return memo[i] = res;
}int main() {cin >> n;for (int i = 0; i < n; i++) {cin >> a[i];}fib.push_back(1); fib.push_back(1);while (fib.back() < n) {fib.push_back(fib.back() + fib[fib.size() - 2]);}memset(memo, -1, sizeof memo);cout << dp(n - 1) << endl;return 0;
}

03.K小姐的幸运数字

题目描述

K小姐非常喜欢一部小说，这部小说的第一部已经完结，但是第二部要等到明年才能开始连载。K小姐等不及了，她决定用一种特殊的方式来打发这段时间。

K小姐有一个数组，她认为数组中所有和为 $3$ 的倍数或 $5$ 的倍数但不是 $4$ 的倍数的子序列都是幸运的。现在她想知道，这个数组中一共有多少个幸运子序列。

由于答案可能很大，你需要输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行输入一个整数 $n$ ，表示数组的长度。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示数组中的元素。

输出格式

输出一个整数，表示幸运子序列的数量对 $10^9+7$ 取模后的结果。

样例输入

3
13 30 17

样例输出

数据范围

$\le n \le 10^5$
$\le a_i \le 10^9$

题解

本题可以使用动态规划来解决。我们可以维护两个二维数组 $f 15$ 和 $f 60$ ，其中 $f 15 [i] [j]$ 表示前 $i$ 个数中，和模 $15$ 等于 $j$ 的子序列数量； $f 60 [i] [j]$ 表示前 $i$ 个数中，和模 $60$ 等于 $j$ 的子序列数量。

对于第 $i$ 个数，我们可以选择将其加入子序列或不加入子序列。如果不加入子序列，那么 $f 15 [i] [j]$ 和 $f 60 [i] [j]$ 的值与 $f 15 [i - 1] [j]$ 和 $f 60 [i - 1] [j]$ 相同；如果加入子序列，那么 $f 15 [i] [j]$ 的值等于 $f15[i-1][(j-a_i) \bmod 15]$ ， $f 60 [i] [j]$ 的值等于 $f60[i-1][(j-a_i) \bmod 60]$ 。

最终的答案即为 $f 15 [n] - f 60 [n]$ ，因为满足和是 $3$ 的倍数或 $5$ 的倍数的子序列数量等于 $f 15 [n]$ ，满足和是 $3$ 的倍数且是 $5$ 的倍数（即是 $15$ 的倍数）的子序列数量等于 $f 60 [n]$ ，我们需要将后者从前者中减去。

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

参考代码

Python

mod = 10**9 + 7def solve():n = int(input())a = list(map(int, input().split()))f15 = [[0] * 15 for _ in range(n+1)]f60 = [[0] * 60 for _ in range(n+1)]f15[0][0] = f60[0][0] = 1for i in range(1, n+1):for j in range(15):f15[i][j] = (f15[i-1][j] + f15[i-1][(j-a[i-1])%15]) % modfor j in range(60):f60[i][j] = (f60[i-1][j] + f60[i-1][(j-a[i-1])%60]) % modans = (f15[n][0] - f60[n][0] + mod) % modprint(ans)solve()

Java

import java.util.*;public class Main {static final int MOD = (int)1e9 + 7;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = sc.nextInt();}long[][] f15 = new long[n+1][15];long[][] f60 = new long[n+1][60];f15[0][0] = f60[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < 15; j++) {f15[i][j] = (f15[i-1][j] + f15[i-1][(j-a[i-1]+15)%15]) % MOD;}for (int j = 0; j < 60; j++) {f60[i][j] = (f60[i-1][j] + f60[i-1][(j-a[i-1]+60)%60]) % MOD;}}long ans = (f15[n][0] - f60[n][0] + MOD) % MOD;System.out.println(ans);}
}

#include <bits/stdc++.h>
using namespace std;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];}vector<vector<long long>> f15(n+1, vector<long long>(15));vector<vector<long long>> f60(n+1, vector<long long>(60));f15[0][0] = f60[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < 15; j++) {f15[i][j] = (f15[i-1][j] + f15[i-1][(j-a[i-1]+15)%15]) % MOD;}for (int j = 0; j < 60; j++) {f60[i][j] = (f60[i-1][j] + f60[i-1][(j-a[i-1]+60)%60]) % MOD;}}long long ans = (f15[n][0] - f60[n][0] + MOD) % MOD;cout << ans << endl;return 0;
}