기술나눔

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

안녕하세요 여러분, 이번 블로그는 여름방학 동안의 학습체크를 기록하는 것이 목적이며, 추후에 칼럼으로 정리하여 여름방학 동안 자료구조에 대한 학습을 ​​마치도록 하겠습니다. 데이터 구조 구현에 대한 관련 블로그를 게시하고 개인 학습 및 활용을 위해 부족한 점을 지적해 주시기 바랍니다.

1. Likou 115, 가장 작은 스택

. - LeetCode

단순히 배열을 사용하여 스택을 시뮬레이션하지만 여기서는 문제를 해결하려고 노력하고 있으며 실행 속도가 그다지 높지 않으며 최적화할 여지가 많습니다.

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. 양희삼각형

. - LeetCode

분석: 앞서 배운 시퀀스 테이블을 사용하기 위해 시퀀스 테이블을 사용하여 2차원 배열을 시뮬레이션합니다.시퀀스 테이블에 의해 시뮬레이션된 2차원 배열은 단순히 첨자를 통해 요소에 액세스할 수 없습니다.

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

셋, 150을 누르고 역 폴란드어 표현을 평가해 보세요

참고: 폴란드어 표현은 컴퓨터가 이해할 수 있는 표현입니다.

. - LeetCode

아이디어: 배열을 탐색하고 먼저 문자열이 숫자인지 확인합니다.숫자이면 숫자로 변환되어 스택에 푸시됩니다. 그렇지 않으면 두 개의 피연산자를 제거하고 "+", "-", "*" 또는 "/" 다음의 피연산자를 제거합니다. 연산자가 사용됩니다., 스택에 남은 것이 최종 답입니다

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

이 블로그는 여기까지입니다. 모두 감사합니다