题目难度：中等题目考察：二叉树，递归题目内容：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 题目分析实际上就是给了中序和前序建立二叉树 首先需要知道前中后序的遍历方式：前序遍历：根左右中序遍历：左根右后序遍历：左右根发现前序遍历的第一个就是根，这就找到了根，可以在中序中找到根，根左边就是左子树，根右边就是右子树下面继续看先序，2，中序分为了4 7和空，说明4 7在以2为根的左子树，右子树为空这时候我们发现...

题目难度：中等考察内容：链表题目内容：输入一个链表，反转链表后，输出新链表的表头。 问题分析首先较为简单的思路是开辟额外空间，去保存链表然后反转，明显用vector保存反转最为方便，直接用stl里的reverse(v.begin(), v.end());即可然后链表以此指向每一个元素即可算法1（构造）下面给出代码 class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead) return nullptr; //特判空链表 vector<Li...

题目难度：中等题目考察：链表题目内容：输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。如果该链表长度小于k，请返回一个长度为 0 的链表。 题目分析：首先一个链表不遍历一遍无法知道长度，所以这题时间复杂度最低是O(n),并且题目要找到倒数第k个数，如果我们知道了链表有n个数，倒数第k个实际上就是正数第n-k+1个。算法1：遍历正数第n-k个就很容易找出了，只需要遍历一遍数组即可下面要考虑链表长度小于k要返回一个空链表下面给出代码 /** * struct ListNode { * int val; * struct ListNode *n...

题目难度：中等题目内容：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。题目分析：给定一个数组，要求奇数在前，偶数在后，并且相对位置不变，首先应该会想到类似排序的思想来交换，但是会出现什么问题，如图所示下面给出一个较为清楚，代码简洁的思路，定义一个数组，第一次遍历加进去所有奇数，第二次遍历加进去所以偶数，这时就完成了题目要求，证明如下算法1（辅助数组加遍历）下面给出代码 class Solution { public: vector<int> reOrde...

题目难度：简单考察内容：暴力，二分题目内容：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。问题分析首先可以O(n)枚举求出最小值，时间复杂度O(n)，空间复杂度O(1)代码如下 class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int ans=1e9; //记录最小值 for(int...

题目难度:中等考察内容：快速幂，递推题目内容：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。题目分析首先有负数次幂，可以进行转化，a^(-b)=1/a^b所以只用考虑a^b即可，很明显可以递推算法1（递推）思路很简单，在代码中体现 class Solution { public: double Power(double base, int exponent) { double ans=1;//记录...

题目难度：中等题目考察：数学，二进制题目内容：输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。 题目分析： 首先考虑正数，负数的二进制是正数的补码，可以通过正数计算得出对于正数，即将数拆分成二进制，统计1的个数有几种方法算法1（辗转相除）首先思考如何统计10进制下的每一位，例如n=1234，最后一位即是n%10，然后把4”删除”，即n/=10,这时候n=123，重复上述操作即可二进制其实同理，和十进制操作一样，例如n=14如图即可统计出1的个数算法2（位运算）n>>1即在二进制下右移一位，所以可以遍历一遍0到31，统计1的个数 for(int i=0;i&lt...

题目难度：中等考察内容：递推，dp，记忆化搜索题目内容：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，从同一个方向看总共有多少种不同的方法？*题目分析：**一个12的矩形只有两种放的方式，横着和竖着，如果一个小矩形横着放，一定是两个矩形一起横着放显然黄色的矩形没有其他放法了，也就是说最后一排只有两种放置情况对于情况1，f[n-1]列已经是确定的了，所以f[n]+=f[n-2]对于情况2，f[n]+=f[n-1]所以f[n]=f[n-1]+f[n-2]惊奇的发现，这是一个斐波那契数列，容易计算f[1]=1,f[2]=2于是有三种解法如下，...

题目难度：简单题目考察：dp，记忆化搜索，递推题目内容：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。首先有一题限制了一次可以跳一步或者两步传送门在那一题状态转移方程为f[i]=f[i-1]+f[i-2]这一题是可以跳任意步，很容易类比出来f[i]=f[0]+f[1]+f[2]+...+f[i-1],f[0]表示从起点一次跳n步，f[1]表示从第一格一次跳n-1格，以此类推既然有了递推表达式，所以一定可以用递归来求解算法1（递归） class Solution { public: int jumpFloorI...

题目难度：中等考察内容：递推，dp，记忆化搜索题目内容：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。题目分析：题目问跳到n一共有多少种跳法，考虑n可以从哪跳上来，从n-1跳一步,从n-2跳两步，所以f[n]=f[n-1]+f[n-2]，这时候发现这和斐波那契数列递推表达式完全一样，斐波那契不同点在与斐波那契f[0]=0,f[1]=1，而这题没有给出，但是我们可以求出来，f[1]=1,f[2]=2,因为到第一个台阶只有1种跳法， 跳到第二个台阶有两种跳法，这时候递推即可。思考通过这题的解法，我们应该思考到dp问题的解法一般...

题目难度：入门考察内容：递推，dp题目内容：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。题目分析首先我们都知道斐波那契数列的递推式子为f[i]=f[i-1]+f[i-2],我们要知道f[n]就要知道f[n-1],f[n-2]，要是到f[n-1]就要知道f[n-2],f[n-3]。。。很明显这可以用递归来解决，递归的终止条件就是我们知道的f[0]=0,f[1]=1于是我们有了一种解法算法1（递归）代码如下 class Solution { public: int Fibonacci(int n) { i...

题目难度：简单考察内容：链表题目简介：给两个非递减单链表l1, l2，合并为一个非递减的单链表。 1.问题分析给了两个非递减的单链表，合并成一个非递减的单链表，这个问题和归并排序的思想很像回忆下归并排序，(l,mid)和(mid+1,r)排好序后合并，下面给出代码 void m_sort(int q[],int l,int r) { if(l>=r)return ; int mid=l+r>>1; m_sort(q,l,mid),m_sort(q,mid+1,r); int i=l,j=mid+1,k=0; while(i<=mi...

题目难度：较难考察知识：树，递归题目大意：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 1.问题分析首先考虑如何判断B是A的子结构，在A的遍历过程中出现了B即说明B是A的子结构，需要注意题目说明了空树不是任意一棵树的子结构，先不考虑空树，想要确实B是否是A的子结构应该如何判断，当A的某子树treeA的value和B的value相同并且和的左右子树也是treeA的左右子树的子结构，这时可以判断B是A的子结构，否则判断B是否是A的左右子树的子结构，如图具体做法为算法设计从上面的分析可以发现，涉及了很多调用子树的情况，所以使用递归可以很方便的处理子树问题...

题目难度：简单考察内容：树,递归，三变量交换题目简介：操作给定的二叉树，将其变换为源二叉树的镜像。算法设计关于树的题目大多和递归有关，这和树的结构有关，子树同样是一棵树，这种采用递归会使代码非常简洁，注意要考虑空树的情况对于这题，实际上就是将左右子树交换如何交换？回想怎么交换两个数a,b，可以swap(a,b)，可以用三变量交换法，c=a,a=b,b=c同理，交换左右子树也可以采用三变量交换法不同的是，交换的左右子树应该是交换后的，如图所示 TreeNode *ch=Mirror(pRoot->right);//ch=右子树，这里等于的右子树需要也交换，所以要递归处理 ...