41 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
if not array:
return []
i = 0
j = len(array) - 1
num = 0
while i < j:
if array[i] + array[j] == tsum:
return array[i],array[j]
else:
if array[i] + array[j] > tsum:
j = j-1
else:
i = i+1
return [] 思路：双指针法，头尾各一个指针，当值大于tsum后指针前移，反之前指针后移，若相遇则退出
易错点: 注意指针移动的条件，由于是递增的数组因此最先找到的一定是乘积最小的，注意返回的是[]，不是None
42 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
if not s:
return ''
return s[n:]+s[:n] 思路1：利用python中的字符串切片函数解决
res1 = self.strreverse(s[0:n]) #三次反转解决，注意字符串反转的几种方法，但是reverse只能直接对List使用
res2 = self.strreverse(s[n:])
res = res1 + res2
res = self.strreverse(res)
return res
def strreverse(self,temp):
return temp[::-1] 思路2：剑指offer的思路，利用三次反转来解决。
43 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
res = s.split(' ')
res.reverse()
res = ' '.join(res)
return res
思路1：利用分割与合并函数
注意：str与List的转换方法
# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
res = self.resverseone(s)
res = res.split(' ')
res1 = []
for i in res:
i = self.resverseone(i)
res1.append(i)
return ' '.join(res1)
def resverseone(self,s):
temp = []
news = ''
for i in s:
temp.append(i)
for i in s:#重要
news = news+temp.pop()
return news
思路2：剑指offer思路，先反转整体，再逐个反转
易错点：！反转函数的第二次循环，不能写成in temp。因为在pop的时候，temp的长度一直在改变。可以写成 range(len(temp))
44 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if not numbers:
return False
numbers.sort()
num0 = numbers.count(0)
if num0 == 0:
temp = set(numbers)
if max(temp)-min(temp) == 4 and len(temp)==5:
return True
else:
return False
elif num0 == 1:
numbers.remove(0)
temp = set(numbers)
if max(temp)-min(temp) <= 4 and len(temp)==4:
return True
else:
return False
elif num0 == 2:
print(1)
temp = set(numbers)
temp.remove(0)
if max(temp)-min(temp) <= 4 and len(temp)==3:
return True
else:
return False
elif num0 ==3:
print(1)
temp = set(numbers)
temp.remove(0)
if max(temp)-min(temp) <= 4 and len(temp)==2:
return True
else:
return False
elif num0 ==4:
return True 思路：根据0的数量分类讨论
注意点：存在0的时候先remove，利用set去重，题目中有四个大小王
链接：https://www.nowcoder.com/questionTerminal/762836f4d43d43ca9deb273b3de8e1f4
来源：牛客网
1、如果输入为空，返回false
2、除了王的任何某个特定数值的牌出现两张或者更多，那么一定凑不齐顺子。
思路，先统计王的数量，再把牌排序，如果后面一个数比前面一个数大于1以上，那么中间的差值就必须用王来补了。看王的数量够不够，如果够就返回true，否则返回false。
def IsContinuous(self, numbers):
if not numbers:return False
numbers.sort()
zeroNum = numbers.count(0)
for i, v in enumerate(numbers[:-1]):
if v != 0:
if numbers[i+1]==v:return False
zeroNum = zeroNum - (numbers[i + 1] - v) + 1
if zeroNum < 0:
return False
return True 思路2：来自评论区，见注释。
思路3：1. 除0外没有重复的数 2. max - min < 5
45 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
（即是著名的约瑟夫环问题）
if n < 1 :
return -1 #异常输入
start = 0 #每次的开头
con = range(n)
while con:
final = (start + m -1 ) %n #关键，确定本轮的位置
res = con.pop(final) #res记录每次弹出的值，最后更新为最后的值
n = n - 1 #长度变小
start = final # 弹出后，从此处开始，由于前一个弹出这时的final的相对位置，已经往后一位了
return res 思路：每次都计算一次本轮位置。模拟这个过程。
递归解法：
if n == 0:
return -1
if n == 1:
return 0
else:
return ((self.LastRemaining_Solution(n-1,m)+m)%n)
通过率：83.3%，超过递归深度
循环解法：
if n < 1:
return -1
last = 0
i = 2
while i<=n:
last = (last+m)%i
i += 1
return last
思路2：找出递推公式，
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)
具体参考见 https://blog.csdn.net/u011500062/article/details/72855826 超清晰。
转载：理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。因为求出的结果是数组中的下标，最终的编号还要加1
注意7的下标变化。
构造链表 https://blog.csdn.net/hj7jay/article/details/79956867
递归理解：https://blog.csdn.net/yanweibujian/article/details/50876631，也很清晰
46 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
# write code here 短路求值
ans = n
temp = ans and self.Sum_Solution(n-1)
ans = ans + temp
return ans
思路：短路求值，&&就是逻辑与，逻辑与有个短路特点，前面为假，后面不计算。利用了递归。
等同于：
if n == 0:
return 0
ans = n
ans = ans + self.Sum_Solution(n-1)
return ans
上边是正常的递归条件。本题中用短路求值代替了判断n==0的情形。
47 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
# -*- coding:utf-8 -*-
class Solution:
def Add(self, a, b): #越界检查，正负数判断
while(b): #有进位的时候
a,b = (a^b) & 0xFFFFFFFF,((a&b)<<1) & 0xFFFFFFFF #a为直接加不考虑进位，b为进位，知道没有进位结束
return a if a<=0x7FFFFFFF else ~(a^0xFFFFFFFF)
思路：分三步
a.先求直接加不考虑进位，二进制中用异或运算
b.再求进制，通过求与运算之后左移一位
c.两者相加，有进位再循环
易错点：python没有无符号右移操作，需要越界检查，详细解释https://blog.csdn.net/lrs1353281004/article/details/87192205
48 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
if not s:
return 0
if s[0] not in ['0','1','2','3','4','5','6','7','8','9','+','-']: #判断首字符
return 0
for i in s[1:]:
if i not in ['0','1','2','3','4','5','6','7','8','9']: #判断后面字符
return 0
res = 0 #分情况讨论
if s[0] =='+':
length = len(s)-2
j = 0
for i in s[1:]:
res = self.findnum(i)*10**(length-j)+res
j = j+1
return res
elif s[0] == '-':
length = len(s)-2
j = 0
for i in s[1:]:
res = self.findnum(i)*10**(length-j)+res
j = j+1
return -1*res
else:
length = len(s)-1
j = 0
for i in s:
res = self.findnum(i)*10**(length-j)+res
j = j+1
return res
def findnum(self,n): #用索引的形式返回其对应的整数值
res = ['0','1','2','3','4','5','6','7','8','9']
return res.index(n)
思路：先确定字符串合法化，随后通过索引的形式判断每个字符对应的整数，最后进行运算即可。
易错点：
摘自评论区：
边界条件：
数据上下 溢出
空字符串
只有正负号
有无正负号
错误标志输出
49 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
if not numbers:
return False
res = []
for i in numbers:
if i not in res:
res.append(i)
else:
duplication[0] = i
return True
return False 思路：建立一个链表，如果不在里面，添加，若在，返回
易错点：注意本题目中对输出的要求。
def duplicate(self, numbers, duplication):
if not numbers:
return False
for i,j in enumerate(numbers):
while numbers[i] != i:
if numbers[i] == numbers[numbers[i]]:
duplication[0] = numbers[i]
return True
temp = numbers[i]
numbers[i] = numbers[temp]
numbers[temp] = temp
return False 思路2：书上的思路，可以使空间复杂度为O(1)，但是改变了原数组。链接：https://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8
来源：牛客网
1、判断输入数组有无元素非法
2、从头扫到尾，只要当前元素值与下标不同，就做一次判断,numbers[i]与numbers[numbers[i]]，相等就认为找到了
重复元素，返回true,否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素，返回false
*/
思路3：类似于二分查找，可以不改变原数组。以时间换空间。
50 给定一个数组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 multiply(self, A):
B = []
for n,i in enumerate(A):
res = 1
for j in A[:n]+A[n+1:]:
res = res*j
B.append(res)
return B 思路1：暴力法，按公式实现
易错点： A[:n]+A[n+1:]，而不是 A[:n]+A[n:]
def multiply(self, A):
# write code here
#计算上下两个三角，然后相乘
length = len(A)
B = list(range(length)) #初始化链表
if length: #不要写成while
B[0] = 1
for i in range(1,length): #下三角
B[i] = B[i - 1] * A[i -1]
temp = 1
for j in range(length-2,-1,-1): #range的用法很重要
temp = temp * A[j+1] #上三角
B[j] = temp * B[j] #上下三角相乘
return B 思路2：上下三角法。如图。
51 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
# -*- coding:utf-8 -*-
'''
题目：请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符（不包括空字符！），而'*'表示它前面的字符可以出现任意次（包含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
'''
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# 如果s与pattern都为空，则True
if len(s) == 0 and len(pattern) == 0:
return True
# 如果s不为空，而pattern为空，则False
elif len(s) != 0 and len(pattern) == 0:
return False
# 如果s为空，而pattern不为空，则需要判断
elif len(s) == 0 and len(pattern) != 0:
# pattern中的第二个字符为*，则pattern后移两位继续比较
if len(pattern) > 1 and pattern[1] == '*':
return self.match(s, pattern[2:])
else:
return False
# s与pattern都不为空的情况
else:
# pattern的第二个字符为*的情况
if len(pattern) > 1 and pattern[1] == '*':
# s与pattern的第一个元素不同，则s不变，pattern后移两位，相当于pattern前两位当成空
if s[0] != pattern[0] and pattern[0] != '.':
return self.match(s, pattern[2:])
else:
# 如果s[0]与pattern[0]相同，且pattern[1]为*，这个时候有三种情况
# pattern后移2个，s不变；相当于把pattern前两位当成空，匹配后面的
# pattern后移2个，s后移1个；相当于pattern前两位与s[0]匹配
# pattern不变，s后移1个；相当于pattern前两位，与s中的多位进行匹配，因为*可以匹配多位
return self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:]) or self.match(s[1:], pattern)
# pattern第二个字符不为*的情况
else:
if s[0] == pattern[0] or pattern[0] == '.':
return self.match(s[1:], pattern[1:]) 思路：代码来自评论区。重点是对于*的讨论。详情见注释。
52 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
# -*- coding:utf-8 -*-
class Solution:
# s字符串
def isNumeric(self, s):
# write code here
#标记小数点，符号，E是否出现过
sign = False
decimal = False
hasE = False
for i in range(len(s)): #遍历字符串
if s[i] =='e' or s[i] == 'E': #遇到E的情况
if i == len(s) - 1: return False #E不能在最后一位
if hasE: return False#E不能有第二次
hasE = True #将E的标志改变
elif s[i] =='+' or s[i] =='-': #出现符号的情况
if sign and s[i-1] != 'e' and s[i-1] !='E': return False #存在第二个符号而且前面不是E
if not sign and i > 0 and s[i-1] != 'e' and s[i-1] !='E' :#不在第一位出现符号且前面不是E
return False
sign = True
elif s[i] =='.': #点只能一次且不能在E之后
if hasE or decimal:
return False
decimal = True
elif s[i] < '0' or s[i] > '9': #判断有无特殊字符
return False
return True
思路：重点关注几个特殊符号，设定标志位，然后按情况分别判断。
参考：
链接：https://www.nowcoder.com/questionTerminal/6f8c901d091949a5837e24bb82a731f2
来源：牛客网
class Solution {
public:
bool isNumeric(char* str) {
// 标记符号、小数点、e是否出现过
bool sign = false, decimal = false, hasE = false;
for (int i = 0; i < strlen(str); i++) {
if (str[i] == 'e' || str[i] == 'E') {
if (i == strlen(str)-1) return false; // e后面一定要接数字
if (hasE) return false; // 不能同时存在两个e
hasE = true;
} else if (str[i] == '+' || str[i] == '-') {
// 第二次出现+-符号，则必须紧接在e之后
if (sign && str[i-1] != 'e' && str[i-1] != 'E') return false;
// 第一次出现+-符号，且不是在字符串开头，则也必须紧接在e之后
if (!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E') return false;
sign = true;
} else if (str[i] == '.') {
// e后面不能接小数点，小数点不能出现两次
if (hasE || decimal) return false;
decimal = true;
} else if (str[i] < '0' || str[i] > '9') // 不合法字符
return false;
}
return true;
}
}; 53 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
# -*- coding:utf-8 -*-
'''
题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
'''
class Solution:
def __init__(self):
self.char_list = [-1 for i in range(256)] #定义一个数组，初始化-1
self.index = 0 # 记录当前字符的个数，可以理解为输入的字符串中的下标
'''
解法：利用一个int型数组表示256个字符，这个数组初值置为-1.
每读出一个字符，将该字符的位置存入字符对应数组下标中。
若值为-1标识第一次读入，不为-1且>0表示不是第一次读入，将值改为-2.
之后在数组中找到>0的最小值，该数组下标对应的字符为所求。
在python中，ord(char)是得到char对应的ASCII码；chr(idx)是得到ASCII位idx的字符
'''
def FirstAppearingOnce(self):
# write code here
min_value = 500
min_idx = -1
for i in range(256):#遍历这个数组
if self.char_list[i] > -1: #如果当前值不是负数，则肯定是第一次更改过的
if self.char_list[i] < min_value: #这一步为了找到最小的值，也就是最小的索引。即第一个出现的。
min_value = self.char_list[i] #每次都更新最小值
min_idx = i #记录i
if min_idx > -1: #如果min_idx被更改过
return chr(min_idx) #chr(idx)是得到ASCII位idx的字符
else:
return '#'
def Insert(self, char):
# 如果是第一出现，则将对应元素的值改为下边
if self.char_list[ord(char)] == -1:
self.char_list[ord(char)] = self.index #将字符流中的位置保存在容器
# 如果出现过一次，则进行修改，修改为-2
else: #第二次或以上次数出现，将其位置换成-2
self.char_list[ord(char)] = -2
self.index += 1 #字符流位置加1
或写成：
# -*- coding:utf-8 -*-
'''
题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
'''
class Solution:
def __init__(self):
self.char_list = [-1 for i in range(256)] #定义一个数组，初始化-1
self.index = 0 # 记录当前字符的个数，可以理解为输入的字符串中的下标
'''
解法：利用一个int型数组表示256个字符，这个数组初值置为-1.
每读出一个字符，将该字符的位置存入字符对应数组下标中。
若值为-1标识第一次读入，不为-1且>0表示不是第一次读入，将值改为-2.
之后在数组中找到>0的最小值，该数组下标对应的字符为所求。
在python中，ord(char)是得到char对应的ASCII码；chr(idx)是得到ASCII位idx的字符
'''
def FirstAppearingOnce(self):
# write code here
res = []
for i in range(256):#遍历这个数组
if self.char_list[i] > -1: #如果当前值不是负数，则肯定是第一次更改过的
res.append(self.char_list[i])
if res: #如果min_idx被更改过
return chr(self.char_list.index(min(res))) #找出索引最小的值所对应的i值，即ascii码
else:
return '#'
def Insert(self, char):
# 如果是第一出现，则将对应元素的值改为下边
if self.char_list[ord(char)] == -1:
self.char_list[ord(char)] = self.index #将字符流中的位置保存在容器
# 如果出现过一次，则进行修改，修改为-2
else: #第二次或以上次数出现，将其位置换成-2
self.char_list[ord(char)] = -2
self.index += 1 #字符流位置加1
思路：每次读取一个字符，将其在位置index保存在下标为其ascii码的数组里。当再次读取，发现某ascii对应的数组位不是初始值，则将其改成-2。在查找最小值的时候，找出数组的不为-1或者-2的值，即出现过一次的值，再找其对应的index最小，即最先出现，即数组中值最小的，然后就可以根据其数组下标，求得其对应的值了。
易错点：搞清楚建立的数组，下标与其中的值分别对应的是什么，题目就不难了。
54 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
def EntryNodeOfLoop(self, pHead):
if not pHead:
return None
res = []
p1 = pHead
while p1 not in res:
res.append(p1)
if p1.next: #注意没用环的情况
p1 = p1.next
else:
return None
return p1 思路：用一个列表记录出现过的结点，如果有重复，则返回这个值
易错点：注意没环的情况，即p1.next不一定存在
def EntryNodeOfLoop(self, pHead):
if not pHead:
return None
fast = pHead
low = pHead #快慢结点
clength = 1 #记录环的长度
while fast.next: #当fast没走到头时候
fast = fast.next.next #走两步
low = low.next
if fast == low:
lownew = low.next #计算环的长度
while low != lownew:
clength += 1
lownew = lownew.next
p1 = pHead
p2 = pHead
for i in range(clength):
p2 = p2.next
while p1 != p2:
p1 = p1.next
p2 = p2.next
return p1
return None 思路2：来自剑指offer书，先让一快一慢指针走，相遇说明存在环。之后原地行进，绕一圈记录环的长度。最后指针P2在链表上向前移动n步，然后两个指针以相同的速度向前移动。相遇即为环节点。
易错点：注意环长度的计算部分。
55 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
def deleteDuplication(self, pHead):
if not pHead: #异常输入判断
return None
pre = ListNode(-1) #头节点的前一个节点
pre.next = pHead
first = pre #备份这个节点
now = pHead #当前节点
while now.next: #当未到最后一个结点
if now.val == now.next.val: #如果相等
while now.next and now.val == now.next.val: #相等则一直往后
now = now.next
pre.next = now.next #前一个节点指向重复节点最后一位的后一个节点
now = pre #将工作节点从重复节点的最后一位设定为前一位
pre = now #将前一位设置为当前节点
if now.next: #如果不是最后一位，则当前节点设定为
now = now.next
return first.next #返回备份节点的后一个节点 思路：使前一个节点始终指向重复节点的后一个节点，
注意点：要定义一个头节点前的节点，因为头节点也可能重复；在删除完重复后，记得把now前移到不重复的节点。
同思路代码：
def deleteDuplication(self, pHead):
first = ListNode(-1)
first.next = pHead
pre = first
cur = pHead
while cur != None:
Dup = False
#while cur.val == cur.next.val and cur.next != None:
while cur.next != None and cur.val == cur.next.val: #先后顺序！！
Dup = True
cur = cur.next
if not Dup:
pre = cur
cur = cur.next
else:
pre.next = cur.next
cur = cur.next #dont forget
return first.next 56 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
#找规律，分三种情况讨论（评论区）
def GetNext(self, pNode):
if not pNode:
return None
if pNode.right:
pNode = pNode.right
while pNode.left:
pNode = pNode.left
return pNode
while pNode.next:
if pNode.next.left == pNode:
return pNode.next
pNode = pNode.next
思路1：书上解法。链接：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e
来源：牛客网
分析二叉树的下一个节点，一共有以下情况：
1.二叉树为空，则返回空；
2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；
3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。如图。
def GetNext(self, pNode):
if not pNode:
return None
proot = pNode
while proot.next:
proot = proot.next
self.res = []
self.mid(proot)
index = self.res.index(pNode)
if index+1 < len(self.res):
return self.res[index+1]
else:
return None
def mid(self,proot):
if not proot: #基准条件
return
self.mid(proot.left)
self.res.append(proot) #添加的是结点不是值
self.mid(proot.right)
思路2：
链接：https://www.nowcoder.com/questionTerminal/9023a0c988684a53960365b889ceaf5e
来源：牛客网
思路，如果这道题是求中序遍历，肯定很简单。所以我们先写一个中序遍历的算法。关键是从根节点开始遍历，所以第一步还是找到某个节点的根节点，方法是一直使用next判断即可。再将从根节点中序遍历的结果保存到一个数组中，直接找pNode所在索引的下一个即可。当然要考虑这个节点是不是最后一个，如果是最后一个，直接返回None。
易错点：注意先判断index+1是不是大于数组范围了。不能判断res[index+1]是否存在，这样本身就不合法。另外要注意添加的是节点不是val。中序遍历要有return即基准条件。
57 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
def isSymmetrical(self, pRoot):
if not pRoot:
return True
return self.compare(pRoot.left,pRoot.right)
def compare(self,left,right):
if not left and not right:
return True
if not left or not right:
return False
if left.val == right.val:
if self.compare(left.left,right.right) and self.compare(left.right,right.left):
return True
return False
思路： （评论区）
/*思路：首先根节点以及其左右子树，左子树的左子树和右子树的右子树相同
* 左子树的右子树和右子树的左子树相同即可，采用递归
* 非递归也可，采用栈或队列存取各级子树根节点
*/Python 简单解法，判断左右子节点的值是否相同即可，并通过递归左右节点遍历整个树。
剑指offer思路：
代码很简单，关键还是知道怎么样才能判断一个
二叉树是否对称，只要采用前序、中序、后序、层次遍历等任何一种遍历方法，分为先左后右和先
右后左两种方法，只要两次结果相等就说明这棵树是一颗对称二叉树。
58 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
if not pRoot: #异常输入处理
return []
result = [] #存储输出值
node = [pRoot] #当前处理的行结点
while node:
newnode = []
res = []
for i in node:
res.append(i.val)
if i.left:
newnode.append(i.left)
if i.right:
newnode.append(i.right)
result.append(res)
node = newnode
final = []
for j,i in enumerate(result): #偶数行反转
if j%2 ==1:
i.reverse()
final.append(i)
return final 思路：层序遍历的思路，每次把下一行存入新列表，之后依次遍历。注意最后要反转偶数行。
if not pRoot:
return []
result = []
node = [pRoot]
i = 0
while node:
i = i + 1
newnode = []
res = []
while node:
if node[-1].val:
res.append(node[-1].val)
if i%2 == 1:
if node[-1].left: #判断
newnode.append(node[-1].left)
if node[-1].right:
newnode.append(node[-1].right)
else:
if node[-1].right:
newnode.append(node[-1].right)
if node[-1].left:
newnode.append(node[-1].left)
node.pop()
result.append(res)
node = newnode
return result
思路2：剑指offer书上的思路。利用栈来实现，注意要奇偶行。
易错点：先判断存在与否再添加，注意不分奇偶数行的话会报错。
59 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
def Print(self, pRoot):
if not pRoot:
return []
result = []
node = [pRoot]
while node:
newnode= []
res = []
for i in node:
if i.left:
newnode.append(i.left)
if i.right:
newnode.append(i.right)
if i.val:
res.append(i.val)
node = newnode
result.append(res) 思路：跟上一题一样
易错点：不要忘记异常输入的判断。
60 请实现两个函数，分别用来序列化和反序列化二叉树
class Solution:
def __init__(self):
self.flag = -1 #设定标志位
def Serialize(self, root):
# write code here
s = ''
self.res = []
self.fro(root)
s = ','.join(self.res)
return s
def fro(self,root):
if not root:
self.res.append('#') #注意不能直接return #，注意双引号
return
self.res.append(str(root.val)) #注意str
self.fro(root.left) #递归
self.fro(root.right)
def Deserialize(self, s):
# write code here
self.flag += 1
l = s.split(',')
root = None #默认为空
if l[self.flag] != '#': #不为空
root = TreeNode(int(l[self.flag])) #要Int
root.left = self.Deserialize(s) #跟前序遍历一样递归
root.right = self.Deserialize(s)
return root
#前序遍历可以直接找到根节点 思路：（评论区）
1. 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点
不为空时，在转化val所得的字符之后添加一个' ， '作为分割。对于空节点则以 '#' 代替。
2. 对于反序列化：按照前序顺序，递归的使用字符串中的字符创建一个二叉树
注意反序列化时候，空直接返回None。
61 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
def KthNode(self, pRoot, k):
if not pRoot or not k: #加判断
return None
self.res = []
self.mid(pRoot)
if k > len(self.res): #重要，加判断
return None
return self.res[k-1]
def mid(self,root):
if not root:
return None
self.mid(root.left)
self.res.append(root) #不是val，是root
self.mid(root.right)
思路：将二叉树中序遍历存储在List，之后按需要提取。关键是理解二叉搜索树的中序遍历是递增的。
易错点：注意返回的是结点不是结点的值，注意异常值的处理，尤其是K超过res长度的时候。
63 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
class Solution:
def __init__(self):
self.res = []
def Insert(self, num):
self.res.append(num)
self.res.sort()
def GetMedian(self,s):
length = len(self.res)
if length%2 == 1:
return self.res[length/2]
else:
return (self.res[length/2]+self.res[length/2 - 1])/2.0 思路：每插入就排序一次。
易错点：通过init定义类变量。引用要加self。、整数除以整数的结果为整数，如果想得到相除结果为
浮点数，则需要除以浮点数（来自https://blog.csdn.net/github_39611196/article/details/88919102 ）
self.l[length//2] + self.l[length//2 -1]) / 2 （这样会取整）
转换为
self.l[length//2] + self.l[length//2 -1]) / 2.0
https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1
# -*- coding:utf-8 -*-
from heapq import *
class Solution:
def __init__(self):
self.heaps = [], []
def Insert(self, num):
# write code here
small, large = self.heaps
heappush(small, -heappushpop(large, num))#将num放入大根堆，并弹出大根堆的最小值，取反，放入大根堆small
if len(large) < len(small):
heappush(large, -heappop(small)) #弹出small中最小的值，取反，即最大的值，放入large
def GetMedian(self,ss):
# write code here
small,large = self.heaps
if len(large) > len(small):
return float(large[0])
return (large[0] - small[0]) /2.0 思路2：用一个最大堆与一个最小堆实现。
链接：https://www.nowcoder.com/questionTerminal/9be0172896bd43948f8a32fb954e1be1
来源：牛客网
- 大根堆：large保存大的半数的数据
- 小根堆：small保存小的半数的数据
获取中位数的时间复杂度为O（1），插入一个数据的时间复杂度为O（log(n)）
技巧：
- 构造小根堆时，对数组元素取负值来构造
- heappush(heap,data),将deat放入大根堆中
- heapposh(heap),弹出heap中的最小值
- heappushpop(heap,data),将data放入大根堆中，再弹出堆heap的最小值
64 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
if not num or not size or size > len(num):
return [] #不是None
res = []
i = 0
while i+size<=len(num):
res.append(max(num[i:i+size]))
i =i+1
return res
思路1：暴力法，求每次的最大值。
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]位置过期 则弹出 ， i-size+1 是最低位
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]]) #q[0]是对应的下标，从第size-1开始
i += 1
temp = []
for j in queue:
temp.append(num[j])
print(temp)
return res 思路2;（评论区）双端队列法。其中queue保存的是数组的下标。
用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次
1.判断当前最大值是否过期
2.新增加的值从队尾开始比较，把所有比他小的值丢掉
65 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
# -*- coding:utf-8 -*-
#回溯法
#遍历矩阵中的每一个位置
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if not matrix:
return False
if not path:
return True
x = [list(matrix[cols*i:cols*i+cols]) for i in range(rows)]
for i in range(rows):
for j in range(cols):
if self.exist_helper(x, i, j, path):
return True
return False
def exist_helper(self, matrix, i, j, p):
if matrix[i][j] == p[0]:
if not p[1:]:
return True #终点
matrix[i][j] = '#' #已走标记
if j > 0 and self.exist_helper(matrix, i, j-1, p[1:]):
return True #重要，要有return,一层层传回去
if j < len(matrix[0])-1 and self.exist_helper(matrix, i, j+1, p[1:]):
return True
if i > 0 and self.exist_helper(matrix, i-1, j, p[1:]):
return True
if i < len(matrix)-1 and self.exist_helper(matrix, i+1, j ,p[1:]):
return True
matrix[i][j] = p[0] #还原标记
return False
else:
return False 思路：回溯法思想。将已走标记为#，如果不成立。则还原回去。
链接：https://www.nowcoder.com/questionTerminal/c61c6999eecb4b8f88a98f66b273a3cc
来源：牛客网
这是一个可以用回朔法解决的典型题。首先，在矩阵中任选一个格子作为路径的起点。如果路径上的第i个字符不是ch，那么这个格子不可能处在路径上的
第i个位置。如果路径上的第i个字符正好是ch，那么往相邻的格子寻找路径上的第i+1个字符。除在矩阵边界上的格子之外，其他格子都有4个相邻的格子。重复这个过程直到路径上的所有字符都在矩阵中找到相应的位置。
由于回朔法的递归特性，路径可以被开成一个栈。当在矩阵中定位了路径中前n个字符的位置之后，在与第n个字符对应的格子的周围都没有找到第n+1个字符，这个时候只要在路径上回到第n-1个字符，重新定位第n个字符。
由于路径不能重复进入矩阵的格子，还需要定义和字符矩阵大小一样的布尔值矩阵，用来标识路径是否已经进入每个格子。 当矩阵中坐标为（row,col）的格子和路径字符串中相应的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)以及(row+1,col)中去定位路径字符串中下一个字符
如果4个相邻的格子都没有匹配字符串中下一个的字符，表明当前路径字符串中字符在矩阵中的定位不正确，我们需要回到前一个，然后重新定位。 一直重复这个过程，直到路径字符串上所有字符都在矩阵中找到合适的位置
易错点：matrix的初始化方法。递归的终止条件。边界条件。标记与还原。
66 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
# -*- coding:utf-8 -*-
class Solution:
def __init__(self): #开始必备，注意self
self.count = 0 #注意加self
def movingCount(self,threshold,rows,cols):
arr = [[1 for i in range(cols)] for j in range(rows)] #注意中括号
self.findblocks(arr,0,0,threshold) #里面不加self，传入的顺序
return self.count #self
def findblocks(self,arr,i,j,k): #ijk对应的值
if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]):
return
sumi = list(map(int,str(i))) #将数字转换为字符串再转换为列表进而用sum
sumj = list(map(int,str(j)))
if sum(sumi) + sum(sumj) > k or arr[i][j] != 1: #不符合条件或已走过（默认为1）
return
self.count = self.count + 1 #要加self，经历过前两关才可以加1
arr[i][j] = 0 #走过的设置为0
self.findblocks(arr,i,j-1,k)
self.findblocks(arr,i,j+1,k)
self.findblocks(arr,i-1,j,k)
self.findblocks(arr,i+1,j,k)
#注意，一定要连通
#回溯，深度优先
思路：（评论区）
|
|
将地图全部置1，遍历能够到达的点，将遍历的点置0并令计数+1.这个思路在找前后左右相连的点很有用，比如leetcode中的海岛个数问题/最大海岛问题都可以用这种方法来求解。
京公网安备 11010502036488号