湛江建站程序_网站制作哪里好_长沙靠谱seo优化_关键词搜索挖掘爱网站

目录

一、前缀和计算问题

问题描述

测试样例

解题思路：

问题理解

数据结构选择

算法步骤

关键点

最终代码： 

运行结果：

​编辑 

二、位置调整的查询记录问题

问题描述

测试样例

 解题思路：

问题理解

数据结构选择

算法步骤

关键点

最终代码： 

运行结果： 

 

---

一、前缀和计算问题

问题描述

小S 手上有一个整数数组 nums，他希望计算该数组的前缀和。

---

测试样例

样例1：

输入：nums = [4, 5, 1, 6]
输出：[4, 9, 10, 16]

样例2：

输入：nums = [2, 2, 2, 2]
输出：[2, 4, 6, 8]

样例3：

输入：nums = [7, 3, 9, 4]
输出：[7, 10, 19, 23]

样例4：

输入：nums = [1, 2, 3]
输出：[1, 3, 6]

解题思路：

问题理解

前缀和是指从数组的第一个元素开始，依次累加到当前元素的和。例如，对于数组 [4, 5, 1, 6]，其前缀和数组为 [4, 9, 10, 16]。

数据结构选择

我们可以使用一个与原数组大小相同的数组来存储前缀和。

算法步骤

1. 初始化：创建一个与原数组大小相同的数组 prefixSum。
2. 第一个元素：将原数组的第一个元素直接赋值给 prefixSum 的第一个元素。
3. 累加计算：从第二个元素开始，依次计算每个元素的前缀和，即 prefixSum[i] = prefixSum[i-1] + nums[i]。
4. 返回结果：最终返回 prefixSum 数组。

关键点

• 注意数组的边界条件，特别是第一个元素的处理。
• 确保循环的范围正确，避免数组越界。

最终代码： 

# include <iostream>
# include <vector>
using namespace std;std::vector<int> solution(std::vector<int> nums) {vector<int>arr(nums.size());arr[0] = nums[0];for (int i = 0;i<nums.size()-1;i++) {arr[i+1] = nums[i+1]+arr[i];}return arr;
}int main() {cout << (solution({4, 5, 1, 6}) == std::vector<int>{4, 9, 10, 16}) << endl;cout << (solution({2, 2, 2, 2}) == std::vector<int>{2, 4, 6, 8}) << endl;cout << (solution({7, 3, 9, 4}) == std::vector<int>{7, 10, 19, 23}) << endl;cout << (solution({1, 2, 3}) == std::vector<int>{1, 3, 6}) << endl;return 0;
}

运行结果：

 

二、位置调整的查询记录问题

问题描述

小T 有一个商品编号数组 q，其中每个元素的取值范围是从 1 到 m 之间的数字。起初，小T 拥有一个编号排列 per = {1, 2, 3, ..., m}。

他需要按照以下规则逐步处理每个 q[i]（i 从 0 到 q.length - 1）：

1. 对于当前的 i，需要找到 q[i] 在编号排列 per 中的位置（从 0 开始计数）。
2. 将 q[i] 从当前位置移到编号排列 per 的最前面（即索引为 0 的位置）。

在每次查询之前，记录 q[i] 在排列 per 中的原始位置。

你的任务是返回一个数组，记录每次查询时 q[i] 在编号排列 per 中的原始位置。

---

测试样例

样例1：

输入：queries = [2, 4, 1, 3], m = 5
输出：[1, 3, 2, 3]

样例2：

输入：queries = [3, 2, 1, 4], m = 4
输出：[2, 2, 2, 3]

样例3：

输入：queries = [1, 2, 1, 2], m = 2
输出：[0, 1, 1, 1]

样例4：

输入：queries = [5, 4, 3, 2], m = 6
输出：[4, 4, 4, 4]

 解题思路：

问题理解

1. 初始状态：你有一个初始的编号排列 per，它是从 1 到 m 的自然数序列。
2. 查询操作：对于每个查询 q[i]，你需要找到它在当前排列 per 中的位置，然后将它移动到排列的最前面。
3. 记录位置：在每次查询之前，你需要记录 q[i] 在排列 per 中的原始位置。

数据结构选择

• 数组：你可以使用一个数组来表示排列 per。数组的优点是查找和修改操作的时间复杂度都是 O(1)。
• 记录位置：你可以使用一个结果数组来记录每次查询时 q[i] 在排列 per 中的原始位置。

算法步骤

1. 初始化：创建一个初始排列 per，它是从 1 到 m 的自然数序列。
2. 遍历查询：对于每个查询 q[i]：
   • 查找位置：在当前排列 per 中查找 q[i] 的位置。
   • 记录位置：将这个位置记录到结果数组中。
   • 移动元素：将 q[i] 移动到排列的最前面。
3. 返回结果：返回记录位置的结果数组。

关键点

• 查找位置：你可以使用 std::find 函数来查找元素在数组中的位置。
• 移动元素：将元素移动到最前面时，需要将它从当前位置删除，然后插入到数组的最前面。

最终代码： 

# include <iostream>
# include <vector>
#include <algorithm> // for std::find
using namespace std;std::vector<int> solution(std::vector<int> queries, int m) {// PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE// write code herevector<int> per(m);for(int i=1;i<=m;i++){per[i-1]=i;}vector<int> result;// 遍历查询 queriesfor (int q : queries) {// 查找 q 在排列 per 中的位置auto it = find(per.begin(), per.end(), q);int pos = it - per.begin(); // 计算位置// 记录位置result.push_back(pos);// 将 q 移动到排列的最前面per.erase(it); // 删除当前位置的元素per.insert(per.begin(), q); // 插入到最前面}return result;
}int main() {cout << (solution({2, 4, 1, 3}, 5) == std::vector<int>{1, 3, 2, 3}) << endl;cout << (solution({3, 2, 1, 4}, 4) == std::vector<int>{2, 2, 2, 3}) << endl;cout << (solution({1, 2, 1, 2}, 2) == std::vector<int>{0, 1, 1, 1}) << endl;cout << (solution({5, 4, 3, 2}, 6) == std::vector<int>{4, 4, 4, 4}) << endl;return 0;
}

运行结果：