有一个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不需要捕获异常