liwzhi
BAN USERgraph = {'A':['B','C','D'],'D':['B','E','F'],'E':['C','F','G']}
def levelFrind(graph):
if graph==None:
return
output = []
count = 1
# currOutput = []
queue = sorted(graph.keys())
for key in queue:
currOutput = []
for value in graph[key]:
label = True
for i in range(len(output)):
if value in output[i] and label:
label = False
if label:
currOutput.append(value)
print 'the level is %d' % count
print currOutput
count +=1
output.append(currOutput)
return output
Ouput =levelFrind(graph)
print Ouput

liwzhi
June 24, 2015 BFS + create new tree
class ListNode:
def __init__(self,x):
self.val = x
self.next = None
class Solution:
def levelList(self,root):
output = []
outputMid = []
level = [root]
nextLevel = []
while (level):
for item in level:
outputMid.append(item.val)
if item.left:
nextLevel.append(item.left)
if item.right:
nextLevel.append(item.right)
i = 0
level = nextLevel
head = ListNode(output[0])
head1 = head
while (i<=len(outputMid)2):
item = ListNode(outputMid[i+1])
head1.next = item
i +=1
head1 = head1.next
output.append(head)
return output

liwzhi
March 04, 2015 def findSub(self,A,target):
length = len(A)
i = 0
while(i<length1):
output = targetA[i]
if output<0:
i+=1
elif output==0:
return True
break
else:
for j in range(i+1,length):
output =outputA[j]
if output <0:
i+=1
break
elif output==0:
return True
break
else:
output = output
return False

liwzhi
February 27, 2015 Using the two pointer idea when getting the elements, time complexity is O(N), space is O(N), too.
class Solution:
def findCube(self,N):
elements = []
for i in range(1,N):
if math.pow(i,3)<N:
elements.append(math.pow(i,3))
else:
break
output = []
left = 0
right = len(elements)1
while(left<right):
curr = int(elements[left] + elements[right])
if curr== N:
output.append([int(elements[left]),int(elements[right])])
left +=1
right =1
elif curr<N:
left +=1
else:
right =1
return output

liwzhi
February 25, 2015 Sorry to first reply, please ignore the previous reply. The code should be:
class Solution:
def indexFind(self,target,A):
A = sorted(A)
left = 0
right = len(A)1
if len(A) ==0 or target<A[0]:
return []
if target>A[right]:
return A
while(left<right):
mid = (left+right)/2
if A[mid]<target:
left = mid+1
else:
right = mid
if A[right]== target:
return A[:right]
else:
return A[:right] + [target]
def dy(self,A):
if len(A)==0:
return 0
maxLength = 0
for i in range(len(A)):
B = self.indexFind(A[i],A[:i])
print B
if len(B)==0:
length = 0
else:
length = len(B)
maxLength = max(length,maxLength)
if maxLength ==len(B):
output = B
return output

liwzhi
February 25, 2015 At first, find the index in subarray, using the length to update the output. Time complexity is O(logn) to find the index for each element, so, the time complexity is O(n*logn) totally.
class Solution:
def indexFind(self,target,A):
A = sorted(A)
left = 0
right = len(A)1
if len(A) ==0 or target<A[0]:
return []
if target>A[right]:
return A
while(left<right):
mid = (left+right)/2
if A[mid]<target:
left = mid+1
else:
right = mid
if A[right]== target:
return A[:right]
else:
return A[:right] + [target]
def dy(self,A):
if len(A)==0:
return 0
maxLength = 0
for i in range(len(A)):
B = self.indexFind(A[i],A[:i])
if len(B)==0:
length = 0
else:
length = len(B)
maxLength = max(length,maxLength)
if maxLength ==len(B):
output = B
return output
Open Chat in New Window
Time(nlogn), space:O(n)
 liwzhi June 24, 2015