eastflag163
BAN USERSpace Complexity:
QuickSort: O(logn)~O(n)
Bubble: O(1)
Insertion: O(1)
Merge: O(n)
BS: O(n)
#!/usr/bin/python
ds = [25, 10, 5, 2, 1]
s = 45
minc = [-1] * (s+1)
minc[0] = 0
for i in range(1, s + 1):
h = s + 1
for d in ds:
if i >= d:
if minc[i-d] >= 0:
if h > minc[i-d]:
h = minc[i-d]
if h > s:
h = -1;
minc[i] = h + 1
print minc[s]
#!/usr/bin/python
matrix = [[2, 3, 4, 5],[4, 5, 10, 11],[20, 6, 9, 12],[6, 7, 8, 40]]
m = len(matrix)
n = len(matrix[0])
lis = []
for i in range(m):
lis.append([0 for x in matrix[0]])
def maxd(i, j):
if lis[i][j] > 0:
return lis[i][j]
flag = False
(up, down, left, right) = (0, 0, 0, 0)
if (i < m - 1) and (matrix[i][j] == matrix[i+1][j] - 1):
down = maxd(i+1, j)
flag = True
if (j < n - 1) and (matrix[i][j] == matrix[i][j+1] - 1):
right = maxd(i, j+1)
flag = True
if (i > 0) and (matrix[i][j] == matrix[i-1][j] - 1):
up = maxd(i-1, j)
flag = True
if (j > 0) and (matrix[i][j] == matrix[i][j-1] - 1):
left = maxd(i, j-1)
flag = True
if not flag:
return 0
else:
lis[i][j] = max(up, down, left, right) + 1
return lis[i][j]
def getLIS(k, i, j):
c = str(matrix[i][j])
if k == 1:
return c
if (i < m - 1) and (lis[i][j] == lis[i+1][j] + 1):
return c + ' ' + getLIS(k-1, i+1, j)
if (j < n - 1) and (lis[i][j] == lis[i][j+1] + 1):
return c + ' ' + getLIS(k-1, i, j+1)
if (i > 0) and (lis[i][j] == lis[i-1][j] + 1):
return c + ' ' + getLIS(k-1, i-1, j)
if (j > 0) and (lis[i][j] == lis[i][j-1] + 1):
return c + ' ' + getLIS(k-1, i, j-1)
def solve(matrix):
print lis
for i in range(m):
for j in range(n):
if lis[i][j] == 0:
maxd(i, j)
print lis
(maxv, maxi, maxj) = (0, 0, 0);
for i in range(m):
for j in range(n):
if maxv < lis[i][j]:
maxv = lis[i][j]
maxi = i
maxj = j
print getLIS(maxv, maxi, maxj)
solve(matrix)
#!/usr/bin/python
def testPW(pw):
key = '1478'
if len(key) != len(pw):
return 'fail'
count = 0
for i in range(len(pw)):
if key[i] != pw[i]:
count += 1
diff = abs(int(key[i]) - int(pw[i]))
if (diff != 1) and (diff != 3):
return 'fail'
if count > 1:
return 'fail'
else:
return 'success'
print testPW('1178')
deleted!!!
- eastflag163 October 26, 2013#!/usr/bin/python
##print password recursively from leftmost digit
##s is current string, minv is min value of leftmost digit, m is number of digits
def printPW(s, minv, m):
for v in range(minv, 11 - m):
if m==1:
print s + str(v)
else:
printPW(s + str(v), v + 1, m - 1)
printPW('', 6, 3)
- eastflag163 November 05, 2013