这是横渡河的代码

Question

Story

来自卡考小学的尼涅斯的朋友们和瑞安一起在秋天野餐时遇到了一条用踏脚石做的小溪，正准备过到另一边去。Ryan女士制定了以下规则，以便Ni ez和他的朋友能够安全过河：

• 踏脚石是排在一起的，孩子踩在石头上的次数是写在每一块石头上的。
• 当一个孩子踩在石头上的时候，石头上的数字就会减少一个。
• 当步进块数达到0时，您就不能再踩它们了。
• 一个孩子可以跳，跳几块石头。一个孩子可以跳过的最大石头数作为参数k。
• 如果一个孩子跳，你总是跳到最近的垫脚石，而不是0。

尼涅斯的朋友们都在河的左边，他们必须穿过河的右边，才算跨过踏脚石。

有多少孩子能过河，给定石头上的初始值和参数k?

约束

• 必须跨过踏脚石的Ninez朋友的数量被认为是无限的。
• 该石块阵列的大小至少为1，最大长度为200,000。
• stones数组中每个元素的初始值为1到200,000,000之间的自然数。
• K是大于或等于1的自然数，小于或等于石头的长度。

代码评审问题

我该如何修改我的代码？这是Kakao实习生代码测试。我用循环来改变石头数字时，步子和重复多次。它还能有多少人能过河。

原始挑战(韩文)

示例

stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
k=3

在第一个孩子穿过之后，这些石头有以下价值：

stones = [1, 3, 4, 2, 1, 0, 3, 1, 4, 0]

第二个孩子成功了，跳了两次

stones = [0, 2, 3, 1, 0, 0, 2, 0, 3, 0]

第三个孩子成功了，跳了四次

stones = [0, 1, 2, 0, 0, 0, 1, 0, 2, 0]

现在要跳4块石头才能到达另一边，这比k= 3还要大。所以这个输入的答案是三个孩子，或者简单地说是3。

def solution(stones, k):
    num=len(stones)
    answer=0
    for count in range(max(stones)):
        stat=-1
        for i in range(num):
            if stat==i-1:
                if stones[i]==0:
                    for j in range(i+1,num):
                        if stones[j]==0:
                            if j-stat>=k:
                                return answer
                            else:
                                pass
                        elif stones[j]!=0:
                            stat=j
                            stones[j]-=1
                            break
                elif stones[i]!=0:
                    stat=i
                    stones[i]-=1
        if stat+k>=num:
            answer+=1
        elif stat+k<num:
            return answer
    return answer

Answer 1

试图避免嵌套if和for循环

代码的结构是一组嵌套的for和if-elif-else语句。尝试通过重构代码或逻辑找到一种压缩这些代码的方法。下面是一些例子：

如果elif足够，则不需要使用else。

if stones[i]==0:
    # code
elif stones[i]!=0:
    # more code

可重写为：

if stones[i]==0:
    # code
else:  # you can place a comment here like: stones[i]!=0 
    # more code

将if语句与and或or合并：

if stat==i-1:
    if stones[i]==0:

可重写为：

if stat==i-1 and stones[i]==0:

如果不做任何事情，则不需要声明和else：

else:
    pass

可以省略。

尝试使用PEP8代码样式和有意义的变量命名

见PEP8。代码中的一些示例可以被其他Pythonistas改进，以获得一致的可读性：

使用运算符周围的空格和比较。这些(不相关的)线：

num=len(stones)
range(i+1,num)
if j-stat>=k:
    pass

变成：

num = len(stones)  # spaces around '='
range(i+1, num)    # space after ',' in function arguments
if j - stat >= k:  # spaces around '-' and '>='
    pass

使用有意义的函数和变量名

• solution() -> num_kids_crossing_river()
• answer -> num_kids或简单的kids
• i -> current_stone
• k -> max_leap
• 等。

使用文档字符串和注释来澄清代码

记录你的代码。将文档放在函数定义下面( "docstring")如下：

def num_kids_crossing_river(stones, max_leap)
""" Return the number of kids that can pass the array of stones. 
    <<some more text here; like in the text from the exercise>>

    Args:
        stones (list(int)): initial values on the stones.
        max_leap (int): maximum number of stones a kid can jump over/skip.

    Returns:
        int: the number of kids that can cross the river.

只要代码本身不清楚，就使用注释来记录您正在做的事情。记录算法/想法，而不是代码本身。

例如：

# Maximum number of iterations is the maximum number on the stones
for count in range(max(stones)):
    etc.

最重要的是:反思问题

所有这些都可以用来改进您的代码和编码风格，但是它并不真正优化您的代码。编码的一个重要步骤是首先考虑将要编码的内容以及如何对其进行编码。

如果你看这个例子，你会发现石头数组中的数字在减少，直到相邻有k个或更多的零。

因此，另一种表述问题的方法是:我可以从数组中减去多少次，直到有k或更多的零相邻？

现在假设k = 0 (没有跳转)。和stones = [5, 6, 7]。你可以看到/想象能通过的孩子的数量是5个。

现在假设k = 1和同一个stones。你可以看到/想象能够通过的孩子的数量是6。5首先变成0，但你可以跳过它。接下来，6变成0。

我们所能做的就是迭代这些石头，并检查k块石头的每一个“窗口”。并检查该窗口中的最大值。在这个步骤数之后，该窗口全部为0，游戏停止。所以我们需要找到第一个到达0的窗口。

所以，现在我们可以再用数学术语重新表述这个问题:长度为k的所有连续窗口的最大值的最小值是多少？

举例说明了问题陈述：k = 3; stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
+-------+                      # maximum = 5 for this window
   +-------+                   # maximum = 5 for this window
      +-------+                # maximum = 5 for this window
         +-------+             # maximum = 3 for this window
            +-------+          # maximum = 4 for this window
               +-------+       # maximum = 4 for this window
                  +-------+    # maximum = 5 for this window
                     +-------+ # maximum = 5 for this window

现在，所有这些最大值的最小值是3，这就是答案。

你可以看到，3的值正好出现在第一个0和第四个孩子被卡住的地方。

这里，我给出两个实现。一种是使用基本的Python概念，比如代码。第二种方法使用(中级Python概念)列表理解。

def min_max_of_subsection(array, k):
    """ Returns the minimum value of the maximum value of each subsection of length k in array.

    Args:
        array (list): an array of values (can be anything that has an order)
        k (int): length of the sub section

    Returns:
        value from array
    """
    max_subsection = []
    for array_index in range(len(array) - k + 1):
       max_subsection.append(max(array[array_index:array_index + k]))
    return min(max_subsection)


def min_max_of_subsection2(array, k):
    """ Returns the minimum value of the maximum value of each subsection of length k in array.

    Args:
        array (list): an array of values (can be anything that has an order)
        k (int): length of the sub section

    Returns:
        value from array
    """
    return min(max(array[idx:idx+k]) for idx in range(len(array) - k + 1))

print(min_max_of_subsection([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3))
print(min_max_of_subsection2([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3))

在网上试试！