//returnasea - 个人主页动态 - 牛客网

发布(106) 评论刷题

2021-10-12 22:10

中南大学 C++

题解 | #二叉树中是否存在节点和为指定值的路径#

二叉树的前序遍历，递归返回条件：走到叶子节点时路径的和等于sum或者不等于sum，走到空结点时为false。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */ bool dfs(Tree...

0 点赞评论收藏

分享

2021-10-12 20:55

中南大学 C++

题解 | #滑动窗口的最大值#

使用max_element()函数对一个范围的数组求最大值。 class Solution { public: vector<int> maxInWindows(const vector<int>& num, unsigned int size) { vector<int> result{}; for(int left=0,right=left+size-1;right<num.size();left++,right++){ int max_val=*max_element(num...

0 点赞评论收藏

分享

2021-10-12 20:35

中南大学 C++

题解 | #有重复项数字的所有排列#

回溯法，求排列的问题在回溯函数中需要用到used标记数组，同时还需要进行去重。去重的方法有两种，一种是在递归返回条件的地方，判断结果集中是否已存在path；另一种是在回溯是判断，对于一排序的序列num，如果后面的元素与前面的元素重复，则只使用前面的第一个元素。 class Solution { public: void backtrack(const vector<int>& num,vector<bool>& used,vector<vector<int>>& result,vector<int>&a...

0 点赞评论收藏

分享

2021-10-12 20:11

中南大学 C++

题解 | #删除有序链表中重复的元素-I#

当下一个元素与下下个元素相同时，删除下下个元素。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { ListNode* dummy_head=new ListNode{-1}; ...

0 点赞评论收藏

分享

2021-10-12 20:00

中南大学 C++

题解 | #重排链表#

首先把链表中的所有结点都保存到vector中，然后双指针left和right分别向数组中间走，重新按照要求拉链。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: void reorderList(ListNode *head) { vector<Li...

0 点赞评论收藏

分享

2021-10-12 15:18

中南大学 C++

题解 | #LFU缓存结构设计#

LFU缓存中元素的换入换出由两个排序码决定：使用次数cont和时间戳time。定义struct结点并且重写<运算符函数，使用红黑树保存结点，就能实现结点按要求自动排序，另外再使用哈希表保存<key,node>，实现了通过key的查找。然后在get和set的过程中更新cont及time，并且元素装满时进行换出。 struct Node{ int key; int value; int cont; int time; Node(int k,int v,int c,int t):key{k},value{v},cont{c},time{t}...

0 点赞评论收藏

分享

2021-10-06 23:51

中南大学 C++

题解 | #数字字符串转化成IP地址#

回溯分割字符串。用'.'的个数作为递归返回条件。 class Solution { public: /** * * @param s string字符串 * @return string字符串vector */ bool is_valid(const string& s,int start,int end){ if(start>end) return false; if(s[start]=='0' && start!=end) return false; i...

0 点赞评论收藏

分享

2021-10-06 23:05

中南大学 C++

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

顺时针旋转之后，行列发生了变换，模拟行列的变换即可。 class Solution { public: vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) { vector<vector<int>> result(n,vector<int>(n,0)); for(int j=0;j<n;j++){ for(int i=0;i<n;i++) ...

0 点赞评论收藏

分享

2021-10-06 22:31

中南大学 C++

题解 | #判断二叉树是否对称#

当左子节点和右子节点都为空时，对称；当左子节点和右子节点一个为空一个不为空时，不对称；当左子节点和右子节点都不为空时，如果两者的值相等则对称，否则递归外侧和内侧的结点，递归判断。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return bool布尔型 */ boo...

0 点赞评论收藏

分享

2021-10-06 22:14

中南大学 C++

题解 | #二叉树的最大路径和#

二叉树任意节点之间的最大路径和=根结点的值+左子树的最大路径+右子树的最大路径。递归求解。 /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: /** * * @param root TreeNode类 * @return int整型 */ int max_path{INT_MIN}; int path_sum(TreeNode* ...

0 点赞评论收藏

分享

2021-10-06 21:36

中南大学 C++

题解 | #链表的奇偶重排#

拆分链表中的结点，把序号为奇数的结点放在数组odd中，把序号为偶数的结点放在数组even中，然后分别遍历两个数组，将接连链接在新的头结点上。 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head...

0 点赞评论收藏

分享

2021-10-06 21:18

中南大学 C++

题解 | #缺失数字#

缺失的数字或者在[0,n-1]的范围内，或者为n。遍历a数组，将已经出现的数字i进行标记，使得a[i]为负，那么若a中存在正数，则此正数的下标就是缺失的数字，否则为n。注意在标记的时候使用abs()。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 找缺失数字 * @param a int整型vector 给定的数字串 * @return int整型 */ int solve(vector<int>& a...

0 点赞评论收藏

分享

2021-10-06 21:00

中南大学 C++

题解 | #缺失的第一个正整数#

nums的长度为n，所以缺失的第一个正整数要么在[1,n]中，要么是n+1。将nums中的负数修改为n+1，然后遍历nums数组，当碰到的元素<=n时，表示此元素在[1,n]中出现过，将它标记为负数。再次遍历nums碰到的第一个非负数的下标表示没有出现过，否则未出现的元素为n+1。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ ...

苏格拉底-larry：有bug

0 点赞评论收藏

分享

2021-10-06 17:48

中南大学 C++

题解 | #矩阵元素查找#

因为行和列的元素是有序递增的，所以大约在副对角线附近的元素就是每个一主对角线上所有元素的中间值，因此从右上角到左下角进行遍历，寻找给定值的元素。 class Solution { public: vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) { vector<int> result(2,0); int row=0, col=m-1; while(row<n && col&gt...

0 点赞评论收藏

分享

2021-10-06 16:49

中南大学 C++

题解 | #反转数字#

思路：使用to_string将int转为string，再利用stringstream流将string转为int，过程中要另外将符号存起来。判断是否溢出可以用更大的long long 保存结果，比较和int是否相等，不相等时溢出。 class Solution { public: /** * * @param x int整型 * @return int整型 */ int reverse(int x) { int sign=1; if(x<0) sign=-1; x*=sign; ...

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务