讲道理的豹子说这不是bug - 个人主页动态 - 牛客网

发布(102) 评论刷题

01-25 22:54

门头沟学院驱动开发

题解 | #【模板】队列#

#include <iostream> using namespace std; int main() { int n = 0; cin >> n; int res[100000]; int end = 0; int start = 0; for (int i = 0; i < n; i++) { string str; cin >> str; if (str == "push") { cin >>...

0 点赞评论收藏

分享

01-24 23:19

门头沟学院驱动开发

题解 | #点击消除#

#include <iostream> #include <stack> using namespace std; int main() { string str; string str1 = ""; stack<char> temp; cin >> str; for (int i = 0; i < str.size(); i++) { if (temp.empty() || temp.top() != str[i]) { temp.pu...

0 点赞评论收藏

分享

01-24 22:56

门头沟学院驱动开发

题解 | #逆波兰表达式求值#

#include <sys/ucontext.h> class Solution { public: int evalRPN(vector<string>& tokens) { int num = 0; stack<int> temp; for (int i = 0; i < tokens.size(); i++) { if (tokens[i] == "*") { num = temp.top(); ...

0 点赞评论收藏

分享

01-18 23:11

门头沟学院驱动开发

题解 | #栈的压入、弹出序列#

class Solution { public: bool IsPopOrder(vector<int>& pushV, vector<int>& popV) { // 特殊情况 if (pushV.size() == 0) return true; int idx_push = 0; int idx_pop = 0; int length = pushV.size(); stack<int> te...

0 点赞评论收藏

分享

2023-10-23 20:00

门头沟学院驱动开发

题解 | #顺时针旋转矩阵#

方法：将数组通过对角线对称的进行元素交换，然后再将每个数组进行翻转。时间复杂度：o(n2)空间复杂度：o(1) class Solution { public: vector<vector<int> > rotateMatrix(vector<vector<int> >& mat, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { int temp = mat[i][j]; mat[i][j] ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-10-18 17:35

门头沟学院驱动开发

题解 | #螺旋矩阵#

方法：边界模拟法思路：这道题就是一个简单的模拟，我们想象有一个矩阵，从第一个元素开始，往右到底后再往下到底后再往左到底后再往上，结束这一圈，进入下一圈螺旋。具体做法:step 1：首先排除特殊情况，即矩阵为空的情况。step 2：设置矩阵的四个边界值，开始准备螺旋遍历矩阵，遍历的截止点是左右边界或者上下边界重合。step 3：首先对最上面一排从左到右进行遍历输出，到达最右边后第一排就输出完了，上边界相应就往下一行，要判断上下边界是否相遇相交。step 4：然后输出到了右边，正好就对最右边一列从上到下输出，到底后最右边一列已经输出完了，右边界就相应往左一列，要判断左右边界是否相遇相交。step ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-10-18 16:43

门头沟学院驱动开发

题解 | #旋转数组#

方法：翻转数组可以很容易的知道右移次数等于数组的元素个数时等于没有移动，所以右移m位，其实等同于右移m%n位；1、先翻转数组的所有元素；2、翻转数组的前m个元素；2、翻转数组的剩余n-m个元素。就可以得到右移m位的数组。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: vector<int> solve(int n, int m, vector<int>& a) { // 特殊情况处理 if (a.size() == 1 || m == 0) return ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-10-17 18:00

门头沟学院驱动开发

题解 | #主持人调度（二）#

方法：贪心算法具体步骤：使用两个辅助数组分别存储节目的开始时间和结束时间；对上面两个数组进行排序（从小到大）遍历n个活动，如果某个活动开始的时间大于之前活动结束的时候，当前主持人就够了，活动结束时间往后一个。若是出现之前活动结束时间晚于当前活动开始时间的，则需要增加主持人。时间复杂度：o(nlog2n)，排序时间需要o(nlog2n)。空间复杂度：o(n) class Solution { public: int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) { ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-10-16 17:34

门头沟学院驱动开发

题解 | #分糖果问题#

方法：贪心算法将每个小孩的糖果数都初始化为1，再遍历数组根据相邻两个孩子的得分情况来更新糖果数目，这样就能得到最少的糖果数具体做法:step 1：使用一个辅助数组记录每个位置的孩子分到的糖果，全部初始化为1.step 2：从左到右遍历数组，如果右边元素比相邻左边元素大，意味着在递增，糖果数就是前一个加1，否则保持1不变。step 3：从右到左遍历数组，如果左边元素比相邻右边元素大， 意味着在原数组中是递减部分，如果左边在上一轮中分到的糖果数更小，则更新为右边的糖果数+1，否则保持不变。step 4：将辅助数组中的元素累加求和。时间复杂度：o(n)空间复杂度：o(n) class Solutio...

刷题题解（c++）

0 点赞评论收藏

分享

2023-10-16 16:56

门头沟学院驱动开发

题解 | #接雨水问题#

方法：双指针step 1：检查数组是否为空的特殊情况step 2：准备双指针，分别指向数组首尾元素，代表最初的两个边界step 3：指针往中间遍历，遇到更低柱子就是底，用较短的边界减去底就是这一列的接水量，遇到更高的柱子就是新的边界，更新边界大小。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: long long maxWater(vector<int>& arr) { // 特殊情况处理 if (arr.size() == 0) return 0; ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-19 17:09

门头沟学院驱动开发

题解 | #最小覆盖子串#

方法：哈希表+双指针1、使用哈希表记录下字符串T中出现的字符的频次（记为负数）；2、遍历字符串S，出现T中的字符就把哈希表中的频次加1，知道哈希表中所有字符串T的字符出现的频次都不为负数时，此时字符串包含了T的所有字符；3、记录下左指针的位置和字符长度，尝试移动左指针缩小窗口；知道遍历完得到最小的长度和对应的左指针位置。 class Solution { public: bool check(unordered_map<char, int> hash, string T) { for (int i = 0; i < T.length(); i++) {...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-18 17:53

门头沟学院驱动开发

题解 | #合并区间#

方法：1、将数组按照区间的起点从小到大的顺序进行排序；2、对排序后数组遍历，如果后一个区间的起点不大于前面一个区间的末尾，说明这两个区间可以合并；否则就不能合并存入数组即可。时间复杂度：o(nlog2n)，排序的复杂度为o(nlog2n)，后续遍历所有区间的复杂度为o(n)空间复杂度：o(n) class Solution { public: // 重载 static bool cmp(Interval& a, Interval& b) { return a.start < b.start; } vector<I...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-14 20:39

已编辑

门头沟学院驱动开发

题解 | #盛水最多的容器#

方法：双指针利用首尾双指针遍历数组，当左指针的高度小于右指针时，左指针向右移动一位；否则，右指针向左移动一位。因为每次向中间移动的时候底部的长度会缩短，所以我们必须要移动较短的一侧高度，这样才有可能得到较大的容积。时间复杂度：o(n)空间复杂度：o(1) class Solution { public: int maxArea(vector<int>& height) { // 特殊情况处理 if (height.size() < 2) return 0; int res = 0; ...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-14 19:23

门头沟学院驱动开发

题解 | #最长无重复子数组#

方法：哈希表遍历数组，使用哈希表记录下数组元素出现的次数，当遇到元素次数大于1时，将数组的left右移直到元素次数不大于1。设置一个值来维护无重复子数组的长度。时间复杂度：o(n)空间复杂度：o(n) class Solution { public: int maxLength(vector<int>& arr) { unordered_map<int, int> map; int res = 0; for (int left = 0, right = 0; left <= right &amp...

刷题题解（c++）

0 点赞评论收藏

分享

2023-09-13 17:48

门头沟学院驱动开发

题解 | #判断是否为回文字符串#

class Solution { public: bool judge(string str) { int len = str.length(); for (int i = 0; i < len; i++) { if (str[i] != str[len - 1 - i]) return false; } return true; } };

刷题题解（c++）

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务