# 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 列互換(倒數第二列)
依此推類
```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) 四角互換**
## 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
(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:
```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 的對角線。
找到對角線後，透過對角點 (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
```
Sign in with Wallet
Connect another wallet