Condivisione della tecnologia

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

Ciao a tutti, lo scopo di questo blog è registrare il check-in di studio durante le vacanze estive. Successivamente verrà organizzato in una rubrica. L'intenzione principale è completare lo studio delle strutture dati durante le vacanze estive. Pertanto, lo farò pubblica alcuni blog correlati sull'implementazione della struttura dei dati e alcuni quiz per lo studio e l'uso personale. Spero anche che tu possa supportarmi molto. Per favore segnala eventuali carenze.

1. Likou 115, lo stack più piccolo

.-LeetCodice

Usa semplicemente un array per simulare uno stack, ma qui sto cercando di evitare problemi e la velocità di esecuzione non è molto elevata e c'è molto spazio per l'ottimizzazione.

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. Triangolo Yang Hui

.-LeetCodice

Analisi: per utilizzare la tabella di sequenza che abbiamo imparato in precedenza, utilizziamo la tabella di sequenza per risolvere questo problema. Utilizzare la tabella di sequenza per simulare un array bidimensionaleL'array bidimensionale simulato dalla tabella di sequenza non può accedere semplicemente agli elementi tramite pedici.

 
        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;
    }
}
 

Tre, premi 150, valuta l'espressione polacca inversa

Nota: l'espressione polacca è un'espressione comprensibile dai computer

.-LeetCodice

Idea: attraversare l'array, determinare prima se la stringa è un numero,Se è un numero, viene convertito in un numero e inserito nello stack. Altrimenti, vengono eliminati due operandi e quello dopo "+", "-", "*" o "/" viene eliminato dopo. viene utilizzato l'operatore, ciò che rimane in pila è la risposta finale

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;
        }
    }
 

Per questo blog è tutto, grazie a tutti