---
# System prepended metadata

title: Math & Geometry (8)
tags: [working]

---

# Math & Geometry (8)

> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
> 
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)

<!-- 常用色碼紀錄
Easy:   <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard:   <font color="#ee2f56">**Hard**</font>
-->

## 1. Rotate Image
<font color="#ffbb00">**Medium**</font>

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:
<img src="https://hackmd.io/_uploads/rJh504O21l.png" width=400>

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

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

### Example 2:
<img src="https://hackmd.io/_uploads/B1R6ANd2ke.png" width=400>

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

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

### Constraints

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

### Recommended complexity

* Time complexity: $O(n^2)$
* Space complexity: $O(1)$

### Solution

**(1) 轉置**
觀察旋轉前後像素位置的改變: $(i, j) \rightarrow (j, n - 1 - i)$。有點類似轉置，但只有對 column 做轉置的動作。應該要思考讓 row 做一些改變使得它也能夠轉置。

$$
(i, j) \rightarrow (T(i), j) \rightarrow (j, T(i)) = (j, n - 1 - i)
$$

$$
\therefore T(i) = n - 1 - i
$$

其中 $n$ 為矩陣的行(列)數。因此 $T(i) = n - 1 - i$ 的轉換是將:

* 第 0 列與第 n - 1 列互換(最後一列)
* 第 1 列與第 n - 2 列互換(倒數第二列)

依此推類

![S__2572318](https://hackmd.io/_uploads/HkLwMS_hkg.jpg)

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

        # reverse row
        mid = n // 2
        for r in range(mid):
            for c in range(n):
                tmp = matrix[r][c]
                matrix[r][c] = matrix[n - 1 - r][c]
                matrix[n - 1 - r][c] = tmp
        
        # transpose
        for r in range(n):
            for c in range(n):
                if r < c:
                    tmp = matrix[r][c]
                    matrix[r][c] = matrix[c][r]
                    matrix[c][r] = tmp
```

**(2) 四角互換**

![S__2572319](https://hackmd.io/_uploads/HynofHOnke.jpg)

## 2. Spiral Matrix
<font color="#ffbb00">**Medium**</font>

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

### Example 1:

<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/fe678b92-8606-4e07-ce70-08ec3479aa00/public" width=200>

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

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

### Example 2:

<img src="https://imagedelivery.net/CLfkmk9Wzy8_9HRyug4EVA/8a460616-db14-4ccf-068b-00aa6d398400/public" width=200>

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

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

### Example 3:
```java
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]
```

### Constraints

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

### Recommended complexity

* Time complexity: $O(m \cot n)$
    * m is the number of rows
    * n is the number of columns
* Space complexity: $O(1)$ extra space

### Solution

依照題目所說旋轉的路徑分成四個方向的迴圈走。為了避免超過矩陣的邊界，所以另外使用 4 個指標指向目前矩陣的外層邊界(準備走但還沒走的路徑)。

<img src="https://hackmd.io/_uploads/Byu4QSd2yx.jpg" width=400>

每一次在外層行經的路徑可分為兩個步驟:

* 往右 + 往下
* 往左 + 往上

依據矩陣行列數的不同(奇數/偶數)，有可能走完「右 + 下」後就結束了，所以走完往右以及往下的迴圈後，中間需要穿插一次檢查矩陣是否走完，若滿足

* `left > right` 且
* `top > bottom`

表示矩陣走完

<img src="https://hackmd.io/_uploads/B1XHVS_hke.jpg" width=650>

```python=
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        res = []
        top, bottom = 0, len(matrix) - 1
        left, right = 0, len(matrix[0]) - 1

        while left <= right and top <= bottom:
            # from left to right (along top)
            for i in range(left, right + 1):
                res.append(matrix[top][i])
            top += 1

            # from top to bottom (along right)
            for i in range(top, bottom + 1):
                res.append(matrix[i][right])
            right -= 1

            if not (left <= right and top <= bottom):
                break
            
            # from right to left (along bottom)
            for i in range(right, left - 1, -1):
                res.append(matrix[bottom][i])
            bottom -= 1

            # from bottom to top (along left)
            for i in range(bottom, top - 1, -1):
                res.append(matrix[i][left])
            left  += 1
        
        return res            
```

## 3. Set Matrix Zeros
<font color="#ffbb00">**Medium**</font>

> Given an `m x n` matrix of integers `matrix`, if an element is `0`, set its entire row and column to `0'`s.
>
> You must update the matrix *in-place*.
>
> **Follow up**: Could you solve it using `O(1)` space?

### Example 1:
<img src="https://hackmd.io/_uploads/H1EN2jAhJe.png" width=500>

```java
Input: matrix = [
  [0,1],
  [1,0]
]

Output: [
  [0,0],
  [0,0]
]
```
### Example 2:
<img src="https://hackmd.io/_uploads/H1fHhsC3Jl.png" width=500>

```java
Input: matrix = [
  [1,2,3],
  [4,0,5],
  [6,7,8]
]

Output: [
  [1,0,3],
  [0,0,0],
  [6,0,8]
]
```

### Constraints

* `1 <= matrix.length, matrix[0].length <= 100`
* `-2^31 <= matrix[i][j] <= (2^31) - 1`

### Recommended complexity

* Time complexity: $O(m \codt n)$
    * m is the numbr of rows
    * n is the number of columns
* Space complexity: $O(1)$

### Solution

**(1) 方法一: 設置記號**
不能在尋找 0 的過程中把其他行或列設為 0，因為會影響後面位置的判斷。比較好的方式是做記號，只要 `matrix[r][c] = 0` 就把對應的行列的非 0 元素都記做 `'M'`。

第二次迭代再把記為 `'M'` 的位置設為 0。時間複雜度為 $O(m \cdot n(m + n))$，但空間複雜度為 $O(1)$

**(2) 方法二: 使用額外陣列紀錄行列**
第一次迭代使用兩個陣額外的一維布林陣列(`rowArr`/`colArr`) or hash set 紀錄 `matrix[r][c] = 0` 時的行跟列。

第二次迭代只要 `matrix[r][c]` 的列或行出現在 `rowArr` 或 `colArr` 中，就表示該位置應該設為 0。

時間複雜度為 $O(m \times n)＄$，空間複雜度為 $O(m + n)$

```python=
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        rows = len(matrix)
        cols = len(matrix[0])

        rowArr = set()
        colArr = set()
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 0:
                    rowArr.add(r)
                    colArr.add(c)
        
        for r in range(rows):
            for c in range(cols):
                if r in rowArr or c in colArr:
                    matrix[r][c] = 0
```

## 4. Happy number
<font color="#00ad5f">**Easy**</font>

> 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:
```java
Input: n = 100

Output: true
```
Explanation: 1^2 + 0^2 + 0^2 = 1

### Example 2:
```java
Input: n = 101

Output: false
```
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`

### Recommended complexity

* Time complexity: as good or better than $O(\log n)$
* Space complexity: as good or better than $O(\log n)$

### Solution

**(1) 使用一個 helper function 計算每個數字的 digital square sum**
對於任意正整數 n，總共有 $\log n + 1 \approx \log n$ 位，因此 help function 的時間複雜度 $= O(\log n)$

**(2) 計算 square sum 的結果分三個情況**

* sum = 1: True
* sum != 1
    * 沒出現過: 繼續計算
    * 出現過: False

```python=
class Solution:
    def isHappy(self, n: int) -> bool:
        
        repeat = set()
        while n not in repeat:
            repeat.add(n)

            if self.computeSum(n) == 1:
                return True
            else:
                n = self.computeSum(n)
        
        return False
            
    def computeSum(self, n):
        partialSum = 0
        while n // 10 != 0:
            r = n % 10
            n = n // 10

            partialSum += r **2
        
        partialSum += n **2
        return partialSum
```

## 5. Plus one
<font color="#00ad5f">**Easy**</font>

> 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:
```java
Input: digits = [1,2,3,4]

Output: [1,2,3,5]
```
Explanation `1234` + `1` = `1235`.

### Example 2:
```java
Input: digits = [9,9,9]

Output: [1,0,0,0]
```

### Constraints

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

### Recommended complexity

* Time complexity: $O(n)$
* Space complexity: $O(n)$

### Solution

從右段端開始分兩個狀況討論:

* 如果 `digits[i] >= 9`
    * 表示 `+1` 後需要進位，直接設 `digits[i] = 0` 後往前移動一個位數
* 如果 `digits[i] < 9`
    * 表示 `+1` 後不需要進位，直接 `+1` 後回傳剩餘的 `digits`

一旦可以往前推進就表示前一位有進位。直到整個 array 都走完表示每位數都需要進位，最後在 digits 前加上 `[1]` 即可

```python=
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        n = len(digits)
        for i in range(n - 1, -1, -1):
            if digits[i] < 9:
                digits[i] += 1
                return digits
            else:
                digits[i] = 0
        return [1] + digits
```

## 6. Power(x, n)
<font color="#ffbb00">**Medium**</font>

> `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:
```java
Input: x = 2.00000, n = 5

Output: 32.00000
```

### Example 2:
```java
Input: x = 1.10000, n = 10

Output: 2.59374
```

### Example 3:
```java
Input: x = 2.00000, n = -3

Output: 0.12500
```

### Constraints

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

### Recommended complexity

* Time complexity:  as good or better than $O(\log n)$
* Space complexity; as good or better than $O(\log n)$

### Solution

以 divide and conquer 做。對每個 $x^n$ 的數字計算 $x^{\frac{n}{2}}$

* 若 n 為偶數，則計算 $x^{\frac{n}{2}} \cdot x^{\frac{n}{2}}$
* 若 n 為奇數，則計算 $x^{n-1} \cdot 2$

直到 n = 1 為止(base condition)再回傳 x 本身($x^1 = x$)

<img src="https://hackmd.io/_uploads/rk23bh0hJx.jpg" width=500>

```python=
`class Solution:
    def myPow(self, x: float, n: int) -> float:
        def power(base, exp):
            if exp == 1:
                return base
            
            if exp % 2 == 0: # even
                return power(base, exp // 2) ** 2
            else:            # odd
                return power(base, exp - 1) * base
        
        if x == 0:
            return 0
        if n == 0:
            return 1
        if n > 0:
            return power(x, n)
        else:
            return 1 / power(x, -n)
```

## 7. Multiply Strings
<font color="#ffbb00">**Medium**</font>

> 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:
```java
Input: num1 = "3", num2 = "4"

Output: "12"
```

### Example 2:
```java
Input: num1 = "111", num2 = "222"

Output: "24642"
```

### Constraints

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

### Recommended complexity

* Time complexity: $O(m \cdot n)$
    * m is the length of string `num1`
    * n is the length of the `num2`
* Space complexity: $O(m + n)$

### Solution

![S__2572367](https://hackmd.io/_uploads/rJL9pIeTJx.jpg)

(1) 事前準備

* 從最低位數開始乘法: 反轉字串從頭開始迭代
* 相乘結果最多到 `len(num1) + len(num2)` 位數

(2) 逐位相乘
假設進行 `num1[i]` 與 `num2[j]` 的乘法，相乘後的結果應該要放在 `res` 的第 `i + j` 位置中，再去做進位

(3) 全部乘完後因為 `res` 的開頭可能會 = 0。Ex. `12 * 13 = 0156`。所以需要把後面的有效數字取出後再轉成字串

```python=
class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if num1 == '0' or num2 == '0':
            return '0'
        
        n, m = len(num1), len(num2)
        res = [0] * (n + m)
        num1, num2 = num1[::-1], num2[::-1]
        for i in range(n):
            for j in range(m):
                digit = int(num1[i]) * int(num2[j])
                res[i + j] += digit
                res[i + j + 1] += res[i + j] // 10
                res[i + j] = res[i + j] % 10
        
        res, begin = res[::-1], 0
        while begin < len(res) and res[begin] == 0:
            begin += 1
        
        res = res[begin:]
        for i in range(len(res)):
            res[i] = str(res[i])
        return "".join(res)
```

## 8. Detect Squares
<font color="#ffbb00">**Medium**</font>

> 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:
![image](https://hackmd.io/_uploads/BJaU0IeTkx.png)

```java
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. 
```

### Constraints

* `point.length == 2`
* `0 <= x, y <= 1000`

### Recommended complexity

* Time complexity: $O(1)$ for each `add()` and $o(n)$ for each `count()`
* Space complexity: $O(n)$

### Solution

給定一個 quert: (qx, qy) 要確定能不能形成正方形，要先去找對角線的點 (x, y)。滿足 |qx - x| = |qy - y| 就表示 (x, y) 是 query 的對角線。

![S__2572368](https://hackmd.io/_uploads/ByH2ZDe6Jx.jpg)

找到對角線後，透過對角點 (x, y) 和 query (qx, qy) 可以找到另外兩個頂點位置為 (x, qy) 以及 (qx, y)。因為點座標可以重複，所以將另外兩點的個數相乘後就是這組對角線可形成的正方形個數。只要迭代所有的點檢查哪些點可形成對角線，再把每組對角點的正方形個數相加後即可。

需要一個 array 儲存加入的點座標，一個 hash map 儲存每個點的出現次數。

```python=
class CountSquares:

    def __init__(self):
        self.ptsCount = {}
        self.pts = []

    def add(self, point: List[int]) -> None:
        point = tuple(point)
        self.ptsCount[point] = self.ptsCount.get(point, 0) + 1
        self.pts.append(point)

    def count(self, point: List[int]) -> int:
        res = 0
        qx, qy = point
        
        # find diagonal
        for x, y in self.pts:
            if (abs(qx - x) != abs(qy - y)) or (x == qx and y == qy):
                continue
            res += self.ptsCount.get((x, qy), 0) * self.ptsCount.get((qx, y), 0)
        return res
```
