Math & Geometry

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

DPまでに比べると優先度は下がるけど、一応解いておきます。

136. Rotate Image

Problem

Given a square n x n matrix of integers matrix, rotate it by 90 degrees clockwise.

You must rotate the matrix in-place. Do not allocate another 2D matrix and do the rotation.

Example 1:

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

Output: [
  [3,1],
  [4,2]
]

Copy

Example 2:

Input: matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

Output: [
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Copy

Constraints:

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

Solution

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

        for r in range(n):
            for c in range(r, n):
                matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
        
        for r in range(n):
            matrix[r].reverse()
        

137. Spiral Matrix

Problem

Given an m x n matrix of integers matrix, return a list of all elements within the matrix in spiral order.

Example 1:

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

Output: [1,2,4,3]

Copy

Example 2:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]

Copy

Example 3:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Copy

Constraints:

• 1 <= matrix.length, matrix[i].length <= 10
• -100 <= matrix[i][j] <= 100

Solution

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ROWS, COLS = len(matrix), len(matrix[0])
        # right, down, left, up
        DIRECTIONS = [[0,1],[1,0],[0,-1],[-1,0]]
        direction = 0
        visited = set()

        res = []
        r = c = 0
        for i in range(ROWS * COLS):
            res.append(matrix[r][c])
            visited.add((r,c))

            dr, dc = DIRECTIONS[direction]
            nr, nc = r + dr, c + dc

            # もしmatrix外に出ていたら方向転換する
            if (nr not in range(ROWS) or
                nc not in range(COLS) or
                (nr, nc) in visited
                ):
                direction = (direction + 1) % 4
                dr, dc = DIRECTIONS[direction]
                nr, nc = r + dr, c + dc
            
            r, c = nr, nc
            
        return res

138. Set Matrix Zeroes

Problem

Given an m x n matrix of integers matrix, return a list of all elements within the matrix in spiral order.

Example 1:

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

Output: [1,2,4,3]

Copy

Example 2:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

Output: [1,2,3,6,9,8,7,4,5]

Copy

Example 3:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Copy

Constraints:

• 1 <= matrix.length, matrix[i].length <= 10
• -100 <= matrix[i][j] <= 100

Solution

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        ROWS, COLS = len(matrix), len(matrix[0])
        
        # row = 0 を row 全体を0にするかどうかの目印に使う
        # col = 0 を col 全体を0にするかどうかの目印に使う
        # row = 1, col = 1について0にかえる
        # col = 0 について変える
        # row = 0 については、フラグを持っておく
        isRowZero = False
        for r in range(ROWS):
            for c in range(COLS):
                if matrix[r][c] == 0:
                    matrix[0][c] = 0
                    if r > 0:
                        matrix[r][0] = 0
                    else:
                        isRowZero = True
        
        # row = 1, col = 1 以降について変える
        for r in range(1, ROWS):
            for c in range(1, COLS):
                if matrix[r][0] == 0 or matrix[0][c] == 0:
                    matrix[r][c] = 0

        # col = 0 について変える
        if matrix[0][0] == 0:
            for r in range(ROWS):
                matrix[r][0] = 0
        
        # row = 0について変える
        if isRowZero:
            for c in range(COLS):
                matrix[0][c] = 0

139. Happy Number

Problem

A non-cyclical number is an integer defined by the following algorithm:

• Given a positive integer, replace it with the sum of the squares of its digits.
• Repeat the above step until the number equals 1, or it loops infinitely in a cycle which does not include 1.
• If it stops at 1, then the number is a non-cyclical number.

Given a positive integer n, return true if it is a non-cyclical number, otherwise return false.

Example 1:

Input: n = 100

Output: true

Copy

Explanation: 1^2 + 0^2 + 0^2 = 1

Example 2:

Input: n = 101

Output: false

Copy

Explanation:
1^2 + 0^2 + 1^2 = 2
2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4 (This number has already been seen)

Constraints:

• 1 <= n <= 1000

Solution

class Solution:
    def isHappy(self, n: int) -> bool:
        hash_set = set()

        while n != 1:
            if n in hash_set:
                return False
            
            hash_set.add(n)
            
            tmp = n
            next_n = 0
            while tmp:
                first_digit = tmp % 10
                tmp = tmp // 10
                next_n += first_digit ** 2
            n = next_n
        
        return True

140. Plus One

Problem

You are given an integer array digits, where each digits[i] is the ith digit of a large integer. It is ordered from most significant to least significant digit, and it will not contain any leading zero.

Return the digits of the given integer after incrementing it by one.

Example 1:

Input: digits = [1,2,3,4]

Output: [1,2,3,5]

Copy

Explanation 1234 + 1 = 1235.

Example 2:

Input: digits = [9,9,9]

Output: [1,0,0,0]

Copy

Constraints:

• 1 <= digits.length <= 100
• 0 <= digits[i] <= 9

Solution

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:

        res = []
        carry = 1

        for i in range(len(digits)-1, -1, -1):
            total = carry + digits[i]
            if total >= 10:
                carry = 1
                res.append(total % 10)
            else:
                carry = 0
                res.append(total)
        
        if carry:
            res.append(carry)

        res.reverse()
        return res

141. Pow(x, n)

Problem

Pow(x, n) is a mathematical function to calculate the value of x raised to the power of n (i.e., x^n).

Given a floating-point value x and an integer value n, implement the myPow(x, n) function, which calculates x raised to the power n.

You may not use any built-in library functions.

Example 1:

Input: x = 2.00000, n = 5

Output: 32.00000

Copy

Example 2:

Input: x = 1.10000, n = 10

Output: 2.59374

Copy

Example 3:

Input: x = 2.00000, n = -3

Output: 0.12500

Copy

Constraints:

• -100.0 < x < 100.0
• -1000 <= n <= 1000
• n is an integer.
• If x = 0, then n will be positive.

Solution

class Solution:
    def myPow(self, x: float, n: int) -> float:
        
        def calc(x: float, n: int) -> float:
            if n == 0:
                return 1
            
            if n == 1:
                return x
            
            if n % 2 == 0:
                return calc(x*x, n // 2)
            else:
                return x * calc(x*x, n // 2)
        
        if n > 0:
            return calc(x, n)
        else:
            return 1 / calc(x, -n)

142. Multiply Strings

Problem

You are given two strings num1 and num2 that represent non-negative integers.

Return the product of num1 and num2 in the form of a string.

Assume that neither num1 nor num2 contain any leading zero, unless they are the number 0 itself.

Note: You can not use any built-in library to convert the inputs directly into integers.

Example 1:

Input: num1 = "3", num2 = "4"

Output: "12"

Copy

Example 2:

Input: num1 = "111", num2 = "222"

Output: "24642"

Copy

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.

Solution

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0':
            return '0'
        
        res = [0] * (len(num1) + len(num2))

        for i in range(len(num1)-1, -1, -1):
            for j in range(len(num2)-1, -1, -1):
                digit = int(num1[i]) * int(num2[j])
                total = res[i+j+1] + digit

                res[i+j] += total // 10
                res[i+j+1] = total % 10
        
        res_s = ''.join(map(str, res))
        return res_s.lstrip('0')

143. Detect Squares

Problem

You are given a stream of points consisting of x-y coordinates on a 2-D plane. Points can be added and queried as follows:

• Add - new points can be added to the stream into a data structure. Duplicate points are allowed and should be treated as separate points.
• Query - Given a single query point, count the number of ways to choose three additional points from the data structure such that the three points and the query point form a square. The square must have all sides parallel to the x-axis and y-axis, i.e. no diagonal squares are allowed. Recall that a square must have four equal sides.

Implement the CountSquares class:

• CountSquares() Initializes the object.
• void add(int[] point) Adds a new point point = [x, y].
• int count(int[] point) Counts the number of ways to form valid squares with point point = [x, y] as described above.

Example 1:

Input: 
["CountSquares", "add", [[1, 1]], "add", [[2, 2]], "add", [[1, 2]], "count", [[2, 1]], "count", [[3, 3]], "add", [[2, 2]], "count", [[2, 1]]]
       
Output:
[null, null, null, null, 1, 0, null, 2]

Explanation:
CountSquares countSquares = new CountSquares();
countSquares.add([1, 1]);
countSquares.add([2, 2]);
countSquares.add([1, 2]);

countSquares.count([2, 1]);   // return 1.
countSquares.count([3, 3]);   // return 0.
countSquares.add([2, 2]);     // Duplicate points are allowed.
countSquares.count([2, 1]);   // return 2. 

Copy

Constraints:

• point.length == 2
• 0 <= x, y <= 1000

Solution

from collections import defaultdict

class CountSquares:

    def __init__(self):
        self.pointsCount = defaultdict(int)
        self.points = []

    def add(self, point: List[int]) -> None:
        self.points.append(point)
        self.pointsCount[tuple(point)] += 1

    def count(self, point: List[int]) -> int:
        res = 0
        new_x, new_y = point
        for x, y in self.points:
            if (abs(new_x-x) != abs(new_y-y) or new_x == x or new_y == y):
                continue
            
            res += self.pointsCount[(new_x, y)] * self.pointsCount[(x, new_y)]
        return res