一、题目描述 JZ38二叉树的深度题目大意：给定一棵二叉树,求该数的高度 二、算法1（自底向上递归） 算法思路 1.总体思路：根据题意,树的深度是从根节点到叶子结点的所有路径中最长路径的长度,要到达叶子结点,要么走左子树要么走右子树,因此对于以某个结点为根节点构成的子树来说,它所表示的二叉树的深度就是以它右儿子为根的子树的深度+1和以它左儿子为根的子树的深度+1中的最大值2.实现细节：对于空结点,它的深度为0,自底向上递归,即先递归到最底部,再逐步返回最优值至上层结点,还有一种写法是自顶向下递归,读者可以尝试写一下 代码实现（C++11） class Solution { public: in...

一、题目描述 JZ40数组中只出现一次的两个数字题目大意：一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字注意审题：题目保证有两个数字只出现一次,其余数字出现两次,并且返回的结果中较小的排在前面 二、算法1（排序） 算法思路 1.总体思路：先对数组从小到大排序,这两相同的两个数就相邻了2.采用类似双指针的思想,当下一个数和自身相同时,移动两步;当下个数与当前数不同时,则将当前数加入答案,移动一步 代码实现（C++11） class Solution { public: vector<int> FindNumsAppearOnce(ve...

一、题目描述 JZ37数字在升序数组中出现的次数题目大意：找到指定数字在升序数组中出现的次数注意审题：升序数组 二、算法1（暴力遍历） 算法思路 1.总体思路：直接遍历一次数组,当遇到指定数字时计数即可2.这种方法虽然直观,但是并没有用上题目中提供的升序这一信息,因此一般不是最优解 代码实现（C++11） class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int ans = 0; for(auto & d : data) ans += d == k; return ans; } }; 时...

一、题目描述 JZ36两个链表的第一个公共结点题目大意：给定两个链表A和B,他们尾部的几个结点可能是相同的,我们需要返回第一个公共结点的指针注意审题：两个链表也可以没有公共结点,此时返回空指针即可 二、算法1（双指针） 算法思路 1.总体思路：我们可以分别用两个指针指向链表的头结点,然后一步一步地向后移动,当两个指针指向相同的结点时,直接返回即可2.但是注意一个问题,由于两链表的长度不一定是相同的,因此我们需要预处理一下,保证两指针的相对位置重合3.实现方法：先计算一下两条链表的长度len1, len2;若len1 > len2,则p1指针向后移动len1 - len2步;若len1 &...

一、题目描述 JZ10矩形覆盖题目大意：我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，从同一个方向看总共有多少种不同的方法？注意审题: 无重叠,重同一个方向看 二、算法1（递归） 算法思路 1.总体思路：根据题意,我们可以假设从左往右看,由于题目给定的小矩形的数量,以及大矩形的形状,因此我们可以发现每次,我们只能有两次选择,要么竖着放一个,要么横着放两个2.递归边界就是当小矩形用完时结束 代码实现（C++11） class Solution { public: int rectCover(int number) { i...

一、题目描述 JZ9跳台阶扩展问题本题有一个简单版本,建议先做一下题目链接题目大意：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。注意审题：每一种跳法都是顺序相关的,即先跳一步再跳两步不等价于先跳两步再跳一步 二、算法1（递归） 算法思路 1.解题思路：暴力尝试每一种走法,到达终点后记为一种方案2.实现方式：递归时我们需要知道当前处于第几级台阶,以及目标是到达第几级台阶,因此递归函数接受两个参数,一个是当前所在的位置,一个是目标位置,递归边界即当前所在位置为目标位置时结束,每个阶段尝试不同的步数即可.3.这种解法的时...

一、题目描述 JZ6旋转数组的最小数字题目大意：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。注意审题：给出的所有元素都大于0，若数组大小为0，请返回0 二、算法1（暴力遍历） 算法思路 总体思想：遍历一遍数组并不断更新最小值即可,可以拿第一个元素作为初始的最小值 代码实现（C++11） class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { ...

一、题目描述 JZ8跳台阶题目大意：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 二、算法1 (递归） 算法思路 1.总体思路：暴力尝试所有的走法2.递归边界即当目前处于第n个台阶时结束 代码实现 （C++11） class Solution { public: int jumpFloor(int number) { int ans = dfs(0, number); return ans; } int dfs(int start, int end){ if(start == end) return 1; if(star...

斐波那契数列题目链接  一、题目描述 JZ7斐波那契数列题目大意：求斐波那契数列数列的第n项是多少注意审题：由于题目中函数的返回值是int类型，可知范围一定不会超过int型所能表示的范围 斐波那契数列的定义如下：  二、算法1 (递归） 算法思路 1.总体思路：递归2.递归边界即F(0)和F(1), 采用自底向上的递归方式, 先递归到边界，然后将结果不断叠加返回即可 代码实现 （C++11） class Solution { public: int Fibonacci(int n) { if(n == 0) return 0; if(n == 1) return 1; return Fibon...