LeetCode-187-重复的DNA序列-编程思维

重复的DNA序列

题目描述:所有 DNA 都由一系列缩写为 'A','C','G' 和 'T' 的核苷酸组成,例如:"ACGAATTCCG"。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来找出所有目标子串,目标子串的长度为 10,且在 DNA 字符串 s 中出现次数超过一次。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/repeated-dna-sequences/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:哈希

首先,判断特殊情况,如果字符串的长度小于11,说明不够组成一个目标子串,不可能有重复的序列,直接返回空。

否则,初始化一个map,用来记录每一个不重复的长度为10的子串,key为子串,value表示相应的key是否是重复序列。然后遍历字符串,每10位作为一个子串,判断当前子串如果不存在,则添加到key中;如果存在且已标为重复,则跳过,如果没有标为重复,则标为重复子串。

最后,返回标为重复的子串即为重复的序列。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class LeetCode_187 {
    /**
     * 哈希
     *
     * @param s
     * @return
     */
    public static List<String> findRepeatedDnaSequences(String s) {
        // 如果字符串的长度小于11,说明不够组成一个目标子串,不可能有重复的序列,直接返回空
        if (s == null || s.length() < 11) {
            return new ArrayList<>();
        }
        // 记录每一个不重复的长度为10的子串,key为子串,value表示相应的key是否是重复序列
        Map<String, Boolean> map = new HashMap<>();
        // 长度间隔为10,从第一个字符开始
        int startIndex = 0, endIndex = startIndex + 10;
        // 遍历到最后一个字符结束
        while (endIndex <= s.length()) {
            String substring = s.substring(startIndex, endIndex);
            // 如果当前子串不存在,则添加到key中;如果存在且已标为重复,则跳过,如果没有标为重复,则标为重复子串
            if (map.containsKey(substring)) {
                if (!map.get(substring)) {
                    map.put(substring, true);
                }
            } else {
                map.put(substring, false);
            }
            startIndex++;
            endIndex++;
        }
        return map.entrySet().stream().filter(e -> e.getValue()).map(Map.Entry::getKey).collect(Collectors.toList());
    }

    public static void main(String[] args) {
        // 测试用例,期望输出: ["AAAAACCCCC","CCCCCAAAAA"]
        for (String str : findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT")) {
            System.out.println(str);
        }
    }
}

【每日寄语】 星星之火,可以燎原。

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/kaesar/p/16190910.html

R2DBC正式孵化成功,利好Spring Webflux-编程思维

2022年4月25日,R2DBC社区宣布具有普遍可用性的1.0.0.RELEASE正式发布。 R2DBC致力于为反应式编程 API操作关系型数据库带来规范支持,R2DBC不同于我们熟知的JDBC规范,它是异步的、响应式的。 R2DBC经历了社区5年的努力和268张投票表决,终于达到了可以发布1.0的状态。经过0.8和

Halo 开源项目学习(四):发布文章与页面-编程思维

基本介绍 博客最基本的功能就是让作者能够自由发布自己的文章,分享自己观点,记录学习的过程。Halo 为用户提供了发布文章和展示自定义页面的功能,下面我们分析一下这些功能的实现过程。 管理员发布文章 Halo 项目中,文章和页面的实体类分别为 Post 和 Sheet,二者都是 BasePost 的子类。BasePost

深入了解 TiDB SQL 优化器-编程思维

分享嘉宾:张建 PingCAP TiDB优化器与执行引擎技术负责人 编辑整理:Druid中国用户组第6次大数据MeetUp 出品平台:DataFunTalk 导读: 本次报告张老师主要从原理上带大家深入了解 TiDB SQL 优化器中的关键模块,比如应用一堆逻辑优化规则的逻辑优化部分,基于代价的物理优化部分,还有和代价

LeetCode-441-排列硬币-编程思维

排列硬币 题目描述:你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。 给定一个数字 n,找出可形成完整阶梯行的总行数。 n 是一个非负整数,并且在32位有符号整型的范围内。 示例说明请见LeetCode官网。 来源:力扣(LeetCode) 链接:https://leetcod

LeetCode-190-颠倒二进制位-编程思维

颠倒二进制位 题目描述:颠倒给定的 32 位无符号整数的二进制位。 提示: 请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。 在 Java 中,编译器使用二进

度小满严澄:数据科学与金融风控模型-编程思维

导读: 众所周知,信息时代下的数据就是能源,就是生产力。但是面对海量、纷繁的数据,特别是在金融领域,如何充分地利用数据是核心问题。本次分享主要想和大家一起探讨下,在金融风控场景下,如何通过数据对齐模型和业务目标,哪些数据、方法可以应用于风控模型,通过哪些指标可以正确地评估模型效果,以及最终如何用数据科学解释模型结果。今