王清楚

分类

ACM(1) PAT(3) uva(1) 未归档(9) 题解(95)

/ 注册

TA的专栏 59篇文章 1人订阅

牛客题霸题解

59篇文章 2753人学习

全部文章（共107篇）

【牛客题霸题解】用两个栈实现队列来自专栏

解法：push()操作：插入到stack1中pop()操作：stack2中有数字，就弹出stack2中的栈顶元素stack2为空，就先把stack1中的所有数字移到stack2中，然后再弹出stack2中的栈顶元素。 c++ class Solution { public: void pus...

2021-05-18

1 557

【牛客题霸题解】设计getMin功能的栈（待更新java、py）来自专栏

一个栈是没有办法O(1)弹出最小值的，所以需要设置一个辅助栈来随时取出目前的最小值。GetMin(): 辅助栈的栈顶元素表示当前的最小值push(int x): 当插入一个元素的时候，和辅助栈的栈顶元素比较，如果插入的元素<=当前栈顶元素的话，就把这个元素也插入到辅助栈中pop(): 当弹出一...

2021-05-18

0 680

【牛客题霸题解】重建二叉树（待更新 Java、py）来自专栏

前序遍历：根左右中序遍历：左根右只看前序遍历的话，我们知道第一个节点是根。但是不知道左子树有多少个节点、右子树有多少个节点知道了根节点是哪个以后，我们就可以根据中序遍历知道左右子树分别有多少个节点。 c++ class Solution { public: void BuildTree(Tr...

2021-05-17

0 661

【牛客题霸题解】实现二叉树先序，中序和后序遍历（待更新）来自专栏

首先，我们要知道二叉树的先序、中序、后序遍历是怎么进行的，这里的先、中、后其实指的是根的位置。举个例子来看一下先序：根左右{1,13,45,6,4,5,8,7,12}中序：左根右{45,13,4,6,1,8,7,8,12}后序：左右根{45,4,6,13,7,8,12,5,1} 递归写法c++ cl...

2021-05-10

0 759

【牛客题霸题解】数字在升序数组中出现的次数来自专栏

这道题目直接遍历一遍也是可以得到答案的。不过如果想快一点的话我们可以用二分查找前置题目：NC105 二分查找用二分的方法找到第一个大于等于k的位置(lower_bound)和第一个大于k的位置(upper_bound)，然后相减就可以得到答案了。如下图：lower_bound = 2,upper_...

2021-04-29

2 987

【牛客题霸题解】链表中环的入口节点来自专栏

前置题目：NC4判断链表中是否有环在判断链表是否有环那道题目中，我们的做法是定义两个指针初始指向头结点，然后快指针每次走两步，慢指针每次走一步。如果快慢指针相遇的话，就表示链表中有环。然后我们观察一下，这个相遇的结点有没有什么用途如图所示，我们设链表头结点到环入口结点的距离是（如果知道了这个距离其...

2021-04-27

1 655

【牛客题霸题解】顺时针旋转矩阵来自专栏

观察可以发现，原矩阵(x,y)位置的数字旋转完成了以后会在(y)(n-1-x)位置。c++ class Solution { public: vector<vector<int> > rotateMatrix(vector<vector<int> &...

2021-04-21

4 823

【牛客题霸题解】重排链表（待更新java、py）来自专栏

前置题目；NC78反转链表NC33合并两个有序链表题目思路：1、找到链表的中间结点2、把后半部分链表反转3、合并两个链表对于第一步操作，我们设置两个指针快指针每次走两步，慢指针每次走一步，快指针走到空结点的时候慢指针就在链表的中间结点了。第二步反转操作参考NC78反转链表第三步合并操作参考NC33合...

2021-04-21

0 825

【牛客题霸题解】最大数来自专栏

排列给出的数据组成一个最大的数。就是一个顺序的问题。先说一个可能会很容易想到的错误方案：大的数数字在前面，小的数字在后面举一个反例说明一下这个方案为什么错：{9,10} 排出来的最大数字是910，但是这样排的结果是109那我们就来考虑一下，到底按一个什么样的方式排序才是正确的。对于两个数字A、B来说...

2021-04-16

0 603

【牛客题霸题解】二叉树的最大深度（待更新py）来自专栏

进行一次深度优先搜索，cur表示当前的层数。搜索到的最深的层就是二叉树的最大深度c++ class Solution { public: int ans = 0; void dfs(TreeNode* root,int cur) { ans = max(ans...

2021-04-15

0 646