牛客网剑指offer-2
牛客网剑指offer-2
剑指offer刷题-2
二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
分析
首先我们需要知道二叉搜索树的特点，也就是左小右大，我们需要递归处理左右子树，交换左右子树中的子节点使其成为链表，根节点在最中间
class Solution:
def Convert(self, pRootOfTree):
# 处理根节点为空
if not pRootOfTree:
return pRootOfTree
# 只有根节点的情况
if not pRootOfTree.left and not pRootOfTree.right:
return pRootOfTree
# 处理左子树
self.Convert(pRootOfTree.left)
left = pRootOfTree.left
# 连接根与左子树最大结点
if left:
while (left.right):
left = left.right
# 交换节点的值
pRootOfTree.left, left.right = left, pRootOfTree
# 处理右子树
self.Convert(pRootOfTree.right)
right = pRootOfTree.right
# 连接根与右子树最小结点
if right:
while (right.left):
right = right.left
# 交换节点的值
pRootOfTree.right, right.left = right, pRootOfTree
# 当左子树存在时
while (pRootOfTree.left):
# 左子树赋值给自己
pRootOfTree = pRootOfTree.left
# 返回链表的头节点
return pRootOfTree字符串的排列
题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
分析
使用标准库中的方法即可，重排序之后进行去重排序
import itertools
class Solution:
def Permutation(self, ss):
# 如果ss为空
if not ss:
return []
# 使用标准库中的permutations进行全排序，使用map函数聚合
# 使用set去重
# 转为list并排序
return sorted(list(set(map(''.join, itertools.permutations(ss)))))数组中出现次数超过一半的数字
题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0
分析
求数组长度的一半，然后遍历数组中每个元素的，判断是否大于数组长度的一半
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# 求的数组长度的一半
mid = len(numbers) / 2
# 遍历数组
for i in numbers:
# 判断数组中元素出现的次数
if numbers.count(i) > mid:
return i
return 0最小的K个数
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
分析
首先判断边界条件，k是否大于数组长度，简单处理可以对列表进行排序并取出前k个
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
if k > len(tinput):
return []
return sorted(tinput)[:k]整数中1出现的次数（从1到n整数中1出现的次
题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。
分析
设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），分别对每个数位上有多少包含1的点进行分析 根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i 当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0~31），每一次都包含100个连续的点，即共有(a%10+1)100个点的百位为1 当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，则共有a%10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00~56，共b+1次，所有点加起来共有（a%10100）+(b+1)，这些点百位对应为1 当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0~30） 综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1 之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
count = 0
i = 1
while i <= n:
a = n / i
b = n % i
count += (a + 8) / 10 * i + (a % 10 == 1) * (b + 1)
i *= 10
return count把数组排成最小的数
题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
分析
使用标准库的全排列方法将列表中的元素进行全排序，然后去重排序取第0个元素即可
import itertools
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ''
numbers = map(str, numbers)
# 全排列去重转列表排序取最小值
res = sorted(list(set(map(''.join, itertools.permutations(numbers)))))
return res[0]丑数
题目描述
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数
分析
既然知道第一个丑数为1，并且丑数的因子只包含2 3 5，我们可以分别乘以2 3 5，来求出其中的最小值，放入丑数列表，最后取出最后一个即可
class Solution:
def GetUglyNumber_Solution(self, index):
if index < 1:
return index
# 使用一个列表保存丑数
res = [1]
i = 0
j = 0
k = 0
# 当丑数数量不等于index时
while len(res) != index:
# 求出当前丑数*2 *3 *5中的最小值
minV = min(res[i] * 2, res[j] * 3, res[k] * 5)
# 将最小值放入丑数列表
res.append(minV)
# 判断当前丑数*2 *3 *5是否小于等于丑数
if res[i] * 2 <= minV:
i += 1
if res[j] * 3 <= minV:
j += 1
if res[k] * 5 <= minV:
k += 1
# 返回最后一个丑数
return res[-1]第一个只出现一次的字符
题目描述
在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置
分析
当s为空时候，直接返回-1，当不为空的时候，遍历字符串，当从双向查找的索引值都相等，即找到所求
class Solution:
def FirstNotRepeatingChar(self, s):
if s == '':
return -1
for i in range(len(s)):
# 当从前往后查找和从后向前查找时返回值相等时，即只出现了一次
if s.find(s[i]) == s.rfind(s[i]):
return i
return -1两个链表的第一个公共结点
题目描述
输入两个链表，找出它们的第一个公共结点。
分析
使用列表存储其中一个链表，遍历第二个链表判断是否在列表中
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
list1 = []
node1 = pHead1
node2 = pHead2
# 使用一个列表存储第一个链表的所有节点
while node1:
list1.append(node1.val)
node1 = node1.next
# 循环遍历第二个链表判断是否存在列表中
while node2:
if node2.val in list1:
return node2
else:
node2 = node2.next数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
分析
由于是排序的，所以可以想到二分查找，当然利用一些标准库函数也可以，但是不符合题意了
class Solution:
def GetNumberOfK(self, data, k):
"""
在Python中可以直接使用data.count(k)来解决
为了题目的意义，这里使用二分查找
:param data:
:param k:
:return:
"""
length = len(data)
if length == 0:
return 0
first = self.get_first_k(data, k, 0, length - 1)
end = self.get_last_k(data, k, 0, length - 1)
if first != -1 and end != -1:
return end - first + 1
return 0
def get_first_k(self, data, k, start, end):
"""
递归写法二分查找
:param data:
:param k:
:param start:
:param end:
:return:
"""
if start > end:
return -1
mid = start + (end - start) / 2
if data[mid] > k:
return self.get_first_k(data, k, start, mid - 1)
elif data[mid] < k:
return self.get_first_k(data, k, mid + 1, end)
elif mid - 1 >= 0 and data[mid - 1] == k:
return self.get_first_k(data, k, start, mid - 1)
else:
return mid
def get_last_k(self, data, k, start, end):
"""
循环写法二分查找
:param data:
:param k:
:param start:
:param end:
:return:
"""
length = len(data)
mid = start + (end - start) / 2
while start <= end:
if data[mid] > k:
end = mid - 1
elif data[mid] < k:
start = mid + 1
elif mid + 1 < length and data[mid + 1] == k:
start = mid + 1
else:
return mid
mid = start + (end - start) / 2
return -1二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
分析
求深度，递归判断左右子树的深度，最后加上根节点即可
class Solution:
def TreeDepth(self, pRoot):
if not pRoot:
return 0
return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1平衡二叉树
题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
分析
根据平衡二叉树的特点求解即可
class Solution:
def IsBalanced_Solution(self, pRoot):
"""
判断一个树是否为平衡二叉树
当check函数的发挥值不等于-1时返回true，等于-1是返回false
:param pRoot: TreeNode
:return: bool
"""
return self.check(pRoot) != -1
def check(self, root):
"""
检查结点
:param root: TreeNode
:return: int
"""
# 结点为空时
if root is None:
return 0
# 递归得出左子树的返回值
left = self.check(root.left)
# 递归得出右子树的返回值
right = self.check(root.right)
# 如果左子树不为平衡树或者右子树不为平衡二叉树，
# 左右子树相减的值大于1(-1-(-1))左右子树不为平衡树的情况
if left == -1 or right == -1 or abs(left - right) > 1:
return -1
# left right分别等于0或1的情况
return 1 + max(left, right)数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
分析
使用一个列表来保存元素，因为每个元素最多出现两次，当出现第二次的时候，删除该元素，最后列表中只会留下只出现一次的元素
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
"""
遍历数组，如果已存在的结果列表中就移除，不存在则添加
:param array:
:return:
"""
tmp = []
for a in array:
if a in tmp:
tmp.remove(a)
else:
tmp.append(a)
return tmp和为S的连续正数序列
题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述: 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
分析
这里给出的解法是最笨的方法，时间复杂度会比较高，也就是依次从0开始相加，直到等于所求的和。还可以根据序列的特点去求解，比如等差数列求和，，，可以相对降低时间复杂度
class Solution:
def FindContinuousSequence(self, tsum):
# 当要求的和的值小于3，不存在这样的序列
if tsum < 3:
return []
s = []
# 遍历从1到所求和之前的值
for i in range(1, tsum):
t = 0
j = i
# 从0开始依次相加，直到不小于和
while t < tsum:
t = t + j
j = j + 1
# 判断是否等于和
if t == tsum:
s.append(range(i, j))
return s和为S的两个数字
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
分析
使用字典存储乘积和两个数的元组，由于递增排序，所以在字典中出现同样乘积的只保留第一组键值对。当结果字典不为空的时候，将字典进行排序取出第一组键值对的值
class Solution:
def FindNumbersWithSum(self, array, tsum):
# 使用一个字典存储乘积和两个数的键值对
res = {}
# 遍历列表
for i in array:
# 判断和减去该元素是否在该列表中
if tsum - i in array:
# 如果乘积的值不在字典中，将字典的值和键值对存储在字典中
if i * (tsum - i) not in res.keys():
res[i * (tsum - i)] = (i, tsum - i)
# 当字典不为空的时候，取出第一个元素的值即为最小的
if res != {}:
return list(sorted(res.items())[0][1])
return []左旋转字符串
题目描述
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
分析
左旋转，斟酌题意可以知道当n大于字符串长度或者小于0，字符串都是没有变化的，直接返回0即可。否则，将前n字符串拼接到后n位字符串后面即可
class Solution:
def LeftRotateString(self, s, n):
# 当n大于字符串长度或者小于0的时候，等于没有变
if n >= len(s) or n <= 0:
return s
# 将字符串的前n位拼接到字符串的最后即可
return s[n:] + s[:n]翻转单词顺序列
题目描述
牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
分析
翻转单词，首先我们需要对字符串进行空格切分，然后将其逆序，再按空格拼接为字符串
class Solution:
def ReverseSentence(self, s):
# 使用空格进行字符串切割转换为列表
l = s.split(' ')
# 使用空格将字符串倒序拼成一个新的字符串
return ' '.join(l[::-1])求1+2+3+…+n
题目描述
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
分析
使用递归解决
class Solution:
def Sum_Solution(self, n):
if n == 1:
return 1
return n + self.Sum_Solution(n - 1)不用加减乘除做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
分析
这里使用内置函数sum
（可以使用位运算，但是Python这里涉及到负数不知道怎么就报错了，就不展示代码了）
class Solution:
def Add(self, num1, num2):
return sum([num1, num2])把字符串转换成整数
题目描述
将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0
分析
首先判断边界条件，最后使用ord()将字符转为数字，计算。
(看答案有人使用int()函数直接解决，但个人觉得不怎么符合题意)
class Solution:
def StrToInt(self, s):
if not s:
return 0
number = 0
start = 0
flage = 1
if s[0] == '+':
start = 1
elif s[0] == '-':
flage = -1
start = 1
# 遍历字符串
for i in range(start, len(s)):
# 如果不在0到9
if s[i] < '0' or s[i] > '9':
return 0
else:
# 转换为数字
number = number * 10 + flage * (ord(s[i]) - ord('0'))
return number数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2
分析
首先判断边界条件，遍历数组时，使用一个列表去保存遍历过的值，判断当前遍历的元素是否存在列表中，如果存在，将当前值保存，并返回true，窦泽将当前值保存在列表中
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# 边界条件
if numbers is None or numbers == []:
return False
# 使用一个列表接收遍历过的值
s = []
for i in numbers:
# 存在
if i in s:
duplication[0] = i
return True
s.append(i)
return False构建乘积数组
题目描述
给定一个数组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]。不能使用除法。
分析
首先初始化b，然后遍历ab，判断当前遍历的索引是否相等，不相等时，将B[i]*A[i]赋值给B[i]
class Solution:
def multiply(self, A):
# 将b列表元素都初始化为1
B = [1] * len(A)
# 遍历a
for i in range(len(A)):
# 遍历b
for j in range(len(B)):
# 如果i不等于j
if i != j:
B[i] *= A[j]
return B正则表达式匹配
题目描述
请实现一个函数用来匹配包括’.’和’‘的正则表达式。模式中的字符’.’表示任意一个字符，而’‘表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”abaca”匹配，但是与”aa.a”和”ab*a”均不匹配
分析
首先也是判断边界条件，当模式或者字符串为空的情况。
然后依次判断每个字符，判断模式串第二个字符是否为*,然后只需判断第一个模式串是否为.或者与字符相等，当满足条件时，递归判断从第二个开始的字符串。
如果模式串第二个字符串不为*时，则递归判断第三个开始的字符串
同时还需要判断只匹配一个字符的情况
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
if len(s) == 0 and len(pattern) == 0: # 若均为空，返回true
return True
if len(s) > 0 and len(pattern) == 0: # 若模式串为空，而字符串不为空，返回False
return False
if len(pattern) > 1 and pattern[1] == '*': # 若模式串的第二个字符为*
if len(s) > 0 and (s[0] == pattern[0] or pattern[0] == '.'): # 若s不为0，且第一个字符匹配
return self.match(s[1:], pattern) or self.match(s, pattern[2:]) or self.match(s[1:], pattern[2:])
# 有三种情况：**表示模式串的第一个字符个数为2即重复了；*表示模式串的第一个字符个数为0；*表示模式串的第一个字符个数为1
else: # s的长度为0时，看模式串后面是否还有未匹配的项
return self.match(s, pattern[2:])
if len(s) > 0 and (pattern[0] == '.' or pattern[0] == s[0]): # 只匹配一个字符的情况
return self.match(s[1:], pattern[1:]) # 继续匹配该字符之后的字符串表示数值的字符串
题目描述
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。
分析
使用float函数转为数字，当转换失败抛出异常时，返回false
或者使用正则表达式去判断
class Solution:
# s字符串
def isNumeric(self, s):
# write code here
try:
a = float(s)
return True
except:
return False字符流中第一个不重复的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。
输出描述: 如果当前字符流没有存在出现一次的字符，返回#字符。
分析
使用字符串和一个字典去保存字符出现的次数(字符为键，次数为值)遍历字符串，判断字典中是否含有键为字符的元素，如果有，值为1时，返回即可。否则返回‘#’
class Solution:
# 返回对应char
def __init__(self):
"""
使用一个字符串和一个字典保存字符串出现的次数
"""
self.s = ''
self.dict1 = {}
def FirstAppearingOnce(self):
# write code here
for i in self.s:
# 如果键值对的值为1(出现的次数为1)
if self.dict1[i] == 1:
return i
return '#'
def Insert(self, char):
# 每次将字符串加上新字符
self.s = self.s + char
# 判断当前字符是否是字典中的键
if char in self.dict1:
# 将对应的键值+1
self.dict1[char] = self.dict1[char] + 1
else:
# 不存在即直接赋值为1
self.dict1[char] = 1链表中环的入口结点
题目描述
一个链表中包含环，请找出该链表的环的入口结点。
分析
使用一个列表保存遍历过的节点，遍历单链表判断是否在列表中。
class Solution:
def EntryNodeOfLoop(self, pHead):
# 遍历链表，环的存在，遍历遇见的第一个重复的即为入口节点
tempList = []
if not pHead or not pHead.next:
return None
node = pHead
while node:
if node in tempList:
return node
else:
tempList.append(node)
node = node.next