Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
class
# maxheap
def maxheapify(a,i):
while i < len(a):
l,r = 2*i+1,2*i+2
m = i
if l < len(a) and a[l] > a[i]:
m = l
if r < len(a) and a[r] > a[m]:
m = r
if m == i:
break
t = a[i]
a[i] = a[m]
a[m] = t
i = m
def buildheap(a):
for i in reversed(range(len(a) // 2)):
maxheapify(a,i)
def popmax(a):
mx = a[0]
a[0] = a[-1]
a.pop()
maxheapify(a,0)
return mx
if __name__ == '__main__':
a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0]
print(a)
maxheapify(a,2)
print(a)
a = [4,1,3,2,16,9,10,14,8,7]
print(a)
buildheap(a)
print(a)
popmax(a)
print(a)
import operator
from functools import reduce
def prod(seq):
return reduce(operator.mul, seq, 1)
def memoize(f):
d = {}
def mem(*args):
if not args in d:
d[args] = f(*args)
return d[args]
return mem
def chain(ps):
@memoize
def __chain__(ps):
if len(ps) == 3:
return prod(ps)
def val(k):
return __chain__(ps[:k]+ps[k+1:]) + prod(ps[k-1:k+2])
return min(map(val, range(1,len(ps)-1)))
return __chain__(ps)
def lcs(x,y):
@memoize
def __lcs__(a,b):
if not a or not b:
return 0
if x[a-1] == y[b-1]:
return __lcs__(a-1,b-1) + 1
return max(__lcs__(a-1,b), __lcs__(a,b-1))
return __lcs__(len(x),len(y))
if __name__ == '__main__':
print(lcs('brad', 'dunbar')) #2
print(lcs('abcxyzabc', 'xyzabcxyz')) #6
print(chain((10,30,5,60))) #4500
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.