連續(xù)子數(shù)組最大和
class Solution:
def maxSubArra(self,nums):
cursum=maxsum=nums[0]
for i in range(1,len(nums)):
cursum=max(nums[i],cursum+nums[i])
maxsum=max(cursum,maxsum)
return maxsum
兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)
二分查找
def bin_search(data, val):
l= 0
h= len(list) - 1
while l<= h:
mid =l+ (h - l) / 2
if data[mid] == val:
return mid
elif data[mid] > val：
h= mid - 1
else:
l= mid + 1
return -1
快排
def quicksort(array):
if len(array)<2:
return array
else:
pivot=array[0]
less=[i for i in array[1:] if i<=pivot]
greater=[i for i in array[1:] if i>pivot]
return quicksort(less)+[pivot]+quicksort(greater)
print(quicksort([5,3,24,6,7,1,3,9,2]))
二叉樹的鏡像
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root==None:
return
root.left,root.right=root.right,root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
鏈表中環(huán)的入口結(jié)點(diǎn)
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow=fast=head
while fast and fast.next:
slow=slow.next
fast=fast.next.next
if slow==fast:
fast=head
while slow!=fast:
slow=slow.next
fast=fast.next
return fast
return None
兩個(gè)棧實(shí)現(xiàn)隊(duì)列
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
if not self.stack1:
return None
while self.stack1:
self.stack2.append(self.stack1.pop())
res = self.stack2.pop()
while self.stack2:
self.stack1.append(self.stack2.pop())
return res
if __name__ == '__main__':
s=Solution()
list=[1,2,3,4,5]
for i in range(len(list)):
s.push(list[i])
for i in range(len(list)):
print(s.pop())
反轉(zhuǎn)單鏈表
class Solution:
"""
@param head: The first node of the linked list.
@return: You should return the head of the reversed linked list.
Reverse it in-place.
"""
def reverse(self, head):
# write your code here
if head is None: return None
p = head
cur = None
pre = None
while p is not None:
cur = p.next
p.next = pre
pre = p
p = cur
return pre
和為S的兩個(gè)數(shù)字且乘積最小
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
dic=dict()
ret=[]
for num in array:
if tsum-num in dic:
if ret==[]:
ret=[tsum-num,num]
elif ret[0]*ret[1]>(tsum-num)*num:
ret=[tsum-num,num]
else:
dic[num]=1
return ret
順時(shí)針打印矩陣
class Solution:
def spiralOrder(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
result = []
while (matrix):
result += matrix.pop(0)
if not matrix or not matrix[0]:
break
matrix = self.turn(matrix)
return result
def turn(self, matrix):
row = len(matrix)
col = len(matrix[0])
newMatrix = []
for i in range(col):
sb = []
for j in range(row):
sb.append(matrix[j][i])
newMatrix.append(sb)
newMatrix.reverse()
return newMatrix
if __name__ == '__main__':
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
print(Solution().spiralOrder(arr))
之字形打印二叉樹（如果是順序打印就刪掉flag相關(guān)邏輯）
class Solution:
def Print(self, pRoot):
# write code here
if not pRoot:
return []
nodeStack=[pRoot]
result=[]
flag=True
while nodeStack:
flag= not flag
nextStack=[]
tmp=[]
for i in nodeStack:
tmp.append(i.val)
if i.left:
nextStack.append(i.left)
if i.right:
nextStack.append(i.right)
nodeStack=nextStack
if flag:
tmp.reverse()
result.append(tmp)
return result
先序中序重建二叉樹
class Solution(object):
def buildTree(self, preorder, inorder):
if len(inorder)>0:
mid=inorder.index(preorder.pop(0))
root=TreeNode(inorder[mid])
root.left=self.buildTree(preorder,inorder[:mid])
root.right=self.buildTree(preorder,inorder[mid+1:])
return root
中序后序重建二叉樹
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if len(inorder)>0:
mid=inorder.index(postorder.pop(len(postorder)-1))
root=TreeNode(inorder[mid])
root.right=self.buildTree(inorder[mid+1:],postorder)
root.left=self.buildTree(inorder[:mid],postorder)
return root
- 滑動窗口的最大值
給定一個(gè)數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值。例如，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個(gè)滑動窗口，他們的最大值分別為{4,4,6,6,6,5}； 針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個(gè)： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
class Solution:
def maxInWindows(self, num, size):
# write code here
if size == 0:
return []
ret = []
stack = []
for pos in range(len(num)):
while (stack and stack[-1][0] < num[pos]):
stack.pop()
stack.append((num[pos], pos))
if pos >= size - 1:
while (stack and stack[0][1] <= pos - size):
stack.pop(0)
ret.append(stack[0][0])
return ret
if __name__ == '__main__':
num = [2, 3, 4, 2, 6, 2, 5, 1]
size = 3
print(Solution().maxInWindows(num, size))
判斷一個(gè)數(shù)是不是丑數(shù)
class Solution(object):
def isUgly(self, num):
"""
:type num: int
:rtype: bool
"""
if num <= 0:
return False
for i in [2,3,5]:
while num % i == 0:
num = num / i
if num == 1:
return True
else:
return False
if __name__ == '__main__':
print(Solution().isUgly(14))
兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)
思考：設(shè)鏈表pHead1的長度為a,到公共結(jié)點(diǎn)的長度為l1；鏈表pHead2的長度為b,到公共結(jié)點(diǎn)的長度為l2，有a+l2 = b+l1
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
# write code here
if pHead1== None or pHead2 == None:
return None
pa = pHead1
pb = pHead2
while(pa!=pb):
pa = pHead2 if pa is None else pa.next
pb = pHead1 if pb is None else pb.next
return pa
import heapq
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
heaps = []
ret = []
for num in tinput:
heapq.heappush(heaps,num)
if k>len(heaps):
return []
for i in range(k):
ret.append(heapq.heappop(heaps))
return ret
二維數(shù)組中的查找
# -*- coding:utf-8 -*-
class Solution:
# array 二維列表
def Find(self, target, array):
# write code here
if not array:
return False
i = 0
j = len(array[0])-1
while(i<len(array) and j>=0):
if array[i][j]==target:
return True
elif array[i][j]>target:
j-=1
else:
i+=1
return False
替換空格
import re
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
return re.sub(" ","%20",s)
是否為平衡二叉樹
class Solution(object):
def isBalanced(self, root):
def height(node):
if not node:return 0
left = height(node.left)
right = height(node.right)
if left == -1 or right == -1 or abs(left-right) > 1:
return -1
return max(left,right) + 1
return height(root) != -1
字符串全排列
class Solution:
def Permutation(self, ss):
if not ss:
return []
res = []
self.helper(ss, res, '')
return sorted(list(set(res)))
def helper(self, ss, res, path):
if not ss:
res.append(path)
else:
for i in range(len(ss)):
self.helper(ss[:i] + ss[i+1:], res, path + ss[i])
if __name__ == '__main__':
print(Solution().Permutation("abcd"))
21.合并兩個(gè)排序的鏈表
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if not l1 and not l2:
return None
dummy = ListNode(0)
cur = dummy
while l1 and l2:
if l1.val <= l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
二叉樹中和為某一值的路徑(dfs)
class Solution:
def __init__(self):
self.li = []
self.liall = []
def FindPath(self, root, expectNumber):
if root is None:
return self.liall
self.li.append(root.val)
expectNumber -= root.val
if expectNumber == 0 and not root.left and not root.right:
self.liall.append(self.li[:])
self.FindPath(root.left, expectNumber)
self.FindPath(root.right, expectNumber)
self.li.pop()
return self.liall
二進(jìn)制中1的個(gè)數(shù)
class Solution:
def numberof1(self,n):
count=0
while n:
n=n&(n-1)
count+=1
return count
跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級。求該青蛙跳上一個(gè)n級的臺階總共有多少種跳法。
class Solution:
def jumpFloor(self, number):
# write code here
'''
n = 1 : 1
n = 2 : 1+1 = 2
n = 3 : dp[n-2]+dp[n-1]
'''
if number == 1 or number == 2:
return number
dp = [1,2]
for i in range(number-2):
dp.append(dp[-1]+dp[-2])
return dp[-1]
變態(tài)跳臺階
一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個(gè)n級的臺階總共有多少種跳法
class Solution:
def jumpFloorII(self, number):
# write code here
if number == 1 or number == 2:
return number
ret = sum_ = 3
for i in range(number-2):
ret = sum_+1
sum_+=ret
return ret
