title: 剑指offer解题思路

剑指offer解题思路

date: 2016-06-06 20:31:12
算法

剑指offer上面的题目十分经典，虽然已经刷了一遍，但是还是有必要将解题思路重新整理一下，好记性不如烂笔头。所有题目会给出解题思路，部分题目会给出实现代码。

1. 二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：取右上角那个数并判断，如果该数大于要查找的数，删除所在行；如果小于要查找的数，删除所在列，如果等于，返回true。

2. 替换空格

请实现一个函数，把字符串中的每个空格替换成"%20"。例如输入"we are happy."，则输出"We%20are%20happy."。
思路：先遍历一遍字符串，计算空格出现的个数，从而计算出新字符串的长度。然后用两个指针分别指向原字符串的末尾和新字符串的末尾，然后从末尾开始到头部开始复制。

3. 从尾到头打印单链表

输入一个链表的头结点，从尾到头反过来打印出每个结点的值。

思路：栈或者递归实现。

4. 重建二叉树

输入某二叉树的前序和中序遍历的结果，请重建改二叉树。假设输入的前序和中序遍历的结果中都不含重复数字。

思路，采用递归或者迭代的思路。

5. 用两个栈实现队列

用两个栈实现一个队列。实现它的两个函数appendTail和deleteHead。分别完成在队列尾部插入结点和在队列头部删除结点的功能。

思路：两个栈，一个栈用来入栈，模仿队列的尾部插入动作，另一个栈用来出栈，模仿队列的头部删除操作，如果出栈为空，则将入栈中的数字按序pop出，并push进入出栈中。

6. 旋转数组的最小数字

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
思路：利用二分查找，如果中间的数比两边的数都要大，那么最小值在右边数组，递归去右半部分查找；如果中间数比两边都要小，那么最小值在左边，递归去左边数组查找；如果，中间的数和两端的数相等时，此时无法判断最小值所在区域，只能采用顺序查找了。

public class Solution {
    //这里的数组是非递减序列，因此有可能存在重复元素
    public int minNumberInRotateArray(int [] array) {
         if (array.length <= 0) {
             return 0;
         }
         if (array.length == 1){
             return array[0];
         }
         int low = 0,high = array.length - 1;
         return findMin(array,low,high);   
    }
    public int findMin(int[] array,int low,int high){
        int mid = (low + high)/2;
        while(low <= high) {
            mid = (low + high)/2;
            if (array[mid] > array[low] && array[mid] < array[high]) {
                return array[low];
            } else if (array[mid] > array[low] && array[mid] > array[high]) {
                low = mid + 1;
            } else if (array[mid] < array[low] && array[mid] < array[high]) {
              //这里表示较小数组占多数，到左边找最小值
                high = mid ;                               
            } else  {
                int t1 = findMin(array,low,mid - 1);
                int t2 = findMin(array,mid+1,high);
                if (t1 <= t2) {
                    return t1;
                } else {
                    return t2;
                }
            }
        }
        return array[mid];
    }
}

7. 青蛙跳台阶问题：一只青蛙一次可以跳上1级台阶，也可以跳上2级...，它也可以跳上n级，此时该青蛙跳上一个n级台阶总共有多少种跳法？数学归纳法可以证明$f(n) = 2^{n - 1}$。

8. 二进制中1的个数

题目：请实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如，把9表示成二进制1001，有2位是1。因此，如果输入9，该函数输出2。
思路：考察位运算， 将n与(n-1)做&运算，每次都会将最右边的1变成0，那么有多少个0就需要做多少次与运算，这样就可以计算出来n中1的个数。假设n中1的个数为K，该算法时间复杂度为$O(K)$

   public int numberof1(int n){
         int count = 0;
         while(n != 0) {
            count++;
            n = n&(n - 1);
         }
         return count;
   }

9. 数值的整次方

题目：实现函数double Power(double base,int exponent),求base的n次方，不得使用库函数，不考虑大数问题。
思路：第一个需要考虑各种非法输入问题，第二个需要考虑解得效率问题，这里求base的n次方，可以考虑使用分治法，先求base的n/2次方，然后相乘。

10. 打印1到最大的n位数

题目：输入数字n，按顺序打印出从1到最大的n位10进制数。比如，输入3，则打印出1,2,3一直到最大的3位数即999。
思路：需要注意的是如果输入的n过大，可能导致无法表示的大数问题。这里采用字符串来表示大数。字符串模拟加法操作

   public void printMaxNNumber(int n) {
       char[] array = new char[n];
       for (int i = 0;i < n;++i) {
           array[i] = '0';
       }
       int carry = 0;
       while(!(array[0] == '9' && carry[0] == '1')){
       }
   }
   public void Increment(cahr[] array){
   }