算法思路及技巧

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        j, ans, sum_ = 0, float('inf'), 0
        for i in range(len(nums)):
            sum_ += nums[i]
            while sum_ >= target:  # 等于也要
                sub_len = i - j + 1
                ans = min(sub_len, ans)
                sum_ -= nums[j]
                j += 1
        return ans if ans != float('inf') else 0

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        startx, starty = 0, 0
        loop = n // 2
        offset = 1
        count = 1
        ans = [[0] * n for _ in range(n)]
        while loop:
            x, y = startx, starty
            while x < n - offset:
                ans[y][x] = count
                x += 1
                count += 1
            while y < n - offset:
                ans[y][x] = count
                y += 1
                count += 1
            while x > startx:
                ans[y][x] = count
                count += 1
                x -= 1
            while y > starty:
                ans[y][x] = count
                count += 1
                y -=1
            offset += 1
            loop -= 1
            startx += 1
            starty += 1
        if n & 1:  # 奇数需要单独画中间部分
            ans[n // 2][n // 2] = n ** 2
        return ans

class Solution:
    def getnext(self, next, s):
        j = -1
        next[0] = j
        for i in range(1, len(s)):
            while j >= 0 and s[i] != s[j + 1]:
                j = next[j]
            if s[i] == s[j + 1]:
                j += 1
            next[i] = j
                
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        next = [0] * len(needle)
        self.getnext(next, needle)
        j = -1
        for i in range(len(haystack)):
            while j >= 0 and haystack[i] != needle[j + 1]:
                j = next[j]
            if haystack[i] == [j + 1]:
                j += 1
            if j == len(needle) - 1:
                return i - len(needle) + 1
        return -1

class Solution:
    def isValid(self, s: str) -> bool:
        map_dic = {']':'[', '}':'{', ')':'('}
        stack =[]
        for i in s:
            if i in map_dic.values():
                stack.append(i)
            else:
                if not stack:
                    return False
                if stack[-1] != map_dic[i]:
                    return False
                stack.pop()
        if stack:
            return False
        return True

from collections import deque
class MyQueue():  # 创建单调队列
    def __init__(self):
        self.que = deque()

    def push(self, val):
        while self.que and val > self.que[-1]:
            self.que.pop()
        self.que.append(val)

    def pop(self, val):
        if self.que and val == self.que[0]:
            self.que.popleft()

    def front(self):
        return self.que[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        for i in nums[:k]:  # 创建窗口
            que.push(i)
        ans = []
        ans.append(que.front())  # 将第一个窗口中的值保存到结果中
        for i in range(k, len(nums)):  # 移动窗口
            que.pop(nums[i - k])  # 移除左边的数
            que.push(nums[i])  # 加入右边的数
            ans.append(que.front())  # 获取最大值
        return ans

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map_dic = dict()
        for i in nums:
            map_dic[i] = map_dic.get(i, 0) + 1

        que = []
        for key, n in map_dic.items():
            heapq.heappush(que, (n, key))
            if len(que) > k:
                heapq.heappop(que)

        ans = []
        for i in que:
            ans.append(i[1])
        return ans