Johnny
BAN USERpublic String valueOf(int num) {
String signed = "";
if (num < 0) {
signed = "-";
}
return signed + numToString(Math.abs(num));
}
String numToString(int num) {
if (num == 0) {
return "0";
}
String result = "";
while (num > 0) {
result = ((char) num % 10) + result;
num = num / 10;
}
return result;
}
def shuffle_without_dup(s):
d = {}
for c in s:
d[c] = d[c] + 1 if c in d else 1
check = max(d.values())
return check * 2 - 2 < len(s)
assert shuffle_without_dup('apple')
assert shuffle_without_dup('a')
assert not shuffle_without_dup('aa')
assert shuffle_without_dup('aab')
assert shuffle_without_dup('aaaabbcc')
class Tree:
def __init__(self, data, children=[]):
self.data = data
self.children = children
def max_path(tree):
d_node = {}
max_val = max_path_helper(tree, d_node, {}, set())
return find_path(tree, d_node), max_val
def max_path_helper(tree, d_node, d_val, done):
if tree == None:
return 0
if (tree not in done):
best_next = None
best_val = 0
for child in tree.children:
val = max_path_helper(child, d_node, d_val, done)
if val > best_val:
best_val = val
best_next = child
d_node[tree] = best_next
d_val[tree] = tree.data + best_val
done.add(tree)
return d_val[tree]
def find_path(tree, d):
path = []
curr = tree
while curr in d:
path.append(curr.data)
curr = d[curr]
return path
# Quick test
second_eight = Tree(8)
five = Tree(5)
first_eight = Tree(8)
first_eight.children = [five, second_eight]
two = Tree(2)
two.children = [second_eight, Tree(2)]
dag = Tree(3, \
[Tree(9, \
[Tree(1, \
[Tree(4), Tree(5)]), \
first_eight]), \
Tree(4, \
[first_eight, \
two])])
print(max_path(dag))
class Tree:
def __init__(data, children = []):
this.data = data
this.child = children
def pair_tree(root, x, y):
if root:
stack = [root]
while (stack is not []):
next_stack = []
found_x, found_y = False, False
for node in stack:
new_stack += node.children
found_x = node.x == x or found_x
found_y = node.y == y or found_y
if (found_x and found_y):
return True
stack = new_stack
return False
def merge(lst1, lst2):
if len(lst1) == 0:
return lst2
if len(lst2) == 0:
return lst1
if (lst1[0] > lst2[0]):
return [lst2[0]] + merge(lst1, lst2[1:])
return [lst1[0]] + merge(lst1[1:], lst2)
def mergesort(lst):
if len(lst) <= 1:
return lst
middle = len(lst)/2
return merge(mergesort(lst[:middle]), mergesort(lst[middle:]))
def sort_2d_matrix(matrix):
lst = []
for row in matrix:
lst += row
sorted_lst = mergesort(lst)
col_len = len(matrix[0])
for i in range(len(matrix)):
for j in range(col_len):
matrix[i][j] = sorted_lst[i+j*col_len]
matrix = [[4, 4, 6, 2], [1, 2, 9, 5], [0, 8, 7, 3], [2, 3, 5, 4], [1, 2, 8, 6]]
sort_2d_matrix(matrix)
for i in range(len(matrix)):
print(matrix[i])
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def min_two_node_diff(tree):
if tree == None:
return float("inf")
compare_with_left, compare_with_right = float("inf"), float("inf")
if tree.left:
compare_with_left = tree.val - right_most_val(tree.left)
if tree.right:
compare_with_right = left_most_val(tree.right) - tree.val
return min(compare_with_left, \
compare_with_right, \
min_two_node_diff(tree.left), \
min_two_node_diff(tree.right))
def right_most_val(tree):
if (tree.right == None):
return tree.val
return right_most_val(tree.right)
def left_most_val(tree):
if (tree.left == None):
return tree.val
return left_most_val(tree.left)
bst = Node(10, Node(5), Node(16, Node(12), Node(20)))
print(min_two_node_diff(bst))
- Johnny March 19, 2016