斐波拉契数列
面试题007 斐波拉契数列
题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39
解题思路：利用dp[i]=dp[i-1]+dp[i-2]
代码
class Solution:
def Fibonacci(self, n):
# write code here
f1 = 0
f2 = 1
if n== 0:
return f1
elif n==1:
return f2
for _ in range(n-1):
f2, f1 = f1+f2, f2
return f2
面试题008 跳台阶
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解题思路：假设第n节台阶有f(n)种跳法。f(1)=1,f(2)=2,f(n)=f(n-1)+f(n-2)
代码
class Solution:
def jumpFloor(self, number):
# write code here
f0 = 0
f1 = 1
f2 = 2
if number == 0:
return f0
if number == 1:
return f1
if number == 2:
return f2
for _ in range(number-2):
f2, f1 = f1+f2, f2
return f2%1000000007
面试题009 变态跳台阶
题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
解题思路：f(1)=1 f(2)=2 f(3)=4 f(4) = 8 ... 得到f(n+2)=2f(n+1)
代码
class Solution:
def jumpFloorII(self, number):
# write code here
f1 = 1
if number == 1:
return f1
for _ in range(number-1):
f1 = 2*f1
return f1
面试题010 矩形覆盖
题目描述：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
解题思路：f(1)=1 f(2)=2 f(n)=f(n-1)+f(n-2)
代码
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
f1 = 1
f2 = 2
if number == 1:
return f1
if number == 2:
return f2
for _ in range(number-2):
f2, f1 = f1+f2, f2
return f2
搜索算法
面试题001 二维数组查找
题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
解题思路：分治解题 从右上角(或左下角)开始查找，target更大 指针下移 target更小 指针左移
代码
function Find(target, array)
{
// write code here
if(array.length != 0) {
var row=0;
var col=array[0].length - 1;
while(row<array.length&&col>=0) {
if(array[row][col]==target) {
return true;
}else if(array[row][col]<target) {
++row;
}else {
--col;
}
}
return false;
}
}
面试题006 旋转数组的最小数字
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
解题思路：From 牛客剑指offer
二分查找变形
二分查找分为三种情况讨论：
1.如果mid > high那么mid一定不是最小的,所以low = mid + 1
2.如果mid < high那么mid可能是最小的，也可能不是，所以high = mid
3.如果mid == high，情况比较特殊例如[0, 1， 1, 1]和[1, 1, 0, 1]，这种只能一个个试high = high -1
题目中给的旋转数组是非递减而不是递增，所以一定要考虑第三种情况
代码
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if not rotateArray:
return 0
lowp = 0
highp = len(rotateArray) - 1
while lowp < highp:
mid = (lowp + highp) // 2
if rotateArray[mid] < rotateArray[highp]:
highp = mid
continue
if rotateArray[mid] > rotateArray[highp]:
lowp = mid + 1
continue
if rotateArray[mid] == rotateArray[highp]:
highp = highp - 1
return rotateArray[lowp]
解题思路：From 牛客剑指offer
非递减是指列表list[i]<=list[i+1],list[2:]中存在一个最小数
代码
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
for i in range(len(rotateArray)-1):
if(rotateArray[i+1]<rotateArray[i]):
return rotateArray[i+1]
return -1
面试题037 数字在排序数组中出现的次数
题目描述：统计一个数字在排序数组中出现的次数。
解题思路：通过两次二分查找，递归中直接计算k的个数
代码
class Solution:
def GetNumberOfK(self, data, k):
if not data:
return 0
return self.helper(data,k)
def helper(self,data,k):
if not data:
return 0
left, right = 0, len(data) - 1
mid = (left + right) // 2
if data[mid] > k:
return self.helper(data[:mid], k)
elif data[mid] < k:
return self.helper(data[mid + 1:], k)
else:
return 1 + self.helper(data[:mid], k) + self.helper(data[mid + 1:], k)
解题思路：双指针
代码
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if len(data)==1:
return 1 if k in data else 0
left=0
right=len(data)-1
while left<right:
if data[left]!=k:
left+=1
if data[right]!=k:
right-=1
if data[left]==k and data[right]==k:
return right-left+1
return 0
全排列
面试题027 字符串的排序
题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
解题思路：From 剑指Offer 全排列
代码
class Solution:
def Permutation(self, ss):
if len(ss) <= 1:
return ss
res = set()
# 遍历字符串，固定第一个元素，第一个元素可以取a,b,c...，然后递归求解
for i in range(len(ss)):
for j in self.Permutation(ss[:i] + ss[i+1:]): # 依次固定了元素，其他的全排列（递归求解）
res.add(ss[i] + j) # 集合添加元素的方法add(),集合添加去重（若存在重复字符，排列后会存在相同，如baa,baa）
return sorted(res) # sorted()能对可迭代对象进行排序,结果返回一个新的list
解题思路：Frome leetcode
回溯法
第一步,求所有可能出现在第一个位置的字符,即把第一个字符和后面所有的字符进行交换
第二步,固定住第一个字符,求后面字符的全排列.这时候我们仍把后面的字符分成两部分: 后面字符的第一个字符以及这个字符后面的所有字符.
然后把第一个字符逐一和它后面的字符交换.
算法最后的结果可能会有重复的情况出现,我们使用python自带的set()函数来去重
代码
class Solution(object):
def permutation(self, s):
"""
:type s: str
:rtype: List[str]
"""
result = []
if not s:
return []
s = list(s)
temp = []
self.stringSort(s, temp, result)
return list(set(result))
def stringSort(self, s, temp, result):
if len(s) == 1:
temp.append(s[0])
result.append(''.join(temp))
temp.pop()
return
for i in range(0,len(s)):
if i!= 0 and s[i] == s[0]:
continue
s[0],s[i] = s[i],s[0]
temp.append(s[0])
self.stringSort(s[1:], temp, result)
temp.pop()
s[i], s[0], = s[0], s[i]
动态规划
面试题030 连续数组的最大和
题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
解题思路：动态规划
代码
class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
n = len(array)
dp = [ i for i in array]
for i in range(1,n):
dp[i] = max(dp[i-1]+array[i],array[i])
return max(dp)
面试题052 正则表达式匹配
题目描述：请实现一个函数用来匹配包括'.'和''的正则表达式。模式中的字符'.'表示任意一个字符，而''表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但是与"aa.a"和"ab*a"均不匹配
解题思路：From 剑指offer
代码
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 False
解题思路：回溯
代码
class Solution:
# s, pattern都是字符串
def isMatch(self, s, p):
if not p: return not s
# 第一个字母是否匹配
first_match = bool(s and p[0] in {s[0],'.'})
# 如果 p 第二个字母是 *
if len(p) >= 2 and p[1] == "*":
return self.isMatch(s, p[2:]) or
first_match and self.isMatch(s[1:], p)
else:
return first_match and self.isMatch(s[1:], p[1:])
解题思路：递归
代码
class Solution:
# s, pattern都是字符串
def match(self, s, pattern):
# write code here
if pattern =="":
return s==""
if len(pattern)>1 and pattern[1]=="*":
return self.match(s, pattern[2:]) or (s and (s[0]==pattern[0] or pattern[0] == '.') and self.match(s[1:],pattern))
else:
return s and (s[0]==pattern[0] or pattern[0]=='.')and self.match(s[1:],pattern[1:])
排序
面试题035 数组中的逆序数
题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
题目保证输入的数组中没有的相同的数字
数据范围：
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入 1,2,3,4,5,6,7,0
输出 7
解题思路：归并
代码
class Solution:
def InversePairs(self, data):
#发现可以用归并排序，归并拼接后用计算排序时元素的index变动了多少
#两个有序序列，每个元素移动index数（严格来说不是移动，这里不知怎么表达）之和好像刚好等于逆序对的个数
#我也不知为什么，找了半天发现了这个规律
_,s=self.MergeSort(data)
return s%1000000007
def MergeSort(self,data):
n=len(data)
#递归基
if n==1:return data, 0
#分两半来排序
part1,part2=data[:n//2],data[n//2:]
sorted_part1,s1=self.MergeSort(part1)
sorted_part2,s2=self.MergeSort(part2)
#排序后拼接这两半，拼接后先计数，然后将两个有序序列合并
s,sorted_temp=0,sorted_part1+sorted_part2
#用p、q两个指针指向两段，计算q中每个元素离插入点的index差
p,q,len1,len_all=0,sorted_temp.index(sorted_part2[0]),len(sorted_part1),len(sorted_temp)
while p<len1 and q<len_all:
#移动p使p成为插入排序的插入点，计算要移动多少个位置
while p<len1:
if sorted_temp[q]<sorted_temp[p]:
s+=len1-p
break
p+=1
q+=1
#完成排序，并把排序后的内容回溯给上一级做准备
l=[]
p,q=0,sorted_temp.index(sorted_part2[0])
while p<len1 and q<len_all:
if sorted_temp[p]<sorted_temp[q]:
l.append(sorted_temp[p])
p+=1
else:
l.append(sorted_temp[q])
q+=1
if p==len1:l+=sorted_temp[q:]
if q==len_all:l+=sorted_part1[p:]
return l,s+s1+s2
代码
class Solution:
def reversePairs(self, nums: List[int]) -> int:
def mergeSort(l=0, r=len(nums)):#左闭右开区间
if r - l > 1:
mid = (l + r)//2
mergeSort(l, mid)
mergeSort(mid, r)
i, j, tmp = l, mid, []
while i < mid and j < r:
if nums[i] <= nums[j]:
tmp.append(nums[i])
i += 1
else:
tmp.append(nums[j])
j += 1
self.cnt += mid - i
tmp.extend(nums[i:mid] if i<mid else nums[j:r])
nums[l:r] = tmp
self.cnt = 0
mergeSort()
return self.cnt
位运算
面试题011 二进制中1的个数
题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
解题思路：二进制表示中，末尾的1减去后，低位变为0，高位不变，按位与就可以去掉这个1
代码
# From leetcode
class Solution(object):
def hammingWeight(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
while n:
res += 1
n &= n - 1
return res
# From 剑指offer 使用c_int()函数，不然负数不会变成0
from ctypes import *
class Solution:
def NumberOf1(self, n):
# write code here
ret = 0
while c_int(n).value:
ret += 1
n = n & n-1
return ret
面试题012 数值的整数次方
解题思路1 考虑所有情况，循环连乘
代码：
def power(base, exponent):
if (base==0):
return 0
if (exponent == 0):
return 1
res = 1
for i in range(abs(exponent)): #i只是循环变量，不起作用
res *= base
return 1/res if exponent < 0 else res
解题思路2 快速幂快速幂详解
代码
def fast_power(self, base, exponent):
if base == 0:
return 0
if exponent == 0:
return 1
e = abs(exponent)
tmp = base
res = 1
while(e > 0):
#如果最后一位为1，那么给res乘上这一位的结果
if (e & 1 == 1):
res =res * tmp
e = e >> 1
tmp = tmp * tmp
return res if exponent > 0 else 1/res
面试题040 数组中只出现一次的数字
题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解题思路：HashMap
代码
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
hashMap = {}
for i in array:
if str(i) in hashMap:
hashMap[str(i)] += 1
else:
hashMap[str(i)] = 1
res = []
for k in hashMap.keys():
if hashMap[k] == 1:
res.append(int(k))
return res
class Solution:
def FindNumsAppearOnce(self, array):
# write code here
map = {}
res = []
for n in array:
map[n] = map.get(n,0)+1
for n in array:
if map[n] == 1:
res.append(n)
return res
解题思路：位运算中异或性质，两个相同数字异或是0 一个数和0异或还是它本身
代码
class Solution:
def FindNumsAppearOnce(self, array):
if not array:
return []
# 对array中的数字进行异或运算
tmp = 0
for i in array:
tmp ^= i
# 获取tmp中最低位1的位置
idx = 0
while (tmp & 1) == 0:
tmp >>= 1
idx += 1
a = b = 0
for i in array:
if self.isBit(i, idx):
a ^= i
else:
b ^= i
return [a, b]
def isBit(self, num, idx):
"""
判断num的二进制从低到高idx位是不是1
:param num: 数字
:param idx: 二进制从低到高位置
:return: num的idx位是否为1
"""
num = num >> idx
return num & 1
其他算法
面试题002 替换空格
题目描述：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解题思路：遍历空格并替换
代码
class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
s = list(s)
count = len(s)
for i in range(0,count):
if s[i]==' ':
s[i] = '%20'
return ''.join(s)
面试题013 调整数组顺序使奇数位于偶数前面
题目描述：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解题思路：遍历，分两个数组分别统计奇数偶数，最后拼接
代码
class Solution:
def reOrderArray(self, array):
# write code here
odd,even = [],[]
for i in array:
odd.append(i) if i%2==1 else even.append(i)
return odd+even
面试题028 数组中出现次数超过一半的数字
题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解题思路：统计数组中每个元素出现的次数，返回次数大于数组长度一半的元素
代码
import collections
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
# write code here
temp = collections.Counter(numbers)
x = len(numbers)/2
for k,v in temp.items():
if v > x:
return k
return 0
面试题031 整数中1出现的次数
题目描述：求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中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%101)，需要增加局部点b+1
之所以补8，是因为当百位为0，则a/10(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)
代码
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
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
面试题032 把数组排成最小的数
题目描述：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路：将n1 n2转成字符串 s1 s2 ，拼接成s1s2 s2s1 取整比较大小，小的放前面
代码
class Solution:
def PrintMinNumber(self, numbers):
# write code here
if not numbers:
return ""
lmb = lambda n1, n2:int(str(n1)+str(n2))-int(str(n2)+str(n1))
array = sorted(numbers, cmp=lmb)
return ''.join([str(i) for i in array])
面试题033 丑数
题目描述：把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
示例
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
解题思路：From Leetcode 动态规划
代码
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
dp, a, b, c = [1] * n, 0, 0, 0
for i in range(1, n):
n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
dp[i] = min(n2, n3, n5)
if dp[i] == n2: a += 1
if dp[i] == n3: b += 1
if dp[i] == n5: c += 1
return dp[-1]
# 剑指Offer
# -*- coding:utf-8 -*-
class Solution:
def GetUglyNumber_Solution(self, index):
if index < 1:
return 0
res = [1]
t2 = t3 = t5 = 0
nextIdx = 1
while nextIdx < index:
minNum = min(res[t2] * 2, res[t3] * 3, res[t5] * 5)
res.append(minNum)
while res[t2] * 2 <= minNum:
t2 += 1
while res[t3] * 3 <= minNum:
t3 += 1
while res[t5] * 5 <= minNum:
t5 += 1
nextIdx += 1
return res[nextIdx - 1]
面试题 顺时针打印矩阵
题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
解题思路:打印第一行 然后删除第一行 剩余部分逆时针转动90度。重复以上步骤，直到矩阵为空
代码
# -*- coding:utf-8 -*-
class Solution:
def printMatrix(self, matrix):
# write code here
s=[]
while matrix:
s+=matrix[0]
del matrix[0]
matrix=zip(*matrix)[::-1]
return s
面试题 旋转数组的最小数字
题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
解题思路：分治法是不断的缩小范围,从而找到符合条件的解
二分法的分析我们知道,数组可以分为前后两个递增数组,下面的分析也都利用递增的特性
当numbers[mid] > numbers[high]时,说明最小值在mid的右边,缩小范围low = mid + 1
当numbers[mid] == numbers[high]时,我们不知道最小值的范围,但是可以肯定的是去除numbers[high]是没有影响的,缩小范围high -= 1
当numbers[mid] < numbers[high]时,我们知道最小值的不是numbers[mid]]就是在mid的左边,缩小范围high = mid
代码
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if not rotateArray:
return None
low = 0
high = len(rotateArray) - 1
while low < high:
mid = (low + high) >> 1
if rotateArray[mid] > rotateArray[high]:
low = mid + 1
elif rotateArray[mid] == rotateArray[high]:
high -= 1
else:
high = mid
return rotateArray[low]
面试题 数据流中的中位数
题目描述：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 ：
输入：
["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
解题思路：首先对数组执行排序（使用 O(N log N)O(NlogN) 时间），然后返回中间元素即可（使用 O(1)O(1) 时间）。
代码
from heapq import *
class MedianFinder:
def __init__(self):
self.A = [] # 小顶堆，保存较大的一半
self.B = [] # 大顶堆，保存较小的一半
def addNum(self, num):
if len(self.A) != len(self.B):
heappush(self.A, num)
heappush(self.B, -heappop(self.A))
else:
heappush(self.B, -num)
heappush(self.A, -heappop(self.B))
def findMedian(self):
return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0
代码优化:
from heapq import *
class MedianFinder:
def __init__(self):
self.A = [] # 小顶堆，保存较大的一半
self.B = [] # 大顶堆，保存较小的一半
def addNum(self, num):
if len(self.A) != len(self.B):
heappush(self.B, -heappushpop(self.A, num)) # 先加到小顶堆，再把小堆顶元素加到大顶堆
else:
heappush(self.A, -heappushpop(self.B, -num)) # 先加到大顶堆，再把大堆顶元素加到小顶堆
def findMedian(self):
return self.A[0] if len(self.A) != len(self.B) else (self.A[0] - self.B[0]) / 2.0
将中位数左边的数保存在大顶堆中，右边的数保存在小顶堆中。这样可以在 {mathcal{O}}(1)O(1) 时间内得到中位数。
注意：Python 中没有大顶堆，只能将值取负保存在小顶堆来模拟。为了方便理解，将堆用优先队列表示
面试题 字符串流中第一个不重复的字符
题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。
解题思路：利用hash表记录字符串s中每个字符出现的次数，再遍历字符串，判断出现次数是否为1，如果是则返回所在位置；遍历完成都没有则说明没有只出现过一次的字符，返回-1
代码
class Solution:
# 返回对应char
def __init__(self):
self.s=''
self.dict1={}
def FirstAppearingOnce(self):
# write code here
for i in self.s:
if self.dict1[i]==1:
return i
return '#'
def Insert(self, char):
# write code here
self.s=self.s+char
if char in self.dict1:
self.dict1[char]=self.dict1[char]+1
else:
self.dict1[char]=1
class Solution:
def __init__(self):
self.s = ''
self.queue = [] #按顺序保存所有只出现一次的字符
self.second = [] #按顺序保存所有出现过的字符
def FirstAppearingOnce(self):
if self.queue:
return self.queue[0]
return '#'
def Insert(self, char):
self.s += char
if char in self.queue:
self.queue.pop(self.queue.index(char))
elif char not in self.second:
self.queue.append(char)
self.second.append(char)
面试题 表示数值的字符串
题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
解题思路：
代码
# 正则
class Solution:
# s字符串
def isNumeric(self, s):
import re
p=re.compile(r'^[+-]?d*(.d+)?([eE][+-]?d+)?$')
return p.match(s)
From leetcode
class Solution(object):
def isNumber(self, s):
"""
:type s: str
:rtype: bool
"""
if '' == s[0]:
return False
else:
s1 = s.rstrip().strip()
if " " in s1:
return False
# 先对+ -号处理
for i in ['+','-']:
if i in s1:
if s1.rindex(i) == 0:
if 'e'==s1[1] :
return False
else: pass
else:
if s1.count(i)==2:
if s1.index(i)==0 and 'e' == s1[s1.rindex(i) -1] and '' != s1[s1.rindex(i)+1:]:pass
else: return False
elif s1.count(i)==1:
if 'e' == s1[s1.rindex(i) -1] and '' != s1[s1.rindex(i)+1:]: pass
else: return False
else:return False
# 对 “.”处理
if '.' in s1:
if s1.count('.') == 1:
pass
else:
return False
# 对 “e”处理
if 'e' in s1:
if s1.count('e') == 1:
e_l = s1.split('e')
if len(e_l[1])>0:
if '.' in e_l[1]:
return False
else:
return False
if len(e_l[0])>0:
if '.'==e_l[0]:
return False
else:
return False
else:
return False
# 数字判断
s2 = s1.replace('+','').replace('-','').replace('.','').replace('e','')
if len(s2)>0:
for i in s2:
if i in ['1','2','3','4','5','6','7','8','9','0']:
pass
else:return False
return True
else:
return False
class Solution(object):
def isNumber(self, s):
try:
s = float(s)
return True
except:
return False