Partage de technologie

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

Bonjour à tous, le but de ce blog est d'enregistrer l'enregistrement de l'étude pendant les vacances d'été. Il sera organisé en colonne plus tard. L'intention principale est de terminer l'étude des structures de données pendant les vacances d'été. publiez des blogs sur la mise en œuvre de la structure de données et des quiz pour une étude et une utilisation personnelles. J'espère également que vous pourrez beaucoup me soutenir. Merci à tous.

1. Likou 115, le plus petit stack

.-LeetCode

Utilisez simplement un tableau pour simuler une pile, mais ici j'essaie d'éviter les problèmes et la vitesse d'exécution n'est pas très élevée et il y a beaucoup de place pour l'optimisation.

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. Le triangle Yang Hui

.-LeetCode

Analyse : Afin d'utiliser la table de séquence que nous avons apprise plus tôt, nous utilisons la table de séquence pour résoudre ce problème. Utilisez la table de séquence pour simuler un tableau à deux dimensions.Le tableau bidimensionnel simulé par la table de séquence ne peut pas simplement accéder aux éléments via des indices.

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

Troisièmement, appuyez sur 150, évaluez l'expression polonaise inversée

Remarque : l'expression polonaise est une expression qui peut être comprise par les ordinateurs.

.-LeetCode

Idée : parcourez le tableau, déterminez d'abord si la chaîne est un nombre,S'il s'agit d'un nombre, il est converti en nombre et placé sur la pile. Sinon, deux opérandes sont retirés, et celui après "+", "-", "*" ou "/" est retiré après le l’opérateur est utilisé., ce qui reste sur la pile est la réponse 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;
        }
    }
 

Voilà pour ce blog, merci à tous