把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
初始思路：旋转数组必然是两个非递减序列的拼接，在连接处才可能出现前项大于后项。
class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { for(int i=0;i<rotateArray.size()-1;i++) { if(rotateArray[i]>rotateArray[i+1]) { return rotateArray[i+1]; } } return 0; } };最佳思路：二分查找分界线。
如果中间元素大于第一个元素，则中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素。移动之后，第一个指针仍然位于前面的递增数组中。如果中间元素小于第一个元素，则中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。移动之后，第二个指针仍然位于后面的递增数组中。
由于本题不是严格递增序列，还需要考虑left，right，mid指向数组元素都相同时的特殊情况，出现此情况只能顺序查找。
class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int size = rotateArray.size(); if(size == 0) { return 0; } int left = 0,right = size - 1; int mid = 0; while(rotateArray[left] >= rotateArray[right]) { if(right - left == 1) { mid = right; break; } mid = left + (right - left) / 2; if(rotateArray[left] == rotateArray[right] && rotateArray[left] == rotateArray[mid]) { return MinOrder(rotateArray,left,right); } if(rotateArray[mid] >= rotateArray[left]) { left = mid; } else { right = mid; } } return rotateArray[mid]; } private: int MinOrder(vector<int> &num,int left,int right) { int result = num[left]; for(int i = left + 1;i < right;++i) { if(num[i] < result) { result = num[i]; } } return result; } }; 斐波那契数列大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。n<=39
思路：斐波那契数列：f[n]=f[n-1]+f[n-2]。切记不要用递归，重复计算次数太多，会发生栈溢出。
用循环解决，可以开数组，需要消耗内存空间。实际只和两个变量f[n-1]和f[n-2]有关。
class Solution { public: int Fibonacci(int n) { if(n<=0) return 0; if(n==1||n==2) return 1; int t1=1; int t2=1; for(int i=3;i<=n;i++) { t2=t1+t2; t1=t2-t1; } return t2; } }; 跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路：最简单的动规。递推公式等于斐波那契数列。与上题相同，初始值稍有改动，t2=2。
变态跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
初始思路：按上题想法思考，递推公式为：f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)
class Solution { public: int jumpFloorII(int number) { int dp[number+1]; int sum=0; for(int i=1;i<=number;i++) { dp[i]=sum+1; sum=sum+dp[i]; } return dp[number]; } };最佳思路：其实递推公式可优化。
f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) + f(n-1) = f(n-1) + f(n-1)
可以得出： f(n) = 2*f(n-1) = 2^(n-1)
class Solution { public: int jumpFloorII(int number) { return 1<<--number; } }; 矩形覆盖我们可以用2＊1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2＊1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
思路：因为大矩形是2*n的，最小单位覆盖方式有两种，一个竖放和两个横放。转变为上面的跳台阶问题。
二进制中1的个数输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路：一道常见的笔试题，给出代码求答案那种233。
class Solution { public: int NumberOf1(int n) { int count=0; while(n) { n=n&(n-1); count++; } return count; } };