- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址: https://leetcode.com/problems/minimum-genetic-mutation/description/
Agene string can be represented by an 8-character long string, with choices from "A", "C", "G", "T"
.
Suppose we need to investigate about a mutation (mutation from "start" to "end"), where ONE mutation is defined as ONE single character changed in the gene string.
Forexample, "AACCGGTT"
-> "AACCGGTA"
is 1 mutation.
Also, there is a given gene "bank", which records all the valid gene mutations. A gene must be in the bank to make it a valid gene string.
Now, given 3 things - start, end, bank, your task is to determine what is the minimum number of mutations needed to mutate from "start" to "end". If there is no such a mutation, return -1.
Note:
1、 Startingpointisassumedtobevalid,soitmightnotbeincludedinthebank.;
2、 Ifmultiplemutationsareneeded,allmutationsduringinthesequencemustbevalid.;
3、 Youmayassumestartandendstringisnotthesame.;
Example 1:
start: "AACCGGTT"
end: "AACCGGTA"
bank: ["AACCGGTA"]
return: 1
Example 2:
start: "AACCGGTT"
end: "AAACGGTA"
bank: ["AACCGGTA", "AACCGCTA", "AAACGGTA"]
return: 2
Example 3:
start: "AAAAACCC"
end: "AACCCCCC"
bank: ["AAAACCCC", "AAACCCCC", "AACCCCCC"]
return: 3
给出了一个起始基因 start
,一个结束基因 end
。
问能不能通过变换,每次变化当前基因的一位,并且变化后的这个基因在基因库中的为有效基因,最后变换成为 end
。如果可以的话,返回变换的最小次数。如果不可以的话,返回 -1.
以题目的示例 2 为例:
输入:start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出:2
变化的过程如下所示:
基本和 127. Word Ladderopen in new window 一模一样的,只不过把 26 个搜索换成了 4 个搜索,所以代码只用改变搜索的范围,以及最后的返回值就行了。
很显然这个问题是 BFS 的问题,同样是走迷宫问题的 4 个方向。
BFS使用队列,把每个还没有搜索到的点依次放入队列,然后再弹出队列的头部元素当做当前遍历点。
BFS总共有两个模板:
如果不需要确定当前遍历到了哪一层,BFS 模板如下。
while queue 不空:
cur = queue.pop()
if cur 有效且未被访问过:
进行处理
for 节点 in cur 的所有相邻节点:
if 该节点有效:
queue.push(该节点)
1 2 3 4 5 6 7
如果要确定当前遍历到了哪一层,BFS 模板如下。 这里增加了 level
表示当前遍历到二叉树中的哪一层了,也可以理解为在一个图中,现在已经走了多少步了。size
表示在当前遍历层有多少个元素,也就是队列中的元素数,我们把这些元素一次性遍历完,即把当前层的所有元素都向外走了一步。
level = 0
while queue 不空:
size = queue.size()
while (size --) {
cur = queue.pop()
if cur 有效且未被访问过:
进行处理
for 节点 in cur的所有相邻节点:
if 该节点有效:
queue.push(该节点)
}
level ++;
1 2 3 4 5 6 7 8 9 10 11 12
上面两个是通用模板,在任何题目中都可以用,是要记住的!
由于本题需要知道变换了多少次,因此需要确定当前遍历到哪一层,故本题中直接套用模板二。
代码总体思路:
利用队列保存有效的字符串
只要队列不空,就持续循环:
记录当前队列的长度,对队列中该长度的字符串逐一遍历:
如果搜索到 end
,直接返回当前的步数 step
否则,对当前字符串中的每个字符,都转变成 ACGT
四个字符,看新形成的字符串是否遇到过
步数 + 1
其中判断字符串是否遇到过,有两种方法:
Python, C++ 代码如下:
class Solution(object):
def minMutation(self, start, end, bank):
"""
:type start: str
:type end: str
:type bank: List[str]
:rtype: int
"""
bfs = collections.deque()
bfs.append((start, 0))
bankset = set(bank)
while bfs:
gene, step = bfs.popleft()
if gene == end:
return step
for i in range(len(gene)):
for x in "ACGT":
newGene = gene[:i] + x + gene[i+1:]
if newGene in bank and newGene != gene:
bfs.append((newGene, step + 1))
bank.remove(newGene)
return -1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
unordered_set<string> bank_set(bank.begin(), bank.end());
queue<string> que;
que.push(start);
unordered_set<string> visited;
visited.insert(start);
int step = 0;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; ++i) {
string cur = que.front(); que.pop();
if (cur == end) {
return step;
}
for (char gene : "ACGT") {
for (int j = 0; j < cur.size(); ++j) {
string next = cur;
next[j] = gene;
if (bank_set.count(next) && !visited.count(next)) {
que.push(next);
visited.insert(next);
}
}
}
}
step ++;
}
return -1;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
class Solution {
public:
int minMutation(string start, string end, vector<string>& bank) {
queue<string> q;
const int N = start.size();
q.push(start);
int step = 0;
while (!q.empty()) {
int size = q.size();
for (int s = 0; s < size; s++) {
auto cur = q.front(); q.pop();
if (cur == end) {
return step;
}
for (int i = 0; i < N; i++) {
for (char n : {'A', 'C', 'G', 'T'}) {
string next = cur.substr(0, i) + n + cur.substr(i + 1);
if (next == cur) continue;
for (auto it = bank.begin(); it < bank.end(); ++it) {
if (*it == next) {
q.push(next);
bank.erase(it);
break;
}
}
}
}
}
step += 1;
}
return -1;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
1、 BFS模板题,而且出现频率挺高的,记住我的模板就行;
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我是 Haskell 术语的初学者。我必须做一个显示所有最低位置的练习。 例如: [1,2,3,1,1] => 0,3,4 这些是最小位置。 我尝试用两种方法来做到这一点,但这些都不起作用。 请有人帮
我需要找到整个矩阵的最小值,它是“坐标”。在像 这样的矩阵中 matrix = 8 7 6 5 4 3 2 1 最小值为 (2, 4) 处的 1。 最佳答案 这可以很简单地通过使用
给定一个正整数“l”和“r”。找到最小的数字“n”,使得 l r: cnt = 32 for i in range(l, r+1): s = bi
numpy.minimum 似乎不适用于复数: np.minimum(5+3*1j,4+30*1j) (4+30j) 我想保持最大幅度的值。它只比较实部。元素最小比较的任何其他功能? MATLAB m
鉴于数据库中的以下事实: foo(a, 3). foo(b, 2). foo(c, 4). foo(d, 3). foo(e, 2). foo(f, 6). foo(g, 3). foo(h, 2).
假设我们给出了给定图 G 的最小生成树 T(有 n 个顶点和 m 个边)和一条权重为 w 的新边 e = (u, v),我们将添加到 G 中。 I) 检查 T 是否仍然是 MST。II) 如果不是,请
我有一个名为“posts”的elasticsearch索引。 http://127.0.0.1:9200/posts/doc/_count返回{"count":240000,"_shards":{"t
我在 MySQL 中有一个表,名称如下 我有两件事要处理 1- 停用所有未使用的书籍 isActive = 1 - Active isActive = 0 - Inactive is_inuse =
我的站点位于 www.ethoma.com/wd/ . 如您所见,我已经使用自己的代码实现了主题和所有菜单。我想在我的网站上安装 WordPress,这样我就可以简单地在 WordPress 上输入我
当我在 bool 数组上使用 numpy 函数 minimum() 和 maximum() 时,结果类型打印为 numpy.int32。但是,与 numpy.int32 类型的比较失败(即使在转换之后
我在分布式系统中遇到分片移动问题。 【问题】 最初每个分区负责任意数量的分片。 (这个数字可以是任意的,因为系统支持将分片从一个分区移动到另一个分区) 然后一个新的分区来了,系统需要重新分片。目标是使
我有 3 个这样的观点: 我需要定义一个约束,以便在蓝色或芥末色垂直调整大小时,红色 View 将保持在任一上 View 的最小距离处,例如 或者 那么我怎样才能达到那个结果呢??? 最佳答案 建立从
题目地址:https://leetcode.com/problems/minimum-area-rectangle/description/ 题目描述 Given a set of points
题目地址:https://leetcode-cn.com/problems/path-with-minimum-effort/ 题目描述 你准备参加一场远足活动。给你一个二维 rows x col
题目地址:https://leetcode.com/problems/minimum-absolute-difference/ 题目描述 Given an array of distinct in
题目地址:https://leetcode.com/problems/minimum-height-trees/description/ 题目描述 Fora undirected graph wi
题目地址:https://leetcode.com/problems/minimum-time-difference/description/ 题目描述: Given a list of 24-h
题目地址: https://leetcode.com/problems/minimum-genetic-mutation/description/ 题目描述 Agene string can be
你们能帮我解决一些我被困的家庭作业问题吗? 完整二叉树中的局部最小值被定义为小于其所有邻居(邻居 = 父、左子、右子)的节点。 我需要在给定的完整二叉树中找到一个局部最小值,它的每个节点都有不同的数字
(defun *smaller* (x y) ( if (> x y) y x)) (defun *minimum* (lst) (do ((numbers lst (cdr
我是一名优秀的程序员,十分优秀!