montu
BAN USERclass Node:
def __init__(self, val):
self.left = None
self.right = None
self.val = val
def replace_with_greater(root, sum_val):
if not root:
return sum_val
val = root.val
sum_val = replace_with_greater(root.right, sum_val)
root.val = max(root.val, sum_val)
sum_val += val
sum_val = replace_with_greater(root.left, sum_val)
return sum_val
def move_between_poles(pole1, pole2):
if not pole1 and not pole2:
return
if not pole1 or (pole1 and pole2 and pole1[-1] > pole2[-1]):
pole1.append(pole2.pop())
elif not pole2 or (pole1 and pole2 and pole1[-1] < pole2[-1]):
pole2.append(pole1.pop())
def toh_iter(n, source, target, aux):
moves = pow(2, n)
if not n%2:
aux,target = target,aux
for i in range(1,moves):
if i % 3 is 1:
move_between_poles(target, source)
if i % 3 is 2:
move_between_poles(aux, source)
if i % 3 is 0:
move_between_poles(target, aux)
def main():
source = [4,3,2,1]
aux = []
target = []
n = len(source)
toh_iter(n, source, target, aux)
print target
Missed out few points from qn. Corrected in this upload
def step_num_count(n1, n2, num):
count = 0
q = []
q.append(num)
while q:
step_num = q.pop(0)
if step_num >= n1 and step_num <= n2 and (step_num/10):
count += 1
if step_num is 0 or step_num > n2:
continue
last_digit = step_num % 10
step_num1 = (step_num * 10) + last_digit + 1
step_num2 = (step_num * 10) + last_digit - 1
if last_digit is 0:
q.append(step_num1)
elif last_digit is 9:
q.append(step_num2)
else:
q.append(step_num1)
q.append(step_num2)
return count
def main():
count = 0
n1 = input("Enter value of n1:")
n2 = input("Enter value of n2:")
for i in range(10):
count += step_num_count(n1, n2, i)
print "Total stepping num :",count
main()
def step_num_count(n, m, num):
count = 0
q = []
q.append(num)
while q:
step_num = q.pop(0)
if step_num >= n and step_num <= m and (step_num/10):
count += 1
if step_num is 0 or step_num > m:
continue
last_digit = step_num % 10
step_num1 = (step_num * 10) + last_digit + 1
step_num2 = (step_num * 10) + last_digit - 1
if last_digit is 0:
q.append(step_num1)
elif last_digit is 9:
q.append(step_num2)
else:
q.append(step_num1)
q.append(step_num2)
return count
def main():
count = 0
n = 0
m = 21
for i in range(10):
count += step_num_count(n, m, i)
print "Total stepping num :",count
main()
class Stack:
def __init__(self):
self.elements = []
def push(self, elem):
self.elements.append(elem)
def pop(self):
return self.elements.pop()
def top(self):
if self.elements:
return self.elements[-1]
else:
print "stack empty"
def insert_indorder(self, elem):
if not self.elements or self.top() < elem:
self.push(elem)
else:
top_elem = self.pop()
self.insert_indorder(elem)
self.push(top_elem)
def sort_stack(self):
if not self.elements:
return
top_elem = self.pop()
self.sort_stack()
self.insert_indorder(top_elem)
def print_stack(self):
for i in self.elements:
print i,
def main():
stack = Stack()
stack.push(3)
stack.push(8)
stack.push(6)
stack.push(1)
stack.push(10)
stack.push(9)
stack.push(0)
stack.sort_stack()
stack.print_stack()
main()
from collections import defaultdict
class AdjNode:
def __init__(self, vertex, weight):
self.v = vertex
self.weight = weight
def get_v(self):
return self.v
def get_weight(self):
return self.weight
class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices
def add_edge(self, u, v, weight):
node = AdjNode(v, weight)
self.graph[u].append(node)
def topological_sort_util(self, v, visited, stack):
visited[v] = 1
for vert in self.graph[v]:
node = vert
if not visited[node.get_v()]:
self.topological_sort_util(node.get_v(), visited, stack)
stack.insert(0, v)
def topological_sort(self):
stack = []
visited = [0] * self.V
for i in range(self.V):
if not visited[i]:
self.topological_sort_util(i, visited, stack)
return stack
def longest_path(self, source):
dist = [-float('inf') if i is not source else 0 for i in range(self.V)]
top_sort = self.topological_sort()
while top_sort:
u = top_sort.pop(0)
if dist[u] != -(float('inf')):
for i in self.graph[u]:
if dist[i.get_v()] < (dist[u] + i.get_weight()):
dist[i.get_v()] = dist[u] + i.get_weight()
print max(dist)
g = Graph(6)
g.add_edge(5, 0, 1)
g.add_edge(5, 2, 1)
g.add_edge(4, 0, 1)
g.add_edge(4, 1, 1)
g.add_edge(3, 1, 1)
g.add_edge(2, 3, 1)
g.longest_path(3)
def minTotalDistance(self, grid):
x = sorted([i for i, row in enumerate(grid) for v in row if v == 1])
y = sorted([j for row in grid for j, v in enumerate(row) if v == 1])
return sum([abs(x[len(x)/2]-i)+abs(y[len(y)/2]-j) for i, row in enumerate(grid) for j, v in enumerate(row) if v == 1])
class Node:
def __init__(self, id, pid):
self.id = id
self.pid = pid
class TreeNode:
def __init__(self, id):
self.id = id
self.children = []
def construct_tree_from_list(node_list):
node_map = {u.pid : [] for u in node_list if u.pid}
for u in node_list:
if u.pid:
node_map[u.pid].append(u.id)
else:
root = u.id
root_node = TreeNode(root)
q = []
q.append(root_node)
while q:
node = q.pop(0)
if node.id in node_map:
node.children = [TreeNode(i) for i in node_map[node.id]]
for j in range(len(node.children)):
q.append(node.children[j])
return root_node
def find_prod(a):
n = len(a)
zero_idx = -1
zero_count = 0
prod = 1
for i in range(n):
if a[i] is 0:
if not zero_count:
zero_idx = i
zero_count += 1
else:
zero_count += 1
prod = 0
else:
prod *= a[i]
if zero_count > 1:
return [0]*n
elif zero_count is 1:
return [prod if i is zero_idx else 0 for i in range(n)]
else:
return [prod/a[i] for i in range(n)]
def find_suba(arr,subarr):
dict = {}
for i in subarr:
dict[i] = []
for i in range(len(arr)):
if arr[i] in dict:
dict[arr[i]].append(i)
for i in range(len(subarr)):
globals()['var%s' % i] = dict[subarr[i]]
diff = [globals()['var%s' % (len(subarr)-1)][i]-var0[i] for i in range(len(var0))]
idx = diff.index(min(diff))
return diff[idx]+1, var0[idx]
- montu April 08, 2017