就地旋转数组

Question

我正在尝试在 Leetcode 上练习我的 Python。

问题是189。旋转阵列。

虽然在其他IDE中工作正常，但在Leetcode中仍然错误。这是我的代码：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        from collections import deque
        nums = deque(nums)
        for i in range(k):
            nums.appendleft(nums.pop())
        nums = list(nums)
        print(nums)

还是不知道。我的代码有什么问题？

Answer 1

list(nums)

和

deque(nums)

将创建一个完全不同的列表对象，因此不认为它是就地替换列表。我认为您必须对索引

i

处的列表使用通用赋值语句（即

nums[i] = <value>

）。下面的代码是使用递归 dfs 和就地列表修改的方法之一

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        
        k = k % len(nums)
        def traverse(nums, i, k, value, count, origin):
            next_i = (i + k) % len(nums)
            if next_i != origin and count < len(nums):
                count = traverse(nums, next_i, k, nums[i], count + 1, origin)
            nums[i] = value
            return count

        count = 0
        offset = 0
        while count < len(nums):
            count = traverse(nums, k + offset, k, nums[offset], count + 1, offset + k)
            offset += 1
    
        return nums

Answer 2

您的解决方案有效，但不符合要求。这根本不是问题所在。

您无需更改

nums

并就地执行所有操作：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        from collections import deque
        A = deque(nums[:])
        for i in range(k):
            A.appendleft(A.pop())
        nums[:] = list(A)

• 要“绕过”要求，请将

  A

  定义为新变量并将

  nums

  复制到

  A

  。

• 然后再次使用

  A

  将

  nums

  复制回

  nums[:]

  。

• 请注意，这不是他们要求的，只是为了告诉您您已经解决了问题，而不是根据要求。

---

一个非常简单的解决方案是使用切片，如下所示：

class Solution:
    def rotate(self, nums: List[int], k: int):
        l = len(nums)
        if k < 1 or l < 2 or k == l:
            return

        k %= l
        nums[:] = nums[-k:] + nums[:l - k]
        print(nums)


if __name__ == '__main__':
    print(Solution().rotate([1, 2, 3, 4, 5, 6, 7], k=3))
    print(Solution().rotate([-1, -100, 3, 99], k=2))

打印

[5,6,7,1,2,3,4]

[3, 99, -1, -100]

Answer 3

list 和 deque 创建一个不同的对象，它不被认为是替换列表的位置

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        l,r = 0, len(nums) -1

        while l<r:
          nums[l],nums[r] = nums[r], nums[l]
          l,r = l+1, r-1

        l,r = 0, k-1
        while l<r:
          nums[l],nums[r] = nums[r], nums[l]
          l,r = l+1, r-1
        
        l, r = k , len(nums) -1
        while l<r:
          nums[l],nums[r] = nums[r], nums[l]
          l,r = l+1, r-1
        
        

Answer 4

我的提交是正确的...

事实并非如此。 正如其他答案和评论所解释的那样，您的代码不满足此问题的要求。

虽然在其他IDE中可以正常工作...

没有。

您认为它“有效”的原因是您的测试方法不正确！

对代码的正确测试应该是这样的：

test = [1, 2, 3, 4, 5, 6, 7]
Solution().rotate(test, k=3)
print(test)

这将表明您的解决方案输出如下内容：

[5, 6, 7, 1, 2, 3, 4]
[1, 2, 3, 4, 5, 6, 7]

第一行来自方法中的

print

语句。 （它不应该在那里。除非要求明确说明它应该输出，否则方法不应该输出内容。）

第二行来自返回测试代码后的

print

...它表明

test

尚未就地进行修改。