class Solution { public: bool validPartition(vector<int>& nums) { int n = nums.size(); vector<bool> f(n + 1, false); f[0] = true; for(int i = 2; i <= n; i ++ ) { if(nums[i - 1] == nums[i - 2]) f[i] = f[i] || f[i - 2]; if(i >= 3) { if(nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) f[i] = f[i] || f[i - 3]; if(nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1) f[i] = f[i] || f[i - 3]; } } return f[n]; } };转换成c++

时间: 2024-03-14 19:46:23 浏览: 42

字节跳动2018校招大数据方向（第一批）.pdf

【编程题1】此题是一道关于二维平面上找“最大”点的问题。给定一组不重复的点，我们需要找出所有“最大”的点，即不存在任何点位于当前点的右上方。解决这个问题的关键在于理解题意，并能有效地进行排序和比较。我们可以将所有点按x坐标排序。然后，对于每一个点，我们检查其右上方是否存在其他点。这可以通过在遍历过程中维护当前最大y坐标来实现。当遇到一个点的y坐标大于或等于当前最大y坐标时，这个点就是“最大”的。因此，我们需要编写一个算法，它能够对点进行排序，并进行遍历以找出所有满足条件的点。 ```cpp #include <iostream> #include <vector> #include <algorithm> struct Point { int x, y; }; bool compareX(const Point &a, const Point &b) { return a.x < b.x; } bool isMax(const Point &p, const std::vector<Point> &points) { for (const Point &q : points) { if (q.x > p.x || (q.x == p.x && q.y >= p.y)) { return false; } } return true; } std::vector<Point> findMaxPoints(std::vector<Point> points) { std::sort(points.begin(), points.end(), compareX); std::vector<Point> maxPoints; int maxY = -1; for (const Point &p : points) { if (p.y > maxY || (p.y == maxY && p.x > maxYX)) { maxPoints.push_back(p); maxY = p.y; } } return maxPoints; } int main() { int N; std::cin >> N; std::vector<Point> points(N); for (int i = 0; i < N; ++i) { std::cin >> points[i].x >> points[i].y; } std::vector<Point> maxPoints = findMaxPoints(points); for (const Point &p : maxPoints) { std::cout << p.x << " " << p.y << std::endl; } return 0; } ``` 【编程题2】这道题要求找到一个数组区间，使得区间内最小值乘以区间内所有数的和最大。这是一个经典的动态规划问题，可以通过动态规划数组dp[i]表示以第i个元素结尾的子数组的最大乘积来解决。对于每个元素，我们需要计算两种情况：包含当前元素和不包含当前元素的子数组的最大乘积。 ```cpp #include <iostream> #include <vector> using namespace std; int maxProduct(vector<int>& nums) { int n = nums.size(); vector<int> dp1(n), dp2(n); dp1[0] = dp2[0] = nums[0]; for (int i = 1; i < n; ++i) { dp1[i] = max(nums[i] * dp1[i - 1], nums[i] * dp2[i - 1]); dp2[i] = min(nums[i] * dp1[i - 1], nums[i] * dp2[i - 1]); } int ans = dp1[n - 1]; for (int i = 1; i < n; ++i) { ans = max(ans, dp1[i] / nums[i]); } return ans; } int main() { int n; cin >> n; vector<int> nums(n); for (int& num : nums) { cin >> num; } cout << maxProduct(nums) << endl; return 0; } ``` 【编程题3】此题涉及到多任务调度问题，需要模拟PM和程序员的行为。我们可以使用优先队列来解决这个问题，优先级最高的任务会被优先处理。对于每个PM，记录他们的想法和优先级，然后按照优先级和时间进行排序。程序员会按顺序处理这些任务。 ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; struct Idea { int pmId, time, priority, reqTime; }; bool compareIdea(const Idea &a, const Idea &b) { if (a.priority != b.priority) { return a.priority > b.priority; } else if (a.time != b.time) { return a.time < b.time; } else { return a.pmId < b.pmId; } } int solve(vector<Idea> &ideas, int m) { priority_queue<Idea, vector<Idea>, decltype(compareIdea)*> pq(compareIdea); for (Idea &idea : ideas) { pq.push(idea); } int currentTime = 0, result[ideas.size()]; while (!pq.empty()) { Idea topIdea = pq.top(); pq.pop(); if (currentTime >= topIdea.time) { result[topIdea.pmId] = currentTime + topIdea.reqTime; currentTime = result[topIdea.pmId]; } else { currentTime = topIdea.time; result[topIdea.pmId] = currentTime + topIdea.reqTime; } } return result; } int main() { int n, m, p; cin >> n >> m >> p; vector<Idea> ideas(p); for (Idea &idea : ideas) { cin >> idea.pmId >> idea.time >> idea.priority >> idea.reqTime; } for (int i = 0; i < p; ++i) { cout << solve(ideas, m)[i] << endl; } return 0; } ``` 【问答题】这道题目要求找到一棵树中节点数最多的层，并返回该层的深度。给定的代码存在错误，例如变量名未正确初始化。下面是修复后的代码： ```cpp #include <iostream> #include <vector> using namespace std; struct Node { vector<Node*> sons; }; void dfsFind(Node* node, int depth, int counter[], int maxDepth) { counter[depth]++; for (Node* child : node->sons) { dfsFind(child, depth + 1, counter, maxDepth); } } int findMaxNodesLayer(Node* root, int maxDepth) { int depCounter[maxDepth + 1] = {0}; dfsFind(root, 0, depCounter, maxDepth); int maxNodes = 0, maxDepthIndex = 0; for (int i = 1; i <= maxDepth; i++) { if (depCounter[i] > maxNodes) { maxNodes = depCounter[i]; maxDepthIndex = i; } } return maxDepthIndex; } int main() { // 读取树结构和最大深度的代码 // ... int maxDepthIndex = findMaxNodesLayer(root, 100000); cout << "The layer with the most nodes is at depth: " << maxDepthIndex << endl; return 0; } ``` 以上代码修复了原始代码中的错误，并提供了正确的实现。`dfsFind`函数现在接受最大深度作为参数，`findMaxNodesLayer`函数正确地初始化了`depCounter`数组，并找到了节点数最多的层的深度。

这段代码已经是C++代码了，如果您想了解它的运行过程和具体实现，可以参考下面的解释和注释。 ```c++ class Solution { public: bool validPartition(vector<int>& nums) { int n = nums.size(); // 获取数组长度 vector<bool> f(n + 1, false); // 定义一个长度为 n+1 的布尔类型的数组 f，初始值全部为 false f[0] = true; // 将 f[0] 赋值为 true for(int i = 2; i <= n; i ++) { // 遍历数组 if(nums[i - 1] == nums[i - 2]) // 如果当前元素与前一个元素相等 f[i] = f[i] || f[i - 2]; // 则将 f[i] 更新为 f[i] 或 f[i-2] if(i >= 3) { if(nums[i - 1] == nums[i - 2] && nums[i - 2] == nums[i - 3]) // 如果当前元素与前两个元素相等 f[i] = f[i] || f[i - 3]; // 则将 f[i] 更新为 f[i] 或 f[i-3] if(nums[i - 1] - nums[i - 2] == 1 && nums[i - 2] - nums[i - 3] == 1) // 如果当前元素与前两个元素相差为 1 f[i] = f[i] || f[i - 3]; // 则将 f[i] 更新为 f[i] 或 f[i-3] } } return f[n]; // 返回 f[n] } }; ```

阅读全文

相关推荐

c++-c++编程基础之leetcode题解第47题全排列II.zip

max_min.rar_c++ max min_c++ 最小质数

class Solution { public: bool containsDuplicate(vector<int>& nums) { return set<int>(nums.begin(), nums.end()).size() != nums.size(); } };返回类型不是bool吗，这是什么

class Solution { public: bool containsDuplicate(vector<int>& nums) { return set<int>(nums.begin(), nums.end()).size() != nums.size(); } };解释这段代码

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { map<int,int> a ; int l=nums.size(); for(int i=0 ; i < l ; i++){ int num=nums[i]; if(a.count(num) &&i-a[num] <=k){ return true; } a[num] = i ; } return false; } };

class Solution { public: bool divideArray(vector<int>& nums) { unordered_map<int, int> freq; // 元素出现次数哈希表 for (int num: nums) { ++freq[num]; } return all_of(freq.begin(), freq.end(), [](auto p) { return p.second % 2 == 0; }); }解释这段代码

bool compare(vector<string> &nums){ return stoi(a)<stoi(b); } C:\Program Files\CodeBlocks\vlan\main.cpp|5|error: 'a' was not declared in this scope|

最新推荐

【含数据库+附源码+说明文档】基于Java swing和mysql实现的银行管理系统（彩色版本）

Aspose资源包：转PDF无水印学习工具

管理建模和仿真的文件

【R语言高性能计算秘诀】：代码优化，提升分析效率的专家级方法

在构建视频会议系统时，如何通过H.323协议实现音视频流的高效传输，并确保通信的稳定性？

Go语言控制台输入输出操作教程

"互动学习：行动中的多样性与论文攻读经历"

【R语言机器学习新手起步】：caret包带你进入预测建模的世界

在选择PL2303和CP2102/CP2103 USB转串口芯片时，应如何考虑和比较它们的数据格式和波特率支持能力？

红外遥控报警器原理及应用详解下载