程序员人生网站导航

2014年阿里巴巴校园招聘算法大题

栏目：互联网时间：2014-09-09 09:37:22

有一个quary和text要求找出两者匹配最长的字符串的长度：

/** * 利用KMP解决求最长匹配长度 * * @author 曾修建 * @version 创建时间：2014-8-29 下午07:43:36 */? public class ALTest { /** * KMP匹配字符串 * * @param s 主串 * @param t 模式串 * @return 若匹配成功，返回能匹配到的最长长度 */ public static int KMP_Index(char[] s, char[] t) { int[] next = next(t); int i = 0; int j = 0; int maxLength = 0; //记录能匹配最长的长度 while (i <= s.length - 1 && j <= t.length - 1) { if (j == -1 || s[i] == t[j]) { i++; j++; maxLength = i; } else { j = next[j]; } } return maxLength; } public static int[] next(char[] t) { int[] next = new int[t.length]; next[0] = -1; int i = 0; int j = -1; while (i < t.length - 1) { if (j == -1 || t[i] == t[j]) { i++; j++; if (t[i] != t[j]) { next[i] = j; } else { next[i] = next[j]; } } else { j = next[j]; } } return next; } public static void main(String[] args) { char []query = {'c','b','a'}, text={'a','c','a','c','c','b','a','b','b'}; System.out.println("能匹配到最长的长度是： "+KMP_Index(query,text)); } }

1/写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率。

#include <iostream>

using namespace std;

struct Node

{

Node *left;

Node *right;

};

struct Detail

{

int Distance;

int Depth;

};

Detail GetMaxDistance(Node* root)

{

if (!root)

{

Detail empty = { 0, -1 };

return empty;

}

Detail lhs = GetMaxDistance(root->left);

Detail rhs = GetMaxDistance(root->right);

Detail Detail;

Detail.Depth = max(lhs.Depth + 1, rhs.Depth + 1);

Detail.Distance = max(max(lhs.Distance, rhs.Distance), lhs.Depth + rhs.Depth + 2);

return Detail;

}

void Link(Node* nodes,int parent,int left,int right)

{

if(left != -1)

nodes[parent].left = &nodes[left];

if(right != -1)

nodes[parent].right = &nodes[right];

}

void main()

{

Node test[9] = { 0 };

Link(test, 0, 1, 2);

Link(test, 1, 3, 4);

Link(test, 3, 5, 6);

Link(test, 5, 7, -1);

Link(test, 6, -1, 8);

cout <<"test: "<< GetMaxDistance(&test[0]).Distance << endl;

}

2、Java中sleep()、wait()区别

功能差不多,都用来进行线程控制,他们最大本质的区别是:

(1)sleep()不释放同步锁,wait()释放同步锁,使得其他线程可以使用同步控制块或者方法

(2)sleep(milliseconds)可以用时间指定来使他自动醒过来,如果时间不到你只能调用interreput()来强行打断;

wait()可以用notify()直接唤起.

(3)这两个方法来自不同的类分别是Thread和Object

(4)wait只能在同步控制方法或者同步控制块里面使用，而sleep可以在任何地方使用

(5)sleep必须捕获异常，而wait不需要捕获异常

------分隔线----------------------------

上一篇 ”4635“――这三个月以来的成就。

下一篇 开发者不容错过的10款免费JavaScript游戏引擎

------分隔线----------------------------