重复的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));
}
}
本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????????
保持热爱，奔赴下一场山海。????????????