- 思路
- example: [-2,-1,0,2,3] --> [0,1,4,4,9]
-
Two Pointer, -> <-
- left, right = 0, n-1
- while left <= right, stop when left > right
- assign to res[idx] （逆序） based on the status at left and right, then move left/right, and update idx (idx -= 1)
- 复杂度. 时间：O(n), 空间: O(1) if not including output
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
left, right = 0, n-1
index = n-1
res = [0 for _ in range(n)]
while left <= right:
if abs(nums[left]) > abs(nums[right]):
res[index] = nums[left] ** 2
left += 1
else:
res[index] = nums[right] ** 2
right -= 1
index -= 1
return res
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
res = [0 for _ in range(n)]
left, right = 0, n-1
idx = n-1
while left <= right:
if nums[left] ** 2 <= nums[right] ** 2:
res[idx] = nums[right] ** 2
right -= 1
else:
res[idx] = nums[left] ** 2
left += 1
idx -= 1
return res
- It's also possible to consider TP with <--*-->, where * is the "center".
# 错误
# e.g., [-5,-3,-2,-1]
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
n = len(nums)
right = n-1
left = 0 # fixed
while right >= 0:
if abs(nums[left]) > abs(nums[right]):
nums[left], nums[right] = nums[right], nums[left]
nums[right] = nums[right] ** 2
right -= 1
return nums
- 思路
- example
- 正整数，长度最小的 连续子数组
- 注意初始化以及返回值
- TP->sliding window, -->--> 滑窗
- feasible window: [left, right] 左闭右闭 (右扩左缩）
- left, right = 0, 0 （起点相同)
- outside loop: right
- 先处理right节点，当前窗口：[left, right], 检查状态: feasible or not （feasible: sum >= target)
- inside loop: left
- while window sum >= target (feasible): move left until we get an invalid window
- if not feasible, left is not moving
- 当前窗口不可行，右移right扩展窗口
- 复杂度. 时间：O(n), 空间: O(1)
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
left, right = 0, 0 # 相同起点
cur_sum = 0 # current windown sum
res = float('inf')
while right < n:
cur_sum += nums[right] # if left == right, then curren windown only consists of one number
while cur_sum >= target and left <= right: # make sure left <= right
# note that target >= 1, so left is always <= right
res = min(res, right - left + 1) # update result
cur_sum -= nums[left] # remove nums[left]
left += 1 # move left
right += 1 # move right
return res if res != float('inf') else 0 # 有可能 res = float('inf')
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
n = len(nums)
left, right = 0, 0
sum_ = 0
res = n+1
while right < n:
sum_ += nums[right]
if sum_ >= target:
while sum_ >= target:
res = min(res, right-left+1)
sum_ -= nums[left]
left += 1
right += 1
return res if res != n+1 else 0
- 思路
- example
- Simulation: Given
, output 
matrix (from 
to 
), clockwise
- use top and bottom for row bounds, use left and right for column bounds
- 累加计数
- while top < bottom and left < right
- stop when top == bottom and left == right (one number left), or top > bottom and left > right (done)
- 复杂度. 时间：
)
, 空间: )
if not counting the output
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
res = [[0] *n for _ in range(n)]
top, bottom = 0, n-1 # row bounds
left, right = 0, n-1 # column bounds
cnt = 1
while top < bottom and left < right:
# four "rays"
#-->
for j in range(left, right):
res[top][j] = cnt
cnt += 1
# downward (on the "right" column)
for i in range(top, bottom):
res[i][right] = cnt
cnt += 1
# <--
for j in range(right, left, -1):
res[bottom][j] = cnt
cnt += 1
# upward (left column)
for i in range(bottom, top, -1):
res[i][left] = cnt
cnt += 1
# update bounds
top += 1
bottom -= 1
left += 1
right -= 1
if top == bottom: # one element left out
res[top][left] = cnt
return res
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
left, right = 0, n-1 # column index
top, bottom = 0, n-1 # row index
mat = [[0 for _ in range(n)] for _ in range(n)]
cnt = 1
while left <= right and top <= bottom:
for j in range(left, right+1):
mat[top][j] = cnt
cnt += 1
for i in range(top+1, bottom+1):
mat[i][right] = cnt
cnt += 1
for j in range(right-1, left-1, -1):
mat[bottom][j] = cnt
cnt += 1
for i in range(bottom-1, top, -1):
mat[i][left] = cnt
cnt += 1
left += 1
right -= 1
top += 1
bottom -= 1
return mat
