Leetcode - Rotation

tags: Leetcode DSMI lab

Rotate Array

觀察: 假設len(nums)=5，rotate 6次和rotate 1次的效果是一樣的
=>rotate k times is equivalent to rotate k%len(nums)

• Solution 1

  class Solution(object):
      def rotate(self, nums, k):
          optimize_step=k%len(nums) 
          
          for i in range(optimize_step):
              first=nums[-1]
              nums.insert(0,first)
              nums.pop()
          return nums

• Solution 2

  class Solution(object):
      def rotate(self, nums, k):
          n = len(nums)
          a = [0] * n
          for i in range(n):
              a[(i + k) % n] = nums[i]
              
          nums= a
          return nums

• Solution 3

  class Solution:
      def rotate(self, nums, k):
          k = k % len(nums)
          nums[k: len(nums)], nums[:k] = nums[: len(nums) - k], nums[-k:]
         
          return nums

Rotate List

• Define a linked list used in leetcode

class ListNode:
    def __init__(self, val=0, next=None):
         self.val = val
         self.next = next
    
    def print_list(self):
        figure=str(self.val)+"->"

        curr=self.next
        while curr:
            figure=figure+str(curr.val)+"->"
            curr=curr.next
        figure=figure+"NULL"
        print(figure)
        
# 1->2->3->4->5->NULL
LN_list=[ListNode(5,None)]
for i in [4,3,2,1]:
    LN_list.append(ListNode(i, LN_list[-1]))
Input=LN_list[-1]          
Input.print_list()

• Solution

    
  class Solution(object):
      def rotateRight(self, head, k):
          """
          :type head: ListNode
          :type k: int
          :rtype: ListNode
          """
          if (k==0 or head is None):
              return head
          
          if head.next is None: #Linked List 長度為1
              return head
          
          #計算有幾個node:
          count=head
          length=0
          while count:
              count=count.next
              length+=1
         #開始轉     
          optimize_steps=k%length #轉到第length 步的時候就根本來的一樣了
          for i in range(optimize_steps):
              curr=head
              while (curr.next.next):
                  curr=curr.next
              
              temp=curr.next #本來的最後一個node
              curr.next=None #本來的倒數第二個node接None
              temp.next=head 
              head=temp #本來的最後一個node接到最前面
          return head

Rotate Image

• Solution

  class Solution(object):
      def rotate(self, matrix):
          size=len(matrix)
          history={}
          for i in range(size):
              for j in range(size):
                  history[(j,size-1-i)]=matrix[j][size-1-i]
  
                  if (i,j) in history:
                      matrix[j][size-1-i]=history[(i,j)]
                  else:
                      matrix[j][size-1-i]=matrix[i][j]