-
LeetCode 641. 设计循环双端队列 / 1656. 设计有序流 / 302. 层数最深叶子节点的和
641. 设计循环双端队列
2022.8.15 每日一题，真正上班了，还是需要多练习python
题目描述
设计实现双端队列。
实现 MyCircularDeque 类:
MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false 。
boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。示例 1：
输入
[“MyCircularDeque”, “insertLast”, “insertLast”, “insertFront”, “insertFront”, “getRear”, “isFull”, “deleteLast”, “insertFront”, “getFront”]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]
解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1); // 返回 true
circularDeque.insertLast(2); // 返回 true
circularDeque.insertFront(3); // 返回 true
circularDeque.insertFront(4); // 已经满了，返回 false
circularDeque.getRear(); // 返回 2
circularDeque.isFull(); // 返回 true
circularDeque.deleteLast(); // 返回 true
circularDeque.insertFront(4); // 返回 true
circularDeque.getFront(); // 返回 4提示：
1 <= k <= 1000
0 <= value <= 1000
insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull 调用次数不大于 2000 次来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-circular-deque
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。思路
数组设计的时候主要还是参考java中那个循环双端队列，有一个多余的位置，用前后指针来判断是否空或者满
class MyCircularDeque: # 数组实现 def __init__(self, k: int): self.front = self.rear = 0 self.elements = [0] * (k + 1) def insertFront(self, value: int) -> bool: if self.isFull(): return False self.front = (self.front - 1) % len(self.elements) self.elements[self.front] = value return True def insertLast(self, value: int) -> bool: if self.isFull(): return False self.elements[self.rear] = value self.rear = (self.rear + 1) % len(self.elements) return True def deleteFront(self) -> bool: if self.isEmpty(): return False self.front = (self.front + 1) % len(self.elements) return True def deleteLast(self) -> bool: if self.isEmpty(): return False self.rear = (self.rear - 1) % len(self.elements) return True def getFront(self) -> int: if self.isEmpty(): return -1 return self.elements[self.front] def getRear(self) -> int: if self.isEmpty(): return -1 return self.elements[(self.rear - 1) % len(self.elements)] def isEmpty(self) -> bool: if self.front == self.rear: return True else: return False def isFull(self) -> bool: return True if self.front == (self.rear + 1) % len(self.elements) else False # Your MyCircularDeque object will be instantiated and called as such: # obj = MyCircularDeque(k) # param_1 = obj.insertFront(value) # param_2 = obj.insertLast(value) # param_3 = obj.deleteFront() # param_4 = obj.deleteLast() # param_5 = obj.getFront() # param_6 = obj.getRear() # param_7 = obj.isEmpty() # param_8 = obj.isFull()- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
链表
class MyCircularDeque: def __init__(self, k: int): self.k = k self.size = 0 self.head = Node(-1) self.tail = Node(-1) self.head.next = self.tail self.tail.prev = self.head def insertFront(self, value: int) -> bool: if self.isFull(): return False node = Node(value) node.next = self.head.next node.prev = self.head self.head.next = node node.next.prev = node self.size += 1 return True def insertLast(self, value: int) -> bool: if self.isFull(): return False node = Node(value) node.prev = self.tail.prev node.next = self.tail self.tail.prev.next = node self.tail.prev = node self.size+=1 return True def deleteFront(self) -> bool: if self.isEmpty(): return False self.head.next = self.head.next.next self.head.next.prev = self.head self.size-=1 return True def deleteLast(self) -> bool: if self.isEmpty(): return False self.tail.prev = self.tail.prev.prev self.tail.prev.next = self.tail self.size-=1 return True def getFront(self) -> int: return -1 if self.isEmpty() else self.head.next.val def getRear(self) -> int: return -1 if self.isEmpty() else self.tail.prev.val def isEmpty(self) -> bool: return self.size == 0 def isFull(self) -> bool: return self.size == self.k # Your MyCircularDeque object will be instantiated and called as such: # obj = MyCircularDeque(k) # param_1 = obj.insertFront(value) # param_2 = obj.insertLast(value) # param_3 = obj.deleteFront() # param_4 = obj.deleteLast() # param_5 = obj.getFront() # param_6 = obj.getRear() # param_7 = obj.isEmpty() # param_8 = obj.isFull() class Node: def __init__(self, val, prev = None, next = None): self.val = val self.prev = prev self.next = next- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
1656. 设计有序流
2022.8.16 每日一题
题目描述
有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。
设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。
实现 OrderedStream 类：
OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。
否则，返回一个空列表。示例：
输入
[“OrderedStream”, “insert”, “insert”, “insert”, “insert”, “insert”]
[[5], [3, “ccccc”], [1, “aaaaa”], [2, “bbbbb”], [5, “eeeee”], [4, “ddddd”]]
输出
[null, [], [“aaaaa”], [“bbbbb”, “ccccc”], [], [“ddddd”, “eeeee”]]
解释
OrderedStream os= new OrderedStream(5);
os.insert(3, “ccccc”); // 插入 (3, “ccccc”)，返回 []
os.insert(1, “aaaaa”); // 插入 (1, “aaaaa”)，返回 [“aaaaa”]
os.insert(2, “bbbbb”); // 插入 (2, “bbbbb”)，返回 [“bbbbb”, “ccccc”]
os.insert(5, “eeeee”); // 插入 (5, “eeeee”)，返回 []
os.insert(4, “ddddd”); // 插入 (4, “ddddd”)，返回 [“ddddd”, “eeeee”]提示：
1 <= n <= 1000
1 <= id <= n
value.length == 5
value 仅由小写字母组成
每次调用 insert 都会使用一个唯一的 id
恰好调用 n 次 insert来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-an-ordered-stream
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。思路
class OrderedStream: def __init__(self, n: int): self.n = n self.arr = [0] * n self.ptr = 0 def insert(self, idKey: int, value: str) -> List[str]: self.arr[idKey - 1] = value res = [] for t in range(self.ptr, self.n): if not self.arr[t]: self.ptr = t break res.append(self.arr[t]) return res- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
1302. 层数最深叶子节点的和
2022.8.17 每日一题
题目描述
给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。
示例 1：
输入：root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
输出：15示例 2：
输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出：19提示：
树中节点数目在范围 [1, 10^4] 之间。
1 <= Node.val <= 100来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/deepest-leaves-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。思路
简单的广度优先
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def deepestLeavesSum(self, root: Optional[TreeNode]) -> int: # 层序遍历 queue = [root] res = 0 while queue: size = len(queue) res = 0 while size: size -= 1 node = queue.pop() res += node.val if node.left: queue.insert(0, node.left) if node.right: queue.insert(0, node.right) return res- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
-
相关阅读:
分布式事务(Seata) 四大模式详解
2023感恩节倒计时：跨境卖家如何借势风潮，成功脱颖而出？
HashMap为什么会发生死循环？
misc类设备驱动1——misc类设备的简介
C++ explicit的作用
【技能树笔记】网络篇——练习题解析（八）
Spring Boot 中的过滤器 (Filter) 使用方案
【产品运营】如何提升B端产品的竞争力（上）
使用 JavaScript Reflect API
算术表达式
- 原文地址：https://blog.csdn.net/windyjcy/article/details/126378126
