自由之路
我想知道，我是否可以使我的解决办法更短和更有效率。下面是挑战的描述(这是一个Leetcode问题) -
在视频游戏Fallout 4中，“自由之路”要求玩家到达一个名为“自由之环”的金属刻度盘，并使用这个表盘拼出一个特定的关键字来打开门。给定一个字符串ring__，它表示刻在外部环上的代码，而另一个字符串key__表示关键字需要拼写。您需要找到最小的步骤数，以便拼写关键字中的所有字符。最初，戒指的第一个字符是在12:00方向对齐。您需要逐个拼写字符串键中的所有字符，方法是顺时针或逆时针旋转环，使字符串键的每个字符在12:00方向对齐，然后按中心按钮。在旋转环的阶段，拼写关键字符键我-
- 你可以顺时针旋转环，也可以逆时针旋转一个place__，它可以算作1步。旋转的最终目的是在12:00方向对齐字符串环的一个字符，其中该字符必须等于字符键我__。
- 如果字符键我已在12:00方向对齐，则需要按中心按钮拼写，这也可算作1步。按压后，您可以开始在键(下一阶段)中拼写下一个字符，否则，您已经完成了所有拼写。
例子-
输入:环状=“教化”，key = "gd“输出:4#解释：#对于第一个键字符'g'，因为它已经到位，我们只需要一个步骤来拼写这个字符。#对于第二个关键字符'd'，我们需要逆时针旋转环“教鞭”两个步骤，使其成为“滴答”。#此外，我们还需要多一个步骤来拼写。#最后的输出是4。注意-
- 环和键的长度都在
1到100__的范围内。 - 两个字符串中只有小写字母，两个字符串中可能都有一些重复字符。
- 可以保证字符串键始终可以通过旋转字符串ring__拼写。
这是我对这个挑战的解决方案-
# Uses dynamic programming
def find_rotate_steps(ring, key):
"""
:type ring: str
:type key: str
:rtype: int
"""
dp = [[min(i, len(ring) - i) for i in range(len(ring))]]
dp.extend([[float('inf')] * len(ring) for _ in range(len(key))])
for i in range(1, len(key) + 1):
for j in range(len(ring)):
if ring[j] != key[i - 1]:
continue
min_step = float('inf')
for k in range(len(ring)):
if dp[i - 1][k] == float('inf'):
continue
step = abs(k - j)
step = min(step, len(ring) - step) + 1 + dp[i - 1][k]
min_step = min(min_step, step)
dp[i][j] = min_step
return min(dp[-1])下面是示例输出所需的时间-
# %timeit find_rotate_steps("godding", "gd")
36.2 µs ± 1.33 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)这是我302个测试用例的代码结果-
注-以下是动态编程的含义(根据freeCodeCamp) -
动态规划就是将优化问题分解为简单的子问题，并将每个子问题的解存储起来，使每个子问题只求解一次。
回答 1
Code Review用户
发布于 2019-06-17 15:41:10
很难理解，您的代码是如何工作的，所以我首先将变量名更改为更有意义的形式，并修复了不必要的+1、-1操作(i - 1、1, len(key) + 1等)：
class Solution:
def findRotateSteps(self, ring, key):
cumulative_lens = [[min(i, len(ring) - i) for i in range(len(ring))]]
cumulative_lens.extend([[float('inf')] * len(ring) for _ in range(len(key))])
for key_num in range(len(key)):
for new_ring_pos in range(len(ring)):
if ring[new_ring_pos] != key[key_num]:
continue
min_sum_len = float('inf')
for prev_ring_pos in range(len(ring)):
prev_ltr_sum_len = cumulative_lens[key_num][prev_ring_pos]
if prev_ltr_sum_len == float('inf'):
continue
clk_w_len = abs(prev_ring_pos - new_ring_pos)
a_clk_len = len(ring) - clk_w_len
new_sum_len = min(clk_w_len, a_clk_len) + prev_ltr_sum_len + 1
min_sum_len = min(min_sum_len, new_sum_len)
cumulative_lens[key_num + 1][new_ring_pos] = min_sum_len
return min(cumulative_lens[-1])现在，我们可以像阅读故事一样阅读代码。低性能的原因是如何存储和搜索访问的信件透镜(cumulative_lens)。将它们保存在列表中，因此需要遍历所有项，而不是为每个键值查找inf项：
for prev_ring_pos in range(len(ring)):
prev_ltr_sum_len = cumulative_lens[key_num][prev_ring_pos]
if prev_ltr_sum_len == float('inf'):
continue你的戒指上有100个字母，钥匙里有10个字母。你发现所有可能的长度在环(只有3)到第一个键的字母和移动到第二个。在下一个键的信件处理中只需要3个，而不是检查其他97个项目，这将是很好的，这是'infs‘。这可以通过在字典中存储环形字母来实现--Python的哈希表结构，如下所示：
letter_indexes = {
'a' : [first a's index, second a's index],
'c' : [first c's index, second c's index, third c's index],
etc
}在这种情况下，我们可以通过执行letter_indexes[letter]获得所需字母位置的列表，而不是干扰其他位置。我写了我自己的解决方案，最后看出来。
此外，我还对代码进行了一些重构：
- 将多个
len(ring)调用更改为ln_ring变量--性能没有提高，但可读性更强。 - 更改为key_num in range(len(key))：new_ring_pos in range(len(ring))：if ring新的_环_位置 != key钥匙_数量：类似于更多的pythonic结构:对于key_num，key_ltr在枚举(Key)中:对于new_ring_pos，ring_ltr在枚举(Ring)：if key_ltr != ring_ltr：
结果：
class Solution:
def findRotateSteps(self, ring, key):
ln_ring = len(ring)
cumulative_lens = [[min(i, ln_ring - i) for i in range(ln_ring)]]
cumulative_lens.extend([[float('inf')] * ln_ring for _ in range(len(key))])
for key_num, key_ltr in enumerate(key):
for new_ring_pos, ring_ltr in enumerate(ring):
if key_ltr != ring_ltr:
continue
min_sum_len = float('inf')
for prev_ring_pos, prev_ltr_sum_len in enumerate(cumulative_lens[key_num]):
if prev_ltr_sum_len == float('inf'):
continue
clk_w_len = abs(prev_ring_pos - new_ring_pos)
a_clk_len = ln_ring - clk_w_len
new_sum_len = min(clk_w_len, a_clk_len) + prev_ltr_sum_len + 1
min_sum_len = min(min_sum_len, new_sum_len)
cumulative_lens[key_num + 1][new_ring_pos] = min_sum_len
return min(cumulative_lens[-1])我的解决方案：
它的工作原理与您的相似，但由于字典的使用，它的速度要快得多。
class Solution:
def findRotateSteps(self, ring, key):
# the 'prev_ltr' variable should have the start value in the
# beginning, so the '#' character is choosed
# It can be changed to any character different from key's content
# In other words, it is like '-1' item with 0 index.
ltr_indexes = {'#' : [0]}
for idx, ltr in enumerate(ring):
ltr_indexes.setdefault(ltr, []).append(idx)
ln = len(ring)
l_lens = [0] * ln
prev_ltr = '#'
for ltr in key:
for pos in ltr_indexes[ltr]:
all_variants = []
for prev_pos in ltr_indexes[prev_ltr]:
clk_w = abs(prev_pos - pos)
a_clk = ln - clk_w
all_variants.append(min(clk_w, a_clk) + l_lens[prev_pos])
l_lens[pos] = min(all_variants)
prev_ltr = ltr
return min(l_lens[pos] for pos in ltr_indexes[ltr]) + len(key)https://codereview.stackexchange.com/questions/221915
复制相似问题
腾讯云开发者
