微软2014实习生在线笔试
昨晚的第四题，求更高效算法……import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Map.Entry;
/**
*
*
*
Time Limit: 10000ms
Case Time Limit: 3000ms
Memory Limit: 256MB
Description
In a running system, there're many logs produced within a short period of time, we'd like to know the count of the most frequent logs.
Logs are produced by a few non-empty format strings, the number of logs is N(1=N=20000), the maximum length of each log is 256.
Here we consider a log same with another when their edit distance (see note) is = 5.
Also we have a) logs are all the same with each other produced by a certain format string b) format strings have edit distance5 of each other.
Your program will be dealing with lots of logs, so please try to keep the time cost close to O(nl), where n is the number of logs, and l is the average log length.
Note edit distance is the minimum number of operations (insertdeletereplace a character) required to transform one string into the other, please refer to httpen.wikipedia.orgwikiEdit_distance for more details.
Input
Multiple lines of non-empty strings.
Output
The count of the most frequent logs.
Sample I
Logging started for id:1
Module ABC has completed its job
Module XYZ has completed its job
Logging started for id:10
Module ? has completed its job
Sample Out
3
* @author lfznh@126.com
*
*/
public class Most_Frequent_Log {
public static Map<String, Integer> map = new HashMap<String, Integer>();
public static final int N = 300;//the maxlength of a String is 256,so 300 will be ok
public static final int dis[][] = new int;
/**
* a classic dp problem
* @param the two words be compared
* @return the edit-distance betweet the two words
*/
public static int distance(String srcA, String srcB) {
int sLen = srcA.length();
int tLen = srcB.length();
int offset;
//disimplies the distance A B
for (int i = 0; i <= sLen; i++) {
dis = i; // if b is empty ,so the distance of them is length A
}
for (int j = 0; j <= tLen; j++) {
dis = j;
}
for (int i = 1; i <= sLen; i++) {
char ch1 = srcA.charAt(i - 1);
for (int j = 1; j <= tLen; j++) {
char ch2 = srcB.charAt(j - 1);
if (ch1 == ch2) {
offset = 0; //if eq then distance is zero,else it just need one step ,change ch1 to ch2 or the opposite
} else {
offset = 1;
}
dis = Math.min(
1 + Math.min(dis, dis),
dis + offset);
}
}
return dis;
}
/**
* preproess the string
* @param s
*/
public static void preprocess(String s) {
boolean flag = false;
String key = "";
int value = 1;
Iterator<Entry<String, Integer>> entryIte = map.entrySet().iterator();
while (entryIte.hasNext()) {
Entry<String, Integer> entry = entryIte.next();
key = entry.getKey();
value = entry.getValue();
if (distance(key, s) <= 5) {
flag = true;//if true stop the loop,we just need to find the first appenance of le 5 position of them
break;
}
}
if (flag) //found the first string le 5 distance with s,then put it into the map,increase its count
map.put(key, value + 1);
else
map.put(s, 1);
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int maxCount = -0xfffffff;
String word;
while (true) {
word = scanner.nextLine();
if (word.equals("")) //end while meets the first "" line
break;
preprocess(word);
}
Iterator<Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Entry<String, Integer> entry = iterator.next();
if (entry.getValue() > maxCount)
maxCount = entry.getValue();
}
System.out.println(maxCount);
}
}
看看……………… 复杂度怎么才能搞到O(nl)!!!!
页:
[1]