217. 存在重复元素
给你一个整数数组
nums。如果任一值在数组中出现 至少两次 ，返回true；如果数组中每个元素互不相同，返回false。
示例 1：
输入：nums = [1,2,3,1] 输出：true示例 2：
输入：nums = [1,2,3,4] 输出：false示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2] 输出：true
解题思路
我们可以遍历数组，将元素添加到一个集合中。在添加之前，我们检查该元素是否已经存在于集合中。如果存在，说明数组中有重复元素，返回 true；否则，继续添加元素。如果遍历结束都没有发现重复元素，返回 false。
- 初始化一个空集合。
- 遍历数组：对于每个元素，检查它是否已经在集合中。
- 如果已存在，立即返回
true。 - 如果不存在，将其添加到集合中。
- 如果已存在，立即返回
- 如果遍历完成没有返回
true，说明没有发现重复元素，返回false。
完整代码
Java
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int num : nums) {
if (seen.contains(num)) {
return true;
}
seen.add(num);
}
return false;
}
}Python
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False223. 矩形面积
给你 二维 平面上两个 由直线构成且边与坐标轴平行/垂直 的矩形，请你计算并返回两个矩形覆盖的总面积。
每个矩形由其 左下 顶点和 右上 顶点坐标表示：
- 第一个矩形由其左下顶点
(ax1, ay1)和右上顶点(ax2, ay2)定义。- 第二个矩形由其左下顶点
(bx1, by1)和右上顶点(bx2, by2)定义。
示例 1：
输入：ax1 = -3, ay1 = 0, ax2 = 3, ay2 = 4, bx1 = 0, by1 = -1, bx2 = 9, by2 = 2 输出：45示例 2：
输入：ax1 = -2, ay1 = -2, ax2 = 2, ay2 = 2, bx1 = -2, by1 = -2, bx2 = 2, by2 = 2 输出：16
解题思路
-
计算每个矩形的面积：
- 矩形1的面积：
(ax2 - ax1) * (ay2 - ay1) - 矩形2的面积：
(bx2 - bx1) * (by2 - by1)
- 矩形1的面积：
-
计算重叠部分的面积：
- 首先，我们需要找出重叠部分的左下角和右上角的坐标。
- 重叠部分的左下角坐标为
(max(ax1, bx1), max(ay1, by1))。 - 重叠部分的右上角坐标为
(min(ax2, bx2), min(ay2, by2))。 - 如果两个矩形有重叠部分，那么重叠部分的宽度为
min(ax2, bx2) - max(ax1, bx1)，高度为min(ay2, by2) - max(ay1, by1)。 - 如果重叠部分的宽度或高度为负数，说明两个矩形没有重叠部分，此时重叠部分的面积为0。
-
计算总面积：
- 总面积 = 矩形1的面积 + 矩形2的面积 - 重叠部分的面积。
完整代码
Java
class Solution {
public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
// 计算两个矩形的面积
int area1 = (ax2 - ax1) * (ay2 - ay1);
int area2 = (bx2 - bx1) * (by2 - by1);
// 计算重叠部分的坐标
int overlapWidth = Math.min(ax2, bx2) - Math.max(ax1, bx1);
int overlapHeight = Math.min(ay2, by2) - Math.max(ay1, by1);
// 计算重叠部分的面积，如果没有重叠部分，则面积为0
int overlapArea = Math.max(0, overlapWidth) * Math.max(0, overlapHeight);
// 计算总面积
return area1 + area2 - overlapArea;
}
}Python
class Solution:
def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
# 计算两个矩形的面积
area1 = (ax2 - ax1) * (ay2 - ay1)
area2 = (bx2 - bx1) * (by2 - by1)
# 计算重叠部分的坐标
overlapWidth = min(ax2, bx2) - max(ax1, bx1)
overlapHeight = min(ay2, by2) - max(ay1, by1)
# 计算重叠部分的面积，如果没有重叠部分，则面积为0
overlapArea = max(0, overlapWidth) * max(0, overlapHeight)
# 计算总面积
return area1 + area2 - overlapArea225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); (); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False
解题思路
-
初始化：创建两个队列，
queue1和queue2。 -
push(x)：将元素
x压入栈顶。- 将
x入队到空队列中（假设为queue1）。 - 将另一个队列（
queue2）中的所有元素依次出队并入队到queue1中。 - 交换
queue1和queue2的引用，这样空队列变为非空队列，非空队列变为空队列。
- 将
-
pop()：移除并返回栈顶元素。
- 直接从非空队列（现在是
queue2）出队元素。
- 直接从非空队列（现在是
-
top()：返回栈顶元素，操作类似
pop，但不移除元素，仅返回队首元素。 -
empty()：如果栈是空的，返回
true；否则，返回false。- 检查非空队列（
queue2）是否为空。
- 检查非空队列（
完整代码
Java
class MyStack {
private Queue<Integer> queue1;
private Queue<Integer> queue2;
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
queue2.add(x);
while (!queue1.isEmpty()) {
queue2.add(queue1.poll());
}
Queue<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
}
public int pop() {
return queue1.poll();
}
public int top() {
return queue1.peek();
}
public boolean empty() {
return queue1.isEmpty();
}
}Python
class MyStack:
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
def push(self, x: int) -> None:
self.queue2.append(x)
while self.queue1:
self.queue2.append(self.queue1.popleft())
self.queue1, self.queue2 = self.queue2, self.queue1
def pop(self) -> int:
return self.queue1.popleft()
def top(self) -> int:
return self.queue1[0]
def empty(self) -> bool:
return not self.queue1
