LEETCODE UNLOCK

LeetCode刷题:栈、队列和递归

2019.08.31 18:32 0

关于栈、队列和递归的几个必知必会的代码实现

  • 用数组实现一个顺序栈

  • 用链表实现一个链式栈

  • 编程模拟实现一个浏览器的前进、后退功能

队列

  • 用数组实现一个顺序队列

  • 用链表实现一个链式队列

  • 实现一个循环队列

递归

  • 编程实现斐波那契数列求值 f(n)=f(n-1)+f(n-2)

  • 编程实现求阶乘 n!

  • 编程实现一组数据集合的全排列

栈题目

Valid Parentheses(有效的括号)

题目:

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: “()”
输出: true

思路:

初始化栈 S
依次处理表达式的每个括号。
如果遇到开括号,入栈上即可。
如果遇到一个闭括号,那么检查栈顶的元素。如果栈顶的元素是一个相同类型的左括号,那么将它从栈中弹出并继续处理。
如果到最后剩下的栈中仍然有元素,那么这意味着表达式无效。

代码如下:

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
public boolean isValid(String s) {
char[] sChar = s.toCharArray();
Stack<Character> s1 = new Stack<>();
int i = 0;
while (i < sChar.length){
if (!s1.isEmpty()) {
if (sChar[i] == ')') {
if (s1.peek() == '(')
s1.pop();
else
return false;
} else if (sChar[i] == '}') {
if (s1.peek() == '{')
s1.pop();
else
return false;
} else if (sChar[i] == ']') {
if (s1.peek() == '[')
s1.pop();
else
return false;
}
else
s1.push(sChar[i]);
}
else
s1.push(sChar[i]);
i++;
}
return s1.isEmpty();
}

Longest Valid Parentheses(最长有效的括号)

题目:

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

思路:

本人没有太好的思路,就去偷瞄官方题解了。。。官方题解

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int longestValidParentheses(String s) {
int maxans = 0;
Stack<Integer> stack = new Stack<>();
stack.push(-1);
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') {
stack.push(i);
} else {
stack.pop();
if (stack.empty()) {
stack.push(i);
} else {
maxans = Math.max(maxans, i - stack.peek());
}
}
}
return maxans;
}

Evaluate Reverse Polish Notatio(逆波兰表达式求值)

题目:

根据逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

说明:

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1:

输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

思路:

定义一个栈辅助计算;
当遇到运算符”+”、”-“、”*”、”/“时,从栈中 pop 出两个数字计算,否则将数字入栈;

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String s : tokens) {
if (s.equals("+")) {
stack.push(stack.pop() + stack.pop());
} else if (s.equals("-")) {
stack.push(-stack.pop() + stack.pop());
} else if (s.equals("*")) {
stack.push(stack.pop() * stack.pop());
} else if (s.equals("/")) {
int num1 = stack.pop();
stack.push(stack.pop() / num1);
} else {
stack.push(Integer.parseInt(s));
}
}
return stack.pop();
}

队列题目

Design Circular Deque(设计一个双端队列)

题目:

设计实现双端队列。
你的实现需要支持以下操作:

  • MyCircularDeque(k):构造函数,双端队列的大小为 k
  • insertFront():将一个元素添加到双端队列头部。 如果操作成功返回 true
  • insertLast():将一个元素添加到双端队列尾部。如果操作成功返回 true
  • deleteFront():从双端队列头部删除一个元素。 如果操作成功返回 true
  • deleteLast():从双端队列尾部删除一个元素。如果操作成功返回 true
  • getFront():从双端队列头部获得一个元素。如果双端队列为空,返回 -1
  • getRear():获得双端队列的最后一个元素。 如果双端队列为空,返回 -1
  • isEmpty():检查双端队列是否为空。
  • isFull():检查双端队列是否满了。

思路:

使用循环数组来实现避免数据迁移,这里直接记录size来做判断队列空还是满,需要注意的是在插入头部时,头部指针回退一位的处理;和删除尾部时,尾部指针回退一位的处理

代码如下:

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
79
80
81
82
83
84
85
86
87
88
89
90
public static final int DEFAULT_CAPACITY = 10;

private int size;
private int capacity;
private int[] elementData;
private int head;
private int tail;

public MyCircularDeque(int k) {
if (k <= 0) {
k = DEFAULT_CAPACITY;
}
elementData = new int[k];
capacity = k;
head = 0;
tail = 0;
}

public boolean insertFront(int value) {
if (isFull()) {
return false;
}
if (head - 1 < 0) {
head = capacity - 1;
} else {
head--;
}
elementData[head] = value;
size++;
return true;
}

// 插入到队列尾部
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
elementData[tail] = value;
tail = (tail + 1) % capacity;
size++;
return true;
}

public boolean deleteFront() {
if (isEmpty()) {
return false;
}
head = (head + 1) % capacity;
size--;
return true;
}

public boolean deleteLast() {
if (isEmpty()) {
return false;
}
if (tail - 1 < 0) {
tail = capacity - 1;
} else {
tail--;
}
size--;
return true;
}

public int getFront() {
if (isEmpty()) {
return -1;
}
return elementData[head];
}

public int getRear() {
if (isEmpty()) {
return -1;
}
// 特别注意!!!!
if (tail - 1 < 0) {
return elementData[capacity - 1];
}
return elementData[tail - 1];
}

public boolean isEmpty() {
return size == 0;
}

public boolean isFull() {
return size == capacity;
}

Sliding Window Maximum(滑动窗口最大值)

题目:

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

返回滑动窗口中的最大值。
提示:

你可以假设 k 总是有效的,在输入数组不为空的情况下,1 ≤ k ≤ 输入数组的大小

进阶:

你能在线性时间复杂度内解决此题吗?

思路:

暴力法可以做,但是太慢了,给上官方题解

代码如下:

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
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
if (k == 1) return nums;

int [] left = new int[n];
left[0] = nums[0];
int [] right = new int[n];
right[n - 1] = nums[n - 1];
for (int i = 1; i < n; i++) {
// from left to right
if (i % k == 0) left[i] = nums[i]; // block_start
else left[i] = Math.max(left[i - 1], nums[i]);

// from right to left
int j = n - i - 1;
if ((j + 1) % k == 0) right[j] = nums[j]; // block_end
else right[j] = Math.max(right[j + 1], nums[j]);
}

int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++)
output[i] = Math.max(left[i + k - 1], right[i]);

return output;
}

递归题目

Climbing Stairs(爬楼梯)

题目:

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 12 个台阶。你有多少种不同的方法可以爬到楼顶呢?

注意:给定 n 是一个正整数。

示例 1:

输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。

  1. 1 阶 + 1
  2. 2

思路:

暴力递归可以通过,但是有没有更好的方案呢,思考一下发现其实就是斐波那契数列 $Fib(n) = Fib(n−1) + Fib(n−2)$

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
public int climbStairs(int n) {
if (n == 1) {
return 1;
}
int first = 1;
int second = 2;
for (int i = 3; i <= n; i++) {
int third = first + second;
first = second;
second = third;
}
return second;
}

好了,就刷到这里了,有问题欢迎和我留言😉。

评论加载中