Analyze User Website Visit Pattern
设计题, 给三个array, 分别是用户名, 访问时间和网址. 定义一个3seq是连续3个访问的网址, 求独立用户访问最多的3seq.
这个题超级tricky, 首先要构造3seq, 然后还要注意给的数据不是排序好的, 还要先排序. 最后求3seq的时候,我用”-“作为分隔符来方便给3seq做hash.
class Solution {
class Pair {
int c;
String s;
public Pair(String s, int c) {
this.s = s;
this.c = c;
}
}
class Triple {
int t;
String s;
String w;
public Triple(String s, int t, String w) {
this.s = s;
this.t = t;
this.w = w;
}
}
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
int n = username.length;
List<Triple> t = new ArrayList<>();
for(int i = 0; i < n; i++) {
t.add(new Triple(username[i], timestamp[i], website[i]));
}
Collections.sort(t,(a, b) -> (a.t-b.t));
Map<String, List<String>> map = new HashMap<>();
for(Triple tt : t) {
map.putIfAbsent(tt.s, new ArrayList<>());
map.get(tt.s).add(tt.w);
}
Map<String, Set<String>> countMap = new HashMap<>();
for(Map.Entry<String,List<String>> e : map.entrySet()) {
countMap.putIfAbsent(e.getKey(), new HashSet<>());
countMap.get(e.getKey()).addAll(getSeq(e.getValue()));
}
Map<String, Set<String>> countMapRev = new HashMap<>();
for(Map.Entry<String,Set<String>> e : countMap.entrySet()) {
for(String s : e.getValue()){
countMapRev.putIfAbsent(s, new HashSet<>());
countMapRev.get(s).add(e.getKey());
}
}
List<String> res = new ArrayList<>();
PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> (a.c == b.c ? a.s.compareTo(b.s) : b.c - a.c));
for(Map.Entry<String,Set<String>> e : countMapRev.entrySet()) {
pq.add(new Pair(e.getKey(), e.getValue().size()));
}
String ss = pq.poll().s;
String[] strs = ss.split("-");
for(String s : strs)
res.add(s);
return res;
}
private Set<String> getSeq(List<String> myArray) {
Set<String> res = new HashSet<>();
for(int i = 0; i < myArray.size() - 2; i++) {
for(int j = i + 1; j < myArray.size() - 1; j++) {
for(int k = j + 1; k < myArray.size(); k++) {
res.add(myArray.get(i)+"-"+myArray.get(j)+"-"+myArray.get(k));
}
}
}
return res;
}
}