Skip to content

Commit c415d1a

Browse files
kumayakumaya
committed
Some additional programs
1 parent 022c5dc commit c415d1a

14 files changed

Lines changed: 555 additions & 35 deletions

‎.gitignore‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -6,3 +6,4 @@
66
test*
77
AUTHORS
88
Authors
9+
venv

‎LinkedList/linkedList_reversal.py‎

Lines changed: 27 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -13,20 +13,32 @@ def reverse_linked_list(head):
1313
return prev
1414

1515

16+
def reverseLLRecursion(head):
17+
# return if empty
18+
if not head:
19+
return head
20+
# return if last node
21+
if not head.node:
22+
return head
23+
lastNode = reverseLLRecursion(head.node)
24+
head.node.node = head
25+
head.node = None
26+
return lastNode
27+
28+
1629
def pairwise_reversal(head):
17-
temp = temp1 = None
1830
current = head
19-
some = current.node
31+
dummy = current.node
2032
while current and current.node:
21-
temp = current.node
22-
temp1 = temp.node
23-
temp.node = current
24-
if temp1 and temp1.node:
25-
current.node = temp1.node
33+
next = current.node
34+
next_to_next = next.node
35+
next.node = current
36+
if next_to_next and next_to_next.node:
37+
current.node = next_to_next.node
2638
else:
27-
current.node = temp1
28-
current = temp1
29-
return some
39+
current.node = next_to_next
40+
current = next_to_next
41+
return dummy
3042

3143

3244
def create_linked_list():
@@ -56,7 +68,11 @@ def printLinkedList(head):
5668
new_head = reverse_linked_list(linked_list1)
5769
print "Reversed",
5870
printLinkedList(new_head)
59-
print "*"*80
71+
linked_list3 = create_linked_list()
72+
new_head = reverseLLRecursion(linked_list3)
73+
print "Reversed (recusrion)",
74+
printLinkedList(new_head)
75+
print "*" * 80
6076
linked_list2 = create_linked_list()
6177
printLinkedList(linked_list2)
6278
new_head = pairwise_reversal(linked_list2)

‎LinkedList/reverseSpecial.py‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
class Node(object):
2+
def __init__(self, val, next=None):
3+
self.val = val
4+
self.next = next
5+
6+
7+
def reverse(head, left, right):
8+
dummy = Node(None)
9+
dummy.next = head
10+
startNodeForReversal = head
11+
preNodeStart = None
12+
count = 1
13+
while count < left:
14+
preNodeStart = startNodeForReversal
15+
startNodeForReversal = startNodeForReversal.next
16+
count += 1
17+
prevNode, nextNode = None, None
18+
current = startNodeForReversal
19+
while count <= right:
20+
nextNode = current.next
21+
current.next = prevNode
22+
prevNode = current
23+
current = nextNode
24+
count += 1
25+
if preNodeStart:
26+
preNodeStart.next = prevNode
27+
else:
28+
dummy.next = prevNode
29+
if startNodeForReversal:
30+
startNodeForReversal.next = nextNode
31+
return dummy.next
32+
33+
34+
if __name__ == '__main__':
35+
head = Node(10)
36+
head.next = Node(20)
37+
head.next.next = Node(30)
38+
head.next.next.next = Node(40)
39+
head.next.next.next.next = Node(50)
40+
left = 1
41+
right = 3
42+
p = reverse(head, left, right)
43+
while p:
44+
print p.val,
45+
p = p.next

‎TreeADT/MaximumInATree.py‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,9 @@
44

55

66
def maximum_node(root):
7+
# if not root:
8+
# return
9+
# return max(maximum_node(root.left_node), maximum_node(root.right_node), root.data)
710
max = 0
811
if root:
912
root_data = root.data

‎TreeADT/morrisTraversal.py‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
class Node(object):
2+
def __init__(self, v, l=None, r=None):
3+
self.v = v
4+
self.l = l
5+
self.r = r
6+
7+
8+
def morrisInOrder(root):
9+
if not root:
10+
return
11+
current = root
12+
while current:
13+
if current.l is None:
14+
print current.v
15+
current = current.r
16+
else:
17+
left = current.l
18+
while left.r is not None and left.r != current:
19+
left = left.r
20+
if left.r is None:
21+
left.r = current
22+
current = current.l
23+
else:
24+
left.r = None
25+
print current.v
26+
current = current.r
27+
28+
29+
if __name__ == '__main__':
30+
if __name__ == '__main__':
31+
root = Node(1, Node(2, Node(4), Node(5)), Node(3))
32+
morrisInOrder(root)

‎TreeADT/outerView.py‎

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
""" Outer view of a binary tree
2+
20
3+
8 22
4+
5 3 25
5+
10 14
6+
7+
1
8+
2 3
9+
4 5 9 11
10+
6 10
11+
7 8
12+
"""
13+
14+
15+
class Node():
16+
def __init__(self, val, left=None, right=None):
17+
self.val = val
18+
self.left = left
19+
self.right = right
20+
21+
22+
def leaf_nodes(r, covered_nodes):
23+
if not r:
24+
return None
25+
if not r.left and not r.right and r.val not in covered_nodes:
26+
print(r.val, end=" ")
27+
covered_nodes.add(r.val)
28+
leaf_nodes(r.left, covered_nodes)
29+
leaf_nodes(r.right, covered_nodes)
30+
31+
32+
def left_view(r, current_level, max_level, covered_nodes):
33+
if not r:
34+
return None
35+
if current_level > max_level[0]:
36+
if r.val not in covered_nodes:
37+
print(r.val, end=" ")
38+
covered_nodes.add(r.val)
39+
max_level[0] = current_level
40+
left_view(r.left, current_level+1, max_level, covered_nodes)
41+
left_view(r.right, current_level+1, max_level, covered_nodes)
42+
43+
44+
def right_view(r, current_level, max_level, covered_nodes):
45+
if not r:
46+
return None
47+
if current_level > max_level[0]:
48+
if r.val not in covered_nodes:
49+
print(r.val, end=" ")
50+
covered_nodes.add(r.val)
51+
max_level[0] = current_level
52+
right_view(r.right, current_level+1, max_level, covered_nodes)
53+
right_view(r.left, current_level+1, max_level, covered_nodes)
54+
55+
56+
def outer_view(r):
57+
if r:
58+
outer_nodes = set()
59+
# print root node
60+
print(r.val, end=" ")
61+
outer_nodes.add(root.val)
62+
# print left view - already covered nodes
63+
left_view(r, 0, [-1], outer_nodes)
64+
# print leaf nodes - already covered nodes
65+
leaf_nodes(r, outer_nodes)
66+
# print right view - already covered nodes
67+
right_view(r, 0, [-1], outer_nodes)
68+
69+
70+
if __name__ == '__main__':
71+
root = Node(1)
72+
root.left = Node(2)
73+
root.left.left = Node(4)
74+
root.left.right = Node(5)
75+
root.left.right.right = Node(6)
76+
root.left.right.right.left = Node(7)
77+
root.left.right.right.right = Node(8)
78+
root.right = Node(3)
79+
root.right.left = Node(9)
80+
root.right.left.right = Node(10)
81+
root.right.right = Node(11)
82+
# root = Node(20)
83+
# root.left = Node(8)
84+
# root.right = Node(22)
85+
# root.left.left = Node(5)
86+
# root.left.right = Node(3)
87+
# root.left.right.left = Node(10)
88+
# root.left.right.right = Node(14)
89+
# root.right.right = Node(25)
90+
outer_view(root)

‎TreeADT/topAndBottomView.py‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,18 @@ def top_view_of_tree(root):
3636
print ""
3737

3838

39+
def topViewRecursion(root, height, hd, globalMap):
40+
if not root:
41+
return
42+
if globalMap.get(hd, None) is None:
43+
globalMap[hd] = [root.data, height]
44+
else:
45+
if globalMap[hd][1] > height:
46+
globalMap[hd] = [root.data, height]
47+
topViewRecursion(root.left, height+1, hd-1, globalMap)
48+
topViewRecursion(root.right, height+1, hd+1, globalMap)
49+
50+
3951
def bottom_view_of_tree(root):
4052
if not root:
4153
return
@@ -57,6 +69,18 @@ def bottom_view_of_tree(root):
5769
print ""
5870

5971

72+
def bottomViewRecursion(root, height, hd, globalMap):
73+
if not root:
74+
return
75+
if globalMap.get(hd, None) is None:
76+
globalMap[hd] = [root.data, height]
77+
else:
78+
if globalMap[hd][1] < height:
79+
globalMap[hd] = [root.data, height]
80+
bottomViewRecursion(root.left, height+1, hd-1, globalMap)
81+
bottomViewRecursion(root.right, height+1, hd+1, globalMap)
82+
83+
6084
if __name__ == '__main__':
6185
root = Node(20)
6286
root.left = Node(8)
@@ -70,5 +94,19 @@ def bottom_view_of_tree(root):
7094
print "Top view of a tree"
7195
top_view_of_tree(root)
7296

97+
print "Top view of a tree recursion"
98+
map = dict()
99+
topViewRecursion(root, 0, 0, map)
100+
print map
101+
for i in sorted(map.items()):
102+
print i[1][0],
103+
print ""
104+
73105
print "Bottom view of a tree"
74106
bottom_view_of_tree(root)
107+
print "Bottom view of a tree recursion"
108+
map = dict()
109+
bottomViewRecursion(root, 0, 0, map)
110+
for i in sorted(map.items()):
111+
print i[1][0],
112+
print ""

‎decodeString.py‎

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
# given encoded input string, return decoded form
2+
# Inp = 2[ab10[b]d]
3+
# Out = "abbbbbbbbbbbdabbbbbbbbbbbd"
4+
5+
def decodeStr(inp):
6+
counts = []
7+
i = 0
8+
while i < len(inp):
9+
if inp[i].isdigit():
10+
count = 0
11+
while inp[i] != "[":
12+
count = count*10 + int(inp[i])
13+
i += 1
14+
if count > 0:
15+
counts.append(count)
16+
else:
17+
i += 1
18+
strStack = []
19+
for i in inp:
20+
if i == "]":
21+
tmp = []
22+
while strStack[-1] != "[":
23+
x = strStack.pop()
24+
tmp.append(x)
25+
strStack.pop() # remove [
26+
count = counts.pop()
27+
# count = int(strStack.pop())
28+
tmp = tmp*int(count)
29+
strStack.append("".join(tmp[::-1]))
30+
elif not i.isdigit():
31+
strStack.append(str(i))
32+
return strStack[0]
33+
34+
35+
if __name__ == '__main__':
36+
inp = "2[ab2[bc]d]"
37+
res = decodeStr(inp)
38+
print res
39+
assert res == "abbcbcdabbcbcd"
40+
inp = "2[a13[b]]"
41+
res = decodeStr(inp)
42+
print res
43+
assert res == "abbbbbbbbbbbbbabbbbbbbbbbbbb"
44+
inp = "2[a10[b]]"
45+
res = decodeStr(inp)
46+
print res
47+
assert res == "abbbbbbbbbbabbbbbbbbbb"

0 commit comments

Comments
 (0)