牛客网【面试必刷TOP101】~ 04 堆/栈/队列

news/2024/5/20 9:18:07 标签: 堆, 栈, 队列, 算法, 面试

牛客网【面试必刷TOP101】~ 04 堆/栈/队列

文章目录

    • 牛客网【面试必刷TOP101】~ 04 堆/栈/队列
    • @[toc]
      • BM42 用两个栈实现队列(★)
      • BM43 包含min函数的栈(★)
      • BM44 有效括号序列(★)
      • BM45 滑动窗口的最大值(★★★)
      • BM46 最小的K个数(★★)
      • BM47 寻找第K大(★★)
      • BM48 数据流中的中位数(★★)
      • BM49 表达式求值(★★)
        • 逆波兰表达式构造
        • 逆波兰表达式求值

BM42 用两个栈实现队列(★)

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

BM43 包含min函数的栈(★)

public class Solution {
    Stack<Integer> valStack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();
    
    public void push(int node) {
        valStack.push(node);
        if (minStack.isEmpty() || node <= minStack.peek()) {
            minStack.push(node);
        }
    }
    
    public void pop() {
        int val = valStack.pop();
        if (minStack.peek() == val) {
            minStack.pop();
        }
    }
    
    public int top() {
        return valStack.peek();
    }
    
    public int min() {
        return minStack.peek();
    }
}

BM44 有效括号序列(★)

方法一：栈

public 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 (c == ')') {
                    if (stack.isEmpty() || stack.peek() != '(') return false;
                } else if (c == '}') {
                    if (stack.isEmpty() || stack.peek() != '{') return false;
                } else if (c == ']') {
                    if (stack.isEmpty() || stack.peek() != '[') return false;
                }
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}

方法二：栈

public class Solution {
    public boolean isValid (String s) {
        Stack<Character> stack = new Stack<>();
        stack.push('a');
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (c == ')') {
                    if (stack.peek() != '(') return false;
                } else if (c == '}') {
                    if (stack.peek() != '{') return false;
                } else if (c == ']') {
                    if (stack.peek() != '[') return false;
                }
                stack.pop();
            }
        }
        return stack.peek() == 'a';
    }
}

BM45 滑动窗口的最大值(★★★)

方法一：暴力法（100ms）

public class Solution {
    public ArrayList<Integer> maxInWindows (int[] nums, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (nums.length == 0 || size == 0) return res;

        for (int i = 0; i <= nums.length - size; i++) {
            int maxVal = nums[i];
            for (int j = i + 1; j < i + size; j++) {
                maxVal = Math.max(maxVal, nums[j]);
            }
            res.add(maxVal);
        }

        return res;
    } 
}

方法二：优先队列1（212ms）

public class Solution {
    public ArrayList<Integer> maxInWindows (int[] nums, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (nums.length == 0 || size == 0) return res;
        
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>((a, b) -> b - a);

        for (int i = 0; i < nums.length; i++) {
            queue.offer(nums[i]);
            if (queue.size() > size) {
                queue.remove(nums[i - size]);
            }
            if (queue.size() == size) {
                res.add(queue.peek());
            }
        }

        return res; 
    }
}

方法三：优先队列2（214ms）

public class Solution {
    public ArrayList<Integer> maxInWindows (int[] nums, int size) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (nums.length == 0 || size == 0 || nums.length < size) return res;
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> {
            return a[0] == b[0] ? b[1] - a[1] : b[0] - a[0];
        });

        for (int i = 0; i < size; i++) pq.offer(new int[]{nums[i], i});
        res.add(pq.peek()[0]);

        for (int i = size; i < n; i++) {
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - size) pq.poll();
            res.add(pq.peek()[0]);
        }

        return res;
    }
}

方法四：单调队列（100ms）

public class Solution {
    public ArrayList<Integer> maxInWindows (int[] nums, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (nums.length == 0 || size == 0 || nums.length < size) return res;

        Deque<Integer> queue = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            while (!queue.isEmpty() && nums[i] > queue.peekLast()) {
                queue.pollLast();
            }
            queue.offerLast(nums[i]);
        }
        res.add(queue.peekFirst());

        for (int i = size; i < nums.length; i++) {
            if (nums[i - size] == queue.peekFirst()) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && nums[i] > queue.peekLast()) {
                queue.pollLast();
            }
            queue.offerLast(nums[i]);
            res.add(queue.peekFirst());
        }

        return res;
    }
}

BM46 最小的K个数(★★)

方法一：库函数排序（29ms）

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        Arrays.sort(input);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) res.add(input[i]);
        return res;
    }
}

方法二：选择排序（36ms）

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < input.length - 1; i++) {
            int x = i;
            for (int j = i + 1; j < input.length; j++) {
                if (input[j] < input[x]) x = j;
            }
            int temp = input[i];
            input[i] = input[x];
            input[x] = temp;
        }
        for (int i = 0; i < k; i++) res.add(input[i]);
        return res;
    }
}

方法三：堆排序/优先队列（33ms）

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (int x : input) queue.offer(x);
        ArrayList<Integer> res = new ArrayList<>();
        while (k-- > 0) res.add(queue.poll());
        return res;
    }
}

方法四：大根堆（131ms）

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        if (input == null || k == 0) return new ArrayList<Integer>();
        Queue<Integer> queue = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int x : input) {
            if (queue.size() < k) {
                queue.offer(x);
            } else if (x < queue.peek()) {
                queue.poll();
                queue.offer(x);
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) res.add(queue.poll());
        return res;
    }
}

方法五：快速排序（25ms）

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        if (input.length == 0 || k == 0) return new ArrayList<Integer>();
        int t = quickSearch(input, 0, input.length - 1, k - 1);
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i++) res.add(input[i]);
        return res;
    }

    private int quickSearch(int[] nums, int le, int ri, int k) {
        int j = partition(nums, le, ri);
        if (j == k) return j;
        return j > k ? quickSearch(nums, le, j - 1, k) : quickSearch(nums, j + 1, ri,
                k);
    }

    private int partition(int[] nums, int le, int ri) {
        int v = nums[le];
        int i = le, j = ri + 1;
        while (true) {
            while (++i <= ri && nums[i] < v);
            while (--j >= le && nums[j] > v);
            if (i >= j) break;
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        nums[le] = nums[j];
        nums[j] = v;
        return j;
    }
}

BM47 寻找第K大(★★)

快速排序思想（23ms）

注意第k大和第k小

public class Solution {
    public int findKth (int[] a, int n, int K) {
        quickSearch(a, 0, n - 1, K - 1);
        return a[K - 1];
    }

    private void quickSearch(int[] a, int le, int ri, int k) {
        int j = partition(a, le, ri);
        if (j == k) return;
        if (j > k) {
            quickSearch(a, le, j - 1, k);
        } else {
            quickSearch(a, j + 1, ri, k);
        }
    }

    private int partition(int[] a, int le, int ri) {
        int v = a[le];
        int i = le, j = ri + 1;

        while (true) {
            while (++i <= ri && a[i] > v);
            while (--j >= le && a[j] < v);
            if (i >= j) break;
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
        a[le] = a[j];
        a[j]  = v;

        return j;
    }

}

BM48 数据流中的中位数(★★)

小根堆+大根堆（321ms）

public class Solution {
    Queue<Integer> qa = new PriorityQueue<Integer>((a, b) -> a - b);
    Queue<Integer> qb = new PriorityQueue<Integer>((a, b) -> b - a);

    public void Insert(Integer num) {
        qa.offer(num);
        while (!qb.isEmpty() && qb.peek() > qa.peek()) {
            qa.offer(qb.poll());
        }
        int sz = (qa.size() + qb.size() + 1) / 2;
        while (qb.size() < sz) {
            qb.offer(qa.poll());
        }
    }

    public Double GetMedian() {
        if (qa.size() < qb.size()) {
            return (double)qb.peek();
        } else {
            return (double)(qb.peek() + qa.peek()) / 2.0;
        }
    }

}

BM49 表达式求值(★★)

逆波兰表达式（Reverse Polish notation）

将表达式求值拆分为：逆波兰表达式构造+逆波兰表达式求值

逆波兰表达式构造

平常的表达式如A+B*(C+D)+E/F为中缀表达式，对应的后缀表达式为ABCD+*+EF/+

参考博客：逆波兰表达式（后缀表达式）

class Solution {

    private class Operator {
        char sign;
        int lever; // + - * / ( 对应的优先级 1 1 2 2 0
        public Operator(char sign, int lever) {
            this.sign = sign;
            this.lever = lever;
        }
    }

    public ArrayList<String> getRPN(String str) {
        ArrayList<String> resultList = new ArrayList<>();
        Stack<Operator> operatorStack = new Stack<>();
        StringBuffer number = new StringBuffer();

        for (char c : str.toCharArray()) {
            if (!isOperator(c)) {
                number.append(c);
                continue;
            }

            if (number.length() > 0) {
                resultList.add(number.toString());
                number.setLength(0);
            }

            switch(c) {
                case '+': stackHelper(resultList, operatorStack, '+', 1); break;
                case '-': stackHelper(resultList, operatorStack, '-', 1); break;
                case '*': stackHelper(resultList, operatorStack, '*', 2); break;
                case '/': stackHelper(resultList, operatorStack, '/', 2); break;
                case '(': operatorStack.push(new Operator('(', 0)); break;
                default:
                    while (!operatorStack.isEmpty() && operatorStack.peek().lever != 0) {
                        resultList.add(operatorStack.pop().sign + "");
                    }
                    if (!operatorStack.isEmpty() && operatorStack.peek().lever == 0) {
                        operatorStack.pop();
                    }
                    break;
            }
        }

        if (number.length() > 0) {
            resultList.add(number.toString());
        }
        while (!operatorStack.isEmpty()) {
            resultList.add(operatorStack.pop().sign + "");
        }

        return resultList;
    }

    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
    }

    private void stackHelper(ArrayList<String> list, Stack<Operator> st, char c, int lever) {
        while (!st.isEmpty() && st.peek().lever >= lever) {
            list.add(st.pop().sign + "");
        }
        st.push(new Operator(c, lever));
    }

}

测试代码：

public class MySolution {
    public static void main(String[] args) {
        Solution so = new Solution();
        String str = "A+B*(C+D)+E/F";
        ArrayList<String> res = so.getRPN(str);
        for (String s : res) {
            System.out.print(s);
        }
      	// ABCD+*+EF/+
    }
}

逆波兰表达式求值

力扣链接：150. 逆波兰表达式求值

输入：tokens = ["2","1","+","3","*"] 输出：9

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        Set<String> set = new HashSet<String>();
        set.add("+");
        set.add("-");
        set.add("*");
        set.add("/");
        for (String token : tokens) {
            if (!set.contains(token)) {
                stack.push(Integer.valueOf(token));
            } else {
                int op2 = stack.pop();
                int op1 = stack.pop();
                if (token.equals("+")) {
                    stack.push(op1 + op2);
                } else if (token.equals("-")) {
                    stack.push(op1 - op2);
                } else if (token.equals("*")) {
                    stack.push(op1 * op2);
                } else {
                    stack.push(op1 / op2);
                }
            }
        }
        return stack.pop();
    }
}

方法整合（Accept）

import java.util.*;


public class Solution {

    public int solve (String s) {
        ArrayList<String> tokens = getRPN(s);
        int result = evalRPN(tokens);
        return result;
    }

    private class Operator {
        char sign;
        int lever; // + - * / ( 对应的优先级 1 1 2 2 0

        public Operator(char sign, int lever) {
            this.sign = sign;
            this.lever = lever;
        }
    }

    public ArrayList<String> getRPN(String str) {
        ArrayList<String> resultList = new ArrayList<>();
        Stack<Operator> operatorStack = new Stack<>();
        StringBuffer number = new StringBuffer();

        for (char c : str.toCharArray()) {
            if (!isOperator(c)) {
                number.append(c);
                continue;
            }

            if (number.length() > 0) {
                resultList.add(number.toString());
                number.setLength(0);
            }

            switch (c) {
                case '+':
                    stackHelper(resultList, operatorStack, '+', 1);
                    break;
                case '-':
                    stackHelper(resultList, operatorStack, '-', 1);
                    break;
                case '*':
                    stackHelper(resultList, operatorStack, '*', 2);
                    break;
                case '/':
                    stackHelper(resultList, operatorStack, '/', 2);
                    break;
                case '(':
                    operatorStack.push(new Operator('(', 0));
                    break;
                default:
                    while (!operatorStack.isEmpty() && operatorStack.peek().lever != 0) {
                        resultList.add(operatorStack.pop().sign + "");
                    }
                    if (!operatorStack.isEmpty() && operatorStack.peek().lever == 0) {
                        operatorStack.pop();
                    }
                    break;
            }
        }

        if (number.length() > 0) {
            resultList.add(number.toString());
        }
        while (!operatorStack.isEmpty()) {
            resultList.add(operatorStack.pop().sign + "");
        }

        return resultList;
    }

    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
    }

    private void stackHelper(ArrayList<String> list, Stack<Operator> st, char c,
                             int lever) {
        while (!st.isEmpty() && st.peek().lever >= lever) {
            list.add(st.pop().sign + "");
        }
        st.push(new Operator(c, lever));
    }

    private int evalRPN(ArrayList<String> tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        Set<String> set = new HashSet<String>();
        set.add("+");
        set.add("-");
        set.add("*");
        set.add("/");
        for (String token : tokens) {
            if (!set.contains(token)) {
                stack.push(Integer.valueOf(token));
            } else {
                int op2 = stack.pop();
                int op1 = stack.pop();
                if (token.equals("+")) {
                    stack.push(op1 + op2);
                } else if (token.equals("-")) {
                    stack.push(op1 - op2);
                } else if (token.equals("*")) {
                    stack.push(op1 * op2);
                } else {
                    stack.push(op1 / op2);
                }
            }
        }
        return stack.pop();
    }

}

http://www.niftyadmin.cn/n/4925605.html

相关文章

【从零学习python 】08.Python了解位运算符, 运算符优先级

【从零学习python 】08.Python了解位运算符, 运算符优先级

文章目录 位运算符&#xff08;了解&#xff09;练习 运算符优先级练习 总结&#xff1a;进阶案例 位运算符&#xff08;了解&#xff09; 按位运算符是把数字看作是二进制来进行计算的。 下表中变量 a 为 60&#xff0c;b 为 13&#xff0c;二进制格式如下&#xff1a; a 0…
阅读更多...
P1489 猫狗大战

P1489 猫狗大战

题目描述 新一年度的猫狗大战通过 SC&#xff08;星际争霸&#xff09;这款经典的游戏来较量&#xff0c;野猫和飞狗这对冤家为此已经准备好久了&#xff0c;为了使战争更有难度和戏剧性&#xff0c;双方约定只能选择 Terran&#xff08;人族&#xff09;并且只能造机枪兵。 …
阅读更多...
【LeetCode每日一题】——575.分糖果

【LeetCode每日一题】——575.分糖果

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 哈希表 二【题目难度】 简单 三【题目编号】 575.分糖果 四【题目描述】 Alice 有 n 枚糖&…
阅读更多...
[GIN-debug] [ERROR] listen tcp: address 8080: missing port in address

[GIN-debug] [ERROR] listen tcp: address 8080: missing port in address

学习Golang_gin框架的第一天 遇到一下报错 : [GIN-debug] [ERROR] listen tcp: address 8080: missing port in address 错误代码 : package mainimport "github.com/gin-gonic/gin"func main() {router : gin.Default()router.GET("/index", func…
阅读更多...
CANoe通过Frame Histogram窗口统计报文周期（方便快捷）

CANoe通过Frame Histogram窗口统计报文周期（方便快捷）

文章目录 效果展示1.插入Frame Histogram窗口2.Activate3.运行CANoe&#xff0c;停止后查看write窗口 效果展示 统计报文周期信息输出在write窗口。 1.插入Frame Histogram窗口 2.Activate 3.运行CANoe&#xff0c;停止后查看write窗口 统计报文周期信息输出在write窗口。
阅读更多...
flutter开发实战-实现marquee根据文本长度显示文本跑马灯效果

flutter开发实战-实现marquee根据文本长度显示文本跑马灯效果

flutter开发实战-实现marquee文本跑马灯效果 最近开发过程中需要marquee文本跑马灯效果&#xff0c;这里使用到了flutter的插件marquee 效果图如下 一、marquee 1.1 引入marquee 在pubspec.yaml中引入marquee # 跑马灯效果marquee: ^2.2.31.2 marquee使用 marquee使用也是…
阅读更多...
如何将NAS空间变为本地磁盘，并拥有与实体硬盘所有常用功能

如何将NAS空间变为本地磁盘，并拥有与实体硬盘所有常用功能

1.前言 作为一个垃圾佬&#xff0c;用自己的双路E5板子&#xff0c;加持PCIE拆分&#xff0c;4块PM983A齐上阵&#xff0c;气势可嘉。作为一个家庭NAS&#xff0c;如果仅仅用他当作一个普通的存储区存储数据那未免太过于浪费了&#xff1b;另一边&#xff0c;由于工作机硬盘太…
阅读更多...
PROFIBUS-DP主站转ETHERCAT网关连接西门子支持ethercat吗

PROFIBUS-DP主站转ETHERCAT网关连接西门子支持ethercat吗

大家好&#xff0c;今天要给大家介绍一款捷米的神秘产品&#xff0c;它的名字叫JM-DPM-ECT&#xff0c;是一款兼具PROFIBUS-DP主站功能的通讯网关。想象一下&#xff0c;它既能和PROFIBUS总线打交道&#xff0c;又能与ETHERCAT网络愉快地交流&#xff0c;是不是感觉很神奇&…
阅读更多...
最新文章

Copyright @ 2022~2023