Python每日一练(20230424) 滑动窗口最大值、栈实现队列、直线上最多的点数

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if len(nums) == 0:
            return []
        if k == 1:
            return nums
        res = []
        res.append(max(nums[:k]))
        for i in range(1, len(nums) - k + 1):
            m = max(nums[i : i + k])
            res.append(m)
        return res
if __name__ == '__main__':
    s = Solution()
    nums = [1,3,-1,-3,5,3,6,7]; k = 3
    print(s.maxSlidingWindow(nums, k))

class MyQueue:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack_push = []
        self.stack_pop = []
    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        while self.stack_pop:
            self.stack_push.append(self.stack_pop.pop())
        self.stack_push.append(x)
    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.empty():
            return None
        else:
            while self.stack_push:
                self.stack_pop.append(self.stack_push.pop())
            return self.stack_pop.pop()
    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.empty():
            return None
        elif not self.stack_pop:
            return self.stack_push[0]
        else:
            return self.stack_pop[-1]
    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return not (self.stack_push or self.stack_pop)
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
myQueue = MyQueue()
myQueue.push(1)  # queue is: [1]
myQueue.push(2)  # queue is: [1, 2] (leftmost is front of the queue)
print(myQueue.peek())   # return 1
print(myQueue.pop())    # return 1, queue is [2]
print(myQueue.empty())  # return false

from typing import List
class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 2:
            return len(points)
        maxNum = 0
        for i in range(len(points)):
            maxNum = max(maxNum, self.find(points[i], points[:i] + points[i + 1 :]))
        return maxNum + 1
    def find(self, point, pointList):
        memories = {}
        count = 0
        inf = float("inf")
        for curPoint in pointList:
            if curPoint[1] == point[1] and curPoint[0] != point[0]:
                memories[inf] = memories.get(inf, 0) + 1
            elif curPoint[1] == point[1] and curPoint[0] == point[0]:
                count += 1
            else:
                slope = (curPoint[0] - point[0]) / (curPoint[1] - point[1])
                memories[slope] = memories.get(slope, 0) + 1
        if memories:
            return count + max(memories.values())
        else:
            return count
if __name__ == '__main__':
    s = Solution()
    null = None
    points = [[1,1],[2,2],[3,3]]
    print(s.maxPoints(points))
    points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
    print(s.maxPoints(points))