算法和数据结构往往是紧密相关的，数据结构关注的是数据的物理/逻辑结构物与组织方式，算法关注的是数据的操作方式。对于任何程序员来说，不能局限于蛮力法思维，像常用的查找和排序算法、递归、回溯方法以及分治、减治、动态规划等思想都应该熟练掌握，并力求做到实际问题下的举一反三。

递归和循环

在我个人看来，递归和循环本身不是一种算法思维，而是算法具体执行的两种形式，它们往往结合在其他算法中。递归往往适用于具有相同子问题结构的问题，关注的是结果；循环则关注的是具体的过程，因而递归通常比循环更简洁。两者都需要设置终止条件，很多情况下递归可以转换为循环，但有些循环没有显示的递归表示。此外，一些情况下递归会导致额外重复的计算，需要根据问题具体判断。

面试题10：斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

解题思路

很经典的题目，这一题其实是结合动态规划的思想来考的，如果直接根据公式f(n)=f(n-1)+f(n-2),n>2用递归来写会产生很多次重复计算，需要使用循环+记忆化的方式避免重复计算。另外青蛙跳台阶、矩形覆盖的问题本质上也是斐波那契数列，下面给出几种写法。

递归解法：

public int JumpFloor(int target) {
    if (target==2||target==1){
            return target;
    }
    return JumpFloor(target-1)+JumpFloor(target-2);
}

动态规划解法，使用数组自底向上存储每一个res[n]：

public int JumpFloor2(int target){
    int[] res=new int[target+1];
    res[1]=1;
    res[2]=2;
    for (int i=3;i<=target;i++){
        res[i]=res[i-1]+res[i-2];
    }
    return res[target];
}

空间优化：由于每次计算只需要前面连续两个数的值所以可以只用两个整形变量来暂存，将空间复杂度由O(n)降为O(1)。

public int JumpFloor3(int target){
    if (target==2||target==1){
        return target;
    }
    int left=1,mid=2,right=0;
    for (int i=3;i<=target;i++){
        right=left+mid;
        left=mid;
        mid=right;
    }
    return right;
}

查找和排序

查找和排序是程序中经常用到的算法。查找算法不多，我们应掌握顺序查找、二分查找、哈希表查找和排序树查找（后面两个是实际常用的索引原理）；而排序算法有很多，务必要对插入、冒泡、归并、快排等排序算法的原理、空间复杂度、时间复杂度（最好情况、最坏情况、平均情况）以及稳定性做到烂熟于胸。

关于排序算法可以参考华东师范大学韦阳同学的这篇博客:十大经典排序算法整理汇总 (opens new window)

面试题11：旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

示例

输入：
数组{3,4,5,1,2}（为{1,2,3,4,5}的一个旋转）
输出：
该数组的最小值1

解题思路

本题最直接的思路自然是暴力法从左向右遍历，遇到后一个值比前一个值小时就找到了最小数字，当然这样时间复杂度为O(n)没有用到数组已经排序的性质。本题考查的是对二分查找的深刻理解，并不一定是指定目标的值来直接查找，而是可以指定目标的特性与该种特性对应的范围。（面试题3的拓展：不改动数组不使用额外O(n)空间找出数组中的重复数字也是采用了这种思维）

在本题中，有一些旋转数组后的特例需要处理（首尾相等、整个数组值都一样、旋转搬动的元素个数为0），先考来虑常规情况。这里要找的数就不知道具体数值，仅仅知道“值最小”这一特性。根据这一特性，在旋转数组中采用二分的方式比较中点的值与数组首尾值的大小就能确定该最小值的范围是在左半部分还是右半部分，在左半部分则high=mid，在右半部分则low=mid+1。就这样不断缩小左右边界直至左边界的值小于右边界的值，此时左边界值array[low]就是最小值。

public int minNumInRotateArray(int[] array){
    switch (array.length){
        case 0:
            return 0;
        case 1:
            return array[0];
    }
    int low=0,high=array.length-1;
    //首先处理特殊情况将递增序列左侧和递减序列右侧可能相同的值排除在外
    //如果数组中的值相同那么此循环结束后下一循环不会执行直接返回一个值
    while(array[low]==array[high]&&low<high){
        low++;
        high--;
    }

    while (array[low]>array[high]){
        int mid=(low+high)/2;
        if (array[mid]>=array[low]){
            //左边界设为mid+1因为array[mid]本身不可能是最小值
            low=mid+1;
        }else if(array[mid]<=array[high]){
            //右边界设为mid因为array[mid]本身可能就是最小值
            high=mid;
        }
    }
    /*1.最后一次while循环中array[mid]>=array[low]>array[high],
    而下一次循环入口检查array[low]即array[mid+1]不满足>array[high],
    说明此时的array[mid+1]小于array[mid]，就是要找的最小值
    2.最后一次while循环中array[mid]<=array[high]<array[low],
    而下一次循环入口检查array[high]即array[mid]不满足<array[low],
    并且这种情况下low没有变动，这就互相矛盾，说明最后一次循环不可能走else分支*/
    return array[low];
}

回溯法

回溯是一种蛮力法的升级版，因为虽然同样是一种全量搜索，但回溯法适用于由多个具有相同结构（有同样多种选择）的步骤组成的问题，每步重复选择直至停止状态。这一点就与递归的特性相吻合，但达到的停止状态可能不是想要的，于是回溯到上一步继续作别的选择。知道找到理想的结果或者搜索完都没有找到理想结果。

面试题12：矩阵中的路径

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。

示例

输入：
矩阵
a   b   c   e
s   f   c   s
a   d   e   e
目标路径 bcced
输出：
true

解题思路

遍历矩阵，以每一个点为入口调用找路径的方法，发现目标路径则返回true。而在找路径的方法中，传入当前在矩阵中的位置、要匹配的字符串以及目前匹配到的位置，只有对应位置匹配且继续四个方向递归中有结果返回true时才返回true。此外，还需要增加一个全局的布尔矩阵用于标记搜索过程中某点是否已被访问过。如果四个方向的递归结果都是false则清除已访问标记并返回false回溯至上一层。

public class PathInMatrix {
    boolean[]isVisited=null;
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str){
        isVisited=new boolean[rows*cols];
        for(int i=0;i<rows;i++){
            for (int j=0;j<cols;j++){
                if (findPath(matrix,rows,cols,str,i,j,0))
                    return true;
            }
        }
        return false;
    }

    public boolean findPath(char[] matrix, int rows, int cols,char[] str,int currentRow, int currentCol, int matchCursor){
        if(matrix[cols*currentRow+currentCol]!=str[matchCursor]||isVisited[rows*currentRow+currentCol])
            return false;
        if (matchCursor==str.length-1){
            return true;
        }
        isVisited[cols*currentRow+currentCol]=true;
        if (currentRow>0&&findPath(matrix,rows,cols,str,currentRow-1,currentCol,matchCursor+1))
            return true;
        if (currentRow<rows-1&&findPath(matrix,rows,cols,str,currentRow+1,currentCol,matchCursor+1))
            return true;
        if (currentCol>0&&findPath(matrix,rows,cols,str,currentRow,currentCol-1,matchCursor+1))
            return true;
        if (currentCol<cols-1&&findPath(matrix,rows,cols,str,currentRow,currentCol+1,matchCursor+1))
            return true;
        isVisited[cols*currentRow+currentCol]=false;
        return false;
    }
}

面试题13：机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解题思路

这道题和上一题类似，传入的参数更少，因为不需要记住字符串路径和已经匹配到的位置，只需要做出判断周围上下左右四个位置能不能访问即可。同样需要一个布尔矩阵标记是否访问过，另外使用一个全局整形变量统计已经访问过的位置的个数，直到递归回溯全部结束。

public class MovingRobot {
    boolean[][] isVisited=null;
    int count=0;
    public int movingCount(int threshold, int rows, int cols){
        isVisited=new boolean[rows][cols];
        visit(0,0,threshold,rows,cols);
        return count;
    }

    public void visit(int rowIndex,int colIndex,int threshold, int rows, int cols){
        if (getCount(rowIndex)+getCount(colIndex)>threshold||isVisited[rowIndex][colIndex])
            return;
        isVisited[rowIndex][colIndex]=true;
        count++;
        if (rowIndex>0)
            visit(rowIndex-1,colIndex,threshold,rows,cols);
        if (rowIndex<rows-1)
            visit(rowIndex+1,colIndex,threshold,rows,cols);
        if (colIndex>0)
            visit(rowIndex,colIndex-1,threshold,rows,cols);
        if (colIndex<cols-1)
            visit(rowIndex,colIndex+1,threshold,rows,cols);
    }

    public int getCount(int a){
        String s=String.valueOf(a);
        char[] c=s.toCharArray();
        int sum=0;
        for (char cc:c){
            sum+=Integer.parseInt(String.valueOf(cc));
        }
        return sum;
    }
}

动态规划

如果一个大问题可以被分解为小问题，并且如果小问题的最优解组合起来能得到整个问题的最优解，那么就可以应用动态规划解决这个问题。通常用自底向上的记忆化方法减少动态规划的计算。

贪心算法试图在每一步都做出当前最优解，这需要多观察问题背后的数学规律和数学证明才能给出解法，想要掌握贪心算法非一日之功。

面试题14：剪绳子

题目描述

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？

示例

输入：
8
输出：
18
说明：
当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

解题思路

每对长度为n的绳子剪一刀，都有[1,n-1][2,n-2]...[i,n-i]种组合，最优方案是这些组合乘积的最大值，即f(n)=Max(f(i)*f(n-i))。可以使用自底向上的动态规划算法计算。

private static int findMax(int i){
    //处理特例，至少剪一刀
    switch (i){
        case 1:
        case 2:
            return 1;
        case 3:
            return 2;
    }
    int[] maxSet=new int[i+1];
    maxSet[0]=0;
    maxSet[1]=1;
    maxSet[2]=2;
    maxSet[3]=3;
    for (int j=4;j<=i;j++){
        int max=0;
        //实际上i从1到n/2就可以了，后半部分和前半部分是对称的
        for (int k=1;k<=j/2;k++){
            int temp=maxSet[k]*maxSet[j-k];
            max=Math.max(max,temp);
        }
        maxSet[j]=max;
    }
    return maxSet[i];
}

位运算

Java中提供的位运算符有：左移<< 、右移>>、无符号右移>>>、位与&、位或|、位非~、位异或^，除了位非~是一元操作符外，其它的都是二元操作符。计算机执行位运算的速度通常比代数运算快。

面试题15：二进制中1的个数

题目描述

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路

书中的负数死循环的例子，在Java中使用无符号右移就可以避免。这题给出了一个规律：

把一个整数减去1，再和原来的整数做与运算，会把该整数最右边的1变成0.

由此可以写出下面的答案：

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

个人认为这一题实用意义不大，更重要的是理解计算机中数字的表示形式和位运算符的作用。