매주 ARTS 10기

1. Algorithm

226. 두 갈래 나무 뒤집기(간단)

설명:
두 갈래 나무 한 그루를 뒤집다
예:

 ：
 :
    4
  2    7
1  3  6  9
 :
    4
  7    2
9  6  3  1

생각:

귀속법: 두 갈래 나무를 뒤집으면 뿌리 노드의 왼쪽 나무를 뒤집는 것이다. 똑같이 오른쪽 나무를 뒤집고 왼쪽 나무를 교환하면 된다..

교체법: 광도 우선 훑어보는 방식과 유사하게 대기열을 사용하여 아직 교환되지 않은 노드를 저장하고 매번 대기열에서 하나의 결점을 꺼내 좌우 결점을 상호작용한다. 대기열이 비어 있을 때까지..

class Solution {
    public TreeNode invertTreeRecursively(TreeNode root) {
        if (root == null) {
            return null;
        }

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTreeRecursively(root.left);
        invertTreeRecursively(root.right);
        return root;
    }

    public TreeNode invertTreeIteratively(TreeNode root) {
        if (root == null) {
            return null;
        }

        LinkedList list = new LinkedList<>();
        list.add(root);
        while (list.isEmpty()) {
            TreeNode current = list.poll();
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;

            if (current.left != null) {
                list.add(current.left);
            }
            if (current.right != null) {
                list.add(current.right);
            }
        }
        return root;
    }
}

분석:
반복은 반복법과 같습니다.

시간 복잡도: O(n)

공간 복잡도: O(n)

326.3의 멱(간단)

설명:
정수를 정하고 함수를 써서 그것이 3의 멱차방인지 아닌지를 판단한다.
예:

 : 27
 : true

생각:

해법1: 누승법

해법 2:3의 멱차질인자는 3에 불과하고 정수 범위 내의 3의 멱차는 최대 1162261467이다

해법:

class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        long m = 1;
        while (m < n) {
            m *= 3;
            if (m == n) {
                return true;
            }
        }
        return false;
    }

    public boolean isPowerOfThree2(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

분석:
해법 1:

시간 복잡도: O(n)

공간 복잡도: O(1)

해법 2:

시간 복잡도: O(1)

공간 복잡도: O(1)

2. Review

Goodbye, Object Oriented Programming 안녕, 객체 프로그래밍
작가는 다년간의 경험을 가진 베테랑 프로그래머이다. 그는 대상을 대상으로 프로그래밍하는 문제를 가차없이 지적했고 각각 봉인, 계승과 다태라는 세 가지 기둥에서 논술했다.

계승의 가장 큰 장점은 복용이다.하지만'원숭이 바나나 정글'문제가 생겼어요. 바나나 하나만 갖고 싶은데 바나나 정글을 얻었어요.다이아몬드 문제는 계승 관계의 구조도가 다이아몬드와 같아서 호출 혼란을 초래하기 쉽다.그리고 기류 문제, 자류는 기류의 실현을 몰라서 조작 오류를 일으킨다.해결 방법은 상속을 조합으로 대체하는 것이다. 원래 뜻은 포함과 위탁이다

포장은 대상이 내부의 변수를 보호받는 것을 보장하지만 문제를 가져왔다.문제를 인용하여 구조 방법에 참고할 때 대상에 여러 가지 응용이 존재하기 때문에 대상이 안전하지 않다.해결 방법은 객체가 깊이 복제되는 것이지만 모든 객체가 클론을 지원하는 것은 아닙니다

대상을 대상으로 프로그래밍하는 데 다태가 필요 없고 인터페이스를 바탕으로 충분히 실현할 수 있다

마지막으로 저자는 대상 프로그래밍, 전향 함수식 프로그래밍과 작별을 고했다.
저자가 이렇게 많은 OOP 문제를 제기했지만 대상을 향한 사상은 여전히 유행하고 있다.소프트웨어 개발에는 은탄이 없어서 기능을 실현하고 문제를 해결할 수 있다는 사상은 모두 채택할 만하다.

3. Tip

일상의 자질구레한 일들은 모두 소프트웨어로 기록된다. 예를 들어 구름 노트, 똑딱이 리스트, Last Pass가 있다.뇌는 생각하는 것이지, 물건을 기억하는 것이 아니라, 하드디스크가 아니라 CPU 역할을 더 많이 한다.그러니 뇌를 가볍게 하고 도구로 기록하세요.

4. Share

스레드와 I/O 모델에 대한 간단한 지식은 주로 스레드와 I/O 모델의 진화 역사, 문제 구동 모델의 진화, 각 모델은 각자의 사용 장면을 말한다.