Jan 20, 2024 赵悦君mock summary

态度问题

1. 感觉心里面很乱，又想不起来要写啥，就他娘的乱写。很不行的。
2. 多花时间在debug，不如在写之前多plan一下怎么写。
3. 实在不行，用iPad写一遍自己的implementation，然后想想什么时候需要update各个var。

• 尽量考虑所有的edge case，写之前先多想想，别忙着写。

4. 切记！！！ 多想想，想清楚再动笔。

技术问题

问题：记不得c++ STL, 以及大部分c++ 内容，感觉现在有些容器都不太记得。
方案：目前正在看八股文，然后找了个c++ 的网站看看。
之后刷题如果可以的话，多用c++ 练练。

滑动窗口

面试

Sliding Window Maximum
239. Sliding Window Maximum

# lc 239
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    queue = []
    ret = []
    for index, item in enumerate(nums):
        if queue and index - queue[0] >= k:
            queue.pop(0)
        # mono decreasing
        while queue and nums[queue[-1]] < item:
            queue.pop()
        queue.append(index)
        if index >= k - 1:
            ret.append(nums[queue[0]])
    return ret

Logic

• Monotomic decreasing stack.
• Only push in the index of elements that need to be considered.
  • Only pop out element at index 0 if out of length k.
  • Pop in elements less than the end of the queue.
• Thus, the top of queue will just be the greatest element that we need to push into the result.

刷题

Jan 21, 2024

LC 35

1732. Find the Highest Altitude

def longestSubarray(self, nums: List[int]) -> int:
    acc = 0
    count_0 = 0
    count_1 = 0
    left = 0
    for right, num in enumerate(nums):
        if num == 1:
            count_1 += 1
            continue
        count_0 += 1
        acc = max(acc, count_1)
        if right == len(nums) - 1:
            break
        while count_0 > 1 and left <= right:
            if nums[left] == 1:
                count_1 -= 1
            elif nums[left] == 0:
                count_0 -= 1
            left += 1
    acc = max(acc, count_1)
    if count_0 == 0:
        acc -= 1
    return acc

Logic:

• Typical sliding window problem.

1. Wrote some procedure do help!
2. Update acc only when increased count_1 to reach a 0 or reach the end of the array.
3. Whenever we have 2 0s, we need to delete one, move left to the RHS, till one 0 is deleted.
4. One edge case that I forgot till debugging:
   • All 1s, and there is no 0 at the end, then we need to -1 on acc.