# **Rotate Array**
###### tags: `Issue`、`Easy`、`Array`

## Issue
### For Q ratate array
1.[::]什麼意思？
https://www.gushiciku.cn/pl/pnZt/zh-tw

2.直接找到要轉到前面的值與其他陣列進行組合(兩陣列相加為組合)
這段話意思是複製然後拼接？ O(N) space?

### For Q rotate image
3.題目不是不能新創一個矩陣和in-place modification嗎？
4.如果用deep copy那個方法可以？
##

## Question


## Solution
- 想法:直接找到要轉到前面的值與其他陣列進行組合(兩陣列相加為組合)

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k%n
        nums[::] = nums[n-k:]+nums[:n-k]

- 想法:將陣列最後一個值移到陣列最前面，然後刪除，但發現這方法的時間複雜度太高，在跑長序列會逾時

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        if 0 <= k <= 10**5:
            for _ in range(k):
                if -2**31 <= nums[-1] <= 2**31 - 1:
                    nums.insert(0, nums[-1])
                    del nums[-1]        

# **Plus One**
## Question

## Solution

class Solution(object):
    def plusOne(self, digits):
        for i in range(len(digits)):
            a = len(digits)-1-i
            if digits[a] == 9:
                digits[a] = 0
            else:
                digits[a] += 1
                return digits
        return [1] + digits

# **Rotate Image**
## Question

## Solution
- 用新的矩陣取代，但不可行，會回傳原矩陣

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        rotatem =[]
        for i in range(len(matrix)):
            tmp = []
            for j in range(len(matrix)):
                tmp.append(matrix[len(matrix)-1-j][i])
            rotatem.append(tmp)
        print(rotatem)
        matrix = rotatem

## Solution
- 最快的方法，由外而內四個邊將矩陣元素值直接取代

class Solution(object):
    def rotate(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: None Do not return anything, modify matrix in-place instead.
        """
        #store the four corners then traverse in a windmill
        #then repeat for inner square
        offset = 0
        size = len(matrix)-1
        while True:
            for i in range(size):
                #starts at top left, top right, bottom right, bottom left
                list = [matrix[offset][i+offset], matrix[i+offset][size+offset], 
                        matrix[size+offset][size+offset-i], 
                        matrix[size+offset-i][offset]] 
                #now rotate it
                matrix[offset][i+offset] = list[3]
                matrix[i+offset][size+offset] = list[0]
                matrix[size+offset][size-i+offset] = list[1]
                matrix[size-i+offset][offset] = list[2]
            if size < 3:
                break
            offset += 1
            size -= 2

## Solution
- 列轉成行，再倒序

class Solution:
    def rotate(self, matrix):
        """
        Do not return anything, modify matrix in-place instead.
        """
        #find the transpose
        for row in range(0,len(matrix)):
          for col in range(row,len(matrix[0])):
            matrix[col][row] , matrix[row][col] = matrix[row][col] , matrix[col][row]
        #reverse the matrix  
        for row in matrix:
          row.reverse()