Day3-LeetCode Medium+Easy

今日题目：48. Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

Example 3:
Input: matrix = [[1]]
Output: [[1]]

Example 4:
Input: matrix = [[1,2],[3,4]]
Output: [[3,1],[4,2]]

Constraints:

• matrix.length == n
• matrix[i].length == n
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

思路：

因题目为rotate by 90 degrees，所以我由the last row之 first column开始，从下向上取，
取完的一个column，即为rotate後的row

My solution:

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
    n = len(matrix)

    for i in range(n):
        ans = []
        for j in range(n - 1, -1, -1):
            ans.append(matrix[j][i])
        matrix.append(ans)

    del matrix[0:2]

Result:

检讨：

後来看其他人的solution，看到一些不错的方法
像是分为两部分，先将 matrix transpose後，再对each row进行reflect
是一个可以更直接想到的方法！！

今日题目2: 136. Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:
Input: nums = [2,2,1]
Output: 1

Example 2:
Input: nums = [4,1,2,1,2]
Output: 4

Example 3:
Input: nums = [1]
Output: 1

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

思路：

建一个list放一个第一次出现的element,将nums内的elements和list比较，如没有则append进去，如已在内则remove

My solution:

class Solution(object):
    def singleNumber(self, nums):

        ans = []
        for n in nums:
            if n in ans:
                ans.remove(n)
            else:
                ans.append(n)
        return(ans[0])

Result:

检讨：

所花费的时间和memory都太多了，看了其他讨论区的solution
有以下两种酷酷的
第一个：

def singleNumber2(self, nums):
    res = 0
    for num in nums:
        res ^= num
    return res

第二个：

def singleNumber3(self, nums):
    return 2*sum(set(nums))-sum(nums)

给大家参考参考！！

以上报告完毕
明天见