漫漫云天自翱翔 - 个人主页动态 - 牛客网

发布(490) 评论刷题收藏

2021-08-17 19:45

已编辑

网易互娱_互娱_底层研发工程师

题解 | #重建二叉树#

前提知识：前序遍历 ： 节点按照[ 根 | 左 | 右 ] 顺序遍历中序遍历： 节点按照[ 左 | 根 |右 ] 顺序遍历由此可知： 1.前序遍历的首元素为树的根节点值。 2.根节点的值可以将中序遍历划分为 [左子树中序遍历 | 根节点 | 右子树中序遍历 ]。 3.根据中序遍历左右子树的节点个数，可以将前序遍历划分为 [根节点 | 左子树前序遍历 | 右子树前序遍历 ]  题解一：递归 题解思路： 通过上述分析，可以递归的处理所有子树 递归分析： 1.递归参数： pre前序遍历数组， vin 中序遍历数组， left中序遍历左边界，right中序遍历右边界 2. 递归边界： left>...

牛客网编程题题解

0 点赞评论收藏

分享

2021-08-17 19:23

已编辑

网易互娱_互娱_底层研发工程师

题解 | #从尾到头打印链表#

题解一：递归题解思路：使用递归先走到链表的末尾，再在回溯时将链表节点中的值加入到数组中。递归边界： head == NULL;递归阶段：一直传入head->next;回溯阶段：将值加入到数组；图示：复杂度分析：时间复杂度:，回溯遍历了整个链表空间复杂度:，去掉输出最终结果vector的数组，栈递归深度为N，所以使用栈的空间为O(N) 实现如下： class Solution { public: vector<int> ans; void recur(ListNode* head){ if(head == NULL) //head == NULL表示递归结束 return; r...

牛客网编程题题解

0 点赞评论收藏

分享

2021-08-17 19:28

已编辑

网易互娱_互娱_底层研发工程师

题解 | #替换空格#

题解一:暴力(原字符串上修改)题解思路:从头开始遍历数组，当遇到空格，先将后续字符往后移2个位置，再在空格位置以及后两个位置填上"%20"这三个字符 示例：复杂度分析：时间复杂度：，暴力的两次循环，第一层循环找空格位置，第二层循环将空格后面的字符往后移2位置空间复杂度：，只使用常数个临时变量存放中间值 实现如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ string replaceSp...

牛客网编程题题解

0 点赞评论收藏

分享

2021-06-24 20:38

已编辑

网易互娱_互娱_底层研发工程师

题解 | #二维数组中的查找#

题解一：暴力搜索解题思路： 逐行逐列的搜索二维数组，判断是否存在目标值。 复杂度分析：时间复杂度：O(MN)空间复杂度：O(1) 实现如下： class Solution { public: bool Find(int target, vector<vector<int> > array) { for(auto i : array)//c++11语法 { for(auto j : i) { if(j == target) return true;//找到目标值 } } return false;//未找到 } }; 题解二： 利用二分搜索解题思路： 利用数组每行每列都是...

牛客网编程题题解

0 点赞评论收藏

分享

2021-07-02 10:26

已编辑

网易互娱_互娱_底层研发工程师

题解 | #斐波那契数列#

什么是斐波拉契数列由题意与斐波拉契数列定义:已知f(n)=f(n-1)+f(n-2),f(0)=0,f(1)=1，求f(n)。题解一:记忆化搜索图示如下：根据思路我们可以实现递归代码： class Solution { public: int Fibonacci(int n) { if(n<=1) return n;//前两项结果，递归结束条件 return Fibonacci(n-1)+Fibonacci(n-2);//递推公式 } }; 仔细观察上图，可以发现，f(2)计算了两次，f(1)计算了3次，f(0)计算了2次。可以采用一个map存储已经被计算过的值(不采用vector的原因...

牛客网编程题题解

0 点赞评论收藏

分享

2021-07-02 10:25

已编辑

网易互娱_互娱_底层研发工程师

题解 | #跳台阶#

题解一:记忆化搜索假设有n阶台阶，在所有的跳法中，由于青蛙一次只能跳1步或者2步，所以青蛙跳上最后一阶只能由f(n-1)+1 或者f(n-2)+2 这两种情况得来。即：f(n)=f(n-1)+f(n-2)同理:f(n-1)=f(n-2)+f(n-3),以此类推。这其实就是一个斐波拉契数列。图示如下：根据思路我们可以实现递归代码： class Solution { public: int jumpFloor(int number) { if(number<=1) return 1; return jumpFloor(number-1)+jumpFloor(number-2); } };仔细...

牛客网编程题题解

0 点赞评论收藏

分享

2021-06-22 15:36

网易互娱_互娱_底层研发工程师

2021.06.22 在牛客打卡469天！

0 点赞评论收藏

分享

2021-06-22 10:27

网易互娱_互娱_底层研发工程师

题解 | #孩子们的游戏(圆圈中最后剩下的数)#

题解一：暴力法解题思路：用数组模拟循环列表，从0开始喊到m个数后，就将其值置为-1。直到数组剩下最后一个数（非-1）。样例如下：  复杂度分析：时间复杂度：O(N^2)空间复杂度：O(N)，申请一个数组标记每个小孩子是否退圈 class Solution { public: int LastRemaining_Solution(int n, int m) { if (m == 0)return -1; vector<int> child(n + 1,0);// int k = 0,j=0;//k=出圈的小孩数,j=报数编号 for (int i = 0;k!=n-1; i=(++i...

不知道叫啥521：吊打官方题解

牛客网编程题题解

0 点赞评论收藏

分享

2021-07-02 13:45

已编辑

网易互娱_互娱_底层研发工程师

题解 | #求1+2+3+...+n#

这是一题考虑思维广度的题目:1、不能使用判断语句，可以从逻辑运算符考虑2、利用类型强转，函数指针3、模板元编程4、放在C++类中考虑6、将1+2+3+...+n的结果开辟为动态内存，内存计算题解一：递归+逻辑运算符前置知识：位运算|、&与逻辑运算符&&、||的区别。1、&、|是按位运算，符号两端为两个数；&&、||是两个逻辑表达式；2、&&、||运算具有短路功能，示例：(A)&&(B)当A部分不成立，则B部分不会执行，(A)||(B)当A部分成立，则B部分不会执行。 复杂度分析:时间复杂度:O(n)空间复杂度:O(...

牛客网编程题题解

0 点赞评论收藏

分享

2021-07-02 13:06

已编辑

网易互娱_互娱_底层研发工程师

题解 | #扑克牌顺子#

题解一:排序+遍历顺子牌的特点：1、顺子一定没有相等的牌；2、顺子中两张相邻的扑克牌的数值差为1，即满足interrapt=numbers[i + 1] - numbers[i] - 1==0;3、当interrapt不为0，代表需要在顺子中插入对应interrapt张牌；4、只有两张王牌；主要思路：1、排序五张牌；2、遍历5张牌，并求出大小王的数量zero_num，与interrapt的大小；3、判断interrapt的大小。(1)interrapt==0,除大小王之外的牌本来就是顺子，大小王随便补齐在头部或者尾部；(2)interrapt<=zero_num,除大小王之外的牌不是顺子...

牛客67878728...：感觉只有第三种方法，是真正的时间复杂度O(n),空间复杂度o(1)。

牛客网编程题题解

0 点赞评论收藏

分享

2021-06-20 21:15

网易互娱_互娱_底层研发工程师

题解 | #翻转单词序列#

题解一： 原地操作法解题思路：将后面的字符插入到前面。主要思路：1.使用两个指针:cur_end与 cur_insert , cur_end表示当前字符串末尾位置，cur_insert表示当前插入位置。2. 从尾至头处理str,cur_end分为三种情况 a.如果cur_end指向的是空字符且上次处理的字符非空，那么将cur_end指向的字符插入到cur_insert同时删除cur_end所指字符。 b. 如果cur_end指向非空字符，那么cur_end指向的字符插入到cur_insert同时删除cur_end所指字符。 c.如果cur_end指向空字符且上一次处理的字符也为空字符，那么直接...

牛客网编程题题解

0 点赞评论收藏

分享

2021-07-02 13:26

已编辑

网易互娱_互娱_底层研发工程师

题解 | #把字符串转换成整数#

题解一：模拟解题思路：模拟考虑各种特殊情况：1、负号“-”与正号“+”只能出现在第一个i=0的位置；2、不能出现除0~9与+、-之外的任何字符；3、不能出现前置零；4、最后结果判断是否越界(INT_MIN<=res<=INT_MAX)；特判所有的特殊情况后，如示例将字符串转换成整数：  复杂度分析：时间复杂度:O(n),遍历字符串空间复杂度:O(1) 实现如下: class Solution { public: int StrToInt(string str) { int flag = 0;//标记数字正负 long long res = 0; for (int i = 0; i ...

牛客网编程题题解

0 点赞评论收藏

分享

2021-06-24 20:48

已编辑

网易互娱_互娱_底层研发工程师

题解 | #左旋转字符串#

题解一：字符切分与拼接解题思路： 获取str[n:] 和 str[:n]子串，目标串target = str[:n] + str[n:];如样例：复杂度分析：时间复杂度： O(N)，需要遍历把子串拷贝出新的内存空间空间复杂度： O(N)，需要申请空间存储两段str子串的长度 class Solution { public: string LeftRotateString(string str,int n){ if(str.size()==0) return str; string s = str.substr(0,n); string res = str.substr(n,str.size()...

牛客网编程题题解

0 点赞评论收藏

分享

2021-06-20 13:35

已编辑

网易互娱_互娱_底层研发工程师

题解 | #数组中重复的数字#

题解一:暴力(TLE超时，不能AC此题)解题思路：第一层循环依次选取一个锚点数字，第二层循环遍历剩下的数字，当找到相同的两个数字，退出循环，返回正确的结果。 复杂度分析：时间复杂度:O(n^2),两层循环空间复杂度:O(1)代码如下： class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param numbers int整型vector * @return int整型 */ int duplicate(vector<int>& numbers) { // write code ...

二徒：第四种方法最差情况是O(2n)吧，比起其他种算法要慢

牛客网编程题题解

0 点赞评论收藏

分享

2021-06-22 21:18

已编辑

网易互娱_互娱_底层研发工程师

题解 | #和为S的两个数字#

题解一： 暴力解题思路： 双层循环,在确定第一个值array[i]的情况下，遍历其余所有值，找到相匹配的array[j]，找到即可结束循环复杂度分析：时间复杂度： O(n^2)空间复杂度： O(1) class Solution { public: vector<int> FindNumbersWithSum(vector<int> array,int sum){ for(int i = 0;i<array.size();i++){//确定第一个数 for(int j = i+1;j<array.size();j++){ if(array[i] + arra...

牛客网编程题题解

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务