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

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

1. 滑动窗口最大值

给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值

示例 1:

输入:nums = [1,3,-1,-3,5,3,6,7], k = 3

输出:[3,3,5,5,6,7]

解释:

滑动窗口的位置                最大值

---------------               -----

[1  3  -1] -3  5  3  6  7       3

1  [3  -1  -3] 5  3  6  7       3

1   3 [-1  -3  5] 3  6  7       5

1   3  -1 [-3  5  3] 6  7       5

1   3  -1  -3 [5  3  6] 7       6

1   3  -1  -3  5 [3  6  7]      7

示例 2:

输入:nums = [1], k = 1

输出:[1]


示例 3:

输入:nums = [1,-1], k = 1

输出:[1,-1]


示例 4:

输入:nums = [9,11], k = 2

输出:[11]


示例 5:

输入:nums = [4,-2], k = 2

输出:[4]


提示:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums.length

出处:

https://edu.csdn.net/practice/26377425

代码:

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))

输出:

[3, 3, 5, 5, 6, 7]


2. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:

  • 你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

进阶:

  • 你能否实现每个操作均摊时间复杂度为 O(1) 的队列?换句话说,执行 n 个操作的总时间复杂度为 O(n) ,即使其中一个操作可能花费较长时间。

示例:

输入:

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

输出:

[null, null, null, 1, 1, false]

解释:

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek();  // return 1

myQueue.pop();   // return 1, queue is [2]

myQueue.empty(); // return false


提示:

  • 1 <= x <= 9
  • 最多调用 100pushpoppeekempty
  • 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

出处:

https://edu.csdn.net/practice/26377426

代码:

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

输出:

1

1

False


3. 直线上最多的点数

给你一个数组 points ,其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1:

输入:points = [[1,1],[2,2],[3,3]]

输出:3


示例 2:

输入:points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]

输出:4


提示:

  • 1 <= points.length <= 300
  • points[i].length == 2
  • -104 <= xi, yi <= 104
  • points 中的所有点 互不相同

出处:

https://edu.csdn.net/practice/26377427

代码:

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))

输出:

3

4


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
8天前
|
C++
【链表】还不会用C++实现链表?一文教会你各种链表的实现
【链表】还不会用C++实现链表?一文教会你各种链表的实现
|
8天前
|
存储 缓存 算法
Python中collections模块的deque双端队列:深入解析与应用
在Python的`collections`模块中,`deque`(双端队列)是一个线程安全、快速添加和删除元素的双端队列数据类型。它支持从队列的两端添加和弹出元素,提供了比列表更高的效率,特别是在处理大型数据集时。本文将详细解析`deque`的原理、使用方法以及它在各种场景中的应用。
|
8天前
|
索引 Python
Python 中寻找列表最大值位置的方法
本文介绍了Python中找列表最大值及其位置的三种方法:1) 使用内置`max()`和`index()`函数;2) 通过循环遍历;3) 利用`enumerate()`函数和生成器表达式。每种方法均附有示例代码,其中`enumerate()`方法在保证效率的同时代码更简洁。
39 2
|
8天前
|
安全
python_threading多线程、queue安全队列
python_threading多线程、queue安全队列
22 2
|
3天前
|
消息中间件 存储 NoSQL
一文读懂python分布式任务队列-celery
# 一文读懂Python分布式任务队列-Celery Celery是一个分布式任务执行框架,支持大量并发任务。它采用生产者-消费者模型,由Broker、Worker和Backend组成。生产者提交任务到队列,Worker异步执行,结果存储在Backend。适用于异步任务、大规模实时任务和定时任务。5月更文挑战第17天
15 1
|
8天前
|
Java C语言
剑指offer(牛客)——合并两个排序的链表
剑指offer(牛客)——合并两个排序的链表
11 1
|
8天前
|
消息中间件 Linux 调度
Python的进程锁,进程队列
Python的进程锁,进程队列
125 3
|
8天前
|
存储 缓存 C++
C++链表常用的函数编写(增查删改)内附完整程序
C++链表常用的函数编写(增查删改)内附完整程序
|
8天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
43 0
|
8天前
|
存储 算法 程序员
深入理解 C++ 自定义链表中实现迭代器
深入理解 C++ 自定义链表中实现迭代器
61 0