面试题
找重复出现次数最多的子串中最长的那个子串。例：
"abcdabc" 2次abc
"bbbb" 4次b
思路：
记录每个长度的字串重复出现的次数，然后找到出现次数最多的所有字串，返回最长的那个。
如，
abcdabc，长度为1的字串有
a:2,b:2,c:2,d:1，长度为2的字串有
ab:2,bc:2,ca:1，长度为3的字串有
abc:2,bcd:1,cda:1,dab:1，长度为4的有
abcd:1,bcda:1,dabc:1，长度为5的有
abcda:1,bcdab:1,cdabc:1，长度为6的有
abcdab:1,bcdabc:1，长度为7的有
abcdabc:1。其中出现最多的是2次，有
a:2,b:2,c:2, ab:2,bc:2, abc:2。其中长度最长的是
abc。
因此可以这样写：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
package com.youthlin;
import java.util.*;
/**
* Created by lin on 2016-04-20-020.
* 面试题
* 重复出现次数最多的子串中最长的那个子串
* "abcabc" 2次abc
* "bbbb" 4次b
*/
public class LongestMaxCountString {
public static String getLongestMaxCountString(String s) {
String result;
Map<String, Integer> map = new HashMap<>();//<子串，出现次数>
for (int i = 1; i <= s.length(); i++) {
//检查长度为i个字符的子串重复出现的次数
for (int j = 0; j < s.length(); j++) {
if (i + j <= s.length()) {
result = s.substring(j, j + i);
if (map.containsKey(result))
map.put(result, map.get(result) + 1);
else map.put(result, 1);
}
}
}
int count;
result = null;
Map<Integer, String> map1 = new HashMap<>();//<次数，最长子串>
Set<String> keys = map.keySet();
for (String key : keys) {
count = map.get(key);
if (map1.containsKey(count)) {
result = map1.get(count);
if (key.length() > result.length())//看新的子串长度是否更大
map1.put(count, key);
} else
map1.put(count, key);
}
count = 0;
Set<Integer> set = map1.keySet();
for (Integer a : set) {//找出次数最多的子串
if (a > count) {
count = a;
result = map1.get(a);
}
}
return result;
}
public static void main(String[] args) {
String s = "abcdabcdeabcd";
System.out.println(getLongestMaxCountString(s));
s = "bbbb";
System.out.println(getLongestMaxCountString(s));
s = "";
System.out.println(getLongestMaxCountString(s));
}
/**输出：
* abcd
* b
* null
*/
}
|
听说是Leecode上的题目，我搜到了一些用
后缀数组解法的，但并没有看明白，上面这种方法也是最笨的方法，不知道还有什么复杂度更低的方法。
Reader Echoes
5 comments