目录
一、数列推进计算任务
问题描述
测试样例
解题思路：
问题理解
数据结构选择
算法步骤
优化思路
最终代码：
运行结果：
二、数组中的幸运数问题
问题描述
测试样例
解题思路：
问题理解
数据结构选择
算法步骤
关键点
最终代码：
运行结果：
编辑
一、数列推进计算任务
问题描述
小F想知道推进数列a的第 n 项值 anan ，该数列由 a0=0,a1=1,a2=1a0=0,a1=1,a2=1 定义，并且对于每个 n>=3,an=an−1+an−2+an−3n>=3,an=an−1+an−2+an−3。
约束条件：
- 时间限制：3s
n为整数，数据范围 1 ≤n≤ 25
测试样例
样例1：
输入：
n = 5
输出：7
样例2：
输入：
n = 12
输出：504
样例3：
输入：
n = 18
输出：19513
解题思路：
问题理解
你正在处理一个递推数列问题，数列的定义如下：
- 初始条件：
a_0 = 0,a_1 = 1,a_2 = 1 - 递推关系：对于
n >= 3，a_n = a_{n-1} + a_{n-2} + a_{n-3}
数据结构选择
由于这是一个递推问题，我们可以使用数组来存储已经计算过的数列值，以避免重复计算。
算法步骤
- 初始化数组：创建一个数组
a，并根据初始条件设置a[0],a[1],a[2]。 - 递推计算：从
n = 3开始，使用递推公式a[n] = a[n-1] + a[n-2] + a[n-3]计算数列的值，直到n。 - 返回结果：返回数组中第
n个元素的值。
优化思路
- 记忆化：为了避免重复计算，可以使用记忆化技术，即在计算过程中存储已经计算过的值。
- 动态规划：通过动态规划的方式，从底向上计算数列的值，这样可以避免递归带来的栈溢出问题。
最终代码：
# include <iostream>
using namespace std;
int solution(int n) {
// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
// write code here
if(n-3>=0)
return solution(n-1)+solution(n-2)+solution(n-3);
if(n==0)
return 0;
if (n==1||n==2) {
return 1;
}
}
int main() {
cout << (solution(5) == 7) << endl;
cout << (solution(12) == 504) << endl;
cout << (solution(18) == 19513) << endl;
return 0;
}运行结果：
二、数组中的幸运数问题
问题描述
在给定整数数组中，找出最大满足该条件的数：出现次数等于其数值的整数，如果不存在则返回 -1。
测试样例
样例1：
输入：
arr = [4, 3, 3, 2]
输出：-1
样例2：
输入：
arr = [1, 2, 2, 3, 3, 4, 4, 4, 4, 3]
输出：4
样例3：
输入：
arr = [6, 6, 6, 6, 6]
输出：-1
解题思路：
问题理解
我们需要在一个整数数组中找到一个数，这个数的出现次数等于它本身的数值。如果不存在这样的数，则返回 -1。
数据结构选择
为了统计每个数出现的次数，我们可以使用一个哈希表（在C++中可以使用 std::unordered_map）。哈希表可以快速地记录和查询每个数出现的次数。
算法步骤
- 初始化哈希表：用于记录每个数出现的次数。
- 遍历数组：统计每个数出现的次数，并将其记录在哈希表中。
- 查找满足条件的数：再次遍历数组，检查每个数是否满足其出现次数等于其数值的条件。
- 返回结果：如果找到满足条件的数，返回该数；否则返回 -1。
关键点
- 哈希表的使用可以大大提高统计和查询的效率。
- 需要两次遍历数组：第一次用于统计，第二次用于查找。
最终代码：
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int solution(std::vector<int> arr) {
// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
// write code here
unordered_map<int, int> ar;
for (auto i : arr) {
ar[i]++;
}
// 遍历哈希表，查找满足条件的数
for (auto it = ar.begin(); it != ar.end(); ++it) {
if (it->first == it->second) {
return it->first;
}
}
return -1;
}
int main() {
cout << (solution({4, 3, 3, 2}) == -1) << endl;
cout << (solution({1, 2, 2, 3, 3, 4, 4, 4, 4, 3}) == 4) << endl;
cout << (solution({6, 6, 6, 6, 6}) == -1) << endl;
return 0;
}运行结果：
