第一題150. 逆波蘭運算式求值
根據 逆波蘭表示法，求運算式的值，
有效的算符包括 +、-、*、/ ，每個運算物件可以是整數，也可以是另一個逆波蘭運算式，
注意 兩個整數之間的除法只保留整數部分，
可以保證給定的逆波蘭運算式總是有效的，換句話說，運算式總會得出有效數值且不存在除數為 0 的情況，
ψ(｀?′)ψ 我的思路
- 題目上提示的已經很清晰了
去掉括號后運算式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據次序計算出正確結果，
適合用堆疊操作運算：遇到數字則入堆疊；遇到算符則取出堆疊頂兩個數字進行計算，并將結果壓入堆疊中
package stackandqueue;
import java.util.Stack;
public class EvalRPN {
public int evalRPN(String[] tokens) {
int m,n;
Stack<String> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
//如果是運算子的話，取出堆疊頂的兩個元素，和運算子計算，結果入堆疊
if(tokens[i].equals("+")){
stack.push(String.valueOf(Integer.parseInt(stack.pop())+Integer.parseInt(stack.pop())));
} else if (tokens[i].equals("-")) {
m = Integer.parseInt(stack.pop());
n = Integer.parseInt(stack.pop());
stack.push(String.valueOf(n-m));
} else if (tokens[i].equals("*")) {
stack.push(String.valueOf(Integer.parseInt(stack.pop())*Integer.parseInt(stack.pop())));
}else if (tokens[i].equals("/")) {
m = Integer.parseInt(stack.pop());
n = Integer.parseInt(stack.pop());
stack.push(String.valueOf(n/m));
} else {
stack.push(tokens[i]);//如果不是運算子的話，入堆疊
}
}
return Integer.parseInt(stack.pop());
}
}
時間復雜度O(n)
- 在力扣上debug也太方便了吧??
第二題239. 滑動視窗最大值
給你一個整數陣列 nums，有一個大小為 k 的滑動視窗從陣列的最左側移動到陣列的最右側，你只可以看到在滑動視窗內的 k 個數字，滑動視窗每次只向右移動一位，
回傳 滑動視窗中的最大值
ψ(｀?′)ψ 我的思路
- 暴力暴力！一個for回圈確定滑動視窗的位置，另一個for回圈確定滑動視窗內的最大值
package stackandqueue;
public class MaxSlidingWindow {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length==1){
return nums;
}
int[] res = new int[nums.length - k + 1];//結果陣列
for (int i = 0; i < nums.length - k + 1; i++) {
// 確定滑動視窗的位置[i,i+k-1]
int x = Integer.MIN_VALUE;
for (int j = i; j < i + k; j++) {
// 遍歷滑動視窗內的值，尋找最大值
x = nums[j] > x ? nums[j] : x;
}
res[i] = x;
}
return res;
}
}
時間復雜度O(n^2)
- 然后就，，，超時了??
- 就很乖的去看了正經解法??
package stackandqueue;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
public class MaxSlidingWindow2 {
static Deque<Integer> que = new LinkedList<>();
public static int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < k; i++) {
push(nums[i]);
}
res[0] = getMax();
for (int i = 1; i < nums.length - k + 1; i++) {
pop(nums[i-1]);//彈出元素
push(nums[i + k-1]);//加入元素
res[i] = getMax();//取最大值
}
return res;
}
public static void pop(int x) {
if (!que.isEmpty() && que.peek() == x) {
//如果佇列不為空，并且佇列出口的值=要彈出的值
que.pop();
}
}
public static void push(int x) {
while (!que.isEmpty()&&x>que.getLast()){
que.removeLast();//當佇列不空且要加入的元素大于佇列最后一個元素時，把最后的元素去掉（保證佇列倒序）
}
que.addLast(x);//在把元素追加至隊尾
}
public static int getMax() {
// 最大值一直是佇列出口的元素
return (int) que.getFirst();
}
public static void main(String[] args) {
int[] ints = maxSlidingWindow(new int[]{1,3,1,2,0,5}, 3);
for (int i = 0; i < ints.length; i++) {
System.out.println(ints[i]);
}
}
}
時間復雜度O(n)
- 盡管聽了思路，實作起來還是有點復雜的，關鍵是push的時候要從隊尾把元素移除，再加入元素，這樣可以保證佇列里的元素倒序，
- 我對佇列是真的不熟悉啊，佇列的實作類竟然是LinkedList，虧我還用ArrayDeque做了好一會兒??
第三題347.前 K 個高頻元素
給你一個整數陣列 nums 和一個整數 k ，請你回傳其中出現頻率前 k 高的元素，你可以按 任意順序 回傳答案，
ψ(｀?′)ψ 我的思路
- 這題我想著是用map，出現的次數為key，出現的元素為value，for回圈一次遍歷將陣列存入map，對key排序，取前k個回傳其value，今天不太舒服就不寫了，直接看代碼隨想錄的新方法，
package stackandqueue;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class TopKFrequent {
public int[] topKFrequent(int[] nums, int k) {
// 先把陣列中的元素裝入map
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (!map.containsKey(nums[i])) {
map.put(nums[i], 1);
} else {
map.put(nums[i],map.get(nums[i])+1);
}
}
PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2)->pair1[1]-pair2[1]);
for(Map.Entry<Integer,Integer> entry:map.entrySet()){//小頂堆只需要維持k個元素有序
if(pq.size()<k){//小頂堆元素個數小于k個時直接加
pq.add(new int[]{entry.getKey(),entry.getValue()});
}else{
if(entry.getValue()>pq.peek()[1]){//當前元素出現次數大于小頂堆的根結點(這k個元素中出現次數最少的那個)
pq.poll();//彈出隊頭(小頂堆的根結點),即把堆里出現次數最少的那個洗掉,留下的就是出現次數多的了
pq.add(new int[]{entry.getKey(),entry.getValue()});
}
}
}
int[] ans = new int[k];
for(int i=k-1;i>=0;i--){//依次彈出小頂堆,先彈出的是堆的根,出現次數少,后面彈出的出現次數多
ans[i] = pq.poll()[0];
}
return ans;
}
}
- 思路聽了下，但并不是很理解PriorityQueue這個東西，感覺我對佇列的理解還是差點兒
總結
- 基本可以用堆疊來解題，但是佇列我還是沒有完全弄明白，大頂堆小頂堆也只是懂一點兒，先欠下來，等6號，7號的時候再做個總結，
- 今天終于做到了一道困難題，還是很開心的，期待二叉樹
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/510920.html
標籤：其他
上一篇：國慶假期一點點記錄