# **程式筆記(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最大值)
全部都是負數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
*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當前數字和前面相加，才是真實高度，找真實高度的最大值
```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
```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個翻轉次數
```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`
Sign in with Wallet
Connect another wallet