5、 listnode
5.1 反转链表
while循环中引入两个中间变量pre,next存储当前节点的前一个节点和下一个节点初始值为None
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
if pHead == None or pHead.next ==None:
return pHead
pre = None # 前一个节点（None初始化）
next = None # 下一个节点（None初始化）
while pHead != None:
next = pHead.next # 先保存下一个节点
pHead.next = pre # 下一个节点指向前一个节点（反转链表）
pre = pHead # 前一个节点更新（用于下一个循环使用，也用于返回值）
pHead = next # 用下一个节点替代当前节点（触发下一步循环）
return pre # 原链表最后一个节点next为none, 因此循环结束返回pre
5.2 链表中的节点每k个一组翻转
1、对输出链表向尾向头赋值，引入一个临时变量next，尾部时next=None, 后续next=cur
class Solution:
def reverseKGroup(self , head , k ):
# write code here
buf = []
while head:
buf.append(head.val)
head = head.next
n = len(buf)
if n==0:
return None
i_max = n//k
for i in range(i_max):
t = buf[i*k:(i+1)*k]
buf[i*k:(i+1)*k] = t[::-1]
buf = buf[::-1]
#print('buf=',buf)
next = None
for i in range(n):
cur = ListNode(buf[i])
cur.next = next
next = cur
return cur
5.3 链表中环的入口结点
遍历单链表的每个结点，如果当前结点地址没有出现在set中，则存入set中
否则，出现在set中，则当前结点就是环的入口结点，整个单链表遍历完，若没出现在set中，则不存在环
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead or not pHead.next:
return None
visited = set()
while pHead:
if pHead not in visited:
visited.add(pHead)
pHead = pHead.next
else:
return pHead
return None
5.4 删除链表的倒数第n个节点
1、将链表节点加入一个List型数组 arr, 通过操作arr[i].next来实现删除
2、head实际长度可能为 0,1,2,3……，head值尽量不要动，其它操作用副本t=head
3、删除的位置在中间是正常情况，异常情况要考虑头尾，超范围等
class Solution:
def removeNthFromEnd(self , head , n ):
# write code here
if not head:
return None
t = head
arr = []
while t:
arr.append(t)
t = t.next
m = len(arr)
if m==1:
if n==1:
return None
else:
return head
if n==1:
arr[-2].next = None
head = arr[0]
elif n==m:
head = arr[1]
elif 1<=n-1<=m and 1<=n+1<=m:
arr[-(n+1)].next = arr[-(n-1)]
return head
5.5 合并有序链表
1、读入两个链表合成一个list再由大小到排序
2、对输出链表向尾向头赋值，引入一个临时变量next，尾部时next=None, 后续next=cur
class Solution:
def mergeTwoLists(self , l1 , l2 ):
# write code here
if l1==None and l2==None:
return None
tmp = []
while l1:
tmp.append(l1.val)
l1 = l1.next
while l2:
tmp.append(l2.val)
l2 = l2.next
tmp = sorted(tmp,reverse=1)
n = len(tmp)
next = None
for i in range(n):
cur = ListNode(tmp[i])
cur.next = next
next = cur
return cur
6、 tree
6.1 数组生成二叉树
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
L = [1,2,3,4,5,6,7,8,9]
n = len(L)
Tree = []
for i in range(n):
Tree.append(TreeNode(L[i]))
for i in range(n):
if 2*i+1<=n-1:
Tree[i].left = Tree[2*i+1]
if 2*i+2<=n-1:
Tree[i].right = Tree[2*i+2]
root = Tree[0]
def dfs(root):
if not root:
return
print(root.val, end=' ')
dfs(root.left)
dfs(root.right)
dfs(root)
6.2 二叉树的层序遍历
1、BFS广度优先搜索，先获得每一层需要输出节点的个数，再一个个减小到0，这一层输出结束后，再输出下一层
2、queue.insert(0, cur.left)，新增节点插入到0位
class Solution:
def levelOrder(self , root ):
# write code here
if not root:
return None
queue = [root]
res = []
def bfs(root):
while queue:
n = len(queue)
level = []
while n>0:
cur = queue.pop()
level.append(cur.val)
if cur.left:
queue.insert(0, cur.left)
if cur.right:
queue.insert(0, cur.right)
n -= 1
res.append(level)
return res
return bfs(root)
6.3 二叉树的之字形层序遍历
1、BFS广度优先搜索，先获得每一层需要输出节点的个数，再一个个减小到0，这一层输出结束后，再输出下一层
2、queue.insert(0, cur.left)，新增节点插入到0位
3、之字型：引入一个变量k记录奇偶层，层数从0开始，奇数层tmp.appe***al) 改成 tmp.insert(0,t.val)
class Solution:
def zigzagLevelOrder(self , root ):
# write code here
if not root:
return None
queue = [root]
res = []
k = 0
while queue:
n = len(queue)
tmp = []
while n>0:
t = queue.pop()
#print('k=',k)
if k%2==0:
tmp.appe***al)
else:
tmp.insert(0,t.val)
if t.left:
queue.insert(0,t.left)
if t.right:
queue.insert(0,t.right)
n -= 1
k += 1
res.append(tmp)
print('res=',res)
return res
6.4 二叉树先序，中序和后序遍历
pre = []
def dfs_pre(root):
if not root:
return
pre.append(root.val)
dfs_pre(root.left)
dfs_pre(root.right)
mid = []
def dfs_mid(root):
if not root:
return
dfs_mid(root.left)
mid.append(root.val)
dfs_mid(root.right)
post = []
def dfs_post(root):
if not root:
return
dfs_post(root.left)
dfs_post(root.right)
post.append(root.val)
class Solution:
def threeOrders(self , root ):
# write code here
dfs_pre(root)
dfs_mid(root)
dfs_post(root)
return [pre,mid,post]
6.5 二叉树中找到两个节点的最近公共祖先
1、先dfs搜索，返回节点路径
2、取路径交集返回最近的交点
def dfs(root,o1,res):
if root.val == o1:
#print('res=',res)
return res
if root.left:
t = dfs(root.left,o1,res+[root.left.val])
if t:
return t
if root.right:
t = dfs(root.right,o1,res+[root.right.val])
if t:
return t
class Solution:
def lowestCommonAncestor(self , root , o1 , o2 ):
# write code here
L1 = dfs(root,o1,[root.val])
L2 = dfs(root,o2,[root.val])
#print(L1)
#print(L2)
L1 = L1[::-1]
L2 = L2[::-1]
for i in L1:
for j in L2:
if i==j:
return i
return None
6.6 二叉树根节点到叶子节点和为指定值的路径
1、先dfs搜索，返回节点路径
2、当前为末端节点，且满足路径和条件，全局保存
class Solution:
def pathSum(self , root , i ):
# write code here
if not root:
return []
res = [root.val]
out = []
def dfs(root,res):
if not root.left and not root.right and sum(res)==i:
out.append(res)
if root.left:
dfs(root.left,res+[root.left.val])
if root.right:
dfs(root.right,res+[root.right.val])
dfs(root,res)
#print('out=',out)
return out
'''
6.7 二叉树重建
#=============================================================================================
https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=196&&tqId=37109&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
解题思路：
前序遍历：先根节点，再左子树，最后右子树
中序遍历：先左子树，再根节点，最后右子树
我们可以先从前序遍历的第一个元素得到根节点root=TreeNode(pre.pop(0))
再从中序排序中找到根节点所在位置，以这个位置为中心，可以得到二叉树的左子树与右子树
二叉树可以分开看，左子树可以看成一个新的二叉树，不断细分，可以确定到每一个叶子节点
同理，右子树也可以，看成新的二叉树，我们可以通过递归来实现
特殊情况的考虑：无论哪一个遍历为空，题目所求都没有意义
#=============================================================================================
'''
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
#print('pre=',pre)
#print('tin=',tin)
#print('---')
val = pre.pop(0)
root = TreeNode(val)
i = tin.index(val)
root.left = self.reConstructBinaryTree(pre, tin[:i])
root.right = self.reConstructBinaryTree(pre, tin[i+1:])
return root
pre = [1,2,3,4,5,6,7]
tin = [3,2,4,1,6,5,7]
Solution().reConstructBinaryTree(pre, tin)
'''
6.8 二叉树深度
https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=196&&tqId=37055&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
'''
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# @param root TreeNode类
# @return int整型
#
class Solution:
def maxDepth(self , root ):
# write code here
if not root:
return 0
out = []
def dfs(root,res):
if not root:
return
if not root.left and not root.right:
out.append(res)
if root.left:
dfs(root.left, res+[root.left.val])
if root.right:
dfs(root.right, res+[root.right.val])
dfs(root,[root.val])
depth = 0
for i in out:
if len(i)>depth:
depth = len(i)
return depth
'''
6.9 最小生成树
https://www.nowcoder.com/practice/735a34ff4672498b95660f43b7fcd628?tpId=196&&tqId=37574&rp=1&ru=/activity/oj&qru=/ta/job-code-total/question-ranking
'''
# 返回最小的花费代价使得这n户人家连接起来
# @param n int n户人家的村庄
# @param m int m条路
# @param cost int二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
# @return int
#
class Solution:
def miniSpanningTree(self , n , m , cost ):
# write code here
p = list(range(n+1))
height = [0 for _ in range(n+1)]
cost = list(sorted(cost, key=lambda x: x[2]))
def find(n):
while n != p[n]:
n = p[n]
return n
i = 0
ans = 0
for a, b, c in cost:
if i == n - 1: break
pa = find(a)
pb = find(b)
if pa == pb:
continue
if height[pa] > height[pb]:
p[pb] = pa
elif height[pb] > height[pa]:
p[pa] = pb
else:
height[pb] += 1
p[pa] = pb
ans += c
i += 1
return ans
Solution().miniSpanningTree(3,3,[[1,3,3],[1,2,1],[2,3,1]])
7、 biSearch
def biSearch(L, v):
x1 = 0
x2 = len(L)-1
while x1<x2:
#print('x1=',x1,'x2=',x2)
xm = (x1+x2)//2
if L[xm] < v: # 注意这里<,<=要多测试
x1 = xm+1 # 注意这里xm+1,xm要多测试
else:
x2 = xm
return x1
7.1 最长增长子序列
L = arr
n = len(L)
#--------------------------------------
# 数组B维护的是当前最长递增子序列的最小末尾值，参见下文
# https://blog.csdn.net/sinat_31790817/article/details/78348722
B = [L[0]]
dp = [1]
for i in range(1, n):
if L[i]>B[-1]:
B.append(L[i])
dp.append(len(B))
else:
t = biSearch(B, L[i])
B[t] = L[i]
dp.append(t+1)
print('B=',B)
print('dp=',dp)
#--------------------------------------
# 在dp序列中反向寻找第一个出现的maxLen，maxLen-1，maxLen-2，…… 1，所对应的原数组元素
C = []
maxLen = max(dp)
for i in range(len(dp)-1,-1,-1):
if dp[i]==maxLen:
C.append(L[i])
maxLen -= 1
return C[::-1]
7.2 求平方根
def f(x):
return x*x
class Solution:
def sqrt(self , x ):
# write code here
y = x
if y<0:
return None
elif y==0:
return 0
elif y==1:
return 1
else:
x1 = 1
x2 = x
while x2-x1>1e-4:
xm = (x1+x2)/2
#print('xm=',xm)
if (f(x1)-y)*(f(xm)-y)>0:
x1 = xm
else:
x2 = xm
print('x2=',x2)
return int(x2)
7.3 求立方根
y = float(input())
x1 = 0.0
if y>0:
x2 = max(y,1)
else:
x2 = min(y,-1)
f = lambda x:x**3
k = 0
while abs(x1-x2) > 1e-4:
x0 = (x1+x2)/2
if (f(x1)-y)*(f(x0)-y)>0:
x1 = x0
else:
x2 = x0
k += 1
print(round(x1*10)/10)
京公网安备 11010502036488号