Compartir tecnología

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Hola a todos, el propósito de este blog es registrar el registro del estudio durante las vacaciones de verano. Más adelante se organizará en una columna. La intención principal es completar el estudio de las estructuras de datos durante las vacaciones de verano. Publique algunos blogs relacionados sobre la implementación de la estructura de datos y algunos cuestionarios para estudio y uso personal. También espero que puedan apoyarme mucho. Señalen cualquier deficiencia.

1. Likou 115, la pila más pequeña

- LeetCode

Simplemente use una matriz para simular una pila, pero aquí estoy tratando de evitar problemas y la velocidad de ejecución no es muy alta y hay mucho espacio para la optimización.

class MinStack {
 
    int[] el;
    int numsize;
 
    public MinStack() {
        el = new int[10000];
        int numsize = 0;
    }
 
    // private void grow(){
    // this.el=Arrays.copyof(el,2*el.lenth);
    // }
 
    public void push(int val) {
        // if (el.lenth == numsize) {
        // grow();
        // }
        el[numsize] = val;
        numsize++;
    }
 
    public int pop() {
        if (empty())
            return -1;
        return el[--numsize];
    }
 
    public int top() {
        return el[numsize - 1];
 
    }
 
    private boolean empty() {
        return numsize == 0;
    }
 
    public int getMin() {
        int num = el[0];
        for (int i = 0; i < numsize; i++) {
            if (el[i] < num)
                num = el[i];
        }
        return num;
    }
}
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

2. Triángulo Yang Hui

- LeetCode

Análisis: para utilizar la tabla de secuencia que aprendimos anteriormente, usamos la tabla de secuencia para resolver este problema. Utilice la tabla de secuencia para simular una matriz bidimensional.La matriz bidimensional simulada por la tabla de secuencia no puede simplemente acceder a elementos a través de subíndices.

 
        class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret=new ArrayList<>();
        List<Integer> list=new ArrayList<>();
        list.add(1);
        ret.add(list);
        for(int i=1;i<numRows;i++){
            List<Integer> row=new ArrayList<>();
            row.add(1);
            List<Integer> a= ret.get(i-1);
            for (int j = 1; j < i; j++) {
                int val1=a.get(j);
                int val2=a.get(j-1);
                row.add(val1+val2);
            }
            row.add(1);
            ret.add(row);
        }
        return ret;
    }
}
 

Tres, presione 150, evalúe la expresión polaca inversa.

Nota: La expresión polaca es una expresión que las computadoras pueden entender.

- LeetCode

Idea: recorrer la matriz, primero determinar si la cadena es un número,Si es un número, se convierte en un número y se coloca en la pila. De lo contrario, se eliminan dos operandos y el que está después de "+", "-", "*" o "/" se elimina después del. Se utiliza el operador., lo que queda en la pila es la respuesta final

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> st = new Stack();
        for (int i = 0; i < tokens.length; i++) {
            String str = tokens[i];
            if (o(str) == false) {
                int val = Integer.parseInt(str);
                st.push(val);
            } else {
                int val1 = st.pop();
                int val2 = st.pop();
                switch (str) {
                    case "+":
                        st.push(val2+val1);
                        break;
                    case "-":
                        st.push(val2-val1);
                        break;
                        case "*":
                        st.push(val2*val1);
                        break;
                        case "/":
                        st.push(val2/val1);
                        break;
                }
 
            }
        }
        return st.peek();
    }
 
 
 
        private boolean o (String s){
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
 
                return true;
            }
            return false;
        }
    }
 

Eso es todo por este blog, gracias a todos.