51.构建乘积数组
给定一个数组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]。不能使用除法。
先求前向乘积列表t_forword=a[0]*a[1]*...*a[i-1];存入b
再求后项乘积列表t_back=a[len(a)-1]*a[len(a)-1]*...*a[i+1];b[i]*t_back得到最后结果
class Solution:def multiplyArr(self,a):b=[1]*len(a)#前向乘积a[0]*a[1]...a[i-1]t_forward=1for i in range(1,len(a),1):t_forward*=a[i-1]b[i]=t_forward#后项乘积获取a[len(a)-1]*a[len(a)-1]*...*a[i+1]t_back=1for i in range(len(a)-1,-1,-1):b[i]*=t_backt_back*=a[i]return bdef valid(self,a):t=1b=[]for i in a:t*=ifor i in a:b.append(t/i)return bs=Solution()
a=[1,2,3,4,5]
r1=s.multiplyArr(a)
r2=s.valid(a)
print(r1,r2)
52.正则表达式匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，
而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配
整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
思路：递归匹配f(s,p)，s字符串,p模式
1、当p的第二个字符p[1]不是*时：（1）如果s[0]与p[0]相匹配，那么s和p均后移一位，匹配剩余的f(s-1,p-1)；
（2）如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
2、当p的第二个字符p[1]是*时：如果s[0]与p[0]相匹配：
（1)字符串后移1位，模式后移2字符。
(2)字符串后移1位，模式不变，相当于x*中的x出现多次；
如果s[0]与p[0]不匹配：字符串不变，模式后移2字符，相当于x*中的x出现0次；
3、当s和p均为0时，匹配成功返回；如果其中一个不为0,匹配失败
class Solution:def match(self,s,p):if len(s)==0 and len(p)==0:return Trueif (len(s)!=0 and len(p)==0) or (len(s)==0 and len(p)!=0):return Falseif len(p)>1 and p[1]=='*':if (p[0]==s[0] or p[0]=='.'):return self.match(s[1:],p[2:]) or self.match(s[1:],p)else:return self.match(s,p[2:])else:if (p[0]==s[0] or p[0]=='.'):return self.match(s[1:],p[1:])else:return Falsea="aaab"
p="ab*ac*a"
s=Solution()
r=s.match(a,p)
print(r)
53.表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123",
"3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路：重点需要考察的是
1）是否有符号;符号只可能出现在开头和eE的后面
2）是否有. ; .只能出现一次,不能在eE附近,不能在eE后面,且前后必须为数字
3）是否有eE; e或E只能出现一次且不能在开头和末尾，前面只能是数字，后面只能是"+-0123456789"
4）是否在"0123456789"之间
class Solution:def isNumStr(self,s):hasDot=TruehasE=Truefor i in range(len(s)):if(s[i] in "+-" and (i==0 or (i<=len(s)-1 and s[i-1] in "Ee") ) ):continueelif hasDot and s[i]=='.':hasDot=Falseif i>=len(s)-1 or s[i+1] not in "0123456789":return Falseelif hasE and s[i] in 'eE':hasDot=FalsehasE=Falseif (i==0 or i>=len(s)-1) or (s[i-1] not in "0123456789") or (s[i+1] not in "+-0123456789"):return Falseelif s[i] not in "0123456789":return Falsereturn Trues=Solution()
r=s.isNumStr("-123.123e-10")
print(r)
54.字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，
第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
思路：声明一个字典记录每个字符出现的次数，遍历字符串，如果第一次出现次数为1的，则返回
class Solution:def findAppearOnce(self,s):char_num={}for c in s:if c not in char_num.keys():char_num[c]=1else:char_num[c]+=1for c in s:if char_num[c]==1:return creturn Nones=Solution()
r=s.findappearOnce("google")
print(r)
55.链表中环的入口节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：快慢指针，快指针走两步，慢指针走一步;当快指针fast与low指针相遇时，及找到了循环链表的入口
class Node:def __init__(self,val):self.val=valself.next=Noneclass Solution:def findEntryNodeOfLoop(self,head):if head ==None or head.next==None or head.next.next==None:return Nonefast=head.next.nextlow=head.nextwhile fast and low:if fast==low:return fastif fast.next==None or fast.next.next==None:return Nonefast=fast.next.nextlow=low.nextreturn None
56.删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。(leetcode82)
思路：1、因为是排序链表，重复的数都是挨着的，遍历一遍链表删除重复的数据
class Node:def __init__(self,val):self.val=valself.next=Noneclass Solution:def deleteDuplicatedNode(self,head):dupli=Node(-1) #避免第一个节点就是重复节点dupli.next=head cur=headlast=dupliwhile cur and cur.next:if cur.val==cur.next.val:val=cur.valwhile cur and val==cur.val:cur=cur.nextlast.next=curelse:last=curcur=cur.nextreturn dupli.nexta = Node(1)
b = Node(2)
c = Node(2)
d = Node(5)
e = Node(6)
f = Node(6)a.next = b
b.next = c
c.next = d
d.next = e
e.next = fs=Solution()
res = s.deleteDuplicatedNode(a)cur = res
while cur:print(cur.val)cur = cur.next
57.二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包
含左右子结点，同时包含指向父结点的指针。
给定二叉树:
3
/ \
9 20
/ \
15 7
思路：
1、如果该节点有右子树，那么它的下一个节点就是它的右子树的最左侧子节点；
2、如果该节点没有右子树且是父节点的左子树，那么下一节点就是父节点；
3、如果该节点没有右子树且是父节点的右子树，比如i节点，那么我们往上找父节点，找到一个节点满足：
它是它的父节点的左子树的节点。
class TreeNode:def __init__(self,val):self.val=valself.left=Noneself.right=Noneself.parent=Noneclass Solution:def findNext(self,root,p):if root==None:return Noneif p.right:res=p.rightwhile res.left:res=res.leftelse: while p.parent:res=p.parentif res.left==p:return resp=p.parentreturn resa = TreeNode(3)
b = TreeNode(9)
d = TreeNode(20)
e = TreeNode(15)
f = TreeNode(7)a.left, a.right = b, d
b.parent,d.parent=a,a
d.left, d.right = e,f
e.parent,f.parent=d,ds=Solution()
res = s.findNext(a,b)
print(res.val)
58.对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，
定义其为对称的。如下二叉树即为对称二叉树
1
/ \
2 2
/ \ / \
3 4 4 3
思路：递归地判断左右子树是否对称；递归结束条件，左右子树都为空,返回True,仅仅left或right为空
或左右子树的值不相等，返回False
class TreeNode:def __init__(self,val):self.val=valself.left=Noneself.right=Noneclass Solution:def isSymmertrical(self,root):if root==None:return Truereturn self.ismirror(root.left,root.right)def ismirror(self,left,right):if left==None and right==None:return Trueif left==None or right==None or left.val!=right.val:return Falsereturn self.ismirror(left.left,right.right) and self.ismirror(left.right,right.left)a = TreeNode(3)
b = TreeNode(9)
d = TreeNode(20)
e = TreeNode(15)
f = TreeNode(7)a.left, a.right = b, d
d.left, d.right = e,fs=Solution()
res = s.isSymmertrical(a)
print(res)
59.把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。（leetcode102题）
给定二叉树:
3
/ \
9 20
/ / \
6 15 7
返回其层次遍历结果：
[
[3],
[9,20],
[6,15,7]
]
思路：层次遍历二叉树；1、申请一队列q，存储当前层次节点；2、循环遍历队列q,pop开头节点cur，并
将cur.val结果存入列表t;3、将每层结果列表t存入最终结果res,循环2直到q为空
class TreeNode:def __init__(self,val):self.val=valself.left=Noneself.right=Noneclass Solution:def printTreeRow(self,root):q=[root]res=[]while q:t=[]cur_level_nodes=len(q)for i in range(cur_level_nodes):cur=q.pop(0)t.append(cur.val)if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)res.append(t)return resa = TreeNode(3)
b = TreeNode(9)
c=TreeNode(6)
d = TreeNode(20)
e = TreeNode(15)
f = TreeNode(7)a.left, a.right = b, d
d.left, d.right = e,f
b.left=cs=Solution()
res = s.printTreeRow(a)
print(res)
60.按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，
第三行按照从左到右的顺序打印，其他行以此类推。
给定二叉树:
3
/ \
9 20
/ / \
6 15 7
返回其层次遍历结果：
[
[3],
[20,9],
[6,15,7]
]
思路：层次遍历二叉树；1、申请一队列q，存储当前层次节点；2、循环遍历队列q,pop开头节点cur，并
将cur.val结果存入列表t; 3、如果是单行将每层结果列表t存入res,如果是双行，将t的反转存到res,
循环2直到q为空
class TreeNode:def __init__(self,val):self.val=valself.left=Noneself.right=Noneclass Solution:def printTreeRowZ(self,root):q=[root]res=[]flag=True #标识单层还是双层while q:t=[]cur_level_nodes=len(q)for i in range(cur_level_nodes):cur=q.pop(0)t.append(cur.val)if cur.left:q.append(cur.left)if cur.right:q.append(cur.right)if flag:res.append(t)flag=Falseelse:res.append(t[::-1])flag=Truereturn resa = TreeNode(3)
b = TreeNode(9)
c=TreeNode(6)
d = TreeNode(20)
e = TreeNode(15)
f = TreeNode(7)a.left, a.right = b, d
d.left, d.right = e,f
b.left=cs=Solution()
res = s.printTreeRowZ(a)
print(res)