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
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
def findSub(self,A,target):
length = len(A)
i = 0
while(i<length-1):
output = target-A[i]
if output<0:
i+=1
elif output==0:
return True
break
else:
for j in range(i+1,length):
output =output-A[j]
if output <0:
i+=1
break
elif output==0:
return True
break
else:
output = output
return False
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
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
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
Time(nlogn), space:O(n)
- liwzhi June 24, 2015