23. 二叉搜索树的后序遍历序列
把每一项都与当前树的根节点比一遍
# -*- coding:utf-8 -*-
class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
if not sequence:
return False
length = len(sequence)
root = sequence[-1]
for i in range(length):
if sequence[i] > root:
break
while i < length - 1:
if sequence[i] < root:
return False
i += 1
left = sequence[:i]
right = sequence[i:-1]
leftIs = True
rightIs = True
if len(left) > 0:
leftIs = self.VerifySquenceOfBST(sequence=left)
if len(right) > 0:
rightIs = self.VerifySquenceOfBST(sequence=right)
return leftIs and rightIs
24. 二叉树中为某一值的路径
- 每经过一个节点
expectNumber-=self.value同时记录这个节点的值 - 当
expectNumber==self.value时就找出这条路径了 - 注意这里的路径是到叶子节点的。也就是说，如果输入是
{10,5,12,4,7},15你输出[[10,5]]是错的。所以第二点的条件就变成if root and not root.left and not root.right and root.val == expectNumber:了。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表，内部每个列表表示找到的路径
def FindPath(self, root, expectNumber):
# write code here
if not root:
return []
if root and not root.left and not root.right and root.val == expectNumber:
return [[root.val]]
res = []
left = self.FindPath(root.left, expectNumber-root.val)
right = self.FindPath(root.right, expectNumber-root.val)
for i in left+right:
res.append([root.val]+i)
return res
25. 复杂链表的复制
相当于deepcopy
直接引用的话会判错
大神的写法
利用递归从链表结尾指向None开始构建
# -*- coding:utf-8 -*-
# class RandomListNode:
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution:
# 返回 RandomListNode
def Clone(self, pHead):
# write code here
if not pHead:
return pHead
p=RandomListNode(pHead.label)
p.next=pHead.next
p.random=pHead.random
p.next=self.Clone(pHead.next)
return p
26. 二叉搜索树与双向链表
二叉树的中序遍历
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Convert(self, pRootOfTree):
# write code here
if not pRootOfTree:return
self.arr = []
self.midTraversal(pRootOfTree)
for i,v in enumerate(self.arr[:-1]):
v.right = self.arr[i + 1]
self.arr[i + 1].left = v
return self.arr[0]
def midTraversal(self, root):
if not root: return
self.midTraversal(root.left)
self.arr.append(root)
self.midTraversal(root.right)
27. 字符串的排列
遍历字符串，固定第一个元素，然后递归求解
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
# write code here
if not ss:
return []
if len(ss) == 1:
return [ss]
ret = []
for i in range(len(ss)):
for j in self.Permutation(ss[:i]+ss[i+1:]):
ret.append(ss[i]+j)
return sorted(list(set(ret)))
28. 数组中出现次数超过一半的数字
统计词频
# -*- coding:utf-8 -*-
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
res_dict = {}
for number in numbers:
res_dict[number] = res_dict.get(number, 0) + 1
res_list = [i for i in res_dict.items()]
res = sorted(res_list ,key=lambda x: x[1])[-1]
if res[1]>len(numbers)/2:
return res[0]
else:
return 0
进阶做法
import collections
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
tmp = collections.Counter(numbers)
x = len(numbers)/2
for k, v in tmp.items():
if v > x:
return k
return 0
其他思路：
- 思路一：数组排序后，如果符合条件的数存在，则一定是数组中间那个数。（比如：1，2，2，2，3；或2，2，2，3，4；或2，3，4，4，4等等）
这种方法虽然容易理解，但由于涉及到快排sort，其时间复杂度为O(NlogN)并非最优； - 思路二：如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。
在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。
29. 最小的K个数
本质上是排序
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if tinput == [] or k > len(tinput):
return []
tinput.sort()
return tinput[: k]
# -*- coding:utf-8 -*-
快速排序
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
def quick_sort(lst):
if not lst:
return []
pivot = lst[0]
left = quick_sort([x for x in lst[1: ] if x < pivot])
right = quick_sort([x for x in lst[1: ] if x >= pivot])
return left + [pivot] + right
if tinput == [] or k > len(tinput):
return []
tinput = quick_sort(tinput)
return tinput[: k]
30. 连续子数组的最大和
实力有限，大佬们都是用动态规划做的，我只能遍历一遍
# -*- coding:utf-8 -*-
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
a=b=len(array)
max =[array[0]]
for i in range(a):
for j in range(i+1,b+1):
if sum(array[i:j])>sum(max):
max = array[i:j]
return sum(max)
31. 整数中1出现的次数（从1到n整数中1出现的次数）
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
cnt = 0
for i in range(n+1):
while i:
if i%10 == 1:
cnt +=1
i//=10
return cnt
32. 把数组排成最小的数
先把原数组排序
# -*- coding:utf-8 -*-
class Solution:
def PrintMinNumber(self, numbers):
# write code here
res = ''
a = list(map(str, numbers))
for i in range(len(a)-1):
for j in range(len(a)-1):
if a[j] + a[j + 1] > a[j + 1] + a[j]:
a[j], a[j + 1] = a[j + 1], a[j]
for i in a:
res+=i
return res
33. 丑数
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
# write code here
if index < 1:
return 0
res = [1]
t2 = t3 = t5 = 0
next = 1
while next < index:
min_num = min(res[t2]*2, res[t3]*3, res[t5]*5)
res.append(min_num)
if res[t2]*2 <= min_num:
t2 += 1
if res[t3]*3 <= min_num:
t3 += 1
if res[t5]*5 <= min_num:
t5 += 1
next += 1
return res[index-1]
