# **程式筆記(math)**
:::info
:information_source: 日期 : 2023/08/12
:::
**:star2:**
* 加法
remainder, carry = ans % 10, ans // 10
* 運算符
% 餘數
** 次方
---
**:star2:四則運算**
**加法**
* Plus One
把list看成數字並加1
```python
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
n = len(digits)
for i, d in enumerate(digits[::-1]):
if d == 9:
digits[n - i - 1] = 0
if i == n - 1:
return [1] + digits
else:
digits[n - i - 1] += 1
return digits
```
**次方**
* Pow(x, n) 實作次方
dfs 時間/空間複雜度為log2(n)
```python
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1/x
n = -n
return self.dfs(x, n)
def dfs(self, x, n):
if n == 1:
return x
if n == 0:
return 1
sub_res = self.dfs(x, n // 2)
res = sub_res * sub_res
if n % 2:
res *= x
return res
```
binary 法
```python
class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1/x
n = -n
pow2 = 1
res = 1
while n:
res *= x ** ((n % 2) * pow2)
n = n >> 1
pow2 *= 2
return res
```
* Happy Number
```
Input: n = 19
Output: true
Explanation:
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1
```
不停的求數字平方和，當數字拆開平方，全加起來為1，就為happy number
*如果產生迴圈，代表永遠都不可能找到平方和為1(永遠都在這個回圈內旋轉)
*一旦找到平方和為1則回傳True
```python
class Solution:
def isHappy(self, n: int) -> bool:
visited = set()
temp = 0
while True:
while n:
temp += (n % 10) ** 2
n = n // 10
if temp == 1:
return True
if temp in visited:
return False
visited.add(temp)
n = temp
temp = 0
```
**乘法**
* Multiply Strings str互乘
以num1為基準，num2的各個數單獨取出，並配合位數去補0
```python
class Solution:
def multiply(self, num1: str, num2: str) -> str:
res = 0
for i2, n2 in enumerate(num2[::-1]):
temp, carry, subRes = 0, 0, 0
for i1, n1 in enumerate(num1[::-1]):
multi = (ord(n2) - ord("0")) * (ord(n1) - ord("0"))
multi += carry
temp, carry = multi % 10, multi // 10
subRes += temp * (10 ** i1)
# there is a carry but we are in the last digit
if i1 == len(num1) - 1 and carry:
subRes += carry * (10 ** (i1 + 1))
res += (subRes * (10 ** i2))
return str(res)
```
* Nth Digit
先找到對應的section，然後在這個section總共的shift為何，接下來減1去彌補python首個index為0的問題，接下來就很單純地做%和floor
```
1 ~ 9, 9 : 1 -> 9
10 ~ 99, 90 : 2 -> 180
100 ~ 999, 900 : 3 -> 2700
# n = 200 -> 11
100 101 102 10
```
```python
class Solution:
def findNthDigit(self, n: int) -> int:
digit = base = 1 # starting from 1 digit
while n > 9 * base * digit: # upper limit of d digits
n -= 9 * base * digit
digit += 1
base *= 10
# n = 3 (n = 10, 11)
# q, r = divmod(n-1, digit)
# n - 1 : index start from 0
q = (n - 1) // digit # q = 1
r = (n - 1) % digit # r = 0
return int(str(base + q)[r])
```
---
**:star2:座標**
* Detect Squares 看座標們可否形成square
dict 統計出現座標數量
假設給定px, py，遍歷dict找對角座標x, y
需要檢查
1. 長度是否相同(正方形)
2. 剩餘兩座標是否存在
3. 是否x != px and y != py
```python
class DetectSquares:
def __init__(self):
self.record = defaultdict(int)
def add(self, point: List[int]) -> None:
self.record[(point[0], point[1])] += 1
def count(self, point: List[int]) -> int:
px, py = point
res = 0
print(self.record)
for (x, y), val in self.record.items():
if (px, y) in self.record and (x, py) in self.record and abs(px - x) == abs(py - y) and px != x and py != y:
res += self.record[(px, y)] * self.record[(x, py)] * val
return res
# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)
```
---
**:star2:其他**
* Task Scheduler
```
tasks = ["A","A","A","B","B","B"]
n = 2 # 代表每一個相同字母之間要距離n
```
```
假設有[A,A,A,B,B,B,B]，n=2
會先將最大出現次數的排下去並且空好空格
B _ _ B _ _ B _ _ B
然後將剩下的字母依序排下去
B A _ B A _ B A _ B
(B A _ )(B A _ )(B A _ )B
B出現的次數 - 1 = 除了最後一個B 其他都算
每個group(括號)的大小 = B的佔位 + 兩個規定空格
最後需要補上沒有算的B
(4 - 1) * (2 + 1) + 1 = 10
```
```
假設有[A,A,A,B,B,B]，n=2，有兩個出現次數一樣多的
代表有多一個要補在最後面
B _ _ B _ _ B
B A _ B A _ B A
(B A _ )( B A _ ) B A
(3 - 1) * (2 + 1) + 2 = 8
```
公式 (maxF - 1) * (n + 1) + sameF
注意 : 當 (maxF - 1) * (n + 1) + sameF 的值小於任務總數時，意味著間隔不足以執行所有的任務。在這種情況下，我們應該返回任務總數，以確保所有的任務都能被執行完畢。
```python
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
record = defaultdict(int)
for c in tasks:
record[c] += 1
maxFreq = max(record.values())
sameFreq = 0
for c, count in record.items():
if count == maxFreq:
sameFreq += 1
return max(len(tasks), (n + 1) * (maxFreq - 1) + sameFreq)
```
**講解連結**
Provided by. me
###### tags: `math` `note` `code`
Sign in with Wallet
Connect another wallet