今天主要写了一下offer 1-41题，余下的稍后整理
1 """
1 镜像二叉树: 递归
"""
def mirror(root):
if not root:
return None
mirror(root.left)
mirror(root.right)
root.left, root.right = root.right, root.left
return root
"""2. 链表环入口
"""
def circle(node):
if not node:
return None
slow,fast = node, node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow = node
while slow != fast:
slow = slow.next
fast = fast.next
return fast
return None
"""
3 删除重复结点
"""
def delNode(pHead):
first = ListNode(-1)
cur = pHead
last = first
while cur and cur.next:
if cur.val != cur.next.val:
cur = cur.next
last = last.next
else:
val = cur.val
while cur and cur.val == val:
cur = cur.next
last.next = cur
return first.next
"""4 打印链表"""
def info(pHead):
res = []
if not pHead:
return None
while pHead:
res.index(pHead.val)
pHead = pHead.next
return res
"""5 斐波那契数列的第n项"""
def Fib(n):
dp = [0,1]
if n == 0:
return 0
if n == 1:
return 1
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[-1]
def Fib1(n):
if n == 0:
return 0
if n == 1:
return 1
a ,b = 0, 1
while n-1:
temp = a
a = b
b = temp + b
n -= 1
return b
"""6 变态跳台阶"""
def jump(n):
if n == 1:
return 1
dp = [1]
for i in range(1, n):
dp[i] = sum(dp[:i]) + 1
return dp[-1]
def jumpFloorII(number):
# write code here
if number == 1:
return 1
dp = [1] * (number)
dp[0], dp[1] = 1, 2
for i in range(2, number):
dp[i] = 2 * dp[i - 1]
return dp[-1]
"""10 平衡二叉树"""
def isBalance(root):
def deep(root):
if not root:
return 0
left = deep(root.left)
right = deep(root.right)
return max(left, right) + 1
if not root:
return True
return abs(deep(root.left) - deep(root.right)) <=1
"""11.和为s的连续数字"""
def findNumber(tsum):
res = []
left, right = 1, 2
if tsum < 3:
return []
while left< right and left < tsum//2+1:
if sum(range(left, right+1)) == tsum:
res.append(range(left, right+1))
left += 1
elif sum(range(left, right+1)) < tsum:
right +=1
else:
left+=1
return res
"""12 左旋字符串"""
def left(s, k):
if s == "":
return ""
k = k%len(s)
return s[k:] + s[:k]
"""13 数字在排序数组出现次数"""
def numberCount(data, k):
if not data:
return 0
left, right = 0, len(data) - 1
while left <= right:
mid = (left + right) // 2
if data[mid] == k:
index = mid
res = 0
while index < len(data) and data[index] == k:
res += 1
index += 1
index = mid - 1
while index >= 0 and data[index] == k:
res += 1
index -= 1
return res
elif data[mid] > k:
right = mid - 1
else:
left = mid + 1
return 0
"""14 数组只出现一次的数字 ： 异或运算"""
def onlyOne(array):
temp = 0
flag = 1
a,b = 0,0
for i in array:
temp = temp ^ i
while temp:
if temp % 2 != 0:
break
temp >> 1
flag = flag << 1
for i in array:
if i&flag:
a =a^i
else:
b = b^i
return a,b
"""16 二叉树深度 ： 参照10"""
"""17 和为s的两个数： 双指针：距离最远的数字最小"""
def FindNumbersWithSum( array, tsum):
left, right = 0, len(array)-1
a,b = 0,0
while left<= right:
if array[left] + array[right] == tsum:
return array[left],array[right]
elif array[left] + array[right] < tsum:
left +=1
else:
right -=1
return []
"""18 顺时针打印矩阵 : 思路：每次打印第一行，将矩阵逆时针旋转90 直到为None"""
def infoArray(matrix):
if not matrix:
return None
res = []
while matrix:
res = res + matrix[0]
matrix.pop(0)
matrix = list(map(list, zip(*matrix)))[::-1]
return res
"""19 二叉树的下一个结点（***）中序遍历（左 中 右）
① 如果结点存在右结点，则进入右子树（最左边的结点） 该节点相当于根
② 若该节点无右子节点，且该节点为父亲的左子节点，则为父节点 该节点为左节点
③ 若该节点无右子节点，且该节点为父亲的右子节点，则需要一直搜索父亲，直到为某个结点的左节点
"""
def nextNode(pNode):
if not pNode:
return None
if pNode.right: #情况1
temp = pNode.right
while temp.left:
temp = temp.left
return temp
else:
temp = pNode.next #temp指向父亲
while temp and temp.right == pNode: #判断是否为父亲的右节点， 不是的话退出 返回上一行的值
#是的话执行情况3
pNode = temp
temp = temp.next
return temp
"""20 对称二叉树"""
def symme(left, right):
if not left and not right:
return True
if left and right:
return left.val == right.val and symme(left.left, right.right) and symme(left.right, right.left)
else:
return False
def issymme(pRoot):
if not pRoot:
return True
return symme(pRoot.left, pRoot.right)
"""21 二叉树打印多行 从左往右打印"""
"""层次遍历二叉树(补充)"""
def cengci(root):
if not root:
return None
queue = [root]
res = []
while queue:
res.append(queue[0].val)
if queue[0].left:
queue.append(queue[0].left)
if queue[0].right:
queue.append(queue[0].right)
queue.pop(0)
return res
"""本题"""
def print(pRoot):
if not pRoot:
return []
res = []
queue = [pRoot]
while queue:
temp = []; queue_temp = []
for i in queue:
temp.append(i.val)
if i.left:
queue_temp.append(i.left)
if i.right:
queue_temp.append(i.right)
queue = queue_temp
res.append(temp)
return res
"""24 数据流中位数 ： 大根堆 和小根堆"""
"""26 重建二叉树 先序 中序"""
def buildTree(pre, tin):
root = pre[0]
index = tin.index(root)
ltin = tin[:index]
rtin = tin[index+1:]
lpre = pre[1:len(ltin)+1]
rpre = pre[1+len(ltin):]
p = TreeNode(root)
p.left = buildTree(lpre,ltin)
p.right = buildTree(rpre,rtin)
return p
"""27 滑动窗口最大"""
"""28 栈实现队列： 根据性质"""
"""29 旋转数组最小值：二分查找"""
def minNumber(rotateArray):
if not rotateArray:
return None
low,high = 0, len(rotateArray)-1
while low < high:
mid = (low + high) //2
if rotateArray[mid] > rotateArray[high]:
left = mid + 1
else:
high = mid
return rotateArray[left]
"""30 丑数"""
def ugly(index):
if index ==0:
return 0
if index == 1:
return 1
dp = [1]
n1,n2,n3 = 0,0,0
for i in range(index-1):
num1,num2,num3 = dp[n1]*2, dp[n2]*3, dp[n3]*5
Min = min(num1, num2,num3)
dp.append(Min)
if num1 == Min:
n1 += 1
if num2 == Min:
n2 += 1
if num3 == Min:
n3 += 1
return dp[-1]
"""31 链表的第一个公共结点"""
def firstCommonNode(pHead1, pHead2):
if not pHead1 or not pHead2:
return None
p1,p2 = pHead1,pHead2
while p1 != p2:
if p1:
p1 = p1.next
else:
p1 = pHead2
if p2:
p2 = p2.next
else:
p2 = pHead1
return p1
"""32 第一次只出现一次的字符
queue 存储每个字符第一次出现的位置
"""
def firstChar(s):
dict = {}
queue = []
for i in range(len(s)):
if s[i] not in dict:
dict[s[i]] = 1
queue.append(i)
else:
dict[s[i]] += 1
for i in queue:
if dict[s[i]] == 1:
return i
return -1
"""33 数组中逆序对
思路： 先排序 从小到大找 对应 原数组中去
例[2,5,1] -> [1,2,5] 从1开始在原数组找它的索引就是它对应的逆序对数 1:2 2:1 5:0
"""
def inverse(data):
temp =[]
res = 0
for i in data:
temp.append(i)
temp = sorted(temp)
for i in temp:
res += data.index(i)
data.remove(i)
return res
"""34 连续数组的最大和"""
def FindGreatestSumOfSubArray(array):
# write code here
for i in range(1, len(array)):
if array[i - 1] >= 0:
array[i] = array[i] + array[i - 1]
else:
continue
return max(array)
"""35 最小的k个数
TOPK问题： 一般建立大根堆， 如果是最大的就建立小根堆
快排也可以实现
"""
# 快排
def p( L, l, r):
temp, i = L[r], l - 1
for j in range(l, r):
if L[j] <= temp:
i += 1
L[i], L[j] = L[j], L[i]
L[i + 1], L[r] = L[r], L[i + 1]
return i + 1
def GetLeastNumbers_Solution( tinput, k):
if k == 0 or k > len(tinput):
return []
else:
flag = p(tinput, 0, len(tinput) - 1) #拆分点
while flag != k - 1:
if flag > k - 1:
flag = p(tinput, 0, flag - 1)
if flag < k - 1:
flag = p(tinput, flag + 1, len(tinput) - 1)
return sorted(tinput[:flag + 1])
#堆排序（TOP） 这是找最大的。
class Solution:
def __init__(self):
pass
def Heap(self, L, i, size): #小根堆维护
root = i
left , right = 2*i+1, 2*i+2
if left < size and L[root]> L[left]:
root = left
if right < size and L[root]> L[right]:
root = right
if root != i:
L[root],L[i] = L[i],L[root]
self.Heap(L,root,size)
return L
def buildHeap(self, L):
for i in range(len(L)//2,-1,-1):
self.Heap(L,i,len(L))
return L
def TopK(self, L, k):
result = L[:k]
result = self.buildHeap(result)
for i in range(k,len(L)):
if L[i] > result[0]:
result[0] = L[i]
self.Heap(result, 0, k)
return result
""""""
"""36 数组超过一半的数
排序（多余一半的肯定出现在中间）"""
def MoreNum(numbers):
numbers = sorted(numbers)
key = numbers[len(numbers) // 2]
if numbers.count(key) > len(numbers) // 2:
return key
else:
return 0
"""37 1 到n中 1出现的次数
找规律
"""
"""38 数组排成最小的数"""
def minNum(numbers):
if numbers is None or len(numbers) == 0:
return ""
numbers = map(str, numbers)
numbers.sort(cmp=lambda x, y: cmp(x + y, y + x))
return "".join(numbers).lstrip()
#错误
def minNum2(numbers):
numbers = sorted(list(map(str, numbers)))
res = ""
for i in numbers:
print(i)
if (res + i) >= (i + res):
res = i+res
else:
res = res+i
return res
"""39 数组中重复的数字"""
def duplicate(numbers, duplication):
# write code here
dict = {}
for i in range(len(numbers)):
if numbers[i] not in dict:
dict[numbers[i]] = 1
else:
dict[numbers[i]] += 1
for i in dict:
if dict[i] > 1:
duplication[0] = i
return True
duplication[0] = -1
return False
"""40 构造乘积数组
给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],
其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。
"""
def mulMatrix(A):
size = len(A)
B = [1] * size
for i in range(1, size): # 构建下三角矩阵（上 到 下）
B[i] = A[i - 1] * B[i - 1]
temp = 1
for i in range(size - 2, -1, -1):
temp = temp * A[i + 1]
B[i] = B[i] * temp
return B
"""?? 旋转数组的查找：二分查找"""
def findKey(target, array):
if not array:
return None
left, right = 0,len(array)-1
while left < right:
mid = (left + right)//2
if array[mid] == target:
return True
if array[mid] < array[right]: #右侧有序
if target > array[mid] and target <= array[right]:
left = mid + 1
else:
right = mid -1
else:
if target >= array[left] and target < array[mid]:
right = mid -1
else:
left = mid + 1
return False
"""41 二维数组的查找"""
def findkey(target, array):
if not array:
return False
row ,col = 0, len(array[0])-1
while row <= len(array) and col>=0:
if array[row][col] == target:
return True
elif array[row][col] > target:
col -= 1
else:
row += 1
return False
