Flatten Binary Tree to Linked List && Generate Parentheses && Gray Code
5176 단어 binary
/**
* 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, 앞으로 주의해야 돼요...
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
이진 트리의 경계 순회은 중복 노드 없이 왼쪽 경계, 잎, 오른쪽 경계를 포함하지만 노드의 값은 중복을 포함할 수 있습니다. 루트 노드에 왼쪽 및 오른쪽 하위 트리가 포함되어 있지 않으면 루트 노드 자체가 왼쪽 경계 또는 오른쪽 경계로 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.