- 基础知识：各个数据结构的基本原理，增删查改复杂度。
- Queue题目：
Leetcode 225. Implement Stack using Queues
Leetcode 346. Moving Average from Data Stream
Leetcode 281. Zigzag Iterator
Leetcode 1429. First Unique Number
Leetcode 54. Spiral Matrix
Leetcode 362. Design Hit Counter
- Stack题目：
Leetcode 155. Min Stack (follow up Leetcode 716 Max Stack)
Leetcode 232. Implement Queue using Stacks
Leetcode 150. Evaluate Reverse Polish Notation
Leetcode 224. Basic Calculator II (I, II, III, IV)
Leetcode 20. Valid Parentheses
Leetcode 1472. Design Browser History
Leetcode 1209. Remove All Adjacent Duplicates in String II
Leetcode 1249. Minimum Remove to Make Valid Parentheses
Leetcode 735. Asteroid Collision
- Hashmap/ Hashset题目：
Leetcode 1. Two Sum
Leetcode 146. LRU Cache (Python中可以使用OrderedDict来代替)
Leetcode 128. Longest Consecutive Sequence
Leetcode 73. Set Matrix Zeroes
Leetcode 380. Insert Delete GetRandom O(1)
Leetcode 49. Group Anagrams
Leetcode 350. Intersection of Two Arrays II
Leetcode 299. Bulls and Cows
Leetcode 348 Design Tic-Tac-Toe
- Heap／Priority Queue题目：
Leetcode 973. K Closest Points
Leetcode 347. Top k Largest Elements
Leetcode 23. Merge K Sorted Lists
Leetcode 264. Ugly Number II
Leetcode 1086. High Five
Leetcode 88. Merge Sorted Arrays
Leetcode 692. Top K Frequent Words
Leetcode 378. Kth Smallest Element in a Sorted Matrix
Leetcode 295. Find Median from Data Stream （标准解法是双heap，但是SortedDict会非常容易）
Leetcode 767. Reorganize String
Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (这个题用单调双端队列、TreeMap、双heap都可以)
Leetcode 895. Maximum Frequency Stack
1.Queue题目：
Leetcode 225. Implement Stack using Queues
题目描述
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
注意:
- 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
- 你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 ，只要是标准的队列操作即可。
- 假设所有操作都是有效的 （例如，一个空的栈不会调用 pop 或者 top 操作）。
示例:
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // 返回 2
stack.pop(); // 返回 2
stack.empty(); // 返回 false
解法
使用两个队列实现栈。每次 push 操作时，将元素加入非空队列。pop 操作时，将非空队列中除最后一个元素外的所有元素依次出队并加入空队列中，然后将最后一个元素出队即可。top 操作与 pop 操作类似，只是最后一个元素不需要出队，而是直接返回。
代码
class MyStack {
private Queue<Integer> q1;
private Queue<Integer> q2;
private int top;
/** Initialize your data structure here. */
public MyStack() {
q1 = new LinkedList<>();
q2 = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
if (!q1.isEmpty()) {
q1.offer(x);
} else {
q2.offer(x);
}
top = x;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
Queue<Integer> nonEmpty = q1.isEmpty() ? q2 : q1;
Queue<Integer> empty = q1.isEmpty() ? q1 : q2;
while (nonEmpty.size() > 1) {
top = nonEmpty.poll();
empty.offer(top);
}
return nonEmpty.poll();
}
/** Get the top element. */
public int top() {
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return q1.isEmpty() && q2.isEmpty();
}
}
复杂度分析
时间复杂度：push 操作的时间复杂度为 ，pop 和 top 操作的时间复杂度为 ，其中 是栈中元素的个数。
空间复杂度：，其中 是栈中元素的个数。需要使用两个队列存储栈中的元素。
Leetcode 346. Moving Average from Data Stream
题目描述
给定一个数字流和一个窗口大小，计算滑动窗口中所有数字的平均值。
实现 MovingAverage 类：
MovingAverage(int size)用窗口大小size初始化对象。double next(int val)计算并返回数据流中最后size个值的移动平均值，其中val是最后一个值。
示例：
输入：
["MovingAverage", "next", "next", "next", "next"]
[[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]
解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
提示：
1 <= size <= 1000-10^5 <= val <= 10^5- 最多调用
MovingAverage.next方法10^4次
解法
本题的解法是使用一个队列来存储最近 个数字，每次加入一个新的数字后，将队列头部的数字弹出，再计算队列中所有数字的平均值。
代码
class MovingAverage {
private int size;
private int sum;
private Queue<Integer> queue;
/** Initialize your data structure here. */
public MovingAverage(int size) {
this.size = size;
this.sum = 0;
this.queue = new LinkedList<>();
}
public double next(int val) {
if (queue.size() == size) {
sum -= queue.poll();
}
queue.offer(val);
sum += val;
return (double) sum / queue.size();
}
}
复杂度分析
时间复杂度：，每次加入一个新的数字和弹出队列头部的数字的时间复杂度均为 。
空间复杂度：，需要使用一个队列来存储最近 个数字。
Leetcode 281. Zigzag Iterator
题目描述
给定两个一维向量，实现一个迭代器来返回它们的元素交替输出。
示例:
输入: v1 = [1,2], v2 = [3,4,5,6]
输出: [1,3,2,4,5,6]
解析: 通过连续调用 next 函数直到 hasNext 函数返回 false，next 函数返回值的次序应依次为: [1,3,2,4,5,6]。
注意：
- 如果两个输入向量的元素个数不等则交错输出直到其中一个向量的所有元素都被访问完为止。
- 第一个调用 next() 函数时，应该返回向量中的第一个元素。
- 题目中的两个向量是以逻辑上的意义来表示的，它们并不是存储在内存中的两个向量。
解法
本题可以使用双指针实现，一个指针指向第一个向量，一个指针指向第二个向量。每次调用 next() 函数时，判断当前指针是否越界，如果没有越界则返回对应位置的元素，并将指针后移一位。如果一个向量已经遍历完，则直接返回另一个向量的剩余部分。
代码
public class ZigzagIterator {
private List<Integer> v1;
private List<Integer> v2;
private int i1;
private int i2;
private boolean isV1;
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
this.v1 = v1;
this.v2 = v2;
this.i1 = 0;
this.i2 = 0;
this.isV1 = true;
}
public int next() {
if (i1 >= v1.size()) {
int res = v2.get(i2);
i2++;
return res;
} else if (i2 >= v2.size()) {
int res = v1.get(i1);
i1++;
return res;
} else {
int res;
if (isV1) {
res = v1.get(i1);
i1++;
} else {
res = v2.get(i2);
i2++;
}
isV1 = !isV1;
return res;
}
}
public boolean hasNext() {
return i1 < v1.size() || i2 < v2.size();
}
}
复杂度分析
时间复杂度：，其中 是两个向量的总长度。
空间复杂度：，只需要常数个额外空间。
Leetcode 1429. First Unique Number
题目描述
你需要实现 FirstUnique 类：
FirstUnique(int[] nums)：用数组里的数字初始化一个对象。int showFirstUnique()：返回FirstUnique对象里的第一个唯一数，如果没有唯一数，返回-1。void add(int value)：把value插入到FirstUnique对象里。
示例 1：
输入：
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
输出：
[null,2,null,2,null,3,null,-1]
解释：
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // 返回 2。
firstUnique.add(5); // 此时数组为 [2,3,5,5]。
firstUnique.showFirstUnique(); // 返回 2。
firstUnique.add(2); // 此时数组为 [2,3,5,5,2]。
firstUnique.showFirstUnique(); // 返回 3。
firstUnique.add(3); // 此时数组为 [2,3,5,5,2,3]。
firstUnique.showFirstUnique(); // 返回 -1。
示例 2：
输入：
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
输出：
[null,-1,null,null,null,null,null,17]
解释：
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // 返回 -1。
firstUnique.add(7); // 此时数组为 [7,7,7,7,7,7,7]。
firstUnique.add(3); // 此时数组为 [7,7,7,7,7,7,7,3]。
firstUnique.add(3); // 此时数组为 [7,7,7,7,7,7,7,3,3]。
firstUnique.add(7); // 此时数组为 [7,7,7,7,7,7,7,3,3,7]。
firstUnique.add(17); // 此时数组为 [7,7,7,7,7,7,7,3,3,7,17]。
firstUnique.showFirstUnique(); // 返回 17。
示例 3：
输入：
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
输出：
[null,809,null,-1]
解释：
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // 返回 809。
firstUnique.add(809); // 此时数组为 [809,809]。
firstUnique.showFirstUnique(); // 返回 -1。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^81 <= value <= 10^8- 最多调用
10^5次showFirstUnique和add。
解法
本题可以使用哈希表和队列来实现。哈希表记录数字出现的次数，队列记录出现顺序。在 add 操作时，如果数字已经出现过，将其从队列中删除；否则，将其加入队列。在 showFirstUnique 操作时，判断队首元素是否只出现过一次，如果是，返回其值；否则，删除队首元素，继续判断下一个元素。
代码
class FirstUnique {
Map<Integer, Integer> count;
Queue<Integer> queue;
public FirstUnique(int[] nums) {
count = new HashMap<>();
queue = new LinkedList<>();
for (int num : nums) {
add(num);
}
}
public int showFirstUnique() {
while (!queue.isEmpty() && count.get(queue.peek()) > 1) {
queue.poll();
}
if (queue.isEmpty()) {
return -1;
}
return queue.peek();
}
public void add(int value) {
count.put(value, count.getOrDefault(value, 0) + 1);
if (count.get(value) == 1) {
queue.offer(value);
} else {
queue.remove(value);
}
}
}
复杂度分析
- 时间复杂度：对于
add操作，哈希表的插入和删除操作的时间复杂度均为 ，队列的插入和删除操作的时间复杂度均为 ，因此时间复杂度为 。对于showFirstUnique操作，最坏情况下需要遍历队列中所有元素，因此时间复杂度为 ，其中 是哈希表中不同数字的个数。 - 空间复杂度：哈希表和队列分别需要 的空间，因此空间复杂度为 。
Leetcode 54. Spiral Matrix
题目描述
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
提示：
m == matrix.lengthn == matrix[i].length1 <= m, n <= 10-100 <= matrix[i][j] <= 100
解法
螺旋矩阵的解法比较直观，可以按照一圈一圈的方式进行遍历。具体来说，我们可以不断缩小矩阵的边界，从而模拟出一圈一圈的遍历过程。
具体地，设当前左上角的行号为 top，右下角的行号为 bottom，左上角的列号为 left，右下角的列号为 right，按照如下方式遍历：
- 从左到右遍历上侧元素，依次为 ，将每个遍历到的元素加入答案数组中。
- 从上到下遍历右侧元素，依次为 ，将每个遍历到的元素加入答案数组中。
- 如果left < right且top < bottom，则从右到左遍历下侧元素，依次为 ，将每个遍历到的元素加入答案数组中。
- 如果left < right且top < bottom，则从下到上遍历左侧元素，依次为 ，将每个遍历到的元素加入答案数组中。
- 完成一圈遍历，将矩阵的上下左右边界均缩小 1，即
top++，bottom--，left++，right--，并重复执行以上操作，直到遍历完整个矩阵。
代码
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ans = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return ans;
}
int m = matrix.length, n = matrix[0].length;
int left = 0, right = n - 1, top = 0, bottom = m - 1;
while (left <= right && top <= bottom) {
for (int i = left; i <= right; i++) {
ans.add(matrix[top][i]);
}
for (int i = top + 1; i <= bottom; i++) {
ans.add(matrix[i][right]);
}
if (left < right && top < bottom) {
for (int i = right - 1; i >= left; i--) {
ans.add(matrix[bottom][i]);
}
for (int i = bottom - 1; i > top; i--) {
ans.add(matrix[i][left]);
}
}
left++;
right--;
top++;
bottom--;
}
return ans;
}
}
复杂度分析
- 时间复杂度：，其中 和 分别是矩阵的行数和列数。矩阵中的每个元素都要被遍历一次。
- 空间复杂度：。除了输出数组以外，空间复杂度是常数。
Leetcode 362. Design Hit Counter
题目描述
设计一个敲击计数器，使它可以统计在过去5分钟内被敲击次数（次数可能为0）。每个函数会接收一个时间戳参数（以秒为单位），你可以假设最早的时间戳从1开始，且都是按照时间顺序对系统进行调用（即时间戳是单调递增）。在同一时刻有可能会有多次敲击。
示例:
HitCounter counter = new HitCounter();
// 在时刻 1 敲击一次。
counter.hit(1);
// 在时刻 2 敲击一次。
counter.hit(2);
// 在时刻 3 敲击一次。
counter.hit(3);
// 在时刻 4 统计过去 5 分钟内的敲击次数, 函数返回 3 。
counter.getHits(4);
// 在时刻 300 敲击一次。
counter.hit(300);
// 在时刻 300 统计过去 5 分钟内的敲击次数，函数返回 4 。
counter.getHits(300);
// 在时刻 301 统计过去 5 分钟内的敲击次数，函数返回 3 。
counter.getHits(301);
提示：
- 本题与主站 362 题相同：https://leetcode-cn.com/problems/design-hit-counter/
-
- hits 方法的调用总共会被调用 30000 次，而 getHits 方法的调用总共不会超过 300 次。
- hits 和 getHits 方法都被要求只能被调用一次 per timestamp（即时刻）。
解法
本题的解法是使用一个队列来存储所有的敲击时间戳，每次调用 hit 方法时，将当前时间戳加入队列，并删除队列中所有超过 5 分钟的时间戳。调用 getHits 方法时，计算队列中剩余时间戳的个数即可。
代码
class HitCounter {
private Queue<Integer> queue;
public HitCounter() {
queue = new LinkedList<>();
}
public void hit(int timestamp) {
queue.offer(timestamp);
while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {
queue.poll();
}
}
public int getHits(int timestamp) {
while (!queue.isEmpty() && timestamp - queue.peek() >= 300) {
queue.poll();
}
return queue.size();
}
}
复杂度分析
时间复杂度：，hit 和 getHits 方法的时间复杂度都是 。
空间复杂度：，其中 是敲击次数。需要使用一个队列来存储敲击时间戳，队列的长度最大为 300。
2.Stack题目：
Leetcode 155. Min Stack (follow up Leetcode 716 Max Stack)
题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
示例 1：
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top(); // 返回 0
minStack.getMin(); // 返回 -2
提示：
- pop、top 和 getMin 操作总是在 非空栈 上调用。
解法
解法与Leetcode 716 Max Stack类似，只是比它简单。使用两个栈，一个栈用来存储元素，另一个栈用来存储当前最小值。
具体实现：
- push 操作：将元素压入数据栈，并将当前最小值与新元素进行比较，如果新元素更小，则将新元素压入最小值栈。
- pop 操作：弹出数据栈的元素，如果弹出的元素恰好是最小值栈的栈顶元素，则也要将最小值栈的栈顶元素弹出。
- top 操作：返回数据栈的栈顶元素。
- getMin 操作：返回最小值栈的栈顶元素。
代码
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
/** initialize your data structure here. */
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || val <= minStack.peek()) {
minStack.push(val);
}
}
public void pop() {
int val = stack.pop();
if (val == minStack.peek()) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
复杂度分析
时间复杂度：对于每个操作，都只需要常数时间，因此总时间复杂度为。
空间复杂度：最坏情况下，数据栈和最小值栈都需要存储个元素，因此空间复杂度为。
Leetcode 232. Implement Queue using Stacks
题目描述
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明: 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
解法
使用两个栈实现队列。一个栈用来存放元素，另一个栈用来辅助操作。当需要 pop 或 peek 时，将存放元素的栈中的元素逐个弹出并压入辅助栈中，这样顶部的元素就是队列的首部元素。当需要 push 时，直接将元素压入存放元素的栈中即可。
代码
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
private int front;
/** Initialize your data structure here. */
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
/** Push element x to the back of queue. */
public void push(int x) {
if (stack1.empty()) {
front = x;
}
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int pop() {
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
/** Get the front element. */
public int peek() {
if (!stack2.empty()) {
return stack2.peek();
}
return front;
}
/** Returns whether the queue is empty. */
public boolean empty() {
return stack1.empty() && stack2.empty();
}
}
复杂度分析
时间复杂度：push 操作的时间复杂度是 ，pop 和 peek 操作的时间复杂度是 ，其中 是元素个数。在最坏情况下，需要将存放元素的栈中的所有元素弹出并压入辅助栈中，时间复杂度是 。
空间复杂度：，其中 是元素个数。需要使用两个栈存储所有元素。
Leetcode 150. Evaluate Reverse Polish Notation
题目描述
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：
从左到右计算表达式的值。
先加上 2 和 1 ，得到 3 。
再将 3 和 3 相乘，得到 9 。
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：
从左到右计算表达式的值。
先将 13 和 5 除以 5 ，得到 2 。
再将 4 加上 2 ，得到 6 。
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：
从左到右计算表达式的值。
先将 6 和 9 加起来，得到 15 。
再将 15 和 3 相加，得到 18 。
再将 -11 乘以 18 ，得到 -198 。
再将 10 除以 -198 ，得到 0 。
再将 0 乘以 17 ，得到 0 。
最后将 0 和 5 相加，得到 5 。
提示：
- 1 <= tokens.length <= 104
- tokens[i] 要么是一个算符（"+"、"-"、"*" 或 "/"），要么是一个在范围 [-104, 104] 内的整数
解法
使用栈，遍历数组，如果遇到数字，则压入栈中；如果遇到操作符，则从栈中弹出两个数字进行运算，运算结果再压入栈中。最终栈中只会剩下一个数字，即为表达式的值。
代码
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.equals("+")) {
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 + num2);
} else if (token.equals("-")) {
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 - num2);
} else if (token.equals("*")) {
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 * num2);
} else if (token.equals("/")) {
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 / num2);
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
复杂度分析
时间复杂度：，其中 是数组的长度，需要遍历整个数组。
空间复杂度：，最坏情况下，栈的大小会达到 ，即表达式中所有的数字都在栈中。
Leetcode 224. Basic Calculator II (I, II, III, IV)
题目描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
提示：
- 1 <= s.length <= 3 * 105
- s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
- s 表示一个 有效表达式
- 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
- 题目数据保证答案是一个 32-bit 整数
解法
本题可以使用栈来实现。遍历整个字符串，对于每个字符，分为以下几种情况：
-
如果是数字，继续遍历到数字的末尾，并将这个数字入栈。
-
如果是加减乘除符号，需要考虑该符号前面的数字和栈顶的数字进行运算。对于乘除法，直接将栈顶元素出栈并进行运算，然后将结果入栈；对于加减法，需要考虑该符号前面的符号是加还是减，如果是加，说明栈顶元素是正数，直接入栈，如果是减，说明栈顶元素是负数，需要取相反数后再入栈。
-
最后将栈中所有元素相加即可。
注意，需要使用一个变量 num 来记录当前数字的值，因为数字可能不止一位。
本题还有三个变体：
- Basic Calculator I：只有加减法，没有乘除法。
- Basic Calculator III：增加了括号，可以使用递归或栈来实现。
- Basic Calculator IV：增加了变量和乘方，需要使用哈希表和递归来实现。
代码
class Solution {
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
char sign = '+';
int num = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length() - 1) {
if (sign == '+') {
stack.push(num);
} else if (sign == '-') {
stack.push(-num);
} else if (sign == '*') {
stack.push(stack.pop() * num);
} else if (sign == '/') {
stack.push(stack.pop() / num);
}
sign = c;
num = 0;
}
}
int res = 0;
for (int x : stack) {
res += x;
}
return res;
}
}
复杂度分析
时间复杂度：，其中 是字符串的长度。
空间复杂度：，最坏情况下，栈的大小为 。
Leetcode 20. Valid Parentheses
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
提示：
- 1 <= s.length <= 104
- s 仅由括号 '()[]{}' 组成
解法
本题可以使用栈来解决。遍历字符串，如果当前字符是左括号，将其入栈；如果当前字符是右括号，判断栈顶的左括号是否与其匹配，如果匹配，则将栈顶元素出栈，如果不匹配，返回 false。
最后如果栈为空，则说明所有括号都有匹配，返回 true，否则返回 false。
代码
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
char top = stack.pop();
if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{')) {
return false;
}
}
}
return stack.isEmpty();
}
}
复杂度分析
时间复杂度：，其中 是字符串的长度。需要遍历字符串一次。
空间复杂度：，其中 是字符串的长度。最坏情况下，栈的深度为 。
Leetcode 1472. Design Browser History
题目描述
你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史 history 中后退 steps 步或前进 steps 步。
请你实现 BrowserHistory 类：
- BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
- void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
- string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中返回 x 步以前的页面，那么你就返回 homepage 。否则，你返回 步骤 x 后的页面。
- string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中向前 x 步以前的页面，那么你就返回 当前页面 。否则，你返回 步骤 x 之后的页面。
示例：
输入： ["BrowserHistory","visit","visit","visit","back","back","forward","visit","forward","back","back"] [["leetcode.com"],["google.com"],["facebook.com"],["youtube.com"],[1],[1],[1],["linkedin.com"],[2],[2],[7]] 输出： [null,null,null,null,"facebook.com","google.com","facebook.com",null,"linkedin.com","google.com","leetcode.com"]
解释： BrowserHistory browserHistory = new BrowserHistory("leetcode.com"); browserHistory.visit("google.com"); // 你原本在浏览 "leetcode.com" 。访问 "google.com" browserHistory.visit("facebook.com"); // 你原本在浏览 "google.com" 。访问 "facebook.com" browserHistory.visit("youtube.com"); // 你原本在浏览 "facebook.com" 。访问 "youtube.com" browserHistory.back(1); // 你原本在浏览 "youtube.com" ，后退到 "facebook.com" 并返回 "facebook.com" browserHistory.back(1); // 你原本在浏览 "facebook.com" ，后退到 "google.com" 并返回 "google.com" browserHistory.forward(1); // 你原本在浏览 "google.com" ，前进到 "facebook.com" 并返回 "facebook.com" browserHistory.visit("linkedin.com"); // 你原本在浏览 "facebook.com" 。 访问 "linkedin.com" browserHistory.forward(2); // 你原本在浏览 "linkedin.com" ，你无法前进任何步数。 browserHistory.back(2); // 你原本在浏览 "linkedin.com" ，后退两步到 "facebook.com" 并返回 "facebook.com" browserHistory.back(7); // 你原本在浏览 "facebook.com" ，但是你只能后退到 "leetcode.com" 。返回 "leetcode.com"
提示：
- 1 <= homepage.length <= 20
- 1 <= url.length <= 20
- 1 <= steps <= 100
- homepage 和 url 都只包含 '.' 和英文小写字母。
- 最多调用 5000 次 visit， back 和 forward 函数。
解法
本题可以使用一个列表来记录浏览历史记录，同时用一个指针来记录当前所处的位置。visit操作时，将当前位置之后的历史记录全部删除，然后将新的url添加到历史记录里。back和forward操作时，根据给定的步数更新指针，并返回相应的历史记录。
代码
class BrowserHistory {
private List<String> history;
private int curIndex;
public BrowserHistory(String homepage) {
history = new ArrayList<>();
history.add(homepage);
curIndex = 0;
}
public void visit(String url) {
while (history.size() > curIndex + 1) {
history.remove(history.size() - 1);
}
history.add(url);
curIndex++;
}
public String back(int steps) {
curIndex = Math.max(curIndex - steps, 0);
return history.get(curIndex);
}
public String forward(int steps) {
curIndex = Math.min(curIndex + steps, history.size() - 1);
return history.get(curIndex);
}
}
复杂度分析
时间复杂度：
- visit操作的时间复杂度为，因为只需要将当前位置之后的历史记录全部删除，然后将新的url添加到历史记录里。
- back和forward操作的时间复杂度为，因为只需要根据给定的步数更新指针，并返回相应的历史记录。
空间复杂度：
- 空间复杂度为，其中是历史记录的长度。需要使用额外的空间来存储历史记录。
Leetcode 1209. Remove All Adjacent Duplicates in String II
题目描述
给你一个字符串 s 和一个整数 k ，请你使用下面的算法将字符串 s 中的所有子串长度为 k 的倍数都删除：
- 首先，删除 s 中长度为 k 的前缀子串。
- 其次，如果 s 中仍然存在长度为 k 的子串，就将最前面的那个长度为 k 的子串反转，然后删除掉前缀。
- 重复步骤 2 ，直到你在 s 中不能找到长度为 k 的子串。
返回删除所有长度为 k 的倍数且非空的子串之后的 s 。
示例 1：
输入：s = "abcd", k = 2
输出："abcd"
解释：没有任何子串长度为 2 的倍数。
示例 2：
输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释：
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"
示例 3：
输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"
提示：
- 1 <= s.length <= 10^5
- 2 <= k <= 10^4
- s 中只含有小写英文字母。
解法
本题的解法是使用栈来模拟删除操作。遍历字符串 s，如果当前字符和栈顶字符相同，则将其入栈；否则将其和栈顶元素一起出栈，并检查是否需要进行反转和删除操作。
具体来说，我们可以使用一个辅助栈 stack，从左到右遍历字符串 s 中的每个字符 c：
- 如果栈为空，或者栈顶元素的字符不等于 c，则将 c 入栈。
- 如果栈顶元素的字符等于 c，则将 c 与栈顶元素一起出栈，并将它们拼接成一个字符串 t。如果 t 的长度等于 k，则直接丢弃；否则将 t 反转后再入栈。
最后，我们将栈中的元素依次弹出并拼接，然后将字符串反转即可。
代码
class Solution {
public String removeDuplicates(String s, int k) {
Stack<Pair<Character, Integer>> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek().getKey() == c) {
stack.push(new Pair<>(c, stack.peek().getValue() + 1));
if (stack.peek().getValue() == k) {
for (int i = 0; i < k; i++) {
stack.pop();
}
}
} else {
stack.push(new Pair<>(c, 1));
}
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
Pair<Character, Integer> pair = stack.pop();
for (int i = 0; i < pair.getValue(); i++) {
sb.append(pair.getKey());
}
}
return sb.reverse().toString();
}
}
复杂度分析
时间复杂度：，其中 是字符串的长度。我们只遍历了字符串一次，并且每个字符最多只入栈和出栈一次。
空间复杂度：，其中 是字符串的长度。我们需要使用一个辅助栈来存储每个字符及其出现次数。在最坏情况下，例如字符串 s 的所有字符都相同，辅助栈最多会存储 个元素。
Leetcode 1249. Minimum Remove to Make Valid Parentheses
题目描述
给你一个只包含字符 '(' 和 ')' 的字符串 s ，请你返回字符串 s 中删除掉最少数量的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
请返回任意一个合法字符串。
有效「括号字符串」应当符合以下 任意一条 要求：
空字符串或只包含小写字母的字符串被认为是有效字符串。
任何左括号 ( 必须有相应的右括号 ) 。
任何右括号 ) 必须有相应的左括号 ( 。
相邻两个括号字符必须是不同的。
示例 1：
输入：s = "lee(t(c)o)de)" 输出："lee(t(c)o)de" 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
示例 2：
输入：s = "a)b(c)d" 输出："ab(c)d"
示例 3：
输入：s = "))((" 输出："" 解释：空字符串也是有效的
示例 4：
输入：s = "(a(b(c)d)" 输出："a(b(c)d)"
提示：
1 <= s.length <= 10^5 s[i] 可能是 '('、')' 或英文小写字母
解法
本题可以使用栈来进行解答。首先遍历整个字符串，将所有不合法的括号标记出来，然后再遍历一遍字符串，将不合法的括号删除即可。
具体来说，我们可以使用一个栈来记录左括号的位置。遍历字符串，当遇到左括号时，将其下标入栈；当遇到右括号时，如果栈为空，则说明该右括号是不合法的，标记该位置需要删除；否则从栈中弹出一个左括号的下标，表示该右括号与该左括号匹配。遍历结束后，如果栈中还有左括号的下标，那么这些左括号都是不合法的，需要标记为删除。
最后遍历一遍字符串，将标记的位置删除即可。
代码
class Solution {
public String minRemoveToMakeValid(String s) {
Stack<Integer> stack = new Stack<>();
boolean[] remove = new boolean[s.length()];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i);
} else if (c == ')') {
if (stack.isEmpty()) {
remove[i] = true;
} else {
stack.pop();
}
}
}
while (!stack.isEmpty()) {
remove[stack.pop()] = true;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!remove[i]) {
sb.append(s.charAt(i));
}
}
return sb.toString();
}
}
复杂度分析
时间复杂度：，其中 是字符串的长度。需要遍历两遍字符串。
空间复杂度：，其中 是字符串的长度。需要使用栈和标记数组。
Leetcode 735. Asteroid Collision
题目描述
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个大小不同的行星发生碰撞时，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星永远不会发生碰撞。
示例：
输入：asteroids = [5,10,-5] 输出：[5,10] 解释：10 和 -5 碰撞后只剩下 10 。 5 和 10 永远不会发生碰撞。
输入：asteroids = [8,-8] 输出：[] 解释：8 和 -8 碰撞后，两者都发生爆炸。
输入：asteroids = [10,2,-5] 输出：[10] 解释：2 和 -5 发生碰撞后剩下 -5 。10 和 -5 发生碰撞后剩下 10 。
输入：asteroids = [-2,-1,1,2] 输出：[-2,-1,1,2] 解释：-2 和 -1 向左移动，1 和 2 向右移动。不发生碰撞。
提示：
2 <= asteroids.length <= 104-1000 <= asteroids[i] <= 1000asteroids[i] != 0
解法
可以使用栈来模拟碰撞过程。对于每颗行星，如果它向右移动或者栈顶的行星向左移动，则它不会与栈顶的行星碰撞，直接入栈。如果它向左移动且栈顶的行星向右移动，则它们一定会碰撞。如果它的大小大于栈顶行星的大小，则栈顶行星爆炸，出栈。重复上述过程，直到所有行星都处理完毕。
代码
class Solution {
public int[] asteroidCollision(int[] asteroids) {
Stack<Integer> stack = new Stack<>();
for (int asteroid : asteroids) {
if (stack.isEmpty() || asteroid > 0 || (stack.peek() < 0 && asteroid < 0)) {
stack.push(asteroid);
} else {
while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < -asteroid) {
stack.pop();
}
if (stack.isEmpty() || stack.peek() < 0) {
stack.push(asteroid);
} else if (stack.peek() == -asteroid) {
stack.pop();
}
}
}
int[] res = new int[stack.size()];
for (int i = res.length - 1; i >= 0; i--) {
res[i] = stack.pop();
}
return res;
}
}
复杂度分析
时间复杂度：，其中 是数组的长度。需要遍历数组一次。
空间复杂度：，其中 是数组的长度。需要使用栈存储行星。
3.Hashmap/ Hashset题目：
Leetcode 1. Two Sum
题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
- 只会存在一个有效答案
解法
本题的解法是使用哈希表，遍历数组，将每个数字与它的下标存入哈希表中。然后再次遍历数组，对于每个数字 ，计算出与目标值的差值 ，然后在哈希表中查找是否存在值等于 的键，如果存在，则返回两个数字的下标。
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (map.containsKey(diff) && map.get(diff) != i) {
return new int[] {i, map.get(diff)};
}
}
return new int[0];
}
}
复杂度分析
时间复杂度：，其中 是数组的长度。需要遍历数组两次，但哈希表的查找操作是 的，所以总时间复杂度为 。
空间复杂度：，其中 是数组的长度。需要使用哈希表存储每个数字的值和它的下标。
Leetcode 146. LRU Cache (Python中可以使用OrderedDict来代替)
题目描述
设计一个LRU缓存机制，实现以下操作：
- get(key)：如果key存在于缓存中，则返回对应的value值，否则返回-1。
- put(key, value)：如果key存在于缓存中，则更新其value值，否则插入该key-value对。当缓存容量达到上限时，删除最近最少使用的key-value对。
LRU缓存的工作方式如下：当缓存容量达到上限时，删除最近最少使用的key-value对，即删除时间戳最早的那个key-value对。
**进阶：**你是否可以在O(1)时间复杂度内完成这两种操作？
示例：
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
解法
本题可以使用哈希表和双向链表实现。哈希表存储键值对，双向链表存储键值对的访问顺序，最近访问的节点放在链表的头部。
- get(key)方法：如果key存在于哈希表中，则将对应的节点移到链表头部并返回value；否则返回-1。
- put(key, value)方法：如果key存在于哈希表中，则将对应的节点移到链表头部并更新value；否则创建新节点并插入到链表头部。如果缓存容量已满，则删除链表尾部的节点。
代码
class LRUCache {
private int capacity;
private Map<Integer, Node> map;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node == null) {
node = new Node(key, value);
map.put(key, node);
addToHead(node);
if (map.size() > capacity) {
Node removed = removeTail();
map.remove(removed.key);
}
} else {
node.value = value;
moveToHead(node);
}
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node node = tail.prev;
removeNode(node);
return node;
}
private class Node {
int key;
int value;
Node prev;
Node next;
public Node() {
this(0, 0);
}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
复杂度分析
时间复杂度：get和put操作的时间复杂度均为O(1)。
空间复杂度：哈希表和双向链表的总空间为O(capacity)。
Leetcode 128. Longest Consecutive Sequence
题目描述
给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。
示例 1:
输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
解法
本题的解法是使用哈希表，先将所有数加入哈希表中。然后遍历数组中的每个数，如果这个数是连续序列的起点，就从哈希表中查找是否存在比这个数大 的数，如果存在就继续查找，直到找不到为止，记录下连续序列的长度。最后返回最长的连续序列长度。
代码
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLen = 0;
for (int num : nums) {
if (!set.contains(num - 1)) { // 如果 num 是连续序列的起点
int curNum = num;
int curLen = 1;
while (set.contains(curNum + 1)) { // 查找比 num 大 1 的数，直到找不到为止
curNum++;
curLen++;
}
maxLen = Math.max(maxLen, curLen);
}
}
return maxLen;
}
}
复杂度分析
时间复杂度：，其中 是数组的长度。需要遍历数组两次，但每个数只会遍历一次。
空间复杂度：，其中 是数组的长度。需要使用哈希表存储所有数。
Leetcode 73. Set Matrix Zeroes
题目描述
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ]
示例 2:
输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]
进阶:
- 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗？
解法
我们可以使用矩阵的第一行和第一列来记录该行或该列是否应该被设置为 0。首先，我们遍历第一行和第一列，如果有一个元素为 0，我们就将其对应的行和列的第一个元素设置为 0。这样，第一行和第一列就记录了所有应该被设置为 0 的行和列。
然后，我们遍历矩阵中除第一行和第一列的所有元素，如果某个元素为 0，我们就将其所在行和列的第一个元素设置为 0。最后，我们根据第一行和第一列的标记，将相应的行和列设置为 0。
代码
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
boolean firstRowHasZero = false;
boolean firstColHasZero = false;
// check if first row has zero
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
firstRowHasZero = true;
break;
}
}
// check if first column has zero
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
firstColHasZero = true;
break;
}
}
// use first row and first column to mark the rows and columns to be set to zero
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
// set rows and columns to zero according to first row and first column
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
// set first row and first column to zero if necessary
if (firstRowHasZero) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
if (firstColHasZero) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
}
}
复杂度分析
时间复杂度：，其中 是矩阵的行数， 是矩阵的列数。需要遍历矩阵中的所有元素。
空间复杂度：，只需要常数空间来存储标记。
Leetcode 380. Insert Delete GetRandom O(1)
题目描述
设计一个支持在平均时间复杂度 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。remove(val)：元素 val 存在时，从集合中移除该项。getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
示例 :
// 初始化一个空的集合。
RandomizedSet randomSet = new RandomizedSet();
// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);
// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);
// 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomSet.insert(2);
// getRandom 应随机返回 1 或 2 。
randomSet.getRandom();
// 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomSet.remove(1);
// 2 已在集合中，返回 false 。
randomSet.insert(2);
// 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
randomSet.getRandom();
提示：
-2^31 <= val <= 2^31 - 1- 最多调用 次 insert、remove 和 getRandom 。
- 在调用 getRandom 方法时，数据结构必须有 size 方法返回集合中元素的个数。
- 所有元素都是唯一的，因此集合中不存在重复的元素。
解法
本题的解法是使用哈希表 + 动态数组。
具体实现如下：
- 使用哈希表存储每个元素在动态数组中的下标，以实现 的插入和删除操作。
- 使用动态数组存储所有元素，以实现 的随机访问操作。
插入操作：
- 如果元素已经存在，则返回 false。
- 否则，在动态数组末尾插入新元素，并在哈希表中存储该元素在动态数组中的下标。
删除操作：
- 如果元素不存在，则返回 false。
- 否则，先在哈希表中查找该元素在动态数组中的下标，然后将该元素与动态数组末尾元素交换位置，并在哈希表中更新末尾元素的下标。
- 最后，删除末尾元素，并在哈希表中删除该元素的下标。
随机访问操作：
- 生成一个随机数 ，然后返回动态数组中的第 个元素。
代码
class RandomizedSet {
List<Integer> list;
Map<Integer, Integer> map;
/** Initialize your data structure here. */
public RandomizedSet() {
list = new ArrayList<>();
map = new HashMap<>();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
list.add(val);
map.put(val, list.size() - 1);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int index = map.get(val);
int lastVal = list.get(list.size() - 1);
list.set(index, lastVal);
map.put(lastVal, index);
list.remove(list.size() - 1);
map.remove(val);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
int index = (int)(Math.random() * list.size());
return list.get(index);
}
}
复杂度分析
时间复杂度：
- 插入操作的时间复杂度为 。
- 删除操作的时间复杂度为 。
- 随机访问操作的时间复杂度为 。
空间复杂度：
- 使用动态数组和哈希表存储所有元素，因此空间复杂度为 ，其中 是元素的个数。
Leetcode 49. Group Anagrams
题目描述
给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词指字母相同，但排列不同的字符串。
示例 1：
输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2：
输入：strs = [""]
输出：[[""]]
示例 3：
输入：strs = ["a"]
输出：[["a"]]
提示：
1 <= strs.length <= 10^40 <= strs[i].length <= 100strs[i]仅包含小写字母
解法
本题的解法是将每个字符串按照字母顺序排序，然后将排序后的字符串作为键，原始字符串作为值存入哈希表中。最后将哈希表中的值取出来即可。
代码
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(s);
map.put(key, list);
}
return new ArrayList<>(map.values());
}
}
复杂度分析
时间复杂度：，其中 是字符串数组的长度， 是字符串的最大长度。对于每个字符串，需要 的时间进行排序。
空间复杂度：，其中 是字符串数组的长度， 是字符串的最大长度。需要使用哈希表存储每个字符串。
Leetcode 350. Intersection of Two Arrays II
题目描述
给定两个数组，编写一个函数来计算它们的交集。
示例 1：
输出：[2,2]
示例 2:
输出：[4,9]
提示：
- 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
进阶:
- 如果给定的数组已经排好序呢？你将如何优化你的算法？
- 如果 nums1 的大小比 nums2 小很多，哪种方法更优？
- 如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
解法
本题的解法是使用HashMap来存储nums1中每个数出现的次数，然后遍历nums2，如果当前数在HashMap中出现，则将其加入结果集中，并将HashMap中该数的出现次数减1。
时间复杂度为，其中和分别是nums1和nums2的长度。
代码
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums1) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
List<Integer> list = new ArrayList<>();
for (int num : nums2) {
if (map.containsKey(num) && map.get(num) > 0) {
list.add(num);
map.put(num, map.get(num) - 1);
}
}
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}
}
复杂度分析
时间复杂度：，其中和分别是nums1和nums2的长度。遍历nums1需要的时间，遍历nums2需要的时间，而HashMap的操作都是的时间。
空间复杂度：，其中是nums1中不同的数的个数。需要使用HashMap来存储nums1中每个数出现的次数。如果nums1和nums2都很大，可以先对其进行排序，然后使用双指针来解决。这种情况下，时间复杂度仍为，但空间复杂度降为。
Leetcode 299. Bulls and Cows
题目描述
你正在和你的朋友玩 猜数字（Bulls and Cows） 游戏：你写下一个秘密数字，并请你的朋友猜这个数字是多少。每次朋友猜测后，你都会给他一个提示，告诉他猜对了几个数字（位置也正确）， 猜对了几个数字（位置不正确）。你的朋友将会根据提示继续猜，直到猜出秘密数字。
写一个函数来获取秘密数字和朋友的猜测，并返回一个提示结果。请用以下格式表示提示结果：
xAxB
其中 x 表示猜对了几个位置的数字，A 表示猜对了几个数字但是位置不对，B 表示猜对了几个位置的数字（也包括猜对了位置和数字）。注意秘密数字和朋友的猜测都可能含有重复数字。
示例 1:
输入: secret = "1807", guess = "7810" 输出: "1A3B" 解释: 1 表示位置正确的数字，3 表示在秘密数字串里但位置错误的数字。 示例 2:
输入: secret = "1123", guess = "0111" 输出: "1A1B" 解释: 朋友猜测到位置1的数字是1，位置3的数字是1，秘密数字中位置1的数字是1，但位置并不对。
说明:
秘密数字和朋友的猜测都只包含数字，并且长度都在范围 [1, 1000] 内。
解法
本题可以通过哈希表来解决。先遍历一遍秘密数字和猜测数字，将相同位置上的数字统计到bulls变量中，将不同位置上的数字统计到哈希表中。然后再遍历一遍哈希表，将相同数字的个数取最小值累加到cows变量中即可。
代码
class Solution {
public String getHint(String secret, String guess) {
int bulls = 0, cows = 0;
int[] count = new int[10];
for (int i = 0; i < secret.length(); i++) {
if (secret.charAt(i) == guess.charAt(i)) {
bulls++;
} else {
count[secret.charAt(i) - '0']++;
count[guess.charAt(i) - '0']--;
}
}
for (int num : count) {
if (num > 0) {
cows += num;
}
}
cows = secret.length() - bulls - cows;
return bulls + "A" + cows + "B";
}
}
复杂度分析
时间复杂度：，其中 是秘密数字和猜测数字的长度。
空间复杂度：，因为哈希表的大小不会超过 。
Leetcode 348 Design Tic-Tac-Toe
题目描述
设计一个 Tic-tac-toe 游戏，使两个玩家轮流在3x3的棋盘上放置标记。第一个玩家放置字符 "X"，第二个玩家放置字符 "O"。玩家标记先在一个空的方格中放置，然后轮流进行下一个标记，直到有玩家在水平，垂直或对角线上形成了长度为 3 的一排标记，或者所有的方块都被填满了。如果所有方块都被填满了，游戏会以平局告终。在游戏结束后，玩家可以再次开始新游戏。
示例：
输入：
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]
输出：
[null, 0, 0, 0, 0, 0, 0, 1]
解释：
TicTacToe ticTacToe = new TicTacToe(3); // 初始化游戏
// 玩家 1 在 (0, 0) 处放置了字符 'X'
// 玩家 2 在 (0, 2) 处放置了字符 'O'
// 玩家 1 在 (2, 2) 处放置了字符 'X'
// 玩家 2 在 (1, 1) 处放置了字符 'O'
// 玩家 1 在 (2, 0) 处放置了字符 'X'
// 玩家 2 在 (1, 0) 处放置了字符 'O'
// 玩家 1 在 (2, 1) 处放置了字符 'X'
// 无法再进行下一步操作，游戏结束。
// 如果玩家 1 赢得了游戏，则返回 1，如果玩家 2 赢得了游戏，则返回 2，如果平局，则返回 0。
提示：
- 2 <= n <= 100
- 每个玩家最多输入 n 次。
- 输入操作时，第三个参数是用来指定玩家的，取值为 1 或 2。
解法
我们可以定义两个数组，分别用于记录每个玩家在每行、每列和两条对角线上的棋子数，当某个玩家在某一行、列或对角线上的棋子数达到 时，该玩家获胜。
对于每次落子操作，我们只需要将相应的数组加 1，然后判断当前玩家是否获胜即可。
代码
class TicTacToe {
private int n;
private int[] rows;
private int[] cols;
private int diagonal;
private int antidiagonal;
/** Initialize your data structure here. */
public TicTacToe(int n) {
this.n = n;
this.rows = new int[n];
this.cols = new int[n];
this.diagonal = 0;
this.antidiagonal = 0;
}
/** Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins. */
public int move(int row, int col, int player) {
int add = player == 1 ? 1 : -1;
rows[row] += add;
cols[col] += add;
if (row == col) {
diagonal += add;
}
if (row == n - 1 - col) {
antidiagonal += add;
}
if (Math.abs(rows[row]) == n || Math.abs(cols[col]) == n || Math.abs(diagonal) == n || Math.abs(antidiagonal) == n) {
return player;
} else {
return 0;
}
}
}
复杂度分析
- 时间复杂度：
- 空间复杂度：，需要使用额外的空间记录每个玩家在每行、每列和两条对角线上的棋子数。
京公网安备 11010502036488号