---
# System prepended metadata

title: '**程式筆記(math)**'
tags: [code, note, math]

---

# **程式筆記(math)**


:::info
:information_source: 日期 : 2023/08/12
:::


**:star2:** 

* 加法
remainder, carry = ans % 10, ans // 10
* 運算符
% 餘數
** 次方


---

**:star2:四則運算** 

**加法**

* Plus One 
把list看成數字並加1

![](https://hackmd.io/_uploads/BkH4cGI33.jpg)
```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 法
![](https://hackmd.io/_uploads/Bydv7G8h3.jpg)
```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
![](https://hackmd.io/_uploads/BkLMEDI33.jpg)

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

![image](https://hackmd.io/_uploads/ByGWdh926.png =70%x)

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