不想编码的程序员：放下筷子的那一刻，我惊呆了~~~~

有问题找社区小助手：本期答案领取地址：  加入牛客讨论2群(244930442 ） 群资料中文件：2015-07-22正式版.pdf

有问题找社区小助手：【题目】 给定一个整数n，代表汉诺塔游戏中从小到大放置的n个圆盘，假设开始时所有圆盘都放在左边的柱子上，想按照汉诺塔游戏的要求把所有圆盘都移到右边的柱子上。实现函数打印最优移动轨迹。 【举例】 n=1时，打印： move from left to right n=2时，打印： move from left to mid move from left to right move from mid to right 【进阶题目】 给定一个整型数组arr其中只含有1、2和3，代表所有圆盘目前的状态，1代表左柱，2代表中柱，3代表右柱，arr[i]的值代表第i+1个圆盘的位置。比如，arr=[3,3,2,1]，代表第1个圆盘在右柱上、第2个圆盘在右柱上、第3个圆盘在中柱上、第4个圆盘在左柱上。如果arr代表的状态是最优移动轨迹过程中出现的状态，返回arr这种状态是最优移动轨迹中的第几个状态。如果arr代表的状态不是最优移动轨迹过程中出现的状态，则返回-1。 【举例】 arr=[1,1]。两个圆盘目前都在左柱上，也就是初始状态，所以返回0。 arr=[2,1]。第一个圆盘在中柱上、第二个圆盘在左柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹的第1步，所以返回1。 arr=[3,3]。第一个圆盘在右柱上、第二个圆盘在右柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹的第3步，所以返回3。 arr=[2,2]。第一个圆盘在中柱上、第二个圆盘在中柱上，这个状态是2个圆盘的汉诺塔游戏中，最优移动轨迹从来不会出现的状态，所以返回-1。 【进阶题目要求】 如果arr长度为N，请实现时间复杂度O(N)，额外空间复杂度O(1)的方法。 【难度】 校★★★☆ 【解答】 原问题。假设有from柱子、mid柱子和to柱子，都在from的圆盘1~i完全移动到to，最优过程为。步骤1为圆盘1~i-1从from移动到mid，步骤2为单独把圆盘i从from移动到to，步骤3为把圆盘1~i-1从mid移动到to。如果圆盘只有1个，直接把这个圆盘从from移动到to即可。打印最优移动轨迹的方法参见如下代码中的hanoi方法。 public void hanoi(int n) { if (n > 0) { func(n, "left", "mid", "right"); } } public void func(int n, String from, String mid, String to) { if (n == 1) { System.out.println("move from " + from + " to " + to); } else { func(n - 1, from, to, mid); func(1, from, mid, to); func(n - 1, mid, from, to); } } 进阶题目。首先求都在from柱子上的圆盘1~i，如果都移动到to上的最少步骤数，假设为S(i)。根据上面的步骤，S(i)=步骤1的步骤总数+1+步骤3的步骤总数=S(i-1)+1+S(i-1)，S(1)=1。所以S(i)+1=2*(S(i-1)+1)，S(1)+1==2。根据等比数列求和公式得到S(i)+1=2^i，所以S(i)=2^i-1。 对于数组arr来说，arr[N-1]表示最大圆盘N在哪个柱子上，情况有以下三种： 1，圆盘N在左柱上，说明步骤1或者没有完成或者已经完成，需要考察圆盘1~N-1的状况。 2，圆盘N在右柱上，说明步骤1已经完成，起码走完了2^(N-1)-1步。步骤2也已经完成，起码又走完了1步，所以当前状况起码是最优步骤的2^(N-1)步，剩下的步骤怎么确定还得继续考察圆盘1~N-1的状况。 3，圆盘N在中柱上，这是不可能的，最优步骤中不可能让圆盘N处在中柱上，直接返回-1。 所以整个过程可以总结为，对于圆盘1~i来说，如果目标为从from到to，那么情况有三种： 1，圆盘i在from上，需要继续考察圆盘1~i-1的状况，圆盘1~i-1的目标为从from到mid。 2，圆盘i在to上，说明起码走完了2^(i-1)步，剩下的步骤怎么确定还得继续考察圆盘1~i-1的状况，圆盘1~i-1的目标为从mid到to。 3，圆盘i在mid上，直接返回-1。 整个过程参看如下代码中的step1方法。 public int step1(int[] arr) { if (arr == null || arr.length == 0) { return -1; } return process(arr, arr.length - 1, 1, 2, 3); } public int process(int[] arr, int i, int from, int mid, int to) { if (i == -1) { return 0; } if (arr[i] != from && arr[i] != to) { return -1; } if (arr[i] == from) { return process(arr, i - 1, from, to, mid); } else { int rest = process(arr, i - 1, mid, from, to); if (rest == -1) { return -1; } return (1 << i) + rest; } } step1方法是递归函数，递归最多调用N次，并且每步的递归函数再调用递归函数的次数最多一次。在每个递归过程中，除去递归调用的部分，剩下过程的时间复杂度为O(1)，所以step1方法的时间复杂度为O(N)。但是因为递归函数需要函数栈的关系，step1方法的额外空间复杂度为O(N)，所以为了达到题目的要求，需要将整个过程改成非递归的方法，具体请参看如下代码中的step2方法。 public int step2(int[] arr) { if (arr == null || arr.length == 0) { return -1; } int from = 1; int mid = 2; int to = 3; int i = arr.length - 1; int res = 0; int tmp = 0; while (i >= 0) { if (arr[i] != from && arr[i] != to) { return -1; } if (arr[i] == to) { res += 1 << i; tmp = from; from = mid; } else { tmp = to; to = mid; } mid = tmp; i--; } return res; }

Ryan_yang：为什么不直接将每个值放到它该放的位置，负数和大于n的都不管，然后再遍历一遍就能找到结果（比老师的好理解）leetcode 41 题

有问题找社区小助手：KMP算法 【题目】 给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有字串match，则返回match在str中的开始位置，不含有则返回-1。 【举例】 str=“acbc”，match=“bc”。返回2。 str=“acbc”，match=“bcc”。返回-1。 【要求】 如果match的长度大于str长度(M>N)，str必然不会含有match，可直接返回-1。但如果N>=M，要求算法复杂度O(N)。     public int getIndexOf(String s, String m) {         if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {         return -1;         }         char[] ss = s.toCharArray();         char[] ms = m.toCharArray();         int si = 0;         int mi = 0;         int[] next = getNextArray(ms);         while (si < ss.length && mi < ms.length) {         if (ss[si] == ms[mi]) {             si++;             mi++;         } else if (next[mi] == -1) {             si++;         } else {             mi = next[mi];         }         }         return mi == ms.length ? si - mi : -1;     }     public int[] getNextArray(char[] ms) {         if (ms.length == 1) {             return new int[] { -1 };         }         int[] next = new int[ms.length];         next[0] = -1;         next[1] = 0;         int pos = 2;         int cn = 0;         while (pos < next.length) {             if (ms[pos - 1] == ms[cn]) {                 next[pos++] = ++cn;             } else if (cn > 0) {                 cn = next[cn];             } else {                 next[pos++] = 0;             }         }         return next;     }

Shining_Ra...：对啊，基本是这样，我之前也面过一次，有几个注意的地方， 一是性格测试有一点啰嗦和恶心，要反复同样的题，做好心理准备； 二是boss面的时候尽量能自己引导谈话的方向，我当时这个环节感觉不好，因为技术面进没进当下就出结果，但是boss面没有这么明显的分界线，你最好自己能准备一下，然后适当的引导下你们的谈话。