awesomeface259Nov 02, 20191. C2. E11. Ccode:import java.util.*;import java.io.*;public class matchingTrees {static String match, tree;static char[] matchTree;static char[] bigTree;public static void addMatch(int index, char c) {if (matchTree[index] == ' ') {matchTree[index] = c;} else {if (matchTree[index] < c) {addMatch(index * 2 + 1, c);} else {addMatch(index * 2, c);}}}public static void addBig(int index, char c) {if (bigTree[index] == ' ') {bigTree[index] = c;} else {if (bigTree[index] < c) {addBig(index * 2 + 1, c);} else {addBig(index * 2, c);}}}public static boolean fits(int indexMatch, int indexBig) {if (matchTree[indexMatch] == ' ') return true;if (bigTree[indexBig] == ' ') return false;return fits(indexMatch * 2, indexBig * 2) && fits(indexMatch * 2 + 1, indexBig * 2 + 1);}public static void main(String[] args) throws IOException {BufferedReader in = new BufferedReader(new FileReader("src/matchingTrees"));for (int q = 0; q < 10; q++) {StringTokenizer st = new StringTokenizer(in.readLine());String match = st.nextToken(", "), tree = st.nextToken();matchTree = new char[Math.min((int) (Math.pow(2, match.length() + 1)), 8000000) + 1];bigTree = new char[Math.min((int) (Math.pow(2, tree.length() + 1)), 8000000) + 1];Arrays.fill(matchTree, ' ');Arrays.fill(bigTree, ' ');for (int i = 0; i < match.length(); i++) {addMatch(1, match.charAt(i));}for (int i = 0; i < tree.length(); i++) {addBig(1, tree.charAt(i));}ArrayList<Character> a = new ArrayList<Character>();for (int i = 1; i < bigTree.length; i++) {if (bigTree[i] == ' ') continue;if (fits(1, i)) {a.add(bigTree[i]);}}if (a.size() == 0) {System.out.println("NONE");} else {for (int i = 0; i < a.size() - 1; i++) {System.out.print(a.get(i) + ", ");}System.out.println(a.get(a.size() - 1));}}in.close();}}
chris13888Nov 11, 2019ceca, b = input().split(', ')class Node(): def __init__(self, value): self.value = value self.left = self.right = None def insert(self, value): if value <= self.value: if self.left == None: self.left = Node(value) # print(f'{value} is the left child of {self.value}') else: self.left.insert(value) if value > self.value: if self.right == None: self.right = Node(value) # print(f'{value} is the right child of {self.value}') else: self.right.insert(value) def match(self, other): if self.left == None and self.right == None: return True if other.left == None and self.left != None: return False if other.right == None and self.right != None: return False if self.left == None: return self.right.match(other.right) if self.right == None: return self.left.match(other.left) return self.left.match(other.left) and self.right.match(other.right) def traverse(self): # print(self.value, self.left, self.right) yield self if self.left != None: yield from self.left.traverse() if self.right != None: yield from self.right.traverse()A = Node(a[0])for c in a[1:]: A.insert(c)B = Node(b[0])for c in b[1:]: B.insert(c)for node in B.traverse(): if A.match(node): print(node.value)
1. C
2. E
11. C
code:
import java.util.*;
import java.io.*;
public class matchingTrees {
static String match, tree;
static char[] matchTree;
static char[] bigTree;
public static void addMatch(int index, char c) {
if (matchTree[index] == ' ') {
matchTree[index] = c;
} else {
if (matchTree[index] < c) {
addMatch(index * 2 + 1, c);
} else {
addMatch(index * 2, c);
}
}
}
public static void addBig(int index, char c) {
if (bigTree[index] == ' ') {
bigTree[index] = c;
} else {
if (bigTree[index] < c) {
addBig(index * 2 + 1, c);
} else {
addBig(index * 2, c);
}
}
}
public static boolean fits(int indexMatch, int indexBig) {
if (matchTree[indexMatch] == ' ') return true;
if (bigTree[indexBig] == ' ') return false;
return fits(indexMatch * 2, indexBig * 2) && fits(indexMatch * 2 + 1, indexBig * 2 + 1);
}
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new FileReader("src/matchingTrees"));
for (int q = 0; q < 10; q++) {
StringTokenizer st = new StringTokenizer(in.readLine());
String match = st.nextToken(", "), tree = st.nextToken();
matchTree = new char[Math.min((int) (Math.pow(2, match.length() + 1)), 8000000) + 1];
bigTree = new char[Math.min((int) (Math.pow(2, tree.length() + 1)), 8000000) + 1];
Arrays.fill(matchTree, ' ');
Arrays.fill(bigTree, ' ');
for (int i = 0; i < match.length(); i++) {
addMatch(1, match.charAt(i));
}
for (int i = 0; i < tree.length(); i++) {
addBig(1, tree.charAt(i));
}
ArrayList<Character> a = new ArrayList<Character>();
for (int i = 1; i < bigTree.length; i++) {
if (bigTree[i] == ' ') continue;
if (fits(1, i)) {
a.add(bigTree[i]);
}
}
if (a.size() == 0) {
System.out.println("NONE");
} else {
for (int i = 0; i < a.size() - 1; i++) {
System.out.print(a.get(i) + ", ");
}
System.out.println(a.get(a.size() - 1));
}
}
in.close();
}
}
1)c 2)e 11)c
cec
a, b = input().split(', ')
class Node():
def __init__(self, value):
self.value = value
self.left = self.right = None
def insert(self, value):
if value <= self.value:
if self.left == None:
self.left = Node(value)
# print(f'{value} is the left child of {self.value}')
else:
self.left.insert(value)
if value > self.value:
if self.right == None:
self.right = Node(value)
# print(f'{value} is the right child of {self.value}')
else:
self.right.insert(value)
def match(self, other):
if self.left == None and self.right == None:
return True
if other.left == None and self.left != None:
return False
if other.right == None and self.right != None:
return False
if self.left == None:
return self.right.match(other.right)
if self.right == None:
return self.left.match(other.left)
return self.left.match(other.left) and self.right.match(other.right)
def traverse(self):
# print(self.value, self.left, self.right)
yield self
if self.left != None:
yield from self.left.traverse()
if self.right != None:
yield from self.right.traverse()
A = Node(a[0])
for c in a[1:]:
A.insert(c)
B = Node(b[0])
for c in b[1:]:
B.insert(c)
for node in B.traverse():
if A.match(node):
print(node.value)