逆波兰表达式求值
link：150. 逆波兰表达式求值 - 力扣（LeetCode）
思路分析
最开始的思路就是用栈解决，非运算符号的先入栈，遇到运算符再出栈对运算符进行判断之后进行相应的运算最后出栈即可.
【注意一点】
为了保证运算顺序，运算都是num2对num1操作（因为先进后出）
前提是搞懂逆波兰式
本质是二叉树中的中序遍历变成了后序遍历.
暴力版
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
| class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
int num1,num2;
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 tmp1 = stack.pop();
int tmp2 = stack.pop();
stack.push(tmp2/tmp1);
}
else
{
stack.push(Integer.valueOf(s));
}
}
return stack.pop();
}
}
|
优化版
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
| class Solution {
public int evalRPN(String[] tokens) {
if(tokens == null || tokens.length == 0) {
return 0;
}
LinkedList<Integer> stack = new LinkedList<>();
Set<String> operators = new HashSet<String>();
operators.add("+");
operators.add("-");
operators.add("*");
operators.add("/");
for(String str : tokens) {
if(!operators.contains(str)) {
stack.push(Integer.valueOf(str));
} else {
int num1 = stack.pop();
int num2 = stack.pop();
int result = 0;
if(str.equals("+")) {
result = num2 + num1;
} else if(str.equals("-")) {
result = num2 - num1;
} else if(str.equals("*")) {
result = num2 * num1;
} else {
result = num2 / num1;
}
stack.push(result);
}
}
return stack.pop();
}
}
|
Tips
HashSet数据结构的contains()操作平均时间复杂度为O(1).
LinkedList 的 push 和 pop 操作时间复杂度为 O(1)，因为它们只涉及在列表头部添加或移除元素
Set 本身具有防止重复的特性，即使重复添加同一个运算符（如 +、-、*、/），集合中也只会保留一个实例。尽管在这个场景中并不特别关键，但这种特性在处理独特元素时非常有用.
link：239. 滑动窗口最大值 - 力扣（LeetCode）
思路分析
看到题目hard不要着急，尝试分析，最开始接触的滑动窗口也是用双端队列【Deque（双端队列）在 Java 中的典型实现是基于循环数组或双向链表】实现（不用暴力是因为时间复杂度肉眼可见的高）那么在这里是否也可以用呢？
根据样例分析发现规律：假设数组nums长度为n，那么滑动窗口的移动次数【也可以叫做移动范围吧】为n-k+1，所以我们结果集res的长度就是n-k+1.
最后就是同样的思路进行筛选比较遍历得到结果.
注意 deque 中存储的是数组 nums 的索引
ArrayDeque 使用一个动态循环数组来存储元素，通过动态调整数组大小来处理空间需求
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
| class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
ArrayDeque<Integer> deque = new ArrayDeque<>();
int n = nums.length;
int[] res = new int[n - k + 1];
int index = 0;
for(int i = 0; i < n; i++) {
while(!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.poll();
}
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offer(i);
if(i >= k-1) {
res[index++] = nums[deque.peek()];
}
}
return res;
}
}
|
Tips
为什么使用索引而不是直接存值？
使用索引而非直接存值有几个好处：
- 保持对原始数组的引用：存储索引可以在
nums 中轻松访问这些值，无需额外的存储空间。
- 维护窗口的有效性：在滑动窗口中移动时，可以根据索引来判断元素是否超出窗口范围（即
deque.peek() < i - k + 1），这在直接存值的情况下较难实现。
