剑指offer-python版（下）
31.从1到n的整数中1出现的个数
比如，1-13中，1出现6次，分别是1，10，11，12，13。
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
count = 0
for i in range(1,n+1):
j = i
while j > 0:
if j%10 == 1:
count += 1
j = j/10
return count
32.把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
思路： 根据题目的要求，两个数字m和n能拼接称数字mn和nm。如果mn<nm，也就是m应该拍在n的前面，我们定义此时m小于n；反之，如果nm<mn，我们定义n小于m。如果mn=nm,m等于n。
class Solution:
def PrintMinNumber(self, numbers):
if not len(numbers):
return ""
arr = [str(x) for x in numbers]
arr.sort(lambda x,y:cmp(x+y,y+x))
return int("".join(arr))
33.丑数
把只包含质因子2、3和5的数称作丑数。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路：动态规划的解法，首先确保数组里的已有的丑数是排好序的，同时要维护三个索引。
代码：
class Solution:
def GetUglyNumber_Solution(self, index):
if index<=0:
return 0
res = [1]
a, b, c = 0
while(len(res) < index):
nextMin = min(res[a] * 2,res[b] * 3,res[c] * 5)
res.append(nextMin)
while res[a] * 2 <= nextMin:
a += 1
while res[b] * 3 <= nextMin:
b += 1
while res[c] * 5 <= nextMin:
c += 1
return res[-1]
34.第一个只出现一次的字符
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）。
思路：创建哈希表，下标为ACII值，值为出现次数。
代码
class Solution:
def FirstNotRepeatingChar(self, s):
#建立哈希表,有256个字符，于是创建一个长度为256的列表
ls=[0]*256
#遍历字符串,下标为ASCII值,值为次数
for i in s:
ls[ord(i)]+=1 #ord()函数以一个字符作为参数，返回对应的ASCII数值
for j in s:
if ls[ord(j)]==1:
return s.index(j)
break
return -1
35.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
#使用归并排序的思路求解
class Solution:
def InversePairs(self, data):
if len(data) > 1:
mid = len(data) / 2
left_half = data[:mid]
right_half = data[mid:]
left_count = self.InversePairs(left_half)%1000000007
right_count = self.InversePairs(right_half)%1000000007
i,j,k,count = len(left_half)-1,len(right_half)-1,len(data)-1,0
while i >= 0 and j >= 0:
if left_half[i] < right_half[j]:
data[k] = right_half[j]
j = j - 1
k = k - 1
else:
data[k] = left_half[i]
count += (j+1)
i = i - 1
k = k - 1
while i >= 0:
data[k] = left_half[i]
k = k - 1
i = i - 1
while j>=0:
data[k] = right_half[j]
k = k - 1
j = j - 1
return (count + left_count + right_count)%1000000007
else:
return 0
36.两个链表的第一个公共结点
(leetcode160) 编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：
image
在节点 c1 开始相交。
注意：
- 如果两个链表没有交点，返回
null. - 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
分析
设置两个指针，一个从headA开始遍历，遍历完headA再遍历headB，另一个从headB开始遍历，遍历完headB再遍历headA，如果有交点，两个指针会同时遍历到交点处。
代码
class Solution(object):
def getIntersectionNode(self, headA, headB):
p1 = headA
p2 = headB
while p1 != p2:
if p1 == None:
p1 = headB
else:
p1 = p1.next
if p2 == None:
p2 = headA
else:
p2 = p2.next
return p2
37.统计一个数字在排序数组中的出现的次数
思路：考虑数组为空的情况，直接返回0；用二分查找法，找到i和j的位置。
class Solution:
def GetNumberOfK(self, data, k):
if len(data) == 0:
return 0
i = 0
j = len(data) - 1
while i < j and data[i] != data[j]:
if data[i] < k:
i += 1
if data[j] > k:
j -= 1
if data[i] != k:
return 0
return j-i+1
38.二叉树的深度
(同leetcode104)输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
思路
递归的方法，比较左边路径和右边路径哪边最长，选择最长的一边路径，加上root结点本身的长度。
代码
class Solution(object):
def maxDepth(self, root):
if root is None:
return 0
else:
return max(self.maxDepth(root.left),self.maxDepth(root.right))+1
39.平衡二叉树
（同leetcode110）输入一个二叉树，判断是否是平衡二叉树。
平衡二叉树：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 :
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
思路
利用104题中判断二叉树最大深度的函数，左子树和右子树的深度差小于等于1即为平衡二叉树。
代码
class Solution(object):
def isBalanced(self, root):
if root == None:
return True
elif abs(self.height(root.left)-self.height(root.right))>1:
return False
else:
return self.isBalanced(root.left) and self.isBalanced(root.right)
def height(self,root):
if root == None:
return 0
else:
return max(self.height(root.left),self.height(root.right))+ 1
40.数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
思路：如果数组中只有一个数字出现了一次，对数组所有数求一次异或，两个相同的数的异或是0。
那么如果数组中有两个数出现了一次，其他出现了两次，将这数组分成两个子数组，这两个数字分别出现在这两个子数组中，那么就转换成了前面所说的求异或的问题。那么怎么分呢，这里的思路是根据要求的这两个数的异或之后最右边不为1的这一位进行划分的。
代码
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
res = 0
for i in array:
res ^= i
splitBit = 1
while splitBit & res == 0:
splitBit = splitBit << 1
res1 = 0
res2 = 0
for i in array:
if i & splitBit == 0:
res1 ^= i
else:
res2 ^= i
return [res1,res2]
41.和为S的连续正数序列
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
思路：维护两个指针，一个指针指向这个连续正数序列的开始，一个指向连续正数序列的结束，判断当前的序列和与目标的关系，不断更新这两个指针的位置。
代码：
class Solution:
def FindContinuousSequence(self, tsum):
res = []
i = 1
j = 2
curSum = i + j
while i <= tsum/2:
if curSum == tsum:
res.append(range(i,j+1))
j = j + 1
curSum += j
elif curSum > tsum:
curSum -= i
i += 1
else:
j += 1
curSum += j
return res
42.和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
思路：由于是排好序的数组，因此对于和相等的两个数来说，相互之间的差别越大，那么乘积越小，因此我们使用两个指针，一个从前往后遍历，另一个从后往前遍历数组即可。
代码：
class Solution:
def FindNumbersWithSum(self, array, tsum):
if len(array)<2:
return []
i = 0
j = len(array)-1
while i < j:
if array[i]+array[j] > tsum:
j -= 1
elif array[i]+array[j] < tsum:
i += 1
else:
return [array[i],array[j]]
return []
43.左旋转字符串
对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
思路：分割法。
class Solution:
def LeftRotateString(self, s, n):
m = len(s)
res1 = s[n:m]
res2 = s[0:n]
res = res1+res2
return res
44.翻转单词顺序列
例如，“student. a am I”翻转为“I am a student.”。
思路：按空格切分为数组，依次入栈，再出栈(用空格连接)
class Solution:
def ReverseSentence(self, s):
if s is None or len(s) == 0:
return s
stack = []
for i in s.split(' '): #split()通过指定分隔符对字符串进行切片
stack.append(i)
res = ""
while len(stack) > 0:
res += stack.pop() + " "
res = res[:-1]
return res
45.扑克牌顺子
一副扑克牌,里面有2个大王，2个小王，从中随机抽出5张牌，如果牌能组成顺子就输出true，否则就输出false。为了方便起见，大小王是0，大小王可以当作任何数字。
思路：
1、将数组排序 ；2、统计数组中0的个数，即判断大小王的个数；3、统计数组中相邻数字之间的空缺总数，如果空缺数小于等于大小王的个数，可以组成顺子，否则不行。如果数组中出现了对子，那么一定是不可以组成顺子的。
代码：
class Solution:
def IsContinuous(self, numbers):
if not numbers:
return False
numbers.sort()
zeros = 0
while numbers[zeros]==0:
zeros = zeros + 1
for i in range(zeros,len(numbers)-1):
if numbers[i+1] == numbers[i] or (numbers[i+1] - numbers[i] - 1) > zeros:
return False
else:
zeros -= (numbers[i+1]-numbers[i]-1)
return True
46.孩子们的游戏（圆圈中最后剩下的数）
游戏是这样的：首先，让小朋友们围成一个大圈。然后，他随机指定一个数m，让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列，不再回到圈中，从他的下一个小朋友开始，继续0...m-1报数....这样下去....直到剩下最后一个小朋友获胜，获胜的小朋友编号多少？(注：小朋友的编号是从0到n-1)
class Solution:
def LastRemaining_Solution(self, n, m):
if not n and not m :
return -1
res = range(n)
i = 0
while len(res)>1:
i = (m+i-1)%len(res)
res.pop(i)
return res[0]
47.求1+2+3+...+n
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
思路：将加法问题转化为递归进行求解即可。
代码：
class Solution:
def __init__(self):
self.sum = 0
def Sum_Solution(self, n):
if n<=0:
return 0
self.getSum(n)
return self.sum
def getSum(self,n):
self.sum+=n
n = n - 1
return n>0 and self.getSum(n)
48.不用加减乘除做加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：
对数字做运算，除了加减乘除外，还有位运算，位运算是针对二进制的，二进制的运算有“三步走”策略：
例如5的二进制是101，17的二进制10001。
第一步：各位相加但不计进位，得到的结果是10100。
第二步：计算进位值，只在最后一位相加时产生一个进位，结果是二进制10。
第三步：把前两步的结果相加，得到的结果是10110。转换成十进制正好是22。
接着把二进制的加法用位运算替代：
（1）不考虑进位对每一位相加，0加0、1加1的结果都是0，1加0、0加1的结果都是1。这和异或运算相同。（2）考虑进位，只有1加1的时候产生进位。 位与运算只有两个数都是1的时候结果为1。考虑成两个数都做位与运算，然后向左移一位。（3）相加的过程依然重复前面两步，直到不产生进位为止。
#当一个正数和一个负数相加时，陷入死循环
class Solution:
def Add(self, num1, num2):
while num2!=0:
sum = num1^num2
carry = (num1&num2)<<1
num1 = sum
num2 = carry
return num1
当一个正数和一个负数相加时，陷入死循环。实际上，在进行负数的按位加法时，有可能发生在最高位还要向前进一位的情形，正常来说，这种进位因为超出了一个int可以表示的最大位数，应该舍去才能得到正确的结果。因此，对于Java，c，c++这样写是正确的。而对于Python，却有点不同。
在早期版本中如Python2.7中，整数的有int和long两个类型。int类型是一个固定位数的数；long则是一个理论上可以存储无限大数的数据类型。当数大到可能溢出时，为了避免溢出，python会把int转化为long。而Python3.x之后整数只有一个可以放任意大数的int了。可是无论哪种，都是采用了特殊的方法实现了不会溢出的大整数。 所以会使程序无限的算下去，这也是Python效率低的一个原因。（python2和python3都有这个问题。）
已经知道了右移过程中大整数的自动转化，导致变不成0，那么只需要在移动的过程中加一下判断就行了，把craay的值和0xFFFFFFFF做一下比较就可以了，具体代码如下所示。
class Solution:
def Add(self, num1, num2):
while num2:
sum = num1 ^ num2
carry = 0xFFFFFFFF&(num1 & num2)<<1
carry = -(~(carry - 1) & 0xFFFFFFFF) if carry > 0x7FFFFFFF else carry
num1 = sum
num2 = carry
return num1
49.把字符串转换成整数
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
输入描述:
输入一个字符串,包括数字字母符号,可以为空
输出描述:
如果是合法的数值表达则返回该数字，否则返回0
示例1：
输入：+2147483647 ，输出：2147483647；输入：1a33，输出：0。
代码：
class Solution:
def StrToInt(self, str):
str = str.strip()
if not str:
return 0
number, flag = 0, 1
#符号位的判断是否有正负号
if str[0] == '-':
str = str[1:]
flag = -1
elif str[0] == '+':
str = str[1:]
#遍历除+，-以外的所有字符，如果遇到非数字，则直接返回0
for c in str:
if c >= '0' and c <= '9':
number = 10*number + int(c)
else:
return 0
number = flag * number
return number
50.数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
思路：一个简单的方法是先排序再查找，时间复杂度是O(nlogn)。还可以用哈希表来解决，遍历每个数字，每扫描到一个数字可以用O(1)的时间来判断哈希表中是否包含了这个数字，如果没有包含，则加到哈希表，如果包含了，就找到了一个重复的数字。时间复杂度O(n)。
我们注意到数组中的数字都在0~n-1范围内，如果这个数组中没有重复的数字，那么当数组排序后数字i在下标i的位置，由于数组中有重复的数字，有些位置可能存在多个数字，同时有些位置可能没有数字。遍历数组，当扫描到下标为i 的数字m时，首先看这个数字是否等于i，如果是，继续扫描，如果不是，拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了一个重复的数字，如果不相等，就交换两个数字。继续比较。
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
for i in range(len(numbers)):
while numbers[i] != i:
m = numbers[i]
if numbers[m] == numbers[i]:
duplication[0] = m
return True
else:
numbers[i] = numbers[m]
numbers[m] = m
return False
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]。不能使用除法。
思路：如果没有不能使用除法的限制，可以直接用累乘的结果除以A[i]。由于题目有限制，一种直观的解法是连乘n-1个数字，但时间复杂度是O(n^2)。可以把B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]分成A[0]A[1]...A[i-1]和A[i+1]...*A[n-1]两部分的乘积。
class Solution:
def multiply(self, A):
C,D = [],[]
for i in range(len(A)):
if i == 0:
C.append(1)
else:
C.append(C[i-1]*A[i-1])
for i in range(len(A)):
if i == 0:
D.append(1)
else:
D.append(D[i-1]*A[len(A)-i])
D = D[::-1]
B = []
for i in range(len(A)):
B.append(C[i]*D[i])
return B
52.正则表达式匹配
请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配。
思路：如果 s和pattern都为空，匹配成功。
当模式中的第二个字符不是*时：（1）如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的；（2）如果字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。
而当模式中的第二个字符是*时：（1）模式后移2字符，相当于x*被忽略；（2）字符串后移1字符，模式后移2字符。
代码
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
if s == pattern:
return True
if len(pattern)>1 and pattern[1] == '*':
if s and (s[0]==pattern[0] or pattern[0] == '.'):
return self.match(s,pattern[2:]) or self.match(s[1:],pattern)
else:
return self.match(s,pattern[2:])
elif s and pattern and (s[0] == pattern[0] or pattern[0]=='.'):
return self.match(s[1:],pattern[1:])
return False
53.表示数值的字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路：数字的格式可以用A[.[B]][E|eC]或者.B[E|eC]表示，其中A和C都是整数（可以有符号也可以没有），B是一个无符号数。
如果遍历到e或E，那么之前不能有e或E，并且e或E不能在末尾；
如果遍历到小数点,那么之前不能有小数点，并且之前不能有e或E；
如果遍历到正负号，那么如果之前有正负号，只能够出现在e或E的后面，如果之前没符号，那么符号只能出现在第一位，或者出现在e或E的后面；
如果遍历到不是上面所有的符号和0~9，返回False。
代码：
class Solution:
# s字符串
def isNumeric(self, s):
hasE = False
hasDot = False
hasSign = False
for i in range(len(s)):
if s[i] == 'e' or s[i] == 'E':
if hasE or i == len(s) - 1:
return False
hasE = True
elif s[i] == '.':
if hasDot or hasE:
return False
hasDot = True
elif s[i] == '+' or s[i] == '-':
if hasSign and s[i - 1] != 'e' and s[i - 1] != 'E':
return False
if not hasSign:
if i != 0 and s[i - 1] != 'e' and s[i - 1] != 'E':
return False
hasSign = True
else:
if s[i] < '0' or s[i] > '9':
return False
return True
54.字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
如果当前字符流没有存在出现一次的字符，返回#字符。
思路：用一个字典保存下出现过的字符，以及字符出现的次数。
除保存出现的字符之外，我们用一个字符数组保存出现过程字符顺序，如果不保存插入的char的话，我们可以遍历ascii码中的字符。
代码：
class Solution:
# 返回对应char
def __init__(self):
self.s=''
self.dict1={}
def FirstAppearingOnce(self):
for i in self.s:
if self.dict1[i]==1:
return i
return '#'
def Insert(self, char):
self.s=self.s+char
if char in self.dict1:
self.dict1[char]=self.dict1[char]+1
else:
self.dict1[char]=1
55.链表中环的入口节点
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：快慢指针，快指针一次走两步，慢指针一次走一步。如果链表中存在环，且环中假设有n个节点，那么当两个指针相遇时，快的指针刚好比慢的指针多走了环中节点的个数，即n步。从另一个角度想，快的指针比慢的指针多走了慢的指针走过的步数，也是n步。相遇后，快指针再从头开始走，快慢指针再次相遇时，所指位置就是入口。
代码：
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
if pHead==None or pHead.next==None or pHead.next.next==None:
return None
low=pHead.next
fast=pHead.next.next
while low!=fast:
if fast.next==None or fast.next.next==None:
return None
low=low.next
fast=fast.next.next
fast=pHead
while low!=fast:
low=low.next
fast=fast.next
return fast
56.删除链表中重复的结点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。(leetcode82)
思路
1.设置一个虚拟头结点，设置两个指针，pre指向虚拟头结点，cur指向头结点。
image
2.判断下一个节点的值和cur的值是否相等，若相等cur后移，直到下个节点的值和cur的值不同。
image
3.此时执行pre.next= cur.next。
image
4.继续走直到结尾.
image
代码
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def deleteDuplicates(self, head):
dummy = ListNode(-1)
dummy.next = head
pre = dummy
cur = head
while cur:
while cur.next and cur.val == cur.next.val:
cur = cur.next
if pre.next == cur:
pre = pre.next
else:
pre.next = cur.next
cur = cur.next
return dummy.next
57.二叉树的下一个结点
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：如下图所示，二叉树的中序遍历序列是{d,b,h,e,i,a,f,c,g}。
image
1、如果该节点有右子树，那么它的下一个节点就是它的右子树的最左侧子节点；
2、如果该节点没有右子树且是父节点的左子树，那么下一节点就是父节点；
3、如果该节点没有右子树且是父节点的右子树，比如i节点，那么我们往上找父节点，找到一个节点满足： 它是它的父节点的左子树的节点。
代码：
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
if not pNode:
return None
if pNode.right:
res = pNode.right
while res.left:
res = res.left
return res
while pNode.next:
tmp = pNode.next
if tmp.left == pNode:
return tmp
pNode = tmp
return None
58.对称的二叉树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。（leetcode101题）
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
思路
递归的思想，首先判断头结点是否为空。然后将根节点的左右两个节点假设成两个独立的树，如果左右两个树都为空，返回True。然后看左子树的左结点和右子树的右结点、左子树的右结点和右子树的左结点是否相同，都相同返回True.
代码
class Solution:
def isSymmetrical(self, pRoot):
if pRoot is None:
return True
return self.isSymmetricTree(pRoot.left,pRoot.right)
def isSymmetricTree(self,left,right):
if left is None and right is None:
return True
if left is None or right is None or left.val != right.val:
return False
return self.isSymmetricTree(left.left,right.right) and self.isSymmetricTree(left.right,right.left)
59.把二叉树打印成多行
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。（leetcode102题）
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
思路
用队列实现，root为空，返回空；队列不为空，记下此时队列中的节点个数temp，temp个节点出队列的同时，记录节点值，并把节点的左右子节点加入队列中。
代码
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Print(self, pRoot):
queue = [pRoot]
res = []
if not pRoot:
return []
while queue:
templist = []
templen = len(queue)
for i in range(templen):
temp = queue.pop(0)
templist.append(temp.val)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
res.append(templist)
return res
60.按之字形顺序打印二叉树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
思路
在上一题的基础上，加上flag标志判断，若flag为负表示偶数行，从右往左遍历。
代码
class Solution:
def Print(self, pRoot):
queue = [pRoot]
res = []
flag = 1 #判断flag是否为负，如果为负表示偶数行，从右往左遍历
if not pRoot:
return []
while queue:
templist = []
templen = len(queue)
for i in range(templen):
temp = queue.pop(0)
templist.append(temp.val)
if temp.left:
queue.append(temp.left)
if temp.right:
queue.append(temp.right)
if flag == -1:
templist = templist[::-1] #反转
res.append(templist)
flag *= -1
return res
61.二叉搜索树的第K个节点
给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。
image
思路：如果是按中序遍历二叉搜索树的话，遍历的结果是递增排序的。所以只需要中序遍历就很容易找到第K个节点。
class Solution:
def __init__(self):
self.my_list = [] # 用于保存中序遍历的序列的结点
def in_order(self, pRoot): # 中序遍历二叉树，并把结果保存到my_list中
if not pRoot:
return None
if pRoot.left:
self.in_order(pRoot.left)
self.my_list.append(pRoot)
if pRoot.right:
self.in_order(pRoot.right)
def KthNode(self, pRoot, k):
self.in_order(pRoot)
if k <= 0 or k > len(self.my_list): # 越界
return None
return self.my_list[k - 1]
62.滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：{[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]}。
思路1：求每次窗口的最大值，时间复杂度O(n*size)。
class Solution:
def maxInWindows(self, num, size):
res = []
i = 0
while size > 0 and i + size - 1 < len(num):
res.append(max(num[i:i + size]))
i += 1
return res
思路2：双向队列，queue存入num的位置，时间复杂度O(n)
class Solution:
def maxInWindows(self, num, size):
queue = []
res = []
i = 0
while size>0 and i<len(num):
if len(queue)>0 and i-size+1 > queue[0]: #若最大值queue[0]位置过期 则弹出
queue.pop(0)
while len(queue)>0 and num[queue[-1]]<num[i]: #每次弹出所有比num[i]的数字
queue.pop()
queue.append(i)
if i>=size-1:
res.append(num[queue[0]])
i += 1
return res
64.矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如，在下面的3 X 4 矩阵中包含一条字符串"bfce"的路径，但是矩阵中不包含"abfb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
a b t g
c f c s
j d e h
思路：回溯法。首先，遍历矩阵中的格子，直到找到一个和字符串第一个字符相同的格子，把这个格子作为这个路径进入矩阵的起点。除了在边界的格子之外，其他各自都有4个相邻的格子。如果矩阵中的某个格子的字符不是ch，那么这个格子不可能处在路径上的第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，说明第n个字符不对，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符即可。
由于路径不能重复进入矩阵的格子，因此需要定义一个和矩阵相同大小的布尔值矩阵，作为当前已经找过的路径是否经过某个格子的标识。 当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置。
class Solution:
def dfs(self,matrix,flag,rows,cols,r,c,s):
if s=='':
return True
dx = [-1,1,0,0]
dy = [0,0,-1,1] # 利用两个数组，来实现对每个格子周围格子的访问
for k in range(4):
x = dx[k] + r
y = dy[k] + c
if x >= 0 and x < rows and y >= 0 and y < cols and flag[x][y] and matrix[x*cols+y]==s[0]:
flag[x][y]=False # 修改当前格子的标识
if self.dfs(matrix,flag[:],rows,cols, x, y,s[1:]): # 递归
return True
flag[x][y]=True
# 如果上一个判断条件返回的是False，那么就说明这个格子目前还不是路径上的格子，再把当前格子的标识修改回来。
return False
def hasPath(self, matrix, rows, cols, path):
if path == '':
return True
flag = [[True for c in range(cols)] for r in range(rows)] # 定义一个表示矩阵
for r in range(rows):
# 对这个矩阵中的元素进行遍历，不断找路径进入矩阵的起点，直到以某个格子为起点找到整个路径为止。
for c in range(cols):
if matrix[r*cols+c] == path[0]:
flag[r][c] = False
if self.dfs(matrix,flag[:],rows,cols, r, c,path[1:]):
return True
flag[r][c] = True
return False
65.机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路：还是利用递归对矩阵进行深度优先搜索，从（0,0）位置出发，每成功走一步标记当前位置为true,然后从当前位置往四个方向探索，返回1 + 4 个方向的探索值之和。判断当前节点是否可达的标准为：当前节点在矩阵内；当前节点未被访问过；当前节点满足K的限制。
class Solution:
def __init__(self): # 机器人可以倒回来，但不能重复计数。
self.count = 0
def movingCount(self, threshold, rows, cols):
flag = [[1 for i in range(cols)] for j in range(rows)]
self.findWay(flag,0,0,threshold) # 从（0，0）开始走
return self.count
def findWay(self,flag,i,j,k):
if i >= 0 and j >= 0 and i < len(flag) and j < len(flag[0]) and sum(list(map(int,str(i)))) + sum(list(map(int,str(j)))) <= k and flag[i][j] == 1:
flag[i][j] = 0
self.count += 1
self.findWay(flag,i-1,j,k)
self.findWay(flag,i+1,j,k)
self.findWay(flag,i,j-1,k)
self.findWay(flag,i,j+1,k)
发布于 2019-07-31
