/
Solution.java
executable file
·83 lines (67 loc) · 1.93 KB
/
Solution.java
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;
public class Solution {
public List<String> findRepeatedDnaSequences(String s) {
List<String> res = new ArrayList<>();
Set<String> resset = new HashSet<>(), has = new HashSet<>();
for(int i = 0; i < s.length() - 10; i++){
String tmp = s.substring(i, i+10);
if(has.contains(tmp)){
resset.add(tmp);
}else{
has.add(tmp);
}
}
for(String i: has){
res.add(i);
}
return res;
}
}
public class Solution {
static final int SIZE = 10;
static final char[] CHAR_TO_INT = {'A', 'C', 'G', 'T'};
static final int[] INT_TO_CHAR = new int['T' + 1];
static final int[] POW = new int[SIZE];
static {
for(int i = 0; i < SIZE; i++){
POW[i] = (int) Math.pow(4, i);
}
INT_TO_CHAR['A'] = 0;
INT_TO_CHAR['C'] = 1;
INT_TO_CHAR['G'] = 2;
INT_TO_CHAR['T'] = 3;
}
int toInt(char[] s, int index){
if(index + SIZE > s.length){
return -1;
}
int n = 0;
for(int i = index; i < index + SIZE; i++){
n += INT_TO_CHAR[s[i]] * POW[i - index];
}
return n;
}
String formInt(int n){
char[] s = new char[SIZE];
for(int i = 0; i < SIZE; i++){
s[i] = CHAR_TO_INT[n % 4];
n /= 4;
}
return new String(s);
}
public List<String> findRepeatedDnaSequences(String s) {
char[] S = s.toCharArray();
final int max = toInt("TTTTTTTTTT".toCharArray(), 0);
int[] m = new int[max + 1];
for(int i = 0; i <= S.length - SIZE; i++){
m[toInt(S, i)]++;
}
ArrayList<String> rt = new ArrayList<>();
for(int i = 0; i < max + 1; i++){
if(m[i] >= 2){
rt.add(formInt(i));
}
}
return rt;
}
}