-
牛客网 剑指offer 二叉树中和为某一值的路径
时间限制：1秒空间限制：32768K热度指数：8801**算法知识视频讲解题目描述输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。题解：利用dfs代码如下：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(N...…
-
牛客网 剑指offer 二叉搜索树与双向链表
时间限制：1秒空间限制：32768K热度指数：6676**算法知识视频讲解题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。题解：双向链表，先通过中序遍历获得顺序然后遍历vector得到右边，然后再往左遍历代码如下：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x),...…
-
牛客网 剑指offer 字符流中第一个不重复的字符
时间限制：1秒空间限制：32768K热度指数：4286本题知识点：字符串**算法知识视频讲解题目描述输出描述:如果当前字符流没有存在出现一次的字符，返回#字符。题解：利用map值为1代码如下：class Solution{public: unordered_map<char,int>m; vector<char>v; //Insert one char from stringstream void Insert(char ch) { ...…
-
牛客网 剑指offer 二叉树中序遍历的下一个结点
时间限制：1秒空间限制：32768K热度指数：4658**算法知识视频讲解题目描述给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。题解：有右孩子，则找右孩子的最左孩子，若无则返回右孩子无右孩子，则返回父节点的左孩子。代码如下：/*struct TreeLinkNode { int val; struct TreeLinkNode *left; struct TreeLinkNode *r...…
-
牛客网 剑指offer 二叉搜索树的后序遍历序列
时间限制：1秒空间限制：32768K热度指数：9504**算法知识视频讲解题目描述输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。题解：利用后序遍历的特征，前半部分为小于根节点，后半部分为大于根节点代码如下：class Solution {public: int index=0; bool VerifySquenceOfBST(vector<int> sequence) { ...…
-
牛客网 剑指offer 链表中环的入口结点
时间限制：1秒空间限制：32768K热度指数：5105本题知识点：链表**算法知识视频讲解题目描述一个链表中包含环，请找出该链表的环的入口结点。题解：利用STL的强大功能中的之一set，若不用set代码如下：/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class Solution {public: L...…
-
牛客网 剑指offer 连续子数组的最大和
时间限制：1秒空间限制：32768K热度指数：8659本题知识点：数组**算法知识视频讲解题目描述HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是...…
-
牛客网 剑指offer 栈的压入、弹出序列
时间限制：1秒空间限制：32768K热度指数：10544本题知识点：栈**算法知识视频讲解题目描述输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）题解：首先定义一个栈，根据顺序来压入栈，每压入一次便与出栈序列比较，若顶部与当前出栈元素相同，则进...…
-
牛客网 剑指offer 数组中重复的数字
时间限制：1秒空间限制：32768K热度指数：6192本题知识点：数组**算法知识视频讲解题目描述在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。题解：利用map来判断是否为重复数字，若map[x]的值大于1则为重复数字返回true,若无，则返回falseps...…
-
牛客网 剑指offer 平衡二叉树
时间限制：1秒空间限制：32768K热度指数：6833**算法知识视频讲解题目描述输入一棵二叉树，判断该二叉树是否是平衡二叉树。题解：判断是否为平衡二叉树的条件是左孩子的高度与右孩子的高度相差至少为2时就不平衡，否则平衡，所以定义一个getheight函数来获得结点的高度，然后进行递归判断是否为平衡二叉树即可注意当传入的结点为空时则为平衡二叉树，因为此时遍历完一条边，需要计算高度来判断是否为平衡二叉树，所以需要返回true.代码如下：class Solution {public: i...…
-
牛客网 剑指offer 对称的二叉树
时间限制：1秒空间限制：32768K热度指数：5138**算法知识视频讲解题目描述请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。题解：利用镜像的含义，左子树等于右子数，左子树的左子树=右子数的右子数左子树的右子数=右子数的左子树代码如下：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode...…
-
牛客网 剑指offer 从上往下打印二叉树
时间限制：1秒空间限制：32768K热度指数：10910**算法知识视频讲解题目描述从上往下打印出二叉树的每个节点，同层节点从左至右打印。利用队列，当当前结点不为空，push进入队列，然后在while循环中检测它的左孩子与右孩子是否存在，若存在则push进入队列，将每一个pop出来的结点的值放入vector，即为层次遍历的结果代码如下：/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; Tr...…
-
牛客网 剑指offer 二叉搜索树的第K个结点
时间限制：1秒空间限制：32768K热度指数：4328**算法知识视频讲解题目描述给定一颗二叉搜索树，请找出其中的第k大的结点。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。题解：二叉搜索树的中序遍历是递增的，所以可以用vector保存，然后遍历vector,返回第k个，如果没有返回NULL代码如下：/*struct TreeNode { int val; struct Tre...…
-
牛客网 剑指offer 链表中倒数第k个结点
时间限制：1秒空间限制：32768K热度指数：15692本题知识点：链表**算法知识视频讲解题目描述输入一个链表，输出该链表中倒数第k个结点。两个指针，第一个指针指到第k位时，第二个指针开始操作，因为总长相同，n=k+m ; n=m+k;或者利用dfs完美解决代码如下：//dfs::/*struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { }};*/class...…
-
牛客网 剑指offer 调整数组
时间限制：1秒空间限制：32768K热度指数：15060本题知识点：数组**算法知识视频讲解题目描述输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。以空间换时间代码如下：class Solution {public: void reOrderArray(vector<int> &array) { vector<int>...…
-
牛客网 剑指offer 重建二叉树
时间限制：1秒空间限制：32768K热度指数：15861**算法知识视频讲解题目描述我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？斐波那契公式的翻版代码如下：class Solution {public: int rectCover(int number) { int b=1,a=0,sum=0; for(int i=1;i<=number;++i){ sum=...…
-
牛客网 剑指offer 求次方
时间限制：1秒空间限制：32768K热度指数：14709**算法知识视频讲解题目描述给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。本以为用循环会有什么地方不对，，，囧。。代码如下：class Solution {public: double Power(double base, int exponent) { if(exponent<0){ base=1/base; ...…
-
牛客网 剑指offer 二叉树的镜像
时间限制：1秒空间限制：32768K热度指数：12848**算法知识视频讲解题目描述输入描述:二叉树的镜像定义：源二叉树 8 / \ 6 10 / \ / \ 5 7 9 11 镜像二叉树 8 / \ 10 6 / \ / \ 11 9 7 5就是简单递归，将左孩子变成右孩子，右孩子变成左孩子，利用一个temp保存需要先换的一个即可代码如下：...…
-
牛客网 剑指offer 树的子结构
时间限制：1秒空间限制：32768K热度指数：11442**算法知识视频讲解题目描述输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）首先当A与B中任一个为空则返回false，若都不为空，查看当前A的value是否等于B的value,若是，则递归检测左孩子与右孩子，递归到B为空时，则说明B是A的子结构，A为空时，说明不是；若当前A的value不等B的value，则需比较A的左孩子，若再不等，比较右孩子。代码如下：/*struct TreeNode {...…
-
牛客网 剑指offer 二叉树的镜像
时间限制：1秒空间限制：32768K热度指数：5159本题知识点：数组**算法知识视频讲解题目描述给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]。不能使用除法。代码如下：第一种low方法class Solution {public: vector<int> multiply(const vector<int>& A) { ...…
