剑指offer上的题目，在牛客网上刷题通过，下面记录相关思路。
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
求幂运算需要注意以下几种情况：
常规求幂运算采用循环或者递归的方法，时间复杂度为O(n)，效率不高，这里介绍快速幂算法。
例如求4^11，将指数11写成二进制形式为1011，11 = 1x2^3 + 1x2^1 + 1x2^0，则4^11 = 4^(2^3) x 4^(2^1) x 4^(2^0) = 4^8 x 4^2 x 4^1。最后得到的表达式的三个乘积项，分别对应于指数的二进制位中的三个非0位。由此可见，对于指数的每一个二进制位，如果该位为1，则将其所对应的项乘进去，而每往高位进一位，对应的项就翻倍（变为前一项的平方），最后连乘所得到的结果即为最终的幂。这就是快速幂算法。
对比与普通的求幂方法，快速幂算法的循环次数为指数的二进制表示的有效位数，即log(n)，时间效率较高。
剑指offer上的题目，在牛客网上刷题通过，下面记录相关思路。
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
涉及到二进制的表示，首先应该想到的是位运算。对于整数可以将其和1进行与运算，如果二进制最后一位为1，则运算结果为1，否则为0，然后将整数右移一位，继续用此方法检测下一位，直到最终整数为0。该方法对非负数有效，如果输入为负数，在右移过程中会自动补1，程序会陷入死循环。
其实主要是要实现每检测一位，就将该位去除（或清0），不必要再保留。如果不采取移位操作来实现，那么可以采用位运算清0。将整数减1后，其二进制表示中最后一位1将变为0，后面的其他位全部由0变为1，如果再与该整数原来的值做与运算，则最后一位1将变为0，其余位均保持不变，达到了检测一位就清除一位的效果。重复上述步骤，直到整数变为0，重复步数即为1的个数（一次清除一个1）。
剑指offer上的题目，在牛客网上刷题通过，下面记录相关思路。
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
印象中，排序数组的元素查找一向以二分法最优，这道题虽然略有不同，但基本思想是一致的。数组旋转前是非递减的，则第一个元素即为最小数字、旋转后最小数字位于数组中间部分，将数组分割为两部分，最小数字左边的元素所构成的数组是非递减的，而它和右边的元素所构成的数组也是非递减的，并且前面子数组的元素都大于后面子数组的元素。题目所给的数组是排序的，并且最小元素是两个子数组的分界点，可以尝试用二分法查找最小元素。
剑指offer上的题目，在牛客网上刷题通过，下面记录相关思路。
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
首先需要明确二叉树的几种遍历方法：
前序遍历的特点是不管在哪颗（子）树，首先访问其根节点。那么很容易知道，在前序遍历结果中，各个（子）树的根节点总是位于左节点与右节点前面的，也就是说前序遍历序列的第一个元素即为根节点，也就是题目中值为1的节点。由中序遍历顺序可知，首先访问左子树，遍历完根节点左边的所有节点后，再去访问根节点，最后去遍历根节点右边的所有元素。由此可得出规律，在中序遍历序列中，根节点左边的元素为左子树节点值，右边的元素为右子树节点值。
前面已知1为根节点，则由中序遍历规律得出左子树节点（中序遍历序列）：{4,7,2}，右子树节点（中序遍历序列）：{5,3,8,6}，即左子树有3个节点，右子树有4个节点。对比树前序遍历序列，根节点后面紧跟着的3个元素即为左子树节点，再接着的4个元素为右子树节点，可知左子树的前序遍历序列：{2,4,7}，右子树的前序遍历序列：{3,5,6,8}。
在分别得到左右子树的前序遍历序列和中序遍历序列后，可采取递归的方法，再次对左右子树执行上述分析步骤。最后直到两个遍历序列中只有一个元素时，即达到叶子节点，构建该节点并返回。经过层层递归后，二叉树构造完毕，函数最终返回二叉树的根节点。
剑指offer上的题目，在牛客网上刷题通过，下面记录相关思路。
我们可以用2x1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2x1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
题目一看就很熟悉，在hdu上做过，同样是一道利用递推求解的题目。借用一下hdu的题目图片：
采取同样的思想，设铺满规模为2*n的矩阵方法有f(n)种。考虑最后一块2x1的小矩阵如何放置：
2*(n-1)的矩阵上竖着放一块2x1小矩阵2*(n-2)的矩阵上放一块规模为2x2的矩阵则可得到递推公式：
f(n) = f(n-1) + f(n-2)
且f(0) = 0，f(1) = 1，f(2) = 2
不难看出这是个斐波那契数列。