java codility training基因组范围查询

任务是：

给出非空的零索引字符串S. 字符串S由大写英文字母A，C，G，T组成的N个字符组成。

该字符串实际上代表DNA序列，大写字母代表单个核苷酸。

您还将获得由M个整数组成的非空零索引数组P和Q. 这些arrays代表关于最小核苷酸的查询。 我们将字符串S的字母表示为数组P和Q中的整数1,2,3,4，其中A = 1，C = 2，G = 3，T = 4，我们假设A <C <G <T 。

查询K要求您找到范围内的最小核苷酸（P [K]，Q [K]），0≤P[i]≤Q[i] <N。

例如，考虑字符串S = GACACCATA和数组P，Q，使得：

P[0] = 0 Q[0] = 8 P[1] = 0 Q[1] = 2 P[2] = 4 Q[2] = 5 P[3] = 7 Q[3] = 7 

来自这些范围的最小核苷酸如下：

  (0, 8) is A identified by 1, (0, 2) is A identified by 1, (4, 5) is C identified by 2, (7, 7) is T identified by 4. 

写一个函数：

 class Solution { public int[] solution(String S, int[] P, int[] Q); } 

如果给定由N个字符组成的非空零索引字符串S和由M个整数组成的两个非空零索引数组P和Q，则返回由M个字符组成的数组，指定所有查询的连续答案。

序列应返回为：

  a Results structure (in C), or a vector of integers (in C++), or a Results record (in Pascal), or an array of integers (in any other programming language). 

例如，给定字符串S = GACACCATA和数组P，Q，使得：

 P[0] = 0 Q[0] = 8 P[1] = 0 Q[1] = 2 P[2] = 4 Q[2] = 5 P[3] = 7 Q[3] = 7 

该函数应返回值[1,1,2,4]，如上所述。

假使，假设：

  N is an integer within the range [1..100,000]; M is an integer within the range [1..50,000]; each element of array P, Q is an integer within the range [0..N − 1]; P[i] ≤ Q[i]; string S consists only of upper-case English letters A, C, G, T. 

复杂：

  expected worst-case time complexity is O(N+M); expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments). 

可以修改输入数组的元素。

我的解决方案是：

 class Solution { public int[] solution(String S, int[] P, int[] Q) { final char c[] = S.toCharArray(); final int answer[] = new int[P.length]; int tempAnswer; char tempC; for (int iii = 0; iii < P.length; iii++) { tempAnswer = 4; for (int zzz = P[iii]; zzz  2) { tempAnswer = 2; } } else if (tempC == 'G') { if (tempAnswer > 3) { tempAnswer = 3; } } } answer[iii] = tempAnswer; } return answer; } } 

它不是最优的，我相信它应该在一个循环中完成，任何提示我如何实现它？

您可以在此处检查解决方案的质量https://codility.com/train/测试名称是Genomic-range-query。

Answer 1

以下是在codility.com中获得100分的解决方案。 请阅读前缀总和以了解解决方案：

 public static int[] solveGenomicRange(String S, int[] P, int[] Q) { //used jagged array to hold the prefix sums of each A, C and G genoms //we don't need to get prefix sums of T, you will see why. int[][] genoms = new int[3][S.length()+1]; //if the char is found in the index i, then we set it to be 1 else they are 0 //3 short values are needed for this reason short a, c, g; for (int i=0; i 0) { result[i] = 1; } else if (genoms[1][toIndex] - genoms[1][fromIndex] > 0) { result[i] = 2; } else if (genoms[2][toIndex] - genoms[2][fromIndex] > 0) { result[i] = 3; } else { result[i] = 4; } } return result; } 

Answer 2

Java，100 /100 ，但没有累积/前缀总和 ！ 我在数组“map”中存储了较低3个nucelotides的最后一个出现索引。 后来我检查最后一个索引是否介于PQ之间。 如果是这样，它返回核苷酸，如果没有找到，它是最重要的（T）：

 class Solution { int[][] lastOccurrencesMap; public int[] solution(String S, int[] P, int[] Q) { int N = S.length(); int M = P.length; int[] result = new int[M]; lastOccurrencesMap = new int[3][N]; int lastA = -1; int lastC = -1; int lastG = -1; for (int i = 0; i < N; i++) { char c = S.charAt(i); if (c == 'A') { lastA = i; } else if (c == 'C') { lastC = i; } else if (c == 'G') { lastG = i; } lastOccurrencesMap[0][i] = lastA; lastOccurrencesMap[1][i] = lastC; lastOccurrencesMap[2][i] = lastG; } for (int i = 0; i < M; i++) { int startIndex = P[i]; int endIndex = Q[i]; int minimum = 4; for (int n = 0; n < 3; n++) { int lastOccurence = getLastNucleotideOccurrence(startIndex, endIndex, n); if (lastOccurence != 0) { minimum = n + 1; break; } } result[i] = minimum; } return result; } int getLastNucleotideOccurrence(int startIndex, int endIndex, int nucleotideIndex) { int[] lastOccurrences = lastOccurrencesMap[nucleotideIndex]; int endValueLastOccurenceIndex = lastOccurrences[endIndex]; if (endValueLastOccurenceIndex >= startIndex) { return nucleotideIndex + 1; } else { return 0; } } } 

Answer 3

JS中的简单，优雅，特定领域，100/100解决方案，带有评论！

 function solution(S, P, Q) { var N = S.length, M = P.length; // dictionary to map nucleotide to impact factor var impact = {A : 1, C : 2, G : 3, T : 4}; // nucleotide total count in DNA var currCounter = {A : 0, C : 0, G : 0, T : 0}; // how many times nucleotide repeats at the moment we reach S[i] var counters = []; // result var minImpact = []; var i; // count nucleotides for(i = 0; i <= N; i++) { counters.push({A: currCounter.A, C: currCounter.C, G: currCounter.G}); currCounter[S[i]]++; } // for every query for(i = 0; i < M; i++) { var from = P[i], to = Q[i] + 1; // compare count of A at the start of query with count at the end of equry // if counter was changed then query contains A if(counters[to].A - counters[from].A > 0) { minImpact.push(impact.A); } // same things for C and others nucleotides with higher impact factor else if(counters[to].C - counters[from].C > 0) { minImpact.push(impact.C); } else if(counters[to].G - counters[from].G > 0) { minImpact.push(impact.G); } else { // one of the counters MUST be changed, so its T minImpact.push(impact.T); } } return minImpact; } 

Answer 4

这是解决方案，假设某人仍然感兴趣。

 class Solution { public int[] solution(String S, int[] P, int[] Q) { int[] answer = new int[P.length]; char[] chars = S.toCharArray(); int[][] cumulativeAnswers = new int[4][chars.length + 1]; for (int iii = 0; iii < chars.length; iii++) { if (iii > 0) { for (int zzz = 0; zzz < 4; zzz++) { cumulativeAnswers[zzz][iii + 1] = cumulativeAnswers[zzz][iii]; } } switch (chars[iii]) { case 'A': cumulativeAnswers[0][iii + 1]++; break; case 'C': cumulativeAnswers[1][iii + 1]++; break; case 'G': cumulativeAnswers[2][iii + 1]++; break; case 'T': cumulativeAnswers[3][iii + 1]++; break; } } for (int iii = 0; iii < P.length; iii++) { for (int zzz = 0; zzz < 4; zzz++) { if ((cumulativeAnswers[zzz][Q[iii] + 1] - cumulativeAnswers[zzz][P[iii]]) > 0) { answer[iii] = zzz + 1; break; } } } return answer; } } 

Answer 5

如果有人关心C：

 #include  struct Results solution(char *S, int P[], int Q[], int M) { int i, a, b, N, *pA, *pC, *pG; struct Results result; result.A = malloc(sizeof(int) * M); result.M = M; // calculate prefix sums N = strlen(S); pA = malloc(sizeof(int) * N); pC = malloc(sizeof(int) * N); pG = malloc(sizeof(int) * N); pA[0] = S[0] == 'A' ? 1 : 0; pC[0] = S[0] == 'C' ? 1 : 0; pG[0] = S[0] == 'G' ? 1 : 0; for (i = 1; i < N; i++) { pA[i] = pA[i - 1] + (S[i] == 'A' ? 1 : 0); pC[i] = pC[i - 1] + (S[i] == 'C' ? 1 : 0); pG[i] = pG[i - 1] + (S[i] == 'G' ? 1 : 0); } for (i = 0; i < M; i++) { a = P[i] - 1; b = Q[i]; if ((pA[b] - pA[a]) > 0) { result.A[i] = 1; } else if ((pC[b] - pC[a]) > 0) { result.A[i] = 2; } else if ((pG[b] - pG[a]) > 0) { result.A[i] = 3; } else { result.A[i] = 4; } } return result; } 

Answer 6

这是一个C＃解决方案，其基本思想与其他答案几乎相同，但它可能更清晰：

 using System; class Solution { public int[] solution(string S, int[] P, int[] Q) { int N = S.Length; int M = P.Length; char[] chars = {'A','C','G','T'}; //Calculate accumulates int[,] accum = new int[3, N+1]; for (int i = 0; i <= 2; i++) { for (int j = 0; j < N; j++) { if(S[j] == chars[i]) accum[i, j+1] = accum[i, j] + 1; else accum[i, j+1] = accum[i, j]; } } //Get minimal nucleotides for the given ranges int diff; int[] minimums = new int[M]; for (int i = 0; i < M; i++) { minimums[i] = 4; for (int j = 0; j <= 2; j++) { diff = accum[j, Q[i]+1] - accum[j, P[i]]; if (diff > 0) { minimums[i] = j+1; break; } } } return minimums; } } 

Answer 7

 import java.util.Arrays; import java.util.HashMap; class Solution { static HashMap characterMapping = new HashMap(){{ put('A',1); put('C',2); put('G',3); put('T',4); }}; public static int minimum(int[] arr) { if (arr.length ==1) return arr[0]; int smallestIndex = 0; for (int index = 0; index 

Answer 8

这是我的解决方案使用段树O（n）+ O（log n）+ O（M）时间

 public class DNAseq { public static void main(String[] args) { String S="CAGCCTA"; int[] P={2, 5, 0}; int[] Q={4, 5, 6}; int [] results=solution(S,P,Q); System.out.println(results[0]); } static class segmentNode{ int l; int r; int min; segmentNode left; segmentNode right; } public static segmentNode buildTree(int[] arr,int l,int r){ if(l==r){ segmentNode n=new segmentNode(); nl=l; nr=r; n.min=arr[l]; return n; } int mid=l+(rl)/2; segmentNode le=buildTree(arr,l,mid); segmentNode re=buildTree(arr,mid+1,r); segmentNode root=new segmentNode(); root.left=le; root.right=re; root.l=le.l; root.r=re.r; root.min=Math.min(le.min,re.min); return root; } public static int getMin(segmentNode root,int l,int r){ if(root.l>r || root.r=l&& root.r<=r) { return root.min; } return Math.min(getMin(root.left,l,r),getMin(root.right,l,r)); } public static int[] solution(String S, int[] P, int[] Q) { int[] arr=new int[S.length()]; for(int i=0;i 

Answer 9

希望这可以帮助。

 public int[] solution(String S, int[] P, int[] K) { // write your code in Java SE 8 char[] sc = S.toCharArray(); int[] A = new int[sc.length]; int[] G = new int[sc.length]; int[] C = new int[sc.length]; int prevA =-1,prevG=-1,prevC=-1; for(int i=0;i=P[i] && A[K[i]] <=K[i]){ result[i] =1; } else if(C[K[i]] >=P[i] && C[K[i]] <=K[i]){ result[i] =2; }else if(G[K[i]] >=P[i] && G[K[i]] <=K[i]){ result[i] =3; } else{ result[i]=4; } } return result; } 

Answer 10

这是我的解决方案。 得分％100。 当然我需要先检查并研究一点点前缀和。

 public int[] solution(String S, int[] P, int[] Q){ int[] result = new int[P.length]; int[] factor1 = new int[S.length()]; int[] factor2 = new int[S.length()]; int[] factor3 = new int[S.length()]; int[] factor4 = new int[S.length()]; int factor1Sum = 0; int factor2Sum = 0; int factor3Sum = 0; int factor4Sum = 0; for(int i=0; i 0){ result[i] = 1; }else if(factor2[end] > 0){ result[i] = 2; }else if(factor3[end] > 0){ result[i] = 3; }else{ result[i] = 4; } }else{ if(factor1[end] > factor1[start-1]){ result[i] = 1; }else if(factor2[end] > factor2[start-1]){ result[i] = 2; }else if(factor3[end] > factor3[start-1]){ result[i] = 3; }else{ result[i] = 4; } } } return result; } 

Answer 11

pshemek的解决方案将自身限制在空间复杂度（O（N）） – 即使使用2-d数组和答案数组，因为常数（4）用于2-d数组。 该解决方案也符合计算复杂度 – 而我的是O（N ^ 2） – 尽管实际的计算复杂度要低得多，因为它会跳过包含最小值的整个范围。

我尝试了一下 – 但我最终会占用更多空间 – 但对我来说更直观（C＃）：

 public static int[] solution(String S, int[] P, int[] Q) { const int MinValue = 1; Dictionary stringValueTable = new Dictionary(){ {'A', 1}, {'C', 2}, {'G', 3}, {'T', 4} }; char[] inputArray = S.ToCharArray(); int[,] minRangeTable = new int[S.Length, S.Length]; // The meaning of this table is [x, y] where x is the start index and y is the end index and the value is the min range - if 0 then it is the min range (whatever that is) for (int startIndex = 0; startIndex < S.Length; ++startIndex) { int currentMinValue = 4; int minValueIndex = -1; for (int endIndex = startIndex; (endIndex < S.Length) && (minValueIndex == -1); ++endIndex) { int currentValue = stringValueTable[inputArray[endIndex]]; if (currentValue < currentMinValue) { currentMinValue = currentValue; if (currentMinValue == MinValue) // We can stop iterating - because anything with this index in its range will always be minimal minValueIndex = endIndex; else minRangeTable[startIndex, endIndex] = currentValue; } else minRangeTable[startIndex, endIndex] = currentValue; } if (minValueIndex != -1) // Skip over this index - since it is minimal startIndex = minValueIndex; // We would have a "+ 1" here - but the "auto-increment" in the for statement will get us past this index } int[] result = new int[P.Length]; for (int outputIndex = 0; outputIndex < result.Length; ++outputIndex) { result[outputIndex] = minRangeTable[P[outputIndex], Q[outputIndex]]; if (result[outputIndex] == 0) // We could avoid this if we initialized our 2-d array with 1's result[outputIndex] = 1; } return result; } 

在pshemek的回答中 - 第二个循环中的“技巧”只是一旦你确定你找到了一个具有最小值的范围 - 你就不需要继续迭代了。 不确定这是否有帮助。

Answer 12

php 100/100解决方案：

 function solution($S, $P, $Q) { $S = str_split($S); $len = count($S); $lep = count($P); $arr = array(); $result = array(); $clone = array_fill(0, 4, 0); for($i = 0; $i < $len; $i++){ $arr[$i] = $clone; switch($S[$i]){ case 'A': $arr[$i][0] = 1; break; case 'C': $arr[$i][1] = 1; break; case 'G': $arr[$i][2] = 1; break; default: $arr[$i][3] = 1; break; } } for($i = 1; $i < $len; $i++){ for($j = 0; $j < 4; $j++){ $arr[$i][$j] += $arr[$i - 1][$j]; } } for($i = 0; $i < $lep; $i++){ $x = $P[$i]; $y = $Q[$i]; for($a = 0; $a < 4; $a++){ $sub = 0; if($x - 1 >= 0){ $sub = $arr[$x - 1][$a]; } if($arr[$y][$a] - $sub > 0){ $result[$i] = $a + 1; break; } } } return $result; } 

Answer 13

这个程序得分为100，性能明智优于上面列出的其他java代码！

代码可以在这里找到。

 public class GenomicRange { final int Index_A=0, Index_C=1, Index_G=2, Index_T=3; final int A=1, C=2, G=3, T=4; public static void main(String[] args) { GenomicRange gen = new GenomicRange(); int[] M = gen.solution( "GACACCATA", new int[] { 0,0,4,7 } , new int[] { 8,2,5,7 } ); System.out.println(Arrays.toString(M)); } public int[] solution(String S, int[] P, int[] Q) { int[] M = new int[P.length]; char[] charArr = S.toCharArray(); int[][] occCount = new int[3][S.length()+1]; int charInd = getChar(charArr[0]); if(charInd!=3) { occCount[charInd][1]++; } for(int sInd=1; sInd=occCount[0].length) continue; a = occCount[Index_A][Q[i]+1] - occCount[Index_A][P[i]]; c = occCount[Index_C][Q[i]+1] - occCount[Index_C][P[i]]; g = occCount[Index_G][Q[i]+1] - occCount[Index_G][P[i]]; M[i] = a>0? A : c>0 ? C : g>0 ? G : T; } return M; } private int getChar(char c) { return ((c=='A') ? Index_A : ((c=='C') ? Index_C : ((c=='G') ? Index_G : Index_T))); } } 

Answer 14

这是一个简单的javascript解决方案，获得100％。

 function solution(S, P, Q) { var A = []; var C = []; var G = []; var T = []; var result = []; var i = 0; S.split('').forEach(function(a) { if (a === 'A') { A.push(i); } else if (a === 'C') { C.push(i); } else if (a === 'G') { G.push(i); } else { T.push(i); } i++; }); function hasNucl(typeArray, start, end) { return typeArray.some(function(a) { return a >= P[j] && a <= Q[j]; }); } for(var j=0; j 

Answer 15

perl 100/100解决方案：

 sub solution { my ($S, $P, $Q)=@_; my @P=@$P; my @Q=@$Q; my @_A = (0), @_C = (0), @_G = (0), @ret =(); foreach (split //, $S) { push @_A, $_A[-1] + ($_ eq 'A' ? 1 : 0); push @_C, $_C[-1] + ($_ eq 'C' ? 1 : 0); push @_G, $_G[-1] + ($_ eq 'G' ? 1 : 0); } foreach my $i (0..$#P) { my $from_index = $P[$i]; my $to_index = $Q[$i] + 1; if ( $_A[$to_index] - $_A[$from_index] > 0 ) { push @ret, 1; next; } if ( $_C[$to_index] - $_C[$from_index] > 0 ) { push @ret, 2; next; } if ( $_G[$to_index] - $_G[$from_index] > 0 ) { push @ret, 3; next; } push @ret, 4 } return @ret; } 

Answer 16

Java 100/100

 class Solution { public int[] solution(String S, int[] P, int[] Q) { int qSize = Q.length; int[] answers = new int[qSize]; char[] sequence = S.toCharArray(); int[][] occCount = new int[3][sequence.length+1]; int[] geneImpactMap = new int['G'+1]; geneImpactMap['A'] = 0; geneImpactMap['C'] = 1; geneImpactMap['G'] = 2; if(sequence[0] != 'T') { occCount[geneImpactMap[sequence[0]]][0]++; } for(int i = 0; i < sequence.length; i++) { occCount[0][i+1] = occCount[0][i]; occCount[1][i+1] = occCount[1][i]; occCount[2][i+1] = occCount[2][i]; if(sequence[i] != 'T') { occCount[geneImpactMap[sequence[i]]][i+1]++; } } for(int j = 0; j < qSize; j++) { for(int k = 0; k < 3; k++) { if(occCount[k][Q[j]+1] - occCount[k][P[j]] > 0) { answers[j] = k+1; break; } answers[j] = 4; } } return answers; } } 

Answer 17

在ruby（100/100）

 def interval_sum x,y,p p[y+1] - p[x] end def solution(s,p,q) #Hash of arrays with prefix sums p_sums = {} respuesta = [] %w(ACGT).each do |letter| p_sums[letter] = Array.new s.size+1, 0 end (0...s.size).each do |count| %w(ACGT).each do |letter| p_sums[letter][count+1] = p_sums[letter][count] end if count > 0 case s[count] when 'A' p_sums['A'][count+1] += 1 when 'C' p_sums['C'][count+1] += 1 when 'G' p_sums['G'][count+1] += 1 when 'T' p_sums['T'][count+1] += 1 end end (0...p.size).each do |count| x = p[count] y = q[count] if interval_sum(x, y, p_sums['A']) > 0 then respuesta << 1 next end if interval_sum(x, y, p_sums['C']) > 0 then respuesta << 2 next end if interval_sum(x, y, p_sums['G']) > 0 then respuesta << 3 next end if interval_sum(x, y, p_sums['T']) > 0 then respuesta << 4 next end end respuesta end 

Answer 18

简单的php 100/100解决方案

 function solution($S, $P, $Q) { $result = array(); for ($i = 0; $i < count($P); $i++) { $from = $P[$i]; $to = $Q[$i]; $length = $from >= $to ? $from - $to + 1 : $to - $from + 1; $new = substr($S, $from, $length); if (strpos($new, 'A') !== false) { $result[$i] = 1; } else { if (strpos($new, 'C') !== false) { $result[$i] = 2; } else { if (strpos($new, 'G') !== false) { $result[$i] = 3; } else { $result[$i] = 4; } } } } return $result; } 

Answer 19

这是我的Java（100/100）解决方案：

 class Solution { private ImpactFactorHolder[] mHolder; private static final int A=0,C=1,G=2,T=3; public int[] solution(String S, int[] P, int[] Q) { mHolder = createImpactHolderArray(S); int queriesLength = P.length; int[] result = new int[queriesLength]; for (int i = 0; i < queriesLength; ++i ) { int value = 0; if( P[i] == Q[i]) { value = lookupValueForIndex(S.charAt(P[i])) + 1; } else { value = calculateMinImpactFactor(P[i], Q[i]); } result[i] = value; } return result; } public int calculateMinImpactFactor(int P, int Q) { int minImpactFactor = 3; for (int nucleotide = A; nucleotide <= T; ++nucleotide ) { int qValue = mHolder[nucleotide].mOcurrencesSum[Q]; int pValue = mHolder[nucleotide].mOcurrencesSum[P]; // handling special cases when the less value is assigned on the P index if( P-1 >= 0 ) { pValue = mHolder[nucleotide].mOcurrencesSum[P-1] == 0 ? 0 : pValue; } else if ( P == 0 ) { pValue = mHolder[nucleotide].mOcurrencesSum[P] == 1 ? 0 : pValue; } if ( qValue - pValue > 0) { minImpactFactor = nucleotide; break; } } return minImpactFactor + 1; } public int lookupValueForIndex(char nucleotide) { int value = 0; switch (nucleotide) { case 'A' : value = A; break; case 'C' : value = C; break; case 'G': value = G; break; case 'T': value = T; break; default: break; } return value; } public ImpactFactorHolder[] createImpactHolderArray(String S) { int length = S.length(); ImpactFactorHolder[] holder = new ImpactFactorHolder[4]; holder[A] = new ImpactFactorHolder(1,'A', length); holder[C] = new ImpactFactorHolder(2,'C', length); holder[G] = new ImpactFactorHolder(3,'G', length); holder[T] = new ImpactFactorHolder(4,'T', length); int i =0; for(char c : S.toCharArray()) { int nucleotide = lookupValueForIndex(c); ++holder[nucleotide].mAcum; holder[nucleotide].mOcurrencesSum[i] = holder[nucleotide].mAcum; holder[A].mOcurrencesSum[i] = holder[A].mAcum; holder[C].mOcurrencesSum[i] = holder[C].mAcum; holder[G].mOcurrencesSum[i] = holder[G].mAcum; holder[T].mOcurrencesSum[i] = holder[T].mAcum; ++i; } return holder; } private static class ImpactFactorHolder { public ImpactFactorHolder(int impactFactor, char nucleotide, int length) { mImpactFactor = impactFactor; mNucleotide = nucleotide; mOcurrencesSum = new int[length]; mAcum = 0; } int mImpactFactor; char mNucleotide; int[] mOcurrencesSum; int mAcum; } } 

链接： https ：//codility.com/demo/results/demoJFB5EV-EG8/我期待实现类似于@Abhishek Kumar解决方案的Segment Tree

Answer 20

这是100％Scala解决方案：

 def solution(S: String, P: Array[Int], Q: Array[Int]): Array[Int] = { val resp = for(ind <- 0 to P.length-1) yield { val sub= S.substring(P(ind),Q(ind)+1) var factor = 4 if(sub.contains("A")) {factor=1} else{ if(sub.contains("C")) {factor=2} else{ if(sub.contains("G")) {factor=3} } } factor } return resp.toArray } 

和性能： https ： //codility.com/demo/results/trainingEUR4XP-425/

Answer 21

我的C ++解决方案

 vector solution(string &S, vector &P, vector &Q) { vector impactCount_A(S.size()+1, 0); vector impactCount_C(S.size()+1, 0); vector impactCount_G(S.size()+1, 0); int lastTotal_A = 0; int lastTotal_C = 0; int lastTotal_G = 0; for (int i = (signed)S.size()-1; i >= 0; --i) { switch(S[i]) { case 'A': ++lastTotal_A; break; case 'C': ++lastTotal_C; break; case 'G': ++lastTotal_G; break; }; impactCount_A[i] = lastTotal_A; impactCount_C[i] = lastTotal_C; impactCount_G[i] = lastTotal_G; } vector results(P.size(), 0); for (int i = 0; i < P.size(); ++i) { int pIndex = P[i]; int qIndex = Q[i]; int numA = impactCount_A[pIndex]-impactCount_A[qIndex+1]; int numC = impactCount_C[pIndex]-impactCount_C[qIndex+1]; int numG = impactCount_G[pIndex]-impactCount_G[qIndex+1]; if (numA > 0) { results[i] = 1; } else if (numC > 0) { results[i] = 2; } else if (numG > 0) { results[i] = 3; } else { results[i] = 4; } } return results; } 

Answer 22

/ * 100/100解决方案C ++。 使用前缀和。 首先在nuc变量中将字符转换为整数。 然后在二维向量中，我们考虑每个核苷x在其各自的prefix_sum [s] [x]中的S的出现。 在我们必须找出每个间隔K中发生的较低的核苷之后。

* /。 向量解（string＆S，vector＆P，vector＆Q）{

 int n=S.size(); int m=P.size(); vector > prefix_sum(n+1,vector(4,0)); int nuc; //prefix occurrence sum for (int s=0;s=0;u--) { if (prefix_sum[Q[k]+1][u] - prefix_sum[P[k]][u] != 0) lower_impact_factor = u+1; } P[k]=lower_impact_factor; } return P; 

}

Answer 23

我的C ++解决方案有什么问题？ 我得到[2,1,1]而不是[2,4,1]

 #include  #include  vector solution(string &S, vector &P, vector &Q) { int SumA[S.size()];SumA[0]=0; int SumC[S.size()];SumC[0]=0; int SumG[S.size()];SumG[0]=0; int SumT[S.size()];SumT[0]=0; for (int unsigned i=0;i answer(P.size()); for (int unsigned i=0;i0) { answer[i]=1;} else if (Csinrange>0) { answer[i]=2;} else if (Gsinrange>0) { answer[i]=3;} else {answer[i]=4;} } return answer; } 

Answer 24

  static public int[] solution(String S, int[] P, int[] Q) { // write your code in Java SE 8 int A[] = new int[S.length() + 1], C[] = new int[S.length() + 1], G[] = new int[S.length() + 1]; int last_a = 0, last_c = 0, last_g = 0; int results[] = new int[P.length]; int p = 0, q = 0; for (int i = S.length() - 1; i >= 0; i -= 1) { switch (S.charAt(i)) { case 'A': { last_a += 1; break; } case 'C': { last_c += 1; break; } case 'G': { last_g += 1; break; } } A[i] = last_a; G[i] = last_g; C[i] = last_c; } for (int i = 0; i < P.length; i++) { p = P[i]; q = Q[i]; if (A[p] - A[q + 1] > 0) { results[i] = 1; } else if (C[p] - C[q + 1] > 0) { results[i] = 2; } else if (G[p] - G[q + 1] > 0) { results[i] = 3; } else { results[i] = 4; } } return results; } 

Answer 25

我知道更多，但这是我得到100/100的答案..我希望它有点可读

 class GenomeCounter { public char GenomeCode { get; private set; } public int Value { get; private set; } private List CountFromStart; private long currentCount; public GenomeCounter(char genomeCode, int value) { CountFromStart = new List(); GenomeCode = genomeCode; currentCount = 0; Value = value; } public void Touch() { CountFromStart.Add(currentCount); } public void Add() { currentCount++; Touch(); } public long GetCountAt(int i) { return CountFromStart[i]; } } class Solution { static readonly Dictionary genomes = new Dictionary{ { 'A',1 }, { 'C',2 }, { 'G',3 }, {'T',4} }; public Solution() { GenomeCounters = new Dictionary(); foreach (var genome in genomes) { GenomeCounters[genome.Key] = new GenomeCounter(genome.Key, genome.Value); } } Dictionary GenomeCounters; int GetMinBetween(string S, int First, int Last) { if (First > Last) throw new Exception("Wrong Input"); int min = GenomeCounters[S[First]].Value; foreach (var genomeCount in GenomeCounters) { if (genomeCount.Value.GetCountAt(First) < (genomeCount.Value.GetCountAt(Last))) { if (min > genomeCount.Value.Value) min = genomeCount.Value.Value; } } return min; } void CalculateTotalCount(string S) { for (var i = 0; i < S.Length; i++) { foreach (var genome in GenomeCounters) { if (genome.Key == S[i]) genome.Value.Add(); else genome.Value.Touch(); } } } public int[] solution(string S, int[] P, int[] Q) { // write your code in C# 6.0 with .NET 4.5 (Mono) int M = P.Length; int N = S.Length; List Mins = new List(); CalculateTotalCount(S); for (int i = 0; i < M; i++) { Mins.Add(GetMinBetween(S, P[i], Q[i])); } return Mins.ToArray(); } } 

Answer 26

斯卡拉解决方案100/100

 import scala.annotation.switch import scala.collection.mutable object Solution { def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = { val n = s.length def arr = mutable.ArrayBuffer.fill(n + 1)(0L) val a = arr val c = arr val g = arr val t = arr for (i <- 1 to n) { def inc(z: mutable.ArrayBuffer[Long]): Unit = z(i) = z(i - 1) + 1L def shift(z: mutable.ArrayBuffer[Long]): Unit = z(i) = z(i - 1) val char = s(i - 1) (char: @switch) match { case 'A' => inc(a); shift(c); shift(g); shift(t); case 'C' => shift(a); inc(c); shift(g); shift(t); case 'G' => shift(a); shift(c); inc(g); shift(t); case 'T' => shift(a); shift(c); shift(g); inc(t); } } val r = mutable.ArrayBuffer.fill(p.length)(0) for (i <- p.indices) { val start = p(i) val end = q(i) + 1 r(i) = if (a(start) != a(end)) 1 else if (c(start) != c(end)) 2 else if (g(start) != g(end)) 3 else if (t(start) != t(end)) 4 else 0 } r.toArray } } 

Answer 27

这对我有用

  #include  vector solution(string &S, vector &P, vector &Q) { vector r; unordered_map> acum; acum.insert(make_pair('A', vector(S.length()))); acum.insert(make_pair('C', vector(S.length()))); acum.insert(make_pair('G', vector(S.length()))); acum.insert(make_pair('T', vector(S.length()))); int a = 0, c = 0, g = 0, t = 0; for(unsigned int i=0; i < S.length(); i++){ char ch = S.at(i); if(ch == 'C') c++; else if(ch == 'G') g++; else if(ch == 'T') t++; else if(ch == 'A') a++; acum.at('C')[i] = c; acum.at('G')[i] = g; acum.at('T')[i] = t; acum.at('A')[i] = a; } for(unsigned int i = 0; i < P.size(); i++){ int init = P[i], end = Q[i]; if(S.at(init) == 'A' || acum.at('A')[end] - acum.at('A')[init] > 0) r.emplace_back(1); else if(S.at(init) == 'C' ||acum.at('C')[end] - acum.at('C')[init] > 0) r.emplace_back(2); else if(S.at(init) == 'G' || acum.at('G')[end] - acum.at('G')[init] > 0) r.emplace_back(3); else if(S.at(init) == 'T' || acum.at('T')[end] - acum.at('T')[init] > 0) r.emplace_back(4); } return r; }