1 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0 #注意是0不是None
nleft = self.TreeDepth(pRoot.left)
nright = self.TreeDepth(pRoot.right)
maxdepth = max(nleft,nright) + 1 #不能max(nleft+1,nright+1)
return maxdepth 采用递归的方法，注意Not pRoot 的边界值，注意max函数的错误用法（注释已给出)
二叉树的三种遍历：来源 http://www.cnblogs.com/turnips/p/5096578.html 与 https://www.cnblogs.com/llguanli/p/7363657.html
树的遍历顺序大体分为三种：前序遍历（先根遍历、先序遍历），中序遍历（中根遍历），后序遍历（后根遍历）。
如图所示二叉树
前序遍历：前序遍历可以记为根左右，若二叉树为空，则结束返回。
前序遍历的规则：
（1）访问根节点
（2）前序遍历左子树
（3）前序遍历右子树
这里需要注意：在完成第2,3步的时候，也是要按照前序遍历二叉树的规则完成。
前序遍历的输出结果：ABDECF
中序遍历：中序遍历可以记为左根右，也就是说在二叉树的遍历过程中，首先要遍历二叉树的左子树，接着遍历根节点，最后遍历右子树。
同样，在二叉树为空的时候，结束返回。
中序遍历的规则：
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树
注意：在完成第1，3步的时候，要按照中序遍历的规则来完成。
中序遍历的输出结果：DBEAFC
后序遍历：后序遍历可以记为左右根，也就是说在二叉树的遍历过程中，首先按照后序遍历的规则遍历左子树，接着按照后序遍历的规则遍历右子树，最后访问根节点。
在二叉树为空的时候，结束返回。
后序遍历二叉树的规则：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点
注意：在完成1,2步的时候，依然要按照后序遍历的规则来完成。
后序遍历的输出顺序：DEBFCA
另外还有层级遍历，广度优先遍历，深度优先遍历等
概念：https://blog.csdn.net/sinat_26533265/article/details/51247920
平衡二叉树： 任何一个节点的左右子树深度差不超过1
二叉搜索树 / 二叉查找树：
如果树不是一颗空树的话，那么二叉查找树具有以下特征：
1. 若左子树不为空，那么左子树所有节点的值小于均小于他的根节点的值。
2. 若右子树不为空，那么右子树的所有节点的值大于根节点的值。
3. 左右子树也分别为二叉排序树。
4. 没有键值相等的节点。 好文：二叉树判断的Python实现 https://www.cnblogs.com/icekx/p/9131304.html
掌握队列的用法 https://www.cnblogs.com/itogo/p/5635629.html 主要是out 与 get
2 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路1：递归判断深度
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#class Solution:
# def IsBalanced_Solution(self, pRoot):
# write code here
if not pRoot:
return True #此处返回的是True
left = self.TreeDepth(pRoot.left)
right = self.TreeDepth(pRoot.right)
diff = abs(left - right)
if diff > 1:
return False #false不要拼写错了
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)#递归调用
def TreeDepth(self, pRoot):
# write code here
if not pRoot:
return 0
nleft = self.TreeDepth(pRoot.left)
nright = self.TreeDepth(pRoot.right)
maxdepth = max(nleft,nright) + 1 #不能max(nleft+1,nright+1)
return maxdept 思路2：避免重复
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
res = True
def IsBalanced_Solution(self, pRoot):
# write code here
self.helper(pRoot)
return self.res
def helper(self,root):
if not root:
return 0
if not self.res : return 1
left = 1 + self.helper(root.left)
right = 1 + self.helper(root.right)
if abs(left-right)>1:
self.res = False
return max(left,right)
#不要每个节点都去求一次高度，避免重复
#语言：Python 3 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
分析：双指针法，和大则前进small，和小则前进big,尤其注意在满足条件时，指针要继续前进，避免陷入无限循环
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
if tsum <1:
return None
small = 0
big = 1
num = list(range(1,tsum))
res = []
while big < tsum and small < big :
if sum(num[small:big]) == tsum:
res.append(num[small:big])
big = big + 1 #缺少此句会进入死循环
elif sum(num[small:big]) < tsum:
big = big + 1
else:
small = small + 1
return res
4 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# 两头开始找匹配，乘积最小必定为最先找到的，如7+8=15 1+14=15乘积1*14小
low, high = 0, len(array) - 1
while low < high:
if array[low] + array[high] > tsum:
high -= 1
elif array[low] + array[high] < tsum:
low += 1
else:
return [array[low], array[high]]
return [] # 匹配失败返回空list 同样利用双指针法，同时本题中乘积最小也就是相距最远的两个数。同时，也可以加入如下判断（牛客网超时）：
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
if tsum <= array[0]:
return None
small = 0
big = len(array) - 1
res = []
res1 = []
last = 0
while big < len(array) and small < big:
if array[small] + array[big] == tsum:
res.append([array[small],array[big]])
small = small + 1
elif array[small] + array[big] < tsum:
big = big + 1
else:
big = big - 1
# return res[0]
for i in range(len(res)):
result = res[i][0]*res[i][1]
if result < last:
res1 = res[i]
last = result = res[i][0]*res[i][1]
return res1
r = r = Solution()
print(r.FindNumbersWithSum(list(range(1,10000)),9000)) 4 左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
# -*- coding:utf-8 -*-
class Solution:
def LeftRotateString(self, s, n):
# write code here
res = s[n:len(s)] #调用切片
res = res + s[0:n]n
return res 简单的，可以利用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] 上边是先将两部分进行翻转拼接，随后进行整体翻转
5 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
# -*- coding:utf-8 -*-
class Solution:
def ReverseSentence(self, s):
# write code here
res = s.split(' ') #掌握字符串切割转换为List的方法
res.reverse()
res1 = ' '.join(res) #掌握list转换为字符串的方法
return res1 掌握字符串与list之间相互转换的方法
6 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。
判断顺子，难点在于有大小王的加入，采用的是分类讨论的方法，根据大小王从0-4的个数
# -*- coding:utf-8 -*-
class Solution:
def IsContinuous(self, numbers):
# write code here
if not numbers: #首先进行排序与判断0的情况，之后对0的数目不同的情况进行讨论
return False
numbers.sort()
num0 = 0
for i in numbers:
if i!= 0 and numbers.count(i)>1:
return False
elif i ==0:
num0 = num0+1
if num0 ==0:
if numbers[4] - numbers[0] > 5:
return False
elif numbers[4] - numbers[0] ==4:
return True
elif num0 ==1:
if numbers[4] - numbers[1] <=4:
return True
else:
return False
elif num0 ==2:
if numbers[4] - numbers[2] <=4:
return True
else:
return False
elif num0 ==3:
if numbers[4] - numbers[3] <=4:
return True
else:
return False
elif num0 ==4:
return True 评论区还有另一种简单的解法：
链接：https://www.nowcoder.com/questionTerminal/762836f4d43d43ca9deb273b3de8e1f4
来源：牛客网
1、如果输入为空，返回false
2、除了王的任何某个特定数值的牌出现两张或者更多，那么一定凑不齐顺子。
思路，先统计王的数量，再把牌排序，如果后面一个数比前面一个数大于1以上，那么中间的差值就必须用王来补了。看王的数量够不够，如果够就返回true，否则返回false。
12
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：链接：https://www.nowcoder.com/questionTerminal/762836f4d43d43ca9deb273b3de8e1f4
来源：牛客网
python solution
这道题很简单，注意两点
1、如果输入为空，返回false
2、除了王的任何某个特定数值的牌出现两张或者更多，那么一定凑不齐顺子。
思路，先统计王的数量，再把牌排序，如果后面一个数比前面一个数大于1以上，那么中间的差值就必须用王来补了。看王的数量够不够，如果够就返回true，否则返回false。
6 约瑟夫环问题，每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
经典解法：模拟一个环形链表：
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n < 1:
return -1
start = 0
con = range(n) #在python3中需要写成 list(range(n)的形式)
while con:
final = (start+ m - 1)%n #确定本轮的位置
res = con.pop(final)
start = final #很关键！！由于前一个弹出这时的final的相对位置，已经往后一位了
n = n - 1
return res 一定要注意弹出后，之后的序列都会往前移动一位
7 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
评论区的短路求值解法，精妙，即通过and逻辑来判断递归的边界条件：
# -*- 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
8 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
考察位运算，注意异或运算的用法，以及越界检查：原文：
不得不吐槽下Python对位操作简直是深坑一座- -
主要原因还是因为python没有无符号又移操作，所以需要越界检查一波～
其他思路和大家是一样的
加法是异或，进位是与<<1
# -*- coding:utf-8 -*-
class Solution:
def Add(self, a, b): #越界检查，正负数判断
while(b):
a,b = (a^b) & 0xFFFFFFFF,((a&b)<<1) & 0xFFFFFFFF
return a if a<=0x7FFFFFFF else ~(a^0xFFFFFFFF) 9 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
主要考察对各种不符合情况输入的判断，如空，有其他字符，+—不止一个等。
# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
# write code here
if not s: #判断空
return 0
for i in s: #判断异常符号
num = ['0','1','2','3','4','5','6','7','8','9','+','-']
if i not in num:
return 0
if s == '+' or s == '-': #判断只有一个符号
return 0
res = 0
flag = True #是否是负数
if s[0] == '+': #去除符号
flag = True
s = s[1:]
elif s[0] == '-': #要用elif，避免误判‘+-’这种情况
flag = False
s = s[1:]
for i in s: #判断除第一位外的加减号
num = ['0','1','2','3','4','5','6','7','8','9']
if i not in num:
return 0
for j in range(len(s)): #计算
res = res + num.index(s[j])*(10**(len(s)-1-j)) #注意此处转换的方法！注意是s[j]而不是j，
if flag: #根据符号输出
return res
elif not flag:
res = -1*res
return res 一定要注意，elif跟连续的两个if之间的不同，要注意==不要跟=混用（老生常谈）
注意本地中 利用 index对应上了数字值
10 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2
def duplicate(self, numbers, duplication):
# write code here
if not numbers:
return False
for i in range(len(numbers)): #冒号跟分号不能混用
# for j in numbers[i:]: #不要混用s[k]与k !!!!!
for j in range(len(numbers[i:])): #切割的区间开闭.j是从哪儿开始的
if numbers[j+i] == numbers[i] and j > 0 : #等号的写法！j的判断,j对应的值
duplication[0] = numbers[i]
return True
return False 暴力解法，注意i 与 s[i]的区别，注意冒号分号别混淆
还可以利用list求解：
def duplicate(self, numbers, duplication): #利用list来解决，判断list中是否有重复
if not numbers:
return False
res = []
for i in numbers:
if i in res:
duplication[0] = i
return True
else:
res.append(i)
return False 补充：
1 c语言中的 && 相当于 python中的 and ，||相当于or,&指的是位运算，and指的是逻辑运算。
2 短路求值 https://blog.csdn.net/xiaoquantouer/article/details/71023448
3 <<在C++中，有两个运算含义：
1.重载输出流运算符，一般运用格式为：cout<<x;其中cout为流文件，如显示设备，输出设备，或者数据文件等。
2.数据移位运算符，左移几位，如：x=i<<4;就是将i的值左移4位（放大2的4此方）后，赋给x，若i=2,则X=32。
4
python range() 函数可创建一个整数列表，一般用在 for 循环中。
函数语法
range(start, stop[, step]) 参数说明：
start: 计数从 start 开始。默认是从 0 开始。例如range（5）等价于range（0， 5）;
stop: 计数到 stop 结束，但不包括 stop。例如：range（0， 5） 是[0, 1, 2, 3, 4]没有5
step：步长，默认为1。例如：range（0， 5） 等价于 range(0, 5, 1)
5 python 的 sort方法
http://www.runoob.com/python3/python3-att-list-sort.html
6
python中list转字符串
命令：''.join(list)
其中，引号中是字符之间的分割符，如“,”，“;”，“\t”等等
如：
list = [1, 2, 3, 4, 5]
''.join(list) 结果即为：12345
','.join(list) 结果即为：1,2,3,4,5
7 数组的定义，例如可以 A = [0], 不能直接 A[0] = 0
8 异或运算
1、异或是一个数学运算符。应用于逻辑运算。
2、例如：真异或假的结果是真，假异或真的结果也是真，真异或真的结果是假，假异或假的结果是假。就是说两个值相 异结果为真。
异或的运算方法是一个二进制运算：
1^1=0
0^0=0
1^0=1
0^1=1
两者相等为0,不等为1
9 list.reverse() 字符串不能直接使用，是python中列表的一个内置方法（也就是说，在字典，字符串或者元组中，是没有这个内置方法的），用于列表中数据的反转；
京公网安备 11010502036488号