一、队列
先进先出的数据结构 FIFO
1.实现队列
// "static void main" must be defined in a public class.
class MyQueue {
// store elements
private List<Integer> data;
// a pointer to indicate the start position
private int p_start;
public MyQueue() {
data = new ArrayList<Integer>();
p_start = 0;
}
/** Insert an element into the queue. Return true if the operation is successful. */
public boolean enQueue(int x) {
data.add(x);
return true;
};
/** Delete an element from the queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
//直接将头指针后移
p_start++;
return true;
}
/** Get the front item from the queue. */
public int Front() {
return data.get(p_start);
}
/** Checks whether the queue is empty or not. */
public boolean isEmpty() {
return p_start >= data.size();
}
};
public class Main {
public static void main(String[] args) {
MyQueue q = new MyQueue();
q.enQueue(5);
q.enQueue(3);
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
}
}
2.分析
+缺点：随着起始指针的移动，浪费了越来越多的空间。 解决方案：更有效的方法是使用<mark>循环队列</mark>。
+具体来说，我们可以使用<mark>固定大小的数组</mark>和<mark>两个指针</mark>来指示起始位置和结束位置。 目的是<mark>重用</mark>我们之前提到的被浪费的存储。+循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
+循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
3.循环队列实现
class MyCircularQueue {
private int[] data;
private int head;
private int tail;
private int size;
/** Initialize your data structure here. Set the size of the queue to be k. */
public MyCircularQueue(int k) {
data = new int[k];
head = -1;
tail = -1;
size = k;
}
/** Insert an element into the circular queue. Return true if the operation is successful. */
public boolean enQueue(int value) {
if (isFull() == true) {
return false;
}
if (isEmpty() == true) {
head = 0;
}
tail = (tail + 1) % size;
data[tail] = value;
return true;
}
/** Delete an element from the circular queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
//再出队一次就为空
if (head == tail) {
head = -1;
tail = -1;
return true;
}
head = (head + 1) % size;
return true;
}
/** Get the front item from the queue. */
public int Front() {
if (isEmpty() == true) {
return -1;
}
return data[head];
}
/** Get the last item from the queue. */
public int Rear() {
if (isEmpty() == true) {
return -1;
}
return data[tail];
}
/** Checks whether the circular queue is empty or not. */
public boolean isEmpty() {
return head == -1;
}
/** Checks whether the circular queue is full or not. */
public boolean isFull() {
return ((tail + 1) % size) == head;
}
}
/** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue obj = new MyCircularQueue(k); * boolean param_1 = obj.enQueue(value); * boolean param_2 = obj.deQueue(); * int param_3 = obj.Front(); * int param_4 = obj.Rear(); * boolean param_5 = obj.isEmpty(); * boolean param_6 = obj.isFull(); */
二、队列和 BFS
广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。
用队列实现BFS的模板
/** * Return the length of the shortest path between root and target node. */
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
add next to queue;
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
下面这个可以保证不会访问一个节点两次,使用了<mark>哈希表</mark>
/** * Return the length of the shortest path between root and target node. */
int BFS(Node root, Node target) {
Queue<Node> queue; // store all nodes which are waiting to be processed
Set<Node> used; // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
add root to queue;
add root to used;
// BFS
while (queue is not empty) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = the first node in queue;
return step if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in used) {
add next to queue;
add next to used;
}
}
remove the first node from queue;
}
}
return -1; // there is no path from root to target
}
岛屿数量问题
给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例
输入:
11110
11010
11000
00000
输出: 1
class Solution {
int nr = 0;//数组的行数
int nc = 0;//数组的列数
void dfs(char[][] grid, int r, int c) {
nr = grid.length;
nc = grid[0].length;
//如果周围的数字有零则结束本次查找,继续向另一个方向查找
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return;
}
//最关键的一步:将查找过得数字赋值为0,避免重复查找,因为前面有约束条件
grid[r][c] = '0';
dfs(grid, r - 1, c);//往左查找
dfs(grid, r + 1, c);//往右查找
dfs(grid, r, c - 1);//往下查找
dfs(grid, r, c + 1);//往上查找
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0;
}
nr = grid.length;
nc = grid[0].length;
int num_islands = 0;//计数
for (int r = 0; r < nr; ++r) {
for (int c = 0; c < nc; ++c) {
if (grid[r][c] == '1') {
++num_islands;
dfs(grid, r, c);//调用广度优先遍历,查看周围的数字
}
}
}
return num_islands;
}
}
三、栈
在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。
与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。
1. 实现堆栈
// "static void main" must be defined in a public class.
class MyStack {
private List<Integer> data; // store elements
public MyStack() {
data = new ArrayList<>();
}
/** Insert an element into the stack. */
public void push(int x) {
data.add(x);
}
/** Checks whether the queue is empty or not. */
public boolean isEmpty() {
return data.isEmpty();
}
/** Get the top item from the queue. */
public int top() {
return data.get(data.size() - 1);
}
/** Delete an element from the queue. Return true if the operation is successful. */
public boolean pop() {
if (isEmpty()) {
return false;
}
data.remove(data.size() - 1);
return true;
}
};
public class Main {
public static void main(String[] args) {
MyStack s = new MyStack();
s.push(1);
s.push(2);
s.push(3);
for (int i = 0; i < 4; ++i) {
if (!s.isEmpty()) {
System.out.println(s.top());
}
System.out.println(s.pop());
}
}
}
大多数流行的语言都提供了内置的栈库，因此你不必重新发明轮子。除了初始化，我们还需要知道如何使用两个最重要的操作：入栈和退栈。除此之外，你应该能够从栈中获得顶部元素。下面是一些供你参考的代码示例：
// "static void main" must be defined in a public class.
public class Main {
public static void main(String[] args) {
// 1. Initialize a stack.
Stack<Integer> s = new Stack<>();
// 2. Push new element.
s.push(5);
s.push(13);
s.push(8);
s.push(6);
// 3. Check if stack is empty.
if (s.empty() == true) {
System.out.println("Stack is empty!");
return;
}
// 4. Pop an element.
s.pop();
// 5. Get the top element.
System.out.println("The top element is: " + s.peek());
// 6. Get the size of the stack.
System.out.println("The size is: " + s.size());
}
}
- push(x) – 将元素 x 推入栈中。
- pop() – 删除栈顶的元素。
- peek() – 获取栈顶元素。
2. 最小栈问题
解法一
最直接的方法就是用两个栈,一个去保存正常出入栈的值,一个去保存最小值（实际上是用栈顶去保存最小值）
- 元素同时入两个栈
- 第二个元素来了，二话不说先入第一个栈，再和第二个栈的栈顶元素比较，如果小于等于他就入栈，假如确实小了，那就入栈
- 第三个元素来了，二话不说入第一个栈，在和第二个栈的栈顶比较，加入比栈顶元素大，不入栈
- 出栈就简单了，如果第一个栈中要出栈的元素等于第二个栈的栈顶元素，就同时出栈，否则只出第一个栈，因为右边的栈顶始终保持的是最小值，你后面不管入栈多少大于它的值我都不管，因为我没入栈。
代码实现
class MinStack {
/** initialize your data structure here. */
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
stack.push(x);
if (!minStack.isEmpty()) {
int top = minStack.peek();
//小于的时候才入栈
if (x <= top) {
minStack.push(x);
}
}else{
minStack.push(x);
}
}
public void pop() {
int pop = stack.pop();
int top = minStack.peek();
//等于的时候再出栈
if (pop == top) {
minStack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
解法二
刚才用了两个栈，那能不能只用一个栈呢？
- 如果只用一个栈，之前的最小元素会被下一个覆盖掉，这样min存的就只是目前的最小值了
- 只能是将当过最小值的数在下一个数入栈之前入栈就可以了，如果要过来的数比min大就不用管，只看小于等于
- 当出栈元素是目前的最小元素怎么办？
- 只需要把出栈元素放心的出栈，然后把下一个元素出栈并赋值给min
class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public void push(int x) {
//当前值更小
if(x <= min){
//将之前的最小值保存
stack.push(min);
//更新最小值
min=x;
}
stack.push(x);
}
public void pop() {
//如果弹出的值是最小值，那么将下一个元素更新为最小值
if(stack.pop() == min) {
min=stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
3. 有效的括号
这个题目的任务相当于编译器给我们提供功能，即检查括号是否匹配：
让我们看看下面的这个想法，从整体表达式中一次删除一个较小的表达式，因为这是一个有效的表达式，我们最后剩留下一个空字符串。
根据题目要求可以想到使用栈来解决问题，因为栈就是后进先出，仔细观察上面的图片，你会发现它具有以下特点：
- 如果外层括号匹配，那么里面的括号也一定匹配
- 那就可以使用递归来从内到外判断
- 我们无法真正地从内到外处理这个问题，因为我们对整体结构一无所知。但是，栈可以帮助我们递归地处理这种情况，即从外部到内部。
注意：
- 如果字符串的长度为奇数，直接返回false
- 最后栈应该是空的
设想一种解决方案：
- 初始化栈；
- 依次处理表达式里的每个括号；
- 如果遇到开括号，我们只需要把它推到栈上；
- 如果遇到一个闭括号，在处理他之前先检查它是否与目前的栈顶元素匹配，如果匹配，就把它们全部踢出去（pop）。如果不匹配，那这个字符串就不是一个有效的括号，因为我们刚才分析了，要想有效，由内而外必须都匹配；
- 如果到最后栈不为空，那么该字符串无效，因为如果都匹配，我们应该是都踢完了才对。
代码实现
class Solution {
private Map<Character, Character> mapping = null;
public Solution() {
mapping = new HashMap<>();
mapping.put(')', '(');
mapping.put(']', '[');
mapping.put('}', '{');
}
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
//如果长度为奇数,直接返回
if (s.length() % 2 == 1) {
return false;
}
//遍历这个字符串
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
//如果是右括号
if (mapping.containsKey(ch)) {
char top = stack.isEmpty() ? '#' : stack.pop();
//如果返回的值和它不匹配,直接返回
if (top != mapping.get(ch)) {
return false;
}
//如果是左括号
} else {
stack.push(ch);
}
}
//最后的栈应该为空
return stack.isEmpty();
}
}
四、栈和DFS
与 BFS 类似，深度优先搜索（DFS）也可用于查找从根结点到目标结点的路径。在本文中，我们提供了示例来解释 DFS 是如何工作的以及栈是如何逐步帮助 DFS 工作的。
节点的处理顺序：
在我们到达最深的结点之后，我们只会
回溯并尝试另一条路径。
- 因此，你在 DFS 中找到的第一条路径并不总是最短的路径。
栈的入栈和退栈顺序是什么：
-
我们首先将
根结点推入到栈中；然后我们尝试第一个邻居并将该结点推入到栈中；等等等等。当我们到达最深的结点时，我们需要回溯。当我们回溯时，我们将从栈中弹出最深的结点，这实际上是推入到栈中的最后一个结点。 -
结点的处理顺序是
完全相反的顺序，就像它们被添加到栈中一样，它是后进先出（LIFO）。这就是我们在 DFS 中使用栈的原因。
1. 模板
正如我们在本章的描述中提到的，在大多数情况下，我们在能使用 BFS 时也可以使用 DFS。但是有一个重要的区别：遍历顺序。
与 BFS 不同，更早访问的结点可能不是更靠近根结点的结点。因此，你在 DFS 中找到的第一条路径可能不是最短路径。
DFS 的递归模板：
1. 实现一
有两种实现 DFS 的方法。第一种方法是进行递归
/* * Return true if there is a path from cur to target. */
boolean DFS(Node cur, Node target, Set<Node> visited) {
return true if cur is target;
for (next : each neighbor of cur) {
if (next is not in visited) {
add next to visted;
return true if DFS(next, target, visited) == true;
}
}
return false;
}
当我们递归地实现 DFS 时，似乎不需要使用任何栈。但实际上，我们使用的是由系统提供的隐式栈，也称为调用栈（Call Stack）。
示例
在每个堆栈元素中，都有一个整数 cur，一个整数 target，一个对访问过的数组的引用和一个对数组边界的引用，这些正是我们在 DFS 函数中的参数。我们只在上面的栈中显示 cur。
每个元素都需要固定的空间。栈的大小正好是 DFS 的深度。因此，在最坏的情况下，维护系统栈需要 O(h)，其中 h 是 DFS 的最大深度。在计算空间复杂度时，永远不要忘记考虑系统栈。
2. 实现二
递归解决方案的优点是它更容易实现。 但是，存在一个很大的缺点：如果递归的深度太高，你将遭受堆栈溢出。 在这种情况下，您可能会希望使用 BFS，或使用显式栈实现 DFS。
/* * Return true if there is a path from cur to target. */
boolean DFS(int root, int target) {
Set<Node> visited;
Stack<Node> s;
add root to s;
while (s is not empty) {
Node cur = the top element in s;
return true if cur is target;
for (Node next : the neighbors of cur) {
if (next is not in visited) {
add next to s;
add next to visited;
}
}
remove cur from s;
}
return false;
}
该逻辑与递归解决方案完全相同。 但我们使用 while 循环和栈来模拟递归期间的系统调用栈。
2. 目标和
给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
1.解法一：枚举
可以使用递归,你把所有的可能全都列举出来肯定可以解决问题，这种就是自底向上解决问题，从最小的分支往上不断的循环。因为你把它拆分了就是两个数比较。
代码如下：
class Solution {
private int count = 0;
public int findTargetSumWays(int[] nums, int s) {
calculate(nums, 0, 0, s);
return count;
}
public void calculate(int[] nums, int i, int sum, int s) {
//终止条件是什么? 应该是到头了,这时的i应该等于数组长度
if (i == nums.length) {
//到头了就看看是不是等于s
if (sum == s) {
count++;
}
} else {
//如果没到头
calculate(nums, i + 1, sum + nums[i], s);
calculate(nums, i + 1, sum - nums[i], s);
}
}
}
但是枚举的时间复杂度太高了
- 时间复杂度：O(2^N)，其中 NN 是数组 nums 的长度。
- 空间复杂度：O(N)，为递归使用的栈空间大小。
2. 解法二：动态规划
这道题也是一个常见的背包问题，我们可以用类似求解背包问题的方法来求出可能的方法数。
参考文章：
Leetcode
京公网安备 11010502036488号