forked from satojkovic/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathrecursion.py
More file actions
196 lines (170 loc) · 4.93 KB
/
Copy pathrecursion.py
File metadata and controls
196 lines (170 loc) · 4.93 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
def fib(n):
if n == 0 or n == 1:
return n
return fib(n-1) + fib(n-2)
def fib_memo(n):
def fib_m(n, memo):
if n == 0 or n == 1:
return n
if memo[n] == 0:
memo[n] = fib_m(n - 1, memo) + fib_m(n - 2, memo)
return memo[n]
# memoization of (n + 1) values (from 0 to n)
memo = (n + 1) * [0]
return fib_m(n, memo)
def reverse_str(s):
if len(s) == 0:
return s
rstr = reverse_str(s[1:])
return ''.join([rstr, s[0]])
def reverse_str2(s):
if len(s) == 0:
return []
rstr = reverse_str2(s[1:])
return rstr + [s[0]]
def reverse_str3(s, head, tail):
if head >= tail:
return
s[head], s[tail] = s[tail], s[head]
return reverse_str3(s, head + 1, tail - 1)
def swap_node_pairs(head):
if head is None or head.next is None:
return head
swap_head = swap_node_pairs(head.next.next)
pair = head.next
head.next = swap_head
pair.next = head
return pair
def climb_stairs(n):
def cs_memo(n, memo):
if n < 0:
return 0
elif n == 0:
return 1
if memo[n] == 0:
memo[n] = cs_memo(n - 1, memo) + cs_memo(n - 2, memo)
return memo[n]
memo = (n + 1) * [0]
return cs_memo(n, memo)
def pascal_triangle(n):
if n == 0:
return []
elif n == 1:
return [n * [1]]
prev_rows = pascal_triangle(n - 1)
cur_row = n * [1]
for i in range(n):
if i == 0 or i == n - 1:
continue
cur_row[i] = prev_rows[n - 2][i - 1] + prev_rows[n - 2][i]
prev_rows.append(cur_row)
return prev_rows
def pascal_triangle2(n):
if n == 0:
return [1]
elif n == 1:
return (n+1) * [1]
prev_row = pascal_triangle2(n - 1)
cur_row = (n+1) * [1]
for i in range(n+1):
if i == 0 or i == n:
continue
cur_row[i] = prev_row[i - 1] + prev_row[i]
return cur_row
def pascal_triangle3(n):
if n == 0:
return [1]
elif n == 1:
return (n+1) * [1]
prev_row = pascal_triangle2(n - 1)
for i in reversed(range(1, n)):
prev_row[i] = prev_row[i - 1] + prev_row[i]
return prev_row + [1]
def reverse_list(head):
if head is None or head.next is None:
return head
node = reverse_list(head.next)
head.next.next = head
head.next = None
return node
def max_depth(root):
def helper(root, depth):
if root is None:
return depth - 1
return max(helper(root.left, depth + 1), helper(root.right, depth + 1))
return helper(root, 0)
def pow(x, n):
if n == 0:
return 1
return x * pow(x, n - 1) if n > 0 else (1/x) * pow(x, n + 1)
def pow2(x, n):
if n == 0:
return 1
elif n == 1:
return x
if n > 0:
return pow2(x, n // 2) * pow2(x, n - n // 2)
else:
n = abs(n)
return pow2(1 / x, n // 2) * pow2(1 / x, n - n // 2)
def pow3(x, n):
def helper(x, n, memo):
if n == 0:
return 1
elif n == 1:
return x
if memo[abs(n)] < 0:
if n > 0:
memo[n] = helper(x, n // 2, memo) * helper(x, n - n // 2, memo)
else:
n = abs(n)
memo[n] = helper(1 / x, n // 2, memo) * helper(1 / x, n - n // 2, memo)
return memo[n]
memo = (abs(n) + 1) * [-1]
return helper(x, n, memo)
def pow4(x, n):
def helper(x, n, memo):
if n == 0:
return 1
elif n == 1:
return x
if memo.get(abs(n)) is None:
if n > 0:
memo[n] = helper(x, n // 2, memo) * helper(x, n - n // 2, memo)
else:
n = abs(n)
memo[n] = helper(1 / x, n // 2, memo) * helper(1 / x, n - n // 2, memo)
return memo[n]
memo = {}
return helper(x, n, memo)
def perm(n):
if n == 0:
return []
elif n == 1:
return [[1]]
res = []
for p in perm(n - 1):
for i in range(n):
res.append(p[:i] + [n] + p[i:])
return res
def search_2d_mat(mat, target):
if len(mat) == 0 or len(mat[0]) == 0:
return False
M, N = len(mat), len(mat[0])
return search(mat, target, 0, 0, M - 1, N - 1)
def search(mat, target, top, left, bottom, right):
# Area size is zero
if top > bottom or left > right:
return False
# Target doesn't exist in this area
elif mat[top][left] > target or mat[bottom][right] < target:
return False
# Search row such that mat[row - 1][mid_col] < target mat[row][mid_col]
# because target should exist somewhere in the bottom-left area or top-right area
mid_col = left + (right - left) // 2
row = top
while row <= bottom and mat[row][mid_col] <= target:
if mat[row][mid_col] == target:
return True
row += 1
return search(mat, target, row, left, bottom, mid_col - 1) or search(mat, target, top, mid_col + 1, row - 1, right)