---
title: Leetcode - Rotation
date: 2020-06-04 14:37:00
comments: true
author: Darcy
categories:
- meeting
tags:
- Leetcode
---
###### tags: `Leetcode` `DSMI lab`
## Rotate Array
<!-- more -->
觀察: 假設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]