Flatten Binary Tree to Linked List && Generate Parentheses && Gray Code

5176 단어 binary
Flatten 너무 쉬워요. 한 번 돌려서 oh yeah = = 자랑스러울 것도 없어요.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (root == null)
            return;
        TreeNode left = root.left;
        TreeNode right = root.right;
        flatten(left);
        flatten(right);
        root.left = null;
        root.right = left;
        TreeNode iter = root;
        while (iter.right != null)
            iter = iter.right;
        iter.right = right;
    }
}

괄호라는 문제는 여러 개의 노드가 하나의 숲을 이루고 있다고 볼 수 있는데, 이렇게 생각하면 귀환으로 할 수 있다.그런데 계산량이 너무 많아서 (중복이 너무 많아서) 점차-동계로 했어요.
S(n) = S(0)*S(n-1) + S(1)*S(n-2) + …… + S(n-1)*S(0)
....그 결과 길이를 계산하는 것이 아니라 문자열을 생성하는 것으로 나타났습니다...근데 밀기도 되잖아요.

public class Solution {
    ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
    
    public ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> results = new ArrayList<String>();
        if (n == 0){
            results.add("");
            return results;
        }
            
        if (lists.size() < n){
            ArrayList<String> temp = generateParenthesis(n-1);
            lists.add(temp);
        }
        ArrayList<String> children;
        ArrayList<String> friends;
        for (int i = 0; i < n; ++i){
            children = new ArrayList<String>();
            friends = new ArrayList<String>();
            children.addAll(lists.get(i));
            friends.addAll(lists.get(n-1-i));
            for (int j = 0; j < children.size(); ++j){
                children.set(j, "(" + children.get(j) + ")");
                for (int k = 0; k < friends.size(); ++j)
                    results.add(children.get(j) + friends.get(k));
            }
        }
        return results;
    }
}

왠지 runtime error, 내일 일어나서 알아봐 sigh
for (int k = 0; k < friends.size ();++제이) 마지막에 케이가 제이라고 썼어요.
그리고 리스트를 함수에 넣는 게 좋을 것 같은데?당연히 시험해 봤지. 아래랑 안이랑 밖이랑 다 돼.

import java.util.ArrayList;

public class Solution {    
    public ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<String>> lists = new ArrayList<ArrayList<String>>();
        ArrayList<String> results = new ArrayList<String>();
        if (n == 0){
            results.add("");
            return results;
        }
            
        for (int i = 0; i < n; ++i){
            ArrayList<String> temp = generateParenthesis(i);
            lists.add(temp);
        }
        ArrayList<String> children;
        ArrayList<String> friends;
        for (int i = 0; i < n; ++i){
            children = new ArrayList<String>();
            friends = new ArrayList<String>();
            children.addAll(lists.get(i));
            friends.addAll(lists.get(n-1-i));
            for (int j = 0; j < children.size(); ++j){
                children.set(j, "(" + children.get(j) + ")");
                for (int k = 0; k < friends.size(); ++k)
                    results.add(children.get(j) + friends.get(k));
            }
        }
        return results;
    }
}

그레코드는 높은 위치가 1이 증가하면 낮은 위치가 항상 한 번 뒤집히면 원래의 여러 개의 그레코드를 구성할 수 있는 법칙을 발견했다.

public class Solution {
    public ArrayList<Integer> grayCode(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Integer> results = new ArrayList<Integer>();
        results.add(0);
        if (n == 0)
            return results;
        results.add(1);
        if (n == 1)
            return results;
        for (int i = 2; i <= n; ++i){
            int size = results.size(); 
            int high = 1 << (i-1);
            for (int j = size-1; j >= 0; j--)
                results.add(high + results.get(j));
        }
        return results;
    }
}

그래도 한 번도 안 해봤어요. 또 순환 중 i가 n이라는 오류를 썼어요. sigh, 앞으로 주의해야 돼요...

좋은 웹페이지 즐겨찾기