- 浏览: 173219 次
- 性别:
- 来自: 济南
文章分类
最新评论
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].
给定一个DNA序列,从中找出长度为10的出现次数大于一次的所有子序列。我们可以借助string的substring方法,从第一个字符开始一次截取,借助哈希表查看是否是重复的子串,如果重复就将这个字符串放入结果集中(结果集中不能重复),对于解决结果集中不能重复我们可以通过contains方法来解决,也可以通过建立两个哈希表,判断一个子串是否应该加入结果集合中时,如果该子串在第一个集合中存在,在第二个集合中不存在,这种情况下就加入,并且这样可以保证结果集中不会有重复的结果。set中的add方法,如果存在要加入的元素返回false,如果不存在当前要加入的元素返回true。代码如下:
我们还可以通过位运算来处理,DNA序列中只有四个元素,我们用两个比特位就可以表示,在构造子串的时候,设置一个变量,初始值为0,然后每次移动两位添加新的元素,移动十次之后就构成了一个子串,这样我们通过比较这个数是否在集合中出现就可以了。代码如下:
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
For example,
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"].
给定一个DNA序列,从中找出长度为10的出现次数大于一次的所有子序列。我们可以借助string的substring方法,从第一个字符开始一次截取,借助哈希表查看是否是重复的子串,如果重复就将这个字符串放入结果集中(结果集中不能重复),对于解决结果集中不能重复我们可以通过contains方法来解决,也可以通过建立两个哈希表,判断一个子串是否应该加入结果集合中时,如果该子串在第一个集合中存在,在第二个集合中不存在,这种情况下就加入,并且这样可以保证结果集中不会有重复的结果。set中的add方法,如果存在要加入的元素返回false,如果不存在当前要加入的元素返回true。代码如下:
public class Solution { public List<String> findRepeatedDnaSequences(String s) { List<String> list = new ArrayList<String>(); Set<String> set = new HashSet<String>(); Set<String> secondSet = new HashSet<String>(); if(s == null || s.length() <= 10) return list; for(int i = 0; i <= s.length() - 10; i++) { String str = s.substring(i, i + 10); if(!set.add(str) && secondSet.add(str)) { list.add(str); } } return list; } }
我们还可以通过位运算来处理,DNA序列中只有四个元素,我们用两个比特位就可以表示,在构造子串的时候,设置一个变量,初始值为0,然后每次移动两位添加新的元素,移动十次之后就构成了一个子串,这样我们通过比较这个数是否在集合中出现就可以了。代码如下:
public class Solution { public List<String> findRepeatedDnaSequences(String s) { List<String> list = new ArrayList<String>(); Set<Integer> set = new HashSet<Integer>(); Set<Integer> secondSet = new HashSet<Integer>(); if(s == null || s.length() <= 10) return list; int[] map = new int[26]; map['A' - 'A'] = 0; map['C' - 'A'] = 1; map['G' - 'A'] = 2; map['T' - 'A'] = 3; for(int i = 0; i <= s.length() - 10; i++) { int key = 0; for(int j = i; j < i + 10; j++) { key |= map[s.charAt(j) - 'A']; key <<= 2; } if(!set.add(key) && secondSet.add(key)) { list.add(s.substring(i, i + 10)); } } return list; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 224Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 223You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 339Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 330Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 448Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 427Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 426The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 384Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 515Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 528Given n non-negative integers r ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 879Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 553Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 599Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 762Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 732You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 626For a undirected graph with tre ... -
Bulb Switcher
2016-02-28 12:12 347There are n bulbs that are init ...
相关推荐
Sequences Medium Single Number(落单的数) 、 / Medium Single Number II(落单的数 II) 、 Medium Single Number III(落单的数 III) Medium Hash Function(哈希函数) Easy Space Replacement(空格替换) Easy Insert...
Repeated DNA Sequences Number of 1 Bits Gray Code Single Number Single Number II Single Number III Power of Two Missing Number Maximum Product of Word Lengths Bitwise AND of Numbers Range Power of ...
java lru leetcode ##Thinking in Java chapter21 ##Netty in Action ####chapter2: echo server/client ##数据结构与算法 ####动态规划 CUT: 分隔钢筋 LCS: 最长公共子序列 ...[Repeated DNA Sequences] () [Lar
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
SPSS Repeated measures ANOVA
dna匹配 leetcode leetcode刷题--C++ 哈希表 Longest Substring Without Repeating Characters 哈希表 双指针 滑动窗口 Substring with Concatenation of All Words 哈希表 注意匹配方向 ...Repeated DNA S
博客中测试代码 【Protocol Buffer】Protocol Buffer入门教程(五):repeated限定修饰符 博客网址:https://blog.csdn.net/dengjin20104042056/article/details/102465638
Repeated Games and Reputation+Game Theor y: Analysis of Conflict+Game Theory for Applied Economists:北大光华学习资料,翁盒老师主讲 高级微观经 济专题 北大光华 翁翕老师主讲 Topics in Advanced Micro ...
repeated限定修饰符的使用,相关教程:http://blog.csdn.net/tennysonsky/article/details/73921025
Solve the following recurrence relation by repeated substitution T(n) = 2T(n/2) + n^3, T(1) = 1
spss数据分析常用数据集:repeated.sav 统计分析及模型构建中常用的数据集; 学习软件的时候,会苦于没有数据进行实操,而其实一般分析软件都会自带数据,现在介绍如何获取SPSS软件自带的数据。 纽约时报的一篇文章...
Building hierarchical structures for 3D scenes with repeated elements
yarn add --dev stylelint-no-repeated-nesting 在.stylelint.yml配置中导入插件并设置规则: plugins: - stylelint-no-repeated-nesting 规则 将blinkist/no-repeated-nesting设置为true以启用该插件。 rules: ...
反复的弦乐游戏 克隆仓库后,您应该安装依赖项 npm install 你可以通过运行看到问题 npm start 在code/index.js编写您的代码 您可以在运行完成后运行测试 npm test 祝你好运
最长非重复子串没有重复字符的最长子串的长度( )
定义protobuf文件(包含enum,message,required,optional,repeated, 结构体定义中引用另一个结构体), 生成java文件,能够构建java对象,并转化为字节byte或者流,能够将流或字节转化为对象
修剪重复修剪连续重复的子字符串: foo--bar---baz → foo-bar-baz安装$ npm install trim-repeated用法import trimRepeated from 'trim-repeated' ;trimRepeated ( 'foo--bar---baz' , '-' ) ;//=> 'foo-bar-baz'...
安装 : npm install retext-repeated-words用假设我们有以下文件example.txt : Well, it it doesn’t have to to be. Like a fish in thethe sea.…我们的脚本example.js如下所示: var vfile = require ( 'to-...
iReport分组报表 利用Print Repeated Values属性以及加边框实现
Planning Repeated Degradation Testing for Products With Three-Source Variability