重复的DNA序列(位运算、哈希表)、括号生成(字符串、动态规划)、外出采摘的日本人(排序和顺序统计量)

重复的DNA序列(位运算、哈希表)

所有 DNA 都由一系列缩写为 ‘A’，‘C’，‘G’ 和 ‘T’ 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。

示例 1：
输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出：[“AAAAACCCCC”,“CCCCCAAAAA”]
示例 2：
输入：s = “AAAAAAAAAAAAA” 输出：[“AAAAAAAAAA”]

提示：

• 0 <= s.length <= 105
• s[i] 为 ‘A’、‘C’、‘G’ 或 ‘T’

解答：

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        Set<String> set = new HashSet<>();
        Set<String> help = new HashSet<>();
        for (int i = 0; i <= s.length() - 10; i++) {
            String cur = s.substring(i, i + 10);
            if (!set.add(cur))
                help.add(cur);
        }
        return new ArrayList<String>(help);
    }
}

括号生成(字符串、动态规划)

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的 **括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

解答：

class Solution {
    void gen(Stack<String> p, int lc, int rc, List<String> r, int n) {
        if (lc > n) {
            return;
        }
        if (lc == n && rc == n) {
            StringBuilder sb = new StringBuilder();
            for (String l : p) {
                sb.append(l);
            }
            r.add(sb.toString());
        }
        p.push("(");
        lc++;
        gen(p, lc, rc, r, n);
        p.pop();
        lc--;
        if (lc > rc) {
            p.push(")");
            rc++;
            gen(p, lc, rc, r, n);
            p.pop();
            rc--;
        }
    }
    public List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList<String>();
        Stack<String> p = new Stack<String>();
        gen(p, 0, 0, results, n);
        return results;
    }
}

外出采摘的日本人(排序和顺序统计量)

二战后的某一天，N个日本人来到了一个山洞休息，为了派出一个日本人去外面充满危险的丛林中采摘食物，他们设置如下游戏产生外出采摘的人： 1、首先，所有参加游戏的日本人按顺序编号为1、2、3…N； 2、接下来每个日本人心里产生一个数字，这个数字称为序号为 N的人的密码P； 3、所有参加游戏的人按照编号站成一个圈，长老为游戏设置初始密码K，从编号为 1的人开始报数，报到 K的人退出队伍，然后将自己心中的密码P说出来，由下一个人继续从 1开始报数，报到P的人退出队伍，以此类推； 4、当队伍中剩下一个人的时候，这个人就是今天要出去采摘的日本人，他可能回不来了！ 请各位同学设计程序并使用Java语言实现改程序，在用户输入了人数N、每个人的密码P和初始密码K的情况下，自动完成上面的选择过程，输出先后离开队伍的人的序号序列，最后输出要去采摘的日本人，输出他的编号。

解答：

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class JosephCircle {
    public int newJoseph(int n, int[] p, int k) {
        List<Integer> num = new ArrayList<Integer>();
        for (int i = 0; i < n; i++)
            num.add(i);
        int t = k, index = 0;
        for (int i = 0; i < n - 1; i++) {
            index = (index + t) % num.size();
            num.remove(index);
            t = p[index];
            if (index == num.size())
                index = 0;
        }
        return num.get(0) + 1;
    }
    public int oldJoseph(int n, int k) {
        int w = 0;
        for (int i = 2; i <= n; i++) {
            w = (w + k) % i;
        }
        return w;
    }
    public static void main(String[] args) {
        JosephCircle jc = new JosephCircle();
        Scanner scan = new Scanner(System.in);
        int n, k;
        int[] p = new int[100];
        System.out.print("Enter N = ");
        n = scan.nextInt();
        System.out.print("Enter P[] = ");
        for (int i = 0; i < n; i++) {
            p[i] = scan.nextInt();
        }
        System.out.print("Enter K = ");
        k = scan.nextInt();
        System.out.println();
        System.out.println("Survivor is No." + jc.newJoseph(n, p, k));
    }
}

本文内容到此结束了，
如有收获欢迎点赞👍收藏💖关注✔️，您的鼓励是我最大的动力。
如有错误❌疑问💬欢迎各位大佬指出。
保持热爱，奔赴下一场山海。🏃🏃🏃