首页 > 代码库 > 阿里巴巴集团2015年秋季校招在线笔试附加题分析
阿里巴巴集团2015年秋季校招在线笔试附加题分析
刚做完，选择题做吐血，好多智力题。。。。附加题有两道编程题。题面是回忆的内容。
1、在text中查找子串quary，返回符合匹配的quary中连续的最大的子串长度，例如 quary = "acbac"，text = "acaccbabb"，quary 中 "cba"是最大的连续子串，返回3。
【分析】 两重循环获得quary的所有连续子串，使用KMP算法在text 查找匹配，如果匹配，则记录子串长度，最后返回最大的子串长度。
代码如下，编译通过
/**
* 创建时间：2014年8月27日 下午9:31:02 项目名称：Test
*
* @author 曹艳丰 北京大学
* @since JDK 1.6.0_21 类说明： 编译通过
*/
public class FindMaxMathch {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String quary = "acbac";
String text = "acaccbabb";
int maxQuary = findMaxMatch(quary, text);
System.out.println(maxQuary);
}
/* 寻找最大的连续匹配字符串的匹配算法 */
public static int findMaxMatch(String quary, String text) {
int diff = -1;
int maxDiff = Integer.MIN_VALUE;
char[] quaryChar = quary.toCharArray();
char[] textChar = text.toCharArray();
for (int i = 0; i < quaryChar.length; i++) {
for (int j = quaryChar.length - 1; j >= i; j--) {
diff = j - i + 1;
/* 获取quary连续的子字符串，并初始化 */
char[] subQuaryChar = new char[diff];
for (int k = 0; k < subQuaryChar.length; k++) {
subQuaryChar[k] = quaryChar[i + k];
}
int position = getKMPMatchPosition(textChar, subQuaryChar);
if (position != -1 && diff > maxDiff) {
maxDiff = diff;
}
}
}
return maxDiff;
}
/* KMP字符匹配算法 */
public static int getKMPMatchPosition(char[] array, char[] subArray) {
if (array.length < subArray.length) {
return -1;
}
int i = 0, j = 0;
int[] next = getNextArray(subArray);
while (i < array.length) {
if (j == -1 || array[i] == subArray[j]) {
i++;
j++;
} else {
j = next[j];
}
if (j == subArray.length) {
return i - subArray.length;
}
}
return -1;
}
/* 求int[] next数组 */
public static int[] getNextArray(char[] array) {
int j = 0;
int k = -1;
int[] next = new int[array.length];
next[0] = -1;
while (j < array.length - 1) {
if (k == -1 || array[j] == array[k]) {
next[++j] = ++k;
} else {
k = next[k];
}
}
return next;
}
}
2、二叉树每个节点存储有int类型数据，节点与节点之间的数据差的绝对值为maxAbs，高效得到求出整棵数中的maxAbs。【分析】前序遍历（或者后续、中序、层次遍历，whatever）二叉树，获得最大值和最小值，返回差值即可。这里遍历没有用递归的方式，而是用了辅助stack的方式。
代码如下，编译通过。
节点类：
/**
* @author 曹艳丰 北京大学
*
*/
public class BinaryTreeNode<T> {
private BinaryTreeNode<T> leftChild,rightChild;
private T data;
public BinaryTreeNode() {
// TODO 自动生成的构造函数存根
leftChild=rightChild=null;
}
public BinaryTreeNode(T data) {
// TODO 自动生成的构造函数存根
leftChild=rightChild=null;
this.data=http://www.mamicode.com/data;>方法主体如下：
/**
* 创建时间：2014年8月29日 下午7:46:07 项目名称：Test
*
* @author 曹艳丰 北京大学
* @since JDK 1.6.0_21 类说明： 找到二叉树中最大的绝对值。
*/
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinaryTreeNode<Integer> root = new BinaryTreeNode<Integer>(1);
BinaryTreeNode<Integer> a = new BinaryTreeNode<Integer>(2);
BinaryTreeNode<Integer> b = new BinaryTreeNode<Integer>(20);
root.setLeftChild(a);
root.setRightChild(b);
int maxAbs = preOrderUsingStack(root);
System.out.println(maxAbs);
}
/* 较简单——使用1个辅助stack方式进行前序遍历，记录最大值和最小值 */
private static int preOrderUsingStack(BinaryTreeNode<Integer> root) {
int maxValue = http://www.mamicode.com/Integer.MIN_VALUE;>
阿里巴巴集团2015年秋季校招在线笔试附加题分析
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。