剑指offer一

最近在看《剑指 offer》，写几篇文章来记录一下，今天有以下几道算法题：

• 斐波那契数列
• 数组中重复的数字
• 二维数组中的查找
• 替换空格

斐波那契数列

写一个函数，输入 n，求斐波那契数列的第 n 项。

递归解法重复计算太多，效率太低，这里我们使用时间复杂度为 O(n)的方法。

解题思路

从下往上计算，首先根据 f(0)和 f(1)算出 f(2)，再根据 f(1)和 f(2)算出 f(3)……. 以此类推就可以算出第 n 项。

代码实现

public class Fibonacci {public static long fibonacci(long n){if (n<0)  throw new RuntimeException("无效的输入");
        if (n==0) return 0;
        if (n==1) return 1;

        long fibOne=0;
        long fibTwo=1;
        long fibSum=0;

        for (int i = 2; i <= n; i++) {            
            fibSum=fibOne+fibTwo;
            fibOne=fibTwo;
            fibTwo=fibSum;
        }
        return fibSum;
    }
}

数组中重复的数字

在一个长度为 n 的数组里的所有数字都在 0 到 n - 1 的范围。数组中某些数字是重复的，但不知道有几个数字重复，也不知道每个数字重复的次数。请找出数组中任意一个重复的数字。例如如果输入长度为 7 的数组{2,3,1,0,2,5,3}, 那么对应的输出是重复的数字 2 或者 3。

解题思路

我们注意到数组中的数字都在 0 到n-1的范围内。如果这个数组中没有重复的数字，那么当数组排序后数字 i 将出现在下标为 i 的位置。

步骤

从头到尾扫描这个数组中的每个数字。当扫描到下标为 i 的数字的时候，首先比较这个数字 (用m 表示）是不是 i。如果是，接着扫描下一个数字。如果不是，再拿它和第 m 个数字进行比较。如果它和第 m 个数字相等，就找到一个重复的数字（该数字在下标为 i 和 m 的位置都出现了）。如果它和第 m 个数字不想等，就把第 i 个数字和第 m 个数字交换，把 m 放到属于它的位置。接下来再重复这个比较，交换的过程，直到发现一个重复的数字。

以数组{2，3，1，0，2，5，3}为例来分析找到重复数字的步骤。数组的第 0 个数字（从 0 开始计数，和数组的下标保持一致）是 2，与它的下标不相等，于是把它和下标为 2 的数字 1 交换，交换后的数组是{1，3，2，0，2，5，3}。此时第 0 个数字是 1，仍然与它的下标不相等，继续把它和下标为 1 的数字 3 交换，得到数组{0，1，2，3，2，5，3}。此时第 0 个数字为 0，接着扫描下一个数字，在接下来的几个数字中，下标为 1，2，3 的三个数字分别为 1，2，3，他们的下标和数值都分别相等，因此不需要做任何操作。接下来扫描下标为 4 的数字 2. 由于它的值与它的下标不相等，再比较它和下标为 2 的数字。注意到此时数组中下标为 2 的数字也是 2，也就是数字 2 和下标为 2 和下标 4 的两个位置都出现了，因此找到一个重复的数字。

代码实现

public class Test {

    public static int duplication;// 用来保存重复数字
    
    public static boolean duplicate(int[] arr) {
        // 判断输入是否合法
        if (arr == null || arr.length == 0) {return false;}
        for (int i = 0; i < arr.length; i++) {if (arr[i] < 0 || arr[i] >= arr.length) {return false;}
        }
        // 核心代码
        for (int i = 0; i < arr.length; i++) {while (arr[i] != i) {
                // 如果两个数相等则返回 true
                if (arr[i] == arr[arr[i]]) {duplication = arr[i];
                    System.out.println(arr[i]);
                    return true;
                }
                // 否则交换数字
                int temp = arr[i];
                arr[i] = arr[temp];
                arr[temp] = temp;
            }
        }
        return false;
    }
}

二维数组的查找

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

解题思路

(1)首先选取数组中右上角的数字。如果该数字等于要查找的数字，则结束查找过程。
(2)如果该数字大于要查找的数字，则剔除这个数字所在的列。
(3)如果该数字小于要查找的数字，则剔除这个数字所在的行。

代码实现

public class Test {public static boolean find(int[][] matrix, int number) {if (matrix == null || matrix.length < 1 || matrix[0].length < 1) {return false;}
 
        int rows = matrix.length; // 数组的行数
        int cols = matrix[1].length; // 数组行的列数
 
        int row = 0; // 起始开始的行号
        int col = cols - 1; // 起始开始的列号
 
        while (row >= 0 && row < rows && col >= 0 && col < cols) {if (matrix[row][col] == number) { // 如果找到了就直接退出
                return true;
            } else if (matrix[row][col] > number) {col--; // 列数减一，代表向左移动} else { // 
                row++; // 行数加一，代表向下移动
            }
        } 
        return false;
    } 
}