python-剑指offer41-62
41、数组
牛客最近来了一个新员工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
if s is None:
return ""
alist = list(s.split(" "))
return " ".join(alist[::-1])解题思路：列表的翻转
42、数组
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 len(numbers) == 0:
return False
numbers = sorted(numbers)
count_0 = 0
for i in range(0,len(numbers)-1):
if numbers[i] == 0:
count_0 += 1
else:
delta = numbers[i+1] - numbers[i]
if delta < 1:
return False
elif delta > 1:
count_0 = count_0 - delta + 1
if count_0 < 0:
return False
return True解题思路：大小王可以视作0，然后把数组排序。从头开始读数组，统计0的个数，然后读后面的数字，相邻两个数字之间如有间隔差值，则用0的个数来填补，如果后面的数字本来就是连续的则肯定ok，如果中间有不连续且刚好能被0填补，则也是顺子。
43、环、数组
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
# -*- coding:utf-8 -*- （140ms、5724k）
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n == 0 or m == 0:
return -1
a = [i for i in range(n)]
while (len(a) > 1):
r = int((m - 1) % len(a))
a.remove(a[r])
a = a[r:] + a[:r]
return a[0]解题思路：我自己的解法就是找到，删除，调整数组。速度有点慢
另一种就是只保存删除的索引，效率较高：
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
if n < 1:
return -1
con = list(range(n))
final = -1
start = 0
while con:
k = (start + m - 1) % n
final = con.pop(k)
n -= 1
start = k
return final44、加法
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
# -*- coding:utf-8 -*-
class Solution:
def Sum_Solution(self, n):
ans = n
temp = ans and self.Sum_Solution(n-1)
ans = ans + temp
return ans解题思路：递归。注意 python 的写法。当and和or等短路运算符，用作普通值而不是布尔值时，短路运算符的返回值是最后一次评估的参数。也就是说下面的句子中，如果ans为0，则temp为0， 如果ans不为0， 则temp就是递归了之后的值。
通过位运算的方法：
首先看十进制是如何做的： 5+7=12，三步走
第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。
同样我们可以用三步走的方式计算二进制值相加： 5-101，7-111
第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111) << 1。
第三步重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010) << 1。 继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。
public class Solution {
public int Add(int num1,int num2) {
while (num2!=0) {
int temp = num1^num2;
num2 = (num1&num2)<<1;
num1 = temp;
}
return num1;
}
}
# -*- 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)补充一下python位运算：
x >> y # 返回 x 向右移 y 位得到的结果
x << y # 返回 x 向左移 y 位得到的结果
x & y # 与操作，xy对应的每一位，只有都为1时才为1
x | y # 或操作，xy对应的每一位，只有都为0时才为0
~x # 按位取反操作，x的每一位如果为0则变为1，如果为1则变为0，从十进制来看，结果是 -x - 1（例如，~8 = -9）
x ^ y # 异或运算，xy对应的每一位，数字不同则为1，数字相同则为0
45、字符串
将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
# -*- coding:utf-8 -*-
class Solution:
def StrToInt(self, s):
# write code here
minus = 1
number = 0
if not s:
return number
if s[0] == '+':
if len(s) > 1:
s = s[1:]
else:
return 0
elif s[0] == '-':
minus = -1
if len(s) > 1:
s = s[1:]
else:
return 0
for i in range(0, len(s)):
if '0' <= s[i] <= '9':
number = number * 10 + ord(s[i]) - ord('0')
else:
return 0
return number * minus解题思路：记得ord(‘0’)=48,ord(‘a’)=97,ord(‘A’)=65
46、数组
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
# -*- coding:utf-8 -*-
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
dis = {}
for i in list(numbers):
if i not in dis:
dis[i] = 1
else:
dis[i] += 1
j = 0
for i in dis:
if dis[i] == 1:
continue
elif dis[i] > 1:
j = i
break
if j == 0:
return False
else:
duplication[0] = j
return True解题思路：hash表
47、数组
给定一个数组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]。不能使用除法。
class Solution:
def multiply(self, A):
ifnot A:
return []
b = [1] * len(A)
for i in range(1,len(A)):
b[i] = b[i] * A[i-1]
tmp = 1
for i in range(len(A)-2,1,-1):
tmp = tmp * A[i+1]
b[i] = b[i] *tmp
return b解题思路：将乘积分为两部分。
48、字符串匹配
请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
# -*- coding:utf-8 -*-
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:])
else:
return False49、类似字符串匹配
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+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):
# 标记符号、小数点、e是否出现过
sign = False
decimal = False
has_e = False
for i in range(len(s)):
if s[i] == 'e' or s[i] == 'E':
if i == len(s) - 1:
return False # E后面必须跟数字，E不可以在字符串结尾
if has_e:
return False # 不可以出现两个E
has_e = True
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'):
return False # 如果第一次出现符号，且不是在开头出现，则必须紧跟在E之后
sign = True
elif s[i] == '.':
if has_e or decimal:
return False # E后面不能出现小数点，或小数点不能出现两次
decimal = True
elif s[i] < '0' or s[i] > '9':
return False # 不合法字符
return True50、hash
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
class Solution:
def __init__(self):
self.stream = []
self.counter = {}
# 返回对应char
def FirstAppearingOnce(self):
for c in self.stream:
if self.counter[c] == 1:
return c
return '#'
def Insert(self, char):
if char in self.counter:
self.counter[char] += 1
else:
self.counter[char] = 1
self.stream.append(char)51、环、链表
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if not pHead:
return None
slow = pHead
fast = pHead
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
slow2 = pHead
while slow2 != slow:
slow = slow.next
slow2 = slow2.next
return slow解题思路：快慢指针法，当slow与fast相遇时，slow走过的就是环的长度。
52、链表
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
if (not pHead) or (not pHead.next):
return pHead
head = ListNode(0)
head.next = pHead
pre = head
last = head.next
while last:
if last.next and last.val == last.next.val:
while last.next and last.val == last.next.val:
last = last.next
pre.next = last.next
last = last.next
else:
pre = pre.next
last = last.next
return head.next 解题思路：注意构建新的链表。
53、树
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
# -*- coding:utf-8 -*-
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
def GetNext(self, pNode):
# write code here
if not pNode:
return None
if pNode.right != None:
r = pNode.right
while r and r.left != None:
r = r.left
elif pNode.next != None:
if pNode.left == None:
if pNode.next.left == pNode:
r = pNode.next
elif pNode.next.next.left != pNode.next:
return None
else:
r = pNode.next.next
else:
r = pNode.next
else:
r = None
return r解题思路：要考虑多种情况
54、树
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSymmetrical(self, pRoot):
if not pRoot:
return True
else:
return self.check(pRoot.left, pRoot.right)
def check(self, left, right):
if (not left) and (not right):
return True
elif not(left and right):
return False
if left.val != right.val:
return False
return self.check(left.left, right.right) and self.check(right.left, left.right)解题思路：递归加判断。
55、树
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def Print(self, pRoot):
# write code here
if not pRoot:
return []
stack = [pRoot]
res = []
while stack:
tmp = []
for i in range(len(stack)):
t = stack.pop(0)
tmp.append(t.val)
if t.left != None:
stack.append(t.left)
if t.right != None:
stack.append(t.right)
res.append(tmp)
for i in range(len(res)):
if i & 1 == 1:
res[i] = res[i][::-1]
return res解题思路：先层次遍历，再转换。
56、树
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if not pRoot:
return []
stack = [pRoot]
res = []
while stack:
tmp = []
for i in range(len(stack)):
t = stack.pop(0)
tmp.append(t.val)
if t.left != None:
stack.append(t.left)
if t.right != None:
stack.append(t.right)
res.append(tmp)
return res解题思路：就是层次遍历。
57、树
请实现两个函数，分别用来序列化和反序列化二叉树
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.flag = -1
def Serialize(self, root):
# write code here
if not root:
return '#,'
return str(root.val)+','+self.Serialize(root.left)+self.Serialize(root.right)
def Deserialize(self, s):
# write code here
self.flag += 1
l = s.split(',')
if self.flag >= len(s):
return None
root = None
if l[self.flag] != '#':
root = TreeNode(int(l[self.flag]))
root.left = self.Deserialize(s)
root.right = self.Deserialize(s)
return root解题思路：递归前序遍历二叉树，对每个节点的孩子如果遇到空就以#来代替，最终得到一个字符串。读取字符串，当前字符作为根，下一个字符作为当前的左孩子，依此递归进行前序遍历，恢复树结构。
58、二叉排序树
给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode
def __init__(self):
self.cur = 0
def KthNode(self, pRoot, k):
# write code here
if k <= 0:
return None
if pRoot == None:
return None
left_val = self.KthNode(pRoot.left,k)
if left_val:
return left_val
self.cur += 1
if self.cur == k:
return pRoot
right_val = self.KthNode(pRoot.right, k)
if right_val:
return right_val
return None解题思路：递归左子树，并判断有无返回节点。如果有，停止递归，返回所要返回的节点；当左子树没有返回节点时，判断当前的根节点是不是第k个遍历到的值（即第k大）。如果是，则返回该节点，停止递归；当左子树和根节点都没有返回节点时，递归右子树，并判断有无返回节点。如果有，停止递归，返回所要返回的节点。
59、堆
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.arr=[]
def Insert(self, num):
self.arr.append(num)
self.arr.sort()
def GetMedian(self,fuck):
length=len(self.arr)
return self.arr[length//2] if length%2==1 else (self.arr[length//2]+self.arr[length//2-1])/2.0这是一般人的思想，另一种是考虑用堆；
import math
import heapq
class Solution:
nums = []
def Insert(self, num):
heapq.heappush(self.nums, num)
def GetMedian(self):
mid = math.ceil(len(self.nums)/2)
return (heapq.nlargest(mid, self.nums)[-1] + heapq.nsmallest(mid, self.nums)[-1])/2.060、数组
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{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]}。
# -*- coding:utf-8 -*-
class Solution:
def maxInWindows(self, num, size):
# write code here
if size <= 0:
return []
left = 0
right = size - 1
res = []
while right <= len(num) - 1:
tmp = num[left:right+1]
m = max(tmp)
res.append(m)
left += 1
right += 1
return res61、递归、回溯、匹配
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
class Solution:
def hasPath(self, matrix, rows, cols, path):
# write code here
if not matrix and rows <= 0 and cols <= 0 and path == None:
return False
# 模拟的字符矩阵
markmatrix = [0] * (rows * cols)
pathlength = 0
# 从第一个开始递归，当然第一二个字符可能并不位于字符串之上，所以有这样一个双层循环找起点用的，一旦找到第一个符合的字符串，就开始进入递归，
# 返回的第一个return Ture就直接跳出循环了。
for row in range(rows):
for col in range(cols):
if self.hasPathCore(matrix, rows, cols, row, col, path, pathlength, markmatrix):
return True
return False
def hasPathCore(self, matrix, rows, cols, row, col, path, pathlength, markmatrix):
# 说明已经找到该路径，可以返回True
if len(path) == pathlength:
return True
hasPath = False
if row >= 0 and row < rows and col >= 0 and col < cols and matrix[row * cols + col] == path[pathlength] and not \
markmatrix[row * cols + col]:
pathlength += 1
markmatrix[row * cols + col] = True
# 进行该值上下左右的递归
hasPath = self.hasPathCore(matrix, rows, cols, row - 1, col, path, pathlength, markmatrix) \
or self.hasPathCore(matrix, rows, cols, row, col - 1, path, pathlength, markmatrix) \
or self.hasPathCore(matrix, rows, cols, row + 1, col, path, pathlength, markmatrix) \
or self.hasPathCore(matrix, rows, cols, row, col + 1, path, pathlength, markmatrix)
# 对标记矩阵进行布尔值标记
if not hasPath:
pathlength -= 1
markmatrix[row * cols + col] = False
return hasPath62、递归、回溯
地上有一个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 movingCount(self, threshold, rows, cols):
# write code here
markmatrix = [False] * (rows * cols)
count = self.GetNum(threshold, rows, cols, 0, 0, markmatrix)
return count
def GetNum(self, threshold, rows, cols, row, col, markmatrix):
count = 0
if self.GetSum(threshold, rows, cols, row, col, markmatrix):
markmatrix[row * cols + col] = True
count = 1 + self.GetNum(threshold, rows, cols, row - 1, col, markmatrix) + \
self.GetNum(threshold, rows, cols, row, col - 1, markmatrix) + \
self.GetNum(threshold, rows, cols, row + 1, col, markmatrix) + \
self.GetNum(threshold, rows, cols, row, col + 1, markmatrix)
return count
def GetSum(self, threshold, rows, cols, row, col, markmatrix):
if row >= 0 and row < rows and col >= 0 and col < cols and self.getDigit(row) + self.getDigit(
col) <= threshold and not markmatrix[row * cols + col]:
return True
return False
def getDigit(self, number):
sumNum = 0
while number > 0:
sumNum += number % 10
number = number // 10
return sumNum解题思路：回溯法，递归，注意判断条件。