---
# System prepended metadata

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

---

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


:::info
:information_source: 日期 : 2023/06/26
:::


* 迴圈
```
break：強制跳出 ❮整個❯ 迴圈

continue：強制跳出 ❮本次❯ 迴圈，繼續進入下一圈

pass：不做任何事情，所有的程式都將繼續
```

* immutable / mutable
```
不可變對象（immutable objects）: 
    數字（int，float），字符串（str），元組（tuple）
可變對象（mutable objects）: 
    列表（list），字典（dictionary），集合（set）

dict中的key需要是不可變，如字串、整數、tuple
```

* list
```
list[1:1] 會返回一個空串列 []
Python 認為切片範圍為「開始位置就是結束位置」，所以不會包含任何元素
```

* [:]
```python
[:] 表示整個列表的切片（slice）
不僅取出 nums 所有元素，還會保留 nums 原本的記憶體位置

nums = [1, 2, 3]
new = [4, 5, 6]

nums[:] = new

print(nums)  # Output: [4, 5, 6]
```


**:star2:**

* two sum

```python
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        record = {} # n : i
        for i, n in enumerate(nums):
            if (target - n) in record.keys():
                return [record[target - n], i]
            record[n] = i
```

* Majority Element
摩爾投票法 Boyer-Moore Voting Algorithm
```python
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        res = nums[0]
        count = 1

        for n in nums[1:]:
            if n == res:
                count += 1
            elif n != res and count > 0:
                count -= 1
            elif n != res and count == 0:
                res = n
                count = 1
        
        return res
```

* Can Place Flowers
**處理edge case
每個1旁邊要都是0，才可以填入，例如flowerbed = [1,0,0,0,1], n = 2，只能填入1個1，故2太多為False
```python
class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        l = len(flowerbed)

        for i in range(l):
            if flowerbed[i] == 0:
                left, right = False, False

                # check right
                if i == l - 1:
                    right = True
                else:
                    if flowerbed[i + 1] == 0:
                        right = True
                
                # check left
                if i == 0:
                    left = True
                else:
                    if flowerbed[i - 1] == 0:
                        left = True
                
                # if right and left are all 0
                if right and left:
                    flowerbed[i] = 1
                    n -= 1

        return True if n <= 0 else False
```

* Longest Consecutive Sequence
例如nums = [100,4,200,1,3,2] 答案為4，從大數字回朔看有幾個小數字，一種優化方法是，看到有比自己大1的數字就continue
Sequence非連續
```python
在set中找數字的時間複雜度是O(1)

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        record = set(nums)
        maxLen = float("-inf")
        for n in nums:
            # 優化 讓後面大的去處理
            if n + 1 in record:
                continue
            temp = 0
            while n in record:
                temp += 1
                n -= 1
            maxLen = max(maxLen, temp)
        return maxLen if maxLen != float("-inf") else 0
```


---

**:star2:** subarray

A subarray is a contiguous non-empty sequence of elements within an array.
edge case可以問 有沒有負數case

dict

* Subarray Sums Divisible by K
兩個數字如果有相同的餘數，那代表他們相減後會整除
類似Subarray Sum Equals K
```python
# if the two substring have the same mod (mod k)
# there subtraction will be divisible by k
class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        record = defaultdict(int) # mod : count
        record[0] = 1
        total = 0
        res = 0

        for n in nums:
            total += n
            if (total % k) in record.keys():
                res += record[total % k]
            record[total % k] += 1
        return res
```

Kadane's Algorithm

* Maximum Subarray
Kadane 演算法是一種類似動態規劃的做法。這個做法對array的所有元素掃描一次，在每個點上計算以該點做為結尾的最大subarray和
```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur_max = 0
        res = float("-inf")

        for n in nums:
            cur_max = max(n, cur_max + n)
            res = max(res, cur_max)
            
        return res
```
* Maximum Sum Circular Subarray
在尾端回傳max(maximum, total-minimum)，代表(中間subarray最大值, circulaur subarray最大值)
![image](https://hackmd.io/_uploads/rJiz2Vdk0.png)
全部都是負數array = maximum也為負數

```python
class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        cur_min, cur_max = 0, 0
        maximum, minimum = float("-inf"), float("inf")
        total = 0

        for n in nums:
            # Kadane's Algorithm to find Maximum subarray sum.
            cur_max = max(cur_max + n, n)
            maximum = max(maximum, cur_max)

            # Kadane's Algorithm to find Minimum subarray sum.
            cur_min = min(cur_min + n, n)
            minimum = min(minimum, cur_min)

            total += n
        
        if maximum < 0: # all number is negative
            return maximum
        else:
            # minimizing the middle subarray, 
            # we maximize the subarray surrounding that subarray
            return max(maximum, total - minimum)
```



---

**:star2:** two pointer

1. pointer 追蹤數字
判斷移位條件 : 確定pointer所在數字正確
2. 用global index i 去紀錄

* Move Zeroes

```
nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
```
r 追蹤非0數字
l 追蹤0數字
```python
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l, r = 0, 0
        while r < len(nums):
            if nums[r] == 0:
                r += 1
            else:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r += 1
```

* Remove Element

```
Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
```
法1.
因為要把val放到尾端 -> r 從尾端開始 追蹤可放val的位置
l 追蹤可以放val的位置
有 while l <= r 條件 (而非 l < r) -> 需要檢查到最中間那個元素
```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l] == val:
                nums[l], nums[r] = nums[r], nums[l]
                r -= 1
            else:
                l += 1

        return l
```
法2.
用global index i 去紀錄
```python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for j in range(len(nums)):
            if nums[j] != val:
                nums[i] = nums[j]
                i += 1
        return i
```

* Remove Duplicates from Sorted Array
用global index i 去紀錄
```python
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 1
        for j in range(1, len(nums)):
            if nums[j] != nums[j - 1]:
                nums[i] = nums[j]
                i += 1

        return i
```

* Merge Sorted Array
```
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
```
用global index (m + n - 1) 去紀錄
從後面開始遍歷，把較大的持續加在nums1[n + m + 1]中，這樣保證必定會有空位可以塞
可進一步討論極端一大edge case的狀況
```python
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        while m and n:
            if nums1[m - 1] < nums2[n - 1]:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
            elif nums1[m - 1] >= nums2[n - 1]:
                nums1[m + n - 1] = nums1[m - 1]
                m -= 1
        
        if n: # m all smaller
            nums1[:n] = nums2[:n]
```

* Squares of a Sorted Array
從大的開始填充
```
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
```
```python
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i, n in enumerate(nums):
            nums[i] = pow(n, 2)
        
        n = len(nums)
        l, r = 0, n - 1
        res = [0] * n
        cur = n - 1

        while cur >= 0:
            if nums[l] > nums[r]:
                res[cur] = nums[l]
                l += 1
            else:
               res[cur] = nums[r]
               r -= 1
            cur -= 1

        return res 
```

* Sort Colors
r -> 追蹤2
l -> 追蹤0
遇到2就把數字推到最右邊，遇到0就推到最左邊
```python
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l, r = 0, len(nums) - 1
        cur = 0
        while cur <= r:
            if nums[cur] == 0:
                nums[cur], nums[l] = nums[l], nums[cur]
                # 可確定現在l上必為0
                # 原始l必不為2 因為必會先被調換到r
                l += 1
                cur += 1
            elif nums[cur] == 2:
                nums[cur], nums[r] = nums[r], nums[cur]
                # 可確定r上必為2
                r -= 1
            elif nums[cur] == 1:
                cur += 1
```


* Search Suggestions System
![image](https://hackmd.io/_uploads/rJtJ7Xnna.png)
*If there are more than three products with a common prefix return the three **lexicographically** minimums products

先sort成字母順序，用l和r去框住valid的單字
注意if條件，如果i已經大於單字長度，則這個單字必定不是推薦字，需要往下遍歷。也需要l小於r
```python
class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        res = []
        l, r = 0, len(products) - 1

        for i in range(len(searchWord)):
            while l <= r and i < len(products[l]) or searchWord[i] != products[l][i]:
                l += 1
            while l <= r and i < len(products[r]) or searchWord[i] != products[r][i]:
                r -= 1
            
            if r - l > 2:
                res.append(products[l : l + 3])
            else:
                res.append(products[l : r + 1])
        
        return res
```



**sorted array -> sum 用雙指針逼近**

* two sum sorted
因為是sorted array 
(binary sort一次只能針對一個數字)
```python
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            if numbers[r] + numbers[l] > target:
                r -= 1
            elif numbers[r] + numbers[l] < target:
                l += 1
            else:
                return [l + 1, r + 1]
```

```python
# 一般two sum 用dict紀錄
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        record = defaultdict(int)
        for i, n in enumerate(numbers):
            if target - n in record:
                return [record[target - n], i + 1]
            record[n] = i + 1
```
* 3Sum
sorted
-> 可以用雙指針找sum
-> 可以跳過重複的開始數字

內部重複的數字，也需要在找到sum時持續排除

```python
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        pre_n = float("-inf")

        for i, n in enumerate(nums):
            if pre_n == n:
                continue
            l, r = i + 1, len(nums) - 1
            pre_n = n
            while l < r:
                if nums[l] + nums[r] + n == 0:
                    pre_l, pre_r = nums[l], nums[r]
                    res.append([nums[l], nums[r], n])
                    l, r = l + 1, r - 1
                    while l < len(nums) and pre_l == nums[l]:
                        l += 1
                    while 0 <= r and pre_r == nums[r]:
                        r -= 1
                elif nums[l] + nums[r] + n > 0:
                    r -= 1
                elif nums[l] + nums[r] + n < 0:
                    l += 1
            
        return res        
```



---

**:star2:** sliding window

架構
```python
while ... :
    1.更新條件
    
    2.修正l到合理範圍

    3.紀錄新長度
    4.修正
```

* Max Consecutive Ones III
```
Input: nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
Output: 6
Explanation: [1,1,1,0,0,1,1,1,1,1,1]
```
k是可以把0換1的數量，問最長的連續1為何
上面修正pointer 下面更新長度
```python
class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        l, r = 0, 0
        maxLen = 0
        count = 0
        while r < len(nums):
            if nums[r] == 0:
                count += 1
            while count > k:
                if nums[l] == 0:
                    count -= 1
                l += 1
                
            maxLen = max(maxLen, r - l + 1)
            r += 1
        return maxLen
```

* Longest Subarray of 1's After Deleting One Element
從0開始往外擴
```
Input: nums = [1,1,0,1]
Output: 3
Explanation: After deleting the number in position 2, 
[1,1,1] contains 3 numbers with value of 1's.
```
```python
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        maxLen = 0
        l, r = 0, 0
        count = 0
        while r < len(nums):
            if nums[r] == 0:
                count += 1
            while count > 1:
                if nums[l] == 0:
                    count -= 1
                l += 1
            
            maxLen = max(maxLen, r - l + 1)
            r += 1

        return maxLen - 1
```


---


**:star2:** prefix sum

* Product of Array Except Self 
除了自己以外的乘積，prefix sum + suffix sum

```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        prefix, suffix, res = [1] * n, [1] * n, [1] * n

        for i in range(1, n):
            prefix[i] = nums[i - 1] * prefix[i - 1]
        
        for i in range(n - 2, -1, -1):
            suffix[i] = nums[i + 1] * suffix[i + 1]
        
        for i in range(n):
            res[i] = prefix[i] * suffix[i]
        
        return res
```
* Find the Highest Altitude
array當前數字和前面相加，才是真實高度，找真實高度的最大值
![image](https://hackmd.io/_uploads/HyNmuOAgyg.png =50%x)
```python
class Solution:
    def largestAltitude(self, gain: List[int]) -> int:
        maxH = 0
        preH = 0

        for i in range(len(gain)):
            preH += gain[i]
            maxH = max(maxH, preH)
        
        return maxH
```

* Trapping Rain Water
水位是由min(左邊最高, 右邊最高) 來決定的，用 left(prefix) 和 right(postfix) 去紀錄從左右邊來的最高值，最後減掉本身的障礙物高度，即水位
```python
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        left, right = [0] * n, [0] * n
        water = 0

        for i in range(1, n):
            left[i] = max(left[i - 1], height[i - 1])
        for i in range(n - 2, -1, -1):
            right[i] = max(right[i + 1], height[i + 1])
        
        for i in range(n):
            w = min(left[i], right[i]) - height[i]
            if w > 0:
                water += w
        return water
```


---


**:star2:** Buy and Sell Stock

* Best Time to Buy and Sell Stock
maximum profit you can achieve from single transaction

```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        minP = float("inf")
        for p in prices:
            minP = min(minP, p)
            profit = max(profit, p - minP)
        return profit
```
也可以用two pointer，l會一直指向最小的數字
```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l, r = 0, 1
        maxRes = 0
        while r < len(prices):
            if prices[l] < prices[r]:
                maxRes = max(prices[r] - prices[l], maxRes)
            else:
                l = r
            r += 1
        return maxRes
```
* Best Time to Buy and Sell Stock II
Greedy
You can only hold at most one share of the stock at any time. 可以連續買賣多次 maximum profit you can achieve
![image](https://hackmd.io/_uploads/rJNoi2PS6.png)
```python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minP = prices[0]
        profit = 0
        for p in prices:
            if p > minP:
                profit += p - minP
                minP = p
            else:
                minP = p
        return profit
```


---

**:star2:** Rotate Array (補)

```
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
```

* Rotate Array
法1. 直接轉k輪
```python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n # speed up the rotation

        for _ in range(k): # turn k times
            pre = nums[-1]
            for i in range(n):
                pre, nums[i] = nums[i], pre
```
法2. 使用新的array紀錄
```python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        new = [0] * n
        for i in range(n):
            new[int((i + k) % n)] = nums[i]
        nums[:] = new
```
法3. 以不同start (0 ~ k - 1) 作為起點，並以k為間距，位移數字，直到累積到n個翻轉次數
![image](https://hackmd.io/_uploads/BkBAxFzfkg.png =50%x)
```python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        total_n = 0 # total count of rotating number
    
        start, pre = 0, 0 # starting point, previous number
        
        while total_n < n:
            pre = nums[start]
            pre_idx = start
            while True:
                cur_idx = (pre_idx + k) % n
                cur = nums[cur_idx]
                nums[cur_idx] = pre # change current number to previous number
                pre_idx, pre = cur_idx, cur # update for next iteration
                total_n += 1 # finish placing 1 number
                # finish one round
                if pre_idx == start:
                    break
            start += 1
```
法4. 反轉
```
Original List                   : 1 2 3 4 5 6 7
After reversing all numbers     : 7 6 5 4 3 2 1
After reversing first k numbers : 5 6 7 4 3 2 1
After revering last n-k numbers : 5 6 7 1 2 3 4 --> Result
```
```python
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        n = len(nums)
        k = k % n
        self.reverse(0, n - 1, nums)
        self.reverse(0, k - 1, nums)
        self.reverse(k, n - 1, nums)

    def reverse(self, start, end, nums):
        while start <= end:
            nums[start], nums[end] = nums[end], nums[start]
            start += 1
            end -= 1    
```




**講解連結**

Provided by. hard working me

###### tags: `arrays` `note` `code`