人民搜索笔试题1

1、打印汉诺塔移动步骤，并且计算复杂度

2、计算两个字符串的是否相似（字符的种类，和出现次数相同）

编程之美中的一道经典的动态规划题目——计算两个字符串的相似度

public class StringSimilar {
    public int fun(String source,String target){
        int i,j;
        int[][] d = new int[source.length()+1][target.length()+1];
        for(i=1;i<source.length()+1;i++){/*初始化临界值*/
            d[i][0]=i;
        }
        for(j=1;j<target.length()+1;j++){/*初始化临界值*/
            d[0][j]=j;
        }
        for(i=1;i<source.length()+1;i++){/*动态规划填表*/
            for(j=1;j<target.length()+1;j++){
                if(source.substring(i-1, i).equals(target.substring(j-1, j))){
                    d[i][j]=d[i-1][j-1];/*source的第i个和target的第j个相同时*/
                }else{/*不同的时候则取三种操作最小的一个*/
                    d[i][j]=min(d[i][j-1]+1,d[i-1][j]+1,d[i-1][j-1]+1);
                }
            }
        }
        return d[source.length()][target.length()];
    }
    private int min(int i, int j, int k) {
        int min = i<j?i:j;
        min = min<k?min:k;
        return min;
    }
    public static void main(String[] args) {
        StringSimilar ss = new StringSimilar();
        System.out.println(ss.fun("SNOWY", "SUNNY"));//3
        System.out.println(ss.fun("a", "b"));//1
        System.out.println(ss.fun("abdd", "aebdd"));//1
        System.out.println(ss.fun("travelling", "traveling"));//1
    }
}

3、定义二叉树，节点值为int，计算二叉树中的值在[a,b]区间的节点的个数

4、动态规划题：一条路有k可坑，每次能跳平方数步长（1 4 9  16。。），不能跳到坑里，从a跳到b最少几步？