例如:s = AGGTCTA
序列中包含了所有长度为1的('A','C','G','T')片段,但是长度为2的没有全部包含,例如序列中不包含"AA",所以输出2。
注:长度为2的全部DNA片段有"AA"、"AC"、"AG"、"AT"、"CA"、"CC"、"CG"、"CT"、"GA"、"GC"、"GG"、"GT"、"TA"、"TC"、"TG"和"TT",共16种。
输入包括一个字符串s,字符串长度length(1 ≤ length ≤ 2000),其中只包含'A','C','G','T'这四种字符。
输出一个正整数,即最短没有出现在DNA序列s中的DNA片段的长度。
AGGTCTA
2
ACGT
2
AACAGATACCGCTGGTCTT
3
#include<iostream> #include<string> #include<set> #include<math.h> using namespace std; int main(){ string x; cin>>x; int i,j,n=x.length(); for(i=1;i<=n;i++){ set<string> s; for(j=0;j<=n-i;j++) s.insert(x.substr(j,i)); if(s.size()<(int)pow(4,i)){ printf("%d",i); return 0; } } }
import java.util.*; public class Main{ public static void main(String args[]){ Scanner scan = new Scanner(System.in); String input = scan.nextLine(); int i,j,n = input.length(); for(i=1;i<=n;i++){ HashSet<String> set= new HashSet<String>(); for(j=0;j<n-i;j++) set.add(input.substring(j,j+i)); if(set.size()<Math.pow(4,i)){ System.out.println(i); break; } } } }
#-*-coding:utf-8-*- while True: try: refer=['A','C','G','T'] s=raw_input() n=len(s) tmp=s[0] i=0 d={} if 'A' in s: d[1]=1 if 'C' in s: d[2]=1 if 'G' in s: d[3]=1 if 'T' in s: d[4]=1 while(i<n): res=0 t=refer.index(tmp)+1 while(i<n and s[i]==tmp): i+=1 res+=1 if i<n: tmp=s[i] if 4*(res-1)+t in d:continue else:d[4*(res-1)+t]=1 q=len(d) ans=-1 for j in range(1,q+1): if j in d: continue else: ans=j break t=ans%4 g=ans/4 if(t>0): g+=1 print d except: break
#-*-coding:utf-8-*- while True: try: s=raw_input() n=len(s) t=0 la=0 lc=0 lg=0 lt=0 for i in range(n): if(s[i]=='A'): t+=1 else: la=max(la,t) t=0 la = max(la, t) t = 0 for i in range(n): if(s[i]=='C'): t+=1 else: lc=max(lc,t) t=0 lc = max(lc, t) t=0 for i in range(n): if(s[i]=='G'): t+=1 else: lg=max(lg,t) t=0 lg = max(lg, t) t = 0 for i in range(n): if(s[i]=='T'): t+=1 else: lt=max(lt,t) t=0 lt = max(lt, t) t = 0 ans=min(la,lc,lg,lt)+1 print ans except: break
不需要讨论实际的序列,只要比较序列的个数就好了。从长度为1到长度为n分别进行讨论,将长度 为i的子串加入到set容器中去,set容器会自动除去重复的元素,这样set容器的大小size()就 表示长度为i的种类数量了。长度为i的序列总共有4的i次方个(排列组合:每个位置都有四种 选择),然后将set容器的size()与4的i次方进行比较,如果小于4的i次方,那肯定存在不包含的 序列。 import java.util.*; public class Main { public static void main(String[] args) { Scanner SC = new Scanner(System.in); String str = SC.next(); System.out.println(fun(str)); } static int fun(String str) { for (int i = 1; i <= str.length(); i++) { Set<String> rq = new TreeSet<>(); for (int j = 0; j < str.length() - i; j++) { rq.add(str.substring(j, j+i)); } if (rq.size() < Math.pow(4, i)) { return i; } } return 1; } }
#include<iostream> #include<string> #include<unordered_set> #include<algorithm> using namespace std; int main(){ string s; cin>>s; unordered_set<string> ss;//保存每次可能的值 int k=0; while(1){ for(int i=0;i<s.size()-k;i++){ ss.insert(s.substr(i,k+1));//加入可能值 } if(ss.size()<pow(4,k+1)){cout<<k+1;return 0;}//判断可能值数量是否满足4^n的条件 k++; ss.clear(); } }
//利用set自动过滤相同元素的性质 #include<iostream> #include<set> #include<string> #include<cmath> using namespace std; //start为起始位置,返回str[start]到str[start+length-1]之间的字符串 string SecString(int start, int length, string str){ string m = ""; int i = 0; while (i < length){ m += str[start + i]; i++; } return m; } int main(){ string str; cin >> str; int m = str.size(); set<string> s; int c = 0,rec=0; for (int i = 0; i < m; i++){ c++; for (int j = 0; j < m-c+1; j++){ s.insert(SecString(j, c, str)); } //rec为最长片段不为c时s理论上应该有的元素个数 rec += pow(4, c); //s.size()<rec即表示s的元素个数小于最长片段不为c时s理论上的元素个数 //即最长片段为c if (s.size() < rec){ cout << c << endl; return 0; } } return 0; }
import itertools # itertools标准包,用于生成各种组合,非常方便 def dna(s): for i in range(1, len(s)+1): for j in itertools.product('ACGT', repeat = i): # 生成i长度的所有可能组合,结果是tuple形式 if ''.join(j) not in s: # 将结果组合成字符串,并看s中是否存在串 return i if __name__ == "__main__": s = input() print(dna(s))
private static int solve(String s) { LinkedList<String> linkedList = new LinkedList<>(); for (int i = 0; i < dns.length; i++) { String string = String.valueOf(dns[i]); if (s.contains(string)) { linkedList.add(String.valueOf(dns[i])); } else { return 1; } } return solve(s, linkedList); } private static int solve(String s, LinkedList<String> linkedList) { boolean find = false; int count = 0; while (!find) { String string = linkedList.poll(); for (int i = 0; i < dns.length; i++) { String string2 = string + dns[i]; if (!s.contains(string2)) { find = true; count = string2.length(); break; } linkedList.offer(string2); } } return count; }
#include<bits/stdc++.h> using namespace std; struct Node { vector<int>pos; int floor; Node(int x = 0) { floor = x; } }; void bfs(string s) { queue<Node*>myQue; Node* n1 = new Node(0); for(int i = 0,len = s.size(); i < len; i++) { n1->pos.push_back(i - 1); } myQue.push(n1); while(!myQue.empty()) { Node* tmp = myQue.front(); myQue.pop(); Node *a1 = new Node(tmp->floor + 1); Node *c1 = new Node(tmp->floor + 1); Node *g1 = new Node(tmp->floor + 1); Node *t1 = new Node(tmp->floor + 1); // 表示上一个结束了 for(int i = 0; i < (tmp->pos).size(); i++) { int t = tmp->pos[i] + 1;// 当前元素的下一位 if(t >= s.size()) continue; char c = s[t]; if(c == 'A') { a1->pos.push_back(t); }else if(c == 'C') { c1->pos.push_back(t); }else if(c == 'G') { g1->pos.push_back(t); }else if(c == 'T') { t1->pos.push_back(t); } } if(a1->pos.empty() || c1->pos.empty() || g1->pos.empty() || t1->pos.empty()) { cout << a1->floor << endl; return; }else { myQue.push(a1); myQue.push(c1); myQue.push(g1); myQue.push(t1); } } } int main() { std::ios::sync_with_stdio(false); string s; cin >> s; bfs(s); return 0; } 采用bfs的思维想法. 没想到用set列举...
这道题目要理解清楚题意才行,不存在的最短DNA序列是什么?
例如,长度为2的序列包括:(AA, AG, AC, AT, CA, CC, CG, CT ……..)
,要全部判断一遍才可以。并不是判断(AA, CC, GG TT)
就可以了。
所以,要一层一层的判断,长度为1的所有子序列,长度为2的所有子序列……长度为n的所有子序列。有点像二叉树的层序遍历。
def calc(string):
arr = ['']
for i in range(0, len(string) + 1):
tmpArr = [] # 下一层要判断的子序列。
for item in arr:
for char in ['A', 'C', 'G', 'T']:
if item + char not in string:
return i + 1
tmpArr.append(item + char)
arr = tmpArr
print(calc(input()))
import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.next(); ArrayList<String> list = new ArrayList<>(); list.add("A"); list.add("G"); list.add("C"); list.add("T"); String s="123"; for(int i=0;i<list.size();i++){ s = list.get(i); if(!str.contains(s)){ break; } list.add(s+"A"); list.add(s+"G"); list.add(s+"C"); list.add(s+"T"); } System.out.print(s.length()); } } 该题的解题思路,你可以最开始给集合list放入A C G T三个字符串,之后遍历集合,A+A A+C A+G A+T B+A B+C.......