剑指Offer

题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 解题思路 递归，由上一步到这一步青蛙跳了一级或跳了两级，当前台阶数为n，那跳n级台阶的方法数就是问跳n-1和跳n-2级楼梯方法数相加。由此可看出，这是一个斐波那契数列。 结束条件就是当n=1时，只有一种方法（跳一级）；n=0时，0种方法；当n=2时，有两种方法（一次跳一级，跳两次；一次直接跳两级） 代码实现 class Solution { public: int jumpFloor(int number) { if

问题描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。 求该青蛙跳上一个n级的台阶总共有多少种跳法。 解题思路： 每一次调用函数都是查找这个楼梯数有多少种跳法，如果楼梯数已为0， 则表明只有这一种跳法，也就是没有下一步的跳法了； 若不为0，则设这一步会跳1、2、3~n阶，然后将跳完这一步的 下一步跳法的跳法相加，返回结果。 示例： n=4 1 1 1 1 1 1 2 1 2 1 1 3

问题描述 我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。 请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形， 总共有多少种方法？ 解题思路 n=1 - 只有横放一个矩形一种解决办法 n=2 - 有横放一个矩形，竖放两个矩形两种解决办法 n=3 - n=2的基础上加1个横向，n=1的基础上加2个竖向 n=4 - n=3的基础上加1个横向，n=2的基础上加2个竖向 · · · n=n - n

题目描述 请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 解题思路 遍历字符串，遇到空格，就把空格后面的所有数后移两个位置； 空格处放'%'，空出来的两个位置放'2'，'0' 代码实现 class Solution { public: void replaceSpace(char *str, int length) { if (length <= 0 || str

问题描述： 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 算法分析： push： 1.将数据压入stack1； pop： 1.将stack1中所有数据弹出到stack2； 2.将stack2中第一个数弹出设置为返回值； 3.将stack2中所有数据弹出到stack1； 4.将返回值返回 代码实现 class Solution { public: void push(int node) { stack1.push(node); } int pop() { while (!stack1.empty(

问题描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 算法分析 这个比较基础，懂斐波那契数列的意思就能写得出来了，不多说。需要注意的是，在牛客网上刷这题的时候不能用递归，递归会超时。 代码实现 class Solution10 { public: int Fibonacci(int n) { if (n == 0){ return 0; } if (n == 1){ return 1; } int r = 0; int

问题描述 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 算法分析 本题需要用到位运算 当传进来一个正整数n时，假设n=3，二进制表示为 011 011&1 = 1 一个1， n右移1位 01&1 = 1 又一个1， n右移1位 共需移31次 传进来一个负整数n，假设n = -2 二进制表示为 原码：10000000 00000000 00000000 00000010 反码：11111111

问题描述： 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。 背景知识： 二叉搜索树（Binary Search Tree），又叫二叉排序树：或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。 算法描述： 将数列分为三段，最后一段是最后一个数，也是树的根；第一段小于根，第二段大于根： | 小于根 | 大于根 | 根 | 然后小于根和大于根这两段又都是树，就可以递归求解了。 当树的大小为0或1时，返回true。

问题描述 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 算法分析 1. 如果 root 等于 输入数，将root放在返回数组里返回；如果root大于输入数，返回空值； 如果root小于输入数，将root放在数组里，输入数自减root，一同随root的子树递归； 2. 如果输入数为0了且左右子树都为空，即为叶子节点，则这条路径可行，返回数组； 如果 root 没有子树了，同时输入数还没为0，说明此路不通，返回NULL。 代码实现 /* struct TreeNode { int val;

题目描述 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 算法描述 使用递归，分别去将当前节点的左右子树变成双向链表，然后获取左边链表的最后一个元素，当前元素的左指针指向它，它的右指针指向当前元素；右边链表的第一个元素，它的左指针指向当前元素，当前元素的右指针指向它；然后从当前元素开始，不断从左边找，找到第一个元素，返回此元素的指针。 总结： 对这种涉及到二叉树的题目，可以使用测试驱动开始，先写测试用例，然后再编码。 代码实现 #include using std::cout; using std::cin; using std:

题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 代码实现 class Solution { public: vector Permutation(string str) { vector r; if(!str.size()) return r; sort(str.

题目描述 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2} 。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。 算法描述 打擂算法：多的留下，少的走 先找出数最多的，然后找有多少个数，最后判断数目是否超过了一半， θ(n)时间复杂度 代码实现 class Solution { public: int MoreThanHalfNum_Solution(

题目描述 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4, 直接使用sort排序，然后返回前k个数： class Solution { public: vector GetLeastNumbers_Solution(vector input, int k) { sort(input.begin(), input.end()); vector

问题描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？ 算法分析 有一个temp用于探路，sum负责保存最终值，初始都为数组第一个数； 每一轮循环里， temp如果小于0，则temp为当前数；否则temp等于temp加上当前数；

题目描述 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321} ，则打印出这三个数字能排成的最小数字为321323。 -------------------------------------------------------------------------------- 将数字转化为字符串，然后对字符串进行快速排序 class Solution { public: string PrintMinNumber(vector numbers) { string r; vector sr; for(int i=0;i

问题描述： 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 算法分析： 传进来一个正整数n，假设n=3，二进制表示为 011 011&1 = 1 一位， n右移1位 01&1 = 1 两位， n右移1位 共需移31次 传进来一个负整数n，假设n = -2 二进制表示为 原码：10000000 00000000 00000000 00000010 反码：11111111 11111111

问题描述： 输入两个整数序列，第一个序列表示栈的压入顺序， 请判断第二个序列是否为该栈的弹出顺序。假设压入 栈的所有数字均不相等。例如序列1,2,3,4,5是某栈 的压入顺序，序列4,5,3,2,1是该压栈序列对应的 一个弹出序列，但4,3,5,1,2就不可能是该压栈序列 的弹出序列。 算法描述： 首先判断两个序列的元素数目是否相等， 不相等，则肯定不是； 相等，进入下一步： 遍历Pop，每遍历一个数，先将Push数组里的压入栈，

问题描述 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。 算法分析 每个位置上的丑数都是某个丑数乘上2或3或5的结果，看如下示例： 第1个丑数是 1, 第2个丑数是 1 * 2 = 2, 第1个丑数*2 第3个丑数是 1 * 3 = 3, 第1个丑数*3 第4个丑数是 2 * 2 = 4, 第2个丑数*

问题描述 在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符的位置。若为空串，返回-1。位置索引从0开始. 示例： 输入：sabcdsdf 输出：1 算法描述 定义一个52个元素的整型数组aCount，初始化为0，每个字母(大小写)依次对应一个,记录字母出现的次数； 定义一个52个元素的整型数组aPos，初始化为-1，每个字母(大小写)对应一个，记录字母第一次出现的位置； 每次遍历一个到字母，aCount数组里对应字母加1，判断目前aCount数组里该字母的计数是否为1，是则在aPos里记录字母出现位置；若已不是1，