[ Leetcode ] Array

nofear195 included in Leetcode

2024-03-28 About 700 words 2 minutes - views - comments

Contents

Operations

主要用 list 實現 Array 的各種操作
有提供 Array module，不常用，主要用於儲存大量數據時，記憶體優化方面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
# initial
arr = [1, 2, 3]

# operations
arr.append(4) # [1, 2, 3, 4]
app.pop() # [1, 2, 3]
len(app) # 3
arr.sort() # [1, 2, 3]
arr.reverse() # [3, 2, 1]

# shallow copy 
# (大多用於複製原始 array 中 immutable 值 ex: integer, string )
arr.copy()
arr[:]

# traversal
for value in arr:
  print(value)

for index, value in enumerate(arr):
  print(index, value)

Classic Questions

Binary Search

使用時機：內容為有序且無重複元素
注意邊界條件：右方閉闔區域

704. Binary Search

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 1. [left, right]
def search(nums: List[int], target: int) -> int:
  left, right = 0 ,len(nums) - 1

  while left <= right: 
    mid = left + (right - left) // 2
    if nums[mid] > target:
      right = mid - 1 # 重點
    elif nums[mid] < target:
      left = mid + 1 # 重點
    else:
      return mid

  return -1

# 2. `[left, right)`
def search(nums: List[int], target: int) -> int:
  left, right = 0 ,len(nums)

  while left < right:
    mid = left + (right - left) // 2
    if nums[mid] > target:
      right = mid # 重點
    elif nums[mid] < target:
      left = mid + 1 # 重點
    else:
      return mid

  return -1

Time complaxity : O(logn)
Space complaxity : O(1)

Two pointers

使用快慢兩個 pointers (slow, fast) 在一個 for loop 中，完成兩個 for loop 的工作量

27. Remove Element

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def removeElement(nums: List[int], val: int) -> int:
  slow = fast = 0

  while fast < len(nums):
    if nums[fast] != val:
      nums[slow] = nums[fast]
      slow += 1
    fast += 1

  return slow

Time complaxity : O(n)
Space complaxity : O(1)

Sliding window

two pointers 應用之一，根據當前子序列情況，動態調整子序列的起始與終止位置，從而降低時間複雜度
key points:
1. 子序列的內容為何
2. 如何移動 window 的起始位置
3. 如何移動 window 的終止位置

209. Minimum Size Subarray Sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def minSubArrayLen(target: int, nums: List[int]) -> int:
  res = float('inf')
  i = j = 0
  sum = 0

  for j in range(len(nums)): # 如何移動 window 的起始位置
    sum += nums[j] # 子序列的內容為何

    while sum > target: # 如何移動 window 的終止位置
      sumLength = j - i + 1
      res = min(res, sumLength)
      i += 1 # 重點

  # 重點: 確認res被赋值有無
  if res != float('inf'): 
    return res
  else:
    return 0

Time complaxity : O(n)
Space complaxity : O(1)

Related
- 904. Fruit Into Baskets
- 76. Minimum Window Substring

Reference

代码随想录