面试题3：数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

如果数组中没有重复数字，那么当数组排序之后数字i将出现在下标为i的位置。由于数组中有重复数字，有些位置可能存在多个数字，同时有些位置可能没有数字。

class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
# write code here
if len(numbers)==0 or len(numbers)==1:
return False
n=len(numbers)
temp=0
for i in range(n):
while numbers[i]!=i:
if numbers[numbers[i]]!=numbers[i]:
temp=numbers[numbers[i]]
numbers[numbers[i]]=numbers[i]
numbers[i]=temp
else:
duplication[0]=numbers[i]
return True
return False

面试题4：二维数组中查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

从左下角元素(标黄)开始找，如果目标值比该元素小，向上移动一行；如果目标值比该元素大，向右移动一列；如果目标值和元素值相等，找到元素并返回True，否则返回False。

e.g.
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15

class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
if len(array[0])==0 or len(array)==0:
return False
i=0
j=-1
while i<len(array[0]) and j>-1*len(array)-1:
if array[j][i] == target:
return True
elif array[j][i]>target:
j-=1
else:
i+=1
return False

面试题5：替换空格

• replace函数

class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
return s.replace(' ','%20')

• 自行实现replace函数

class Solution:
# s 源字符串
def replaceSpace(self, s):
# write code here
l = list(s)
for i in range(len(l)):
if l[i] == ' ':
l[i]='%20'
return "".join(l)

面试题6：从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

# -*- coding:utf-8 -*-
# class ListNode:
#
def __init__(self, x):
#
self.val = x
#
self.next = None
class Solution:
# 返回从尾部到头部的列表值序列，例如[1,2,3]
def printListFromTailToHead(self, listNode):
# write code here
l=[]
while listNode != None:
l.append(listNode.val)
listNode=listNode.next
return l[::-1]

面试题7：重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

• 前序遍历是根左右、中序遍历是左根右

# -*- coding:utf-8 -*-
# class TreeNode:
#
def __init__(self, x):
#
self.val = x
#
self.left = None
#
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if not pre or not tin:
return None
root=TreeNode(pre.pop(0))
index=tin.index(root.val)
root.left=self.reConstructBinaryTree(pre,tin[:index])
root.right=self.reConstructBinaryTree(pre,tin[index+1:])
return root

面试题8：二叉树的下一个节点

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

如果一个节点有右子树，那么它的下一个节点就是它右子树中的最左子节点；
如果一个节点没有右子树：

• 节点是它父节点的左子节点，那么它的下一个节点就是它的父节点；
• 节点是它父节点的右子节点，我们可以沿着指向父节点的指针一直向上遍历，直到找到一个它父节点的左子节点的节点，如果存在，那么这个节点的父节点就是我们找的下一个节点。

# -*- 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 pNode.right:# 如果有右子树
p = pNode.right
while p.left:
p = p.left
return p
else:# 如果没有右子树
while pNode.next:
if pNode.next.left == pNode:
return pNode.next
pNode = pNode.next
return

面试题9：用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

class Solution:
def __init__(self):
self.stack1=[]
self.stack2=[]
def push(self, node):
# write code here
self.stack1.append(node)
def pop(self):
# return xx
if self.stack2==[]:
while self.stack1!=[]:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()

面试题10：斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。n<=39
0 1 1 2 3 5 8 13…

• 递归实现（牛客无法通过，时间复杂度过大）：

当n=0时，f(0)=0
当n=1时，f(1)=1
当n=k(k>1)时，f(k)=f(k-1)+f(k-2)

class Solution:
def Fibonacci(self, n):
if n == 1:
return 1
if n == 0:
return 0
return self.Fibonacci(n - 1) + self.Fibonacci(n - 2)

时间复杂度为O(2ⁿ)

• 非递归实现：

class Solution:
def Fibonacci(self, n):
a_0=0
a_1=1
l=[a_0,a_1]
for i in range(n+1):
a_2=a_0+a_1
l.append(a_2)
a_0=a_1
a_1=a_2
return l[n]

时间复杂度为O(n)

跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

其实就是斐波那契，如果只有一个台阶有一种跳法，两个台阶两种跳法（一次蹦两个、一个一个蹦）

• 非递归实现：

class Solution:
def jumpFloor(self, number):
a_1=1
a_2=2
if number==1:
return a_1
elif number==2:
return a_2
else:
for i in range(3,number+1):
temp=a_1+a_2
a_1=a_2
a_2=temp
return a_2

变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

• 规律1实现：

class Solution:
def jumpFloorII(self, number):
# number 1 -- 1
# number 2 -- 2
# number 3 -- 4
# number 4 -- 8
# ......
# number n -- 2^(n-1)
return pow(2,number-1)

• 规律2实现：

class Solution:
def jumpFloorII(self, number):
# f(n)=f(n-1)+f(n-2)+……+f(1)
# f(n-1)=f(n-2)+f(n-3)+……+f(1)
# f(n)=2*f(n-1)
if number==1:
return 1
else:
return 2*self.jumpFloorII(number-1)

矩阵覆盖

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

• 还是斐波那契的思路，左上角横着放f(n-2)和左上角竖着放f(n-1)，结合就是f(n)

class Solution:
def rectCover(self, number):
# write code here
n=number
a_1=1
a_2=2
ans=0
if n==0:
return 0
if n==1:
return a_1
if n==2:
return a_2
if n>2:
for i in range(3,n+1):
ans=a_1+a_2
a_1=a_2
a_2=ans
return ans

面试题11：旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

• 方法1：从头到尾遍历

class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray)==0:
return 0
minNum = rotateArray[0]
for v in rotateArray:
if minNum > v:
minNum = v
return minNum

• 方法2：二分法(与最右边的数比)

class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray) == 0:
return 0
if len(rotateArray) == 1:
return rotateArray[0]
left = 0
right = len(rotateArray) - 1
while left <= right:
mid = (left + right) // 2
if rotateArray[mid] > rotateArray[right]:
left = mid + 1
elif rotateArray[mid] < rotateArray[right]:
right = mid
else:
right -= 1
return rotateArray[left]

面试题14：剪绳子

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]xk[1]x…xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

• 方法一：动态规划

class Solution:
# 贪婪算法
def cutRope(self, number):
# 长度3 以下时，同时要求必须切一刀，最大值结果
n = number
if n < 2:
return 0
if n == 2:
return 1
if n == 3:
return 2
products=[0,1,2,3] # 长度为0,1,2,3时能取得的最大值(不考虑必须切一刀)
# 公式：f(i) = max(f(j)*f(i-j)),其中i为长度（i>=4），j为从绳中间某个位置切(为了不重复计算，j计算到绳长的一半即可)
for i in range(4, n+1):
tmp_max = 0
for j in range(1, n//2+1):
if products[j]*products[i-j]>tmp_max:
tmp_max = products[j]*products[i-j]
products.append(tmp_max)
return products[-1]

• 方法二：贪婪算法（尽量多的3）

class Solution:
# 贪婪算法
def cutRope(self, number):
# 长度3 以下时，同时要求必须切一刀，最大值结果
n = number
if n < 2:
return 0
if n == 2:
return 1
if n == 3:
return 2
# 贪婪算法的基本思想是当长度大于5时让长度是3的绳子尽量多
# 1. 如果绳子长度本身就是3的倍数，就全部按照3来剪
ans = 1
if n % 3 == 0:
num = n // 3
for i in range(num):
ans = ans * 3
return ans
# 2. 如果绳子长度全分成3后，余1，那么3就少剪一个，最后留4剪成2、2
if n % 3 == 1:
num = n // 3 - 1
for i in range(num):
ans = ans * 3
return ans * 4
# 3. 如果绳子长度全分成3后，余2，那么3就少剪一个，最后留5剪成3、2
if n % 3 == 2:
num = n // 3 - 1
for i in range(num):
ans = ans * 3
return ans * 6

面试题15：二进制中1的个数

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

• 方法一：转换成二进制（字符串），直接数“1”的个数

class Solution:
def NumberOf1(self, n):
n = n & 0xFFFFFFFF
bin_num = bin(n)
count=0
for i in bin_num:
if i == '1':
count+=1
return count

• 方法二： 位运算
  mask=1<<i，其中i表示向左移动几位，右边加0，并与原来结果相与。原数位为1，相与结果为1；原数位为0，相与结果为0（if那句话）。

class Solution:
def NumberOf1(self, n):
n = n & 0xFFFFFFFF
count = 0
for i in range(32):
mask = 1 << i
if mask & n != 0:
count+=1
return count

• 方法三：骚操作
  n与n-1相与，每次循环可以将n中的一个1去掉，直到所有1去掉变为0。

class Solution:
def NumberOf1(self, n):
n = n & 0xFFFFFFFF
count = 0
while n:
n = n&(n-1)
count += 1
return count

面试题16：数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0。

• 普通方法（考虑指数大于0，等于0，小于0三种情况）

class Solution:
def Power(self, base, exponent):
# write code here
ans=1
if exponent>0:
while exponent>0:
ans=ans*base
exponent-=1
return ans
elif exponent==0:
return 1
else:
while exponent<0:
ans=ans*base
exponent+=1
return 1/ans

• 递归：递归函数外判断指数正负，并得到相应结果

class Solution:
def Power(self, base, exponent):
if exponent == 0:
return 1
if exponent == 1:
return base
result = self.Power(base, exponent >> 2)
result *= result
if exponent & 0x1 == 1:
result *= base
return result

面试题21：调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

• 辅助数组

class Solution:
def reOrderArray(self, array):
# write code here
res = []
for i in array:
if i % 2==1:
res.append(i)
for i in array:
if i % 2==0:
res.append(i)
return res

时间和空间复杂度都为o(n)

面试题22：链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个结点。

• 遍历

# class ListNode:
#
def __init__(self, x):
#
self.val = x
#
self.next = None
class Solution:
def FindKthToTail(self, head, k):
# write code here
li=[]
while head:
li.append(head)
head=head.next
if k>len(li) or k<1:
return
else:
return li[-k]

面试题27：二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

• 对于根节点，执行左右子节点的互换；利用递归将左右子节点分别作为根节点代入上述函数。

# class TreeNode:
#
def __init__(self, x):
#
self.val = x
#
self.left = None
#
self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root == None:
return root
# 处理根节点
root.left, root.right = root.right, root.left
# 处理左右子节点
self.Mirror(root.left)
self.Mirror(root.right)

面试题28：对称的二叉树

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

• 递归

# class TreeNode:
#
def __init__(self, x):
#
self.val = x
#
self.left = None
#
self.right = None
class Solution:
def isSymmetrical(self, pRoot):
# write code here
def isMirror(left, right):
if left == None and right == None:
return True
elif left == None or right == None:
return False
if left.val != right.val:
return False
else:
ret1 = isMirror(left.left,right.right)
ret2 = isMirror(left.right,right.left)
return ret1 and ret2
if pRoot == None:
return True
return isMirror(pRoot.left,pRoot.right)

面试题30：包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。注意：保证测试中不会当栈为空的时候，对栈调用pop()或者min()或者top()方法。

• 引入一个辅助栈，该栈的功能是存入相应数据栈对应位置前最小的栈中数据，同时push和pop随着数据栈进行相应的处理。

class Solution:
def __init__(self):
self.stack=[] # 数据栈
self.min_stack=[] # 辅助栈
def push(self, node):
# write code here
self.stack.append(node)
if self.min_stack!=[]:
if self.min_stack[-1]<node:# 新入栈的元素比min_stack栈顶元素大
self.min_stack.append(self.min_stack[-1])
else:# 新入栈的元素比min_stack栈顶元素小
self.min_stack.append(node)
else:#min_stack为空，直接插入node
self.min_stack.append(node)
def pop(self):
# write code here
if self.stack!=[]:
self.min_stack.pop()
return self.stack.pop()
else:
return None
def top(self):
# write code here
if self.stack!=[]:
return self.stack[-1]
else:
return None
def min(self):
# write code here
if self.min_stack!=[]:
return self.min_stack[-1]
else:
return None

面试题31：栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

• 解题步骤：
  【1】首先需要有一个栈
  【2】按照pushV的方式将元素依次压入栈
  【3】弹出的时候是需要循环判断是否需要弹出。判断需要弹出的情况的条件：压入栈的顶部（stack[-1]）和弹出栈的顶部（popV[i]）数据相等
  【4】判断是否需要弹出的时机，刚刚压入过后就判断
  【5】最后如果stack内都弹出了，说明popV是弹出序列，否则不是（上述弹出条件不满足，不弹出数据）

class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
if pushV==[] or len(pushV)!=len(popV): # 栈不为空，两个序列的长度相等
return None
stack=[]
i=0
for item in pushV:
stack.append(item)
while stack and stack[-1] == popV[i]:
stack.pop()
i+=1
return True if stack==[] else False

面试题32：从上到下打印二叉树

不分行从上到下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

• 引入一个队列，存放节点
  该题为对二叉树的层次遍历，引入一个队列，初始为只包含一个根节点（root），从队列出去一个元素，就将该元素的左右节点放入该队列中。

# class TreeNode:
#
def __init__(self, x):
#
self.val = x
#
self.left = None
#
self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if root is None:
return []
stack = [root]
l=[]
while stack:
l.append(stack[0].val)
if stack[0].left:
stack.append(stack[0].left)
if stack[0].right:
stack.append(stack[0].right)
del stack[0]
return l

分行从上到下打印二叉树

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

• 引入两个队列

# 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 pRoot is None:
return []
stack1=[pRoot]
stack2=[]
ret=[]
while stack1 or stack2:
# 奇数层
tmp_ret=[]
while stack1:
tmpNode=stack1[0]
tmp_ret.append(tmpNode.val)
if tmpNode.left:
stack2.append(tmpNode.left)
if tmpNode.right:
stack2.append(tmpNode.right)
del stack1[0]
if tmp_ret != []:
ret.append(tmp_ret)
# 偶数层
tmp_ret=[]
while stack2:
tmpNode=stack2[0]
tmp_ret.append(tmpNode.val)
if tmpNode.left:
stack1.append(tmpNode.left)
if tmpNode.right:
stack1.append(tmpNode.right)
del stack2[0]
if tmp_ret != []:
ret.append(tmp_ret)
return ret

之字形打印二叉树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

• 引入两个栈

# 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 []
stack1=[pRoot]
stack2=[]
ret=[]
while stack1 or stack2:
# 奇数层
tmpRet=[]
while stack1:
tmpNode=stack1.pop()
tmpRet.append(tmpNode.val)
if tmpNode.left:
stack2.append(tmpNode.left)
if tmpNode.right:
stack2.append(tmpNode.right)
if tmpRet!=[]:
ret.append(tmpRet)
# 偶数层（注意先右后左）
tmpRet=[]
while stack2:
tmpNode=stack2.pop()
tmpRet.append(tmpNode.val)
if tmpNode.right:
stack1.append(tmpNode.right)
if tmpNode.left:
stack1.append(tmpNode.left)
if tmpRet!=[]:
ret.append(tmpRet)
return ret

面试题33：二叉搜索树的后续遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

• 递归

class Solution:
def VerifySquenceOfBST(self, sequence):
# write code here
# 正常来说，空树是二叉搜索树，应该返回True，但是这道题视作False
if sequence == []:
return False
rootNum = sequence[-1] # 后序遍历的最后一个值为根节点的值
del sequence[-1] # 删除掉根节点，只剩下左子树和右子树
index = None
for i in range(len(sequence)):
if index == None and
sequence[i]>rootNum: # 寻找左右子树的分割线
index = i
if index != None and sequence[i]<rootNum: # 如果分割线的右边有比根节点小的数，说明不是二叉搜索树
return False
if sequence[:index] == []: # 空树是二叉搜索树
return True
else:
leftRet=self.VerifySquenceOfBST(sequence[:index]) # 递归左子树
if sequence[index:] == []: # 空树是二叉搜索树
return True
else:
rightRet=self.VerifySquenceOfBST(sequence[index:]) # 递归右子树
return leftRet and rightRet

面试题42：连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

class Solution:
def FindGreatestSumOfSubArray(self, array):
# write code here
max_num = None # 数组之和的最大值
tmp_num = 0 # 临时数：从某一个数开始的加和
for i in array:
if max_num == None: # 初始最大值为None时，将最大值设为第一个数
max_num = i
if tmp_num + i < i: # 如果临时数加上一个数后还没有这个数大，将临时数赋值为该数
tmp_num = i
else: # 否则临时数赋值为临时数加上该数
tmp_num += i
if max_num < tmp_num: # 更新数组之和的最大值
max_num = tmp_num
return max_num

面试题43：1~n整数中1出现的次数

输入一个整数n，求1 ~ n这n个整数的十进制表示中1出现的次数。例如，输入12，1~12这些整数中包含1的数字有1、10、11和12，1一共出现了5次。

• 字符串求解

class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
count=0
for i in range(1,n+1):
for s in str(i):
if s == '1':
count+=1
return count

• 三种情况分段

以n=3459082190为例，分成三段：lowNum（低位），midNum（中位），highNum（高位）
【1】如果midNum为1（highNum=3459082，midNum=1，lowNum=90），可以有两种情况：1的右边取大于90的情况和右边取小于等于90的情况，如果右边取大于90，左边只能取小于highNum的数（0 ~ 3459081）；如果右边取小于等于90，左边可以取等于及小于highNum的数（0 ~ 3459082）。
【2】如果midNum大于1（highNum=34590，midNum=8，lowNum=2190），当该位为1时，左边取0~34590，右边可以取任意四位数，也就是10⁴种取法。
【3】如果midNum小于1（highNum=3459，midNum=0，lowNum=82190），当该位为1时，必须得跟higNum借一位，所以左边取0~3458，右边可以取任意五位数，也就是10⁵种取法。

class Solution:
def NumberOf1Between1AndN_Solution(self, n):
# write code here
i=0
sum_num=0
highNum=1 # 初始化
while highNum!=0:
lowNum=n%(10**i)
midNum=n//(10**i)%10
highNum=n//(10**(i+1))
if midNum == 1:
sum_num+=(highNum+1)*(lowNum+1)+highNum*(10**i-lowNum-1)
if midNum >1:
sum_num+=(highNum+1)*(10**i)
if midNum <1:
sum_num+=highNum*(10**i)
i+=1
return sum_num

面试题49：丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

• 暴力求解（不推荐，牛客网无法通过）

class Solution:
# 判断丑数
def is_UglyBunber(self, num):
while num % 2 == 0:
num //= 2
while num % 3 == 0:
num //= 3
while num % 5 == 0:
num //= 5
if num == 1:
return True
else:
return False
def GetUglyNumber_Solution(self, index):
# write code here
l = []
i = 1
while True:
if self.is_UglyBunber(i) is True:
l.append(i)
i += 1
else:
i += 1
if len(l) == index:
return l[-1]

• 移动游标

设定三个游标，指向对应的数（初始都指向第一个数），并分别执行*2、*3、*5操作，哪个数最小就在list中插入，作为下一个丑数。

class Solution:
def GetUglyNumber_Solution(self, index):
if index<=0:
return 0
l=[1]
point_2=0
point_3=0
point_5=0
count=1
while count!=index:
l.append(min(2*l[point_2],3*l[point_3],5*l[point_5]))
count+=1
if 2*l[point_2]==l[-1]:
point_2+=1
if 3*l[point_3]==l[-1]:
point_3+=1
if 5*l[point_5]==l[-1]:
point_5+=1
return l[-1]

面试题56：数组中数字出现的次数

数组中只出现一次的两个数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

如果两个数相同，那么这两个数的异或操作就为0。首先将数组中所有的数进行异或处理，得到两个出现一次数字的异或结果。再找异或结果的第一个二进制不相同的位，将数组分成两组（一组该二进制位为0，另一组该二进制位为1），再在这两组中进行各自的异或处理，得到对应的两个数。

class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
if array == []:
return None
tmp_ans = None
for num in array:
if tmp_ans == None:
tmp_ans = num
else:
tmp_ans = tmp_ans ^ num
# 这时候tmp_ans就是两个只出现一次的数的异或
count = 0
while tmp_ans % 2 == 0:
count += 1
tmp_ans = tmp_ans >> 1
mask = 1 << count
# 找到第一个二进制不相同的位
first_num = None
second_num = None
for num in array:
if num & mask == 0:
if first_num == None:
first_num = num
else:
first_num = first_num ^ num
else:
if second_num == None:
second_num = num
else:
second_num = second_num ^ num
return first_num, second_num

数组中唯一只出现一次的数字

在一个数组中除一个数字只出现一次之外，其他数字都出现了三次，请找出那个只出现一次的数字。

把数组中所有数字的二进制表示的每一位都加起来。如果某一位的和能被3整除，那么这个只出现一次的数字二进制表示中对应的那一位是0，否则是1。

class Solution:
def FindNumsAppearOnlyOnce(self, array):
# write code here
if not array:
return None
bin_list = [0] * 32
# 构建一个32位的list，用于存放数组中每个数的二进制位
for num in array:
bin_num = bin(num)[2:]
# '1010'
for i in range(-1, -1 * len(bin_num) - 1, -1):
bin_list[i] += int(bin_num[i])
# bin_list存所有数的二进制对应位加和
for i in range(len(bin_list)):
if bin_list[i] % 3 == 0:
bin_list[i] = 0
else:
bin_list[i] = 1
bin_list=[str(v) for v in bin_list]
s = ''.join(bin_list)
return int(s, 2)

面试题64：求1+2+……+n

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

• 递归实现(有if不能使用)

class Solution:
def Sum_Solution(self, n):
# write code here
if n<=0:
return 0
else:
return n+self.Sum_Solution(n-1)

• python自带函数（第二种方法就是考察不同语言的函数、模板或者指针等的使用）

class Solution:
def Sum_Solution(self, n):
return sum(range(1, n+1))

面试题65：不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

• 位运算

步骤：
【1】不考虑进位。0+0,1+1结果都是0；0+1,1+0结果都是1，也就是异或操作
【2】考虑进位。0+0,0+1,1+0不会产生进位，1+1会向前产生一个进位。因此可以将两个数先做位与运算，再左移一位（0&0,0&1,1&0结果都是0，左移结果不变；1&1结果是1，左移一位10表示向前进一位）
【3】上述两个步骤相加，但是不允许相加操作，所以重复上述过程，直到没有进位。

class Solution:
def Add(self, num1, num2):
# write code here
# 异或、与（与计算考虑进位）之和
xorNum = num1 ^ num2 # 不考虑进位
andNum = (num1 & num2)<<1 # 考虑进位
while andNum!=0: # 若果没有进位的话直接输出结果
tmp1 = xorNum ^ andNum
tmp2 = (xorNum & andNum)<<1
tmp1 = tmp1 & 0xFFFFFFFF # 为了避免负数过大，取前32位
xorNum = tmp1
andNum = tmp2
return xorNum if xorNum<=0x7FFFFFFF else ~(xorNum^0xFFFFFFFF)
# 通过与0x7FFFFFF比较大小判断xorNum为正数还是负数，正数则直接返回。负数则返回~(xorNum^0xFFFFFFFF)

python 中最后运算结果是按补码进行存储，正数补码是本身，负数补码是该数绝对值的所有位取反再加1。举例来说，如果最后结果是-15，然而不做处理的话xorNum=4294967281（111…110001，15原码或补码为0…01111），该数为-15的补码但是被python认为是一个Long型的长整数。将上述结果与0xFFFFFFFF取异或，可以得到上述数的绝对值15，再取反，得到最后结果。这种操作看似做了个无用操作，但是告诉python解释器这个结果不是长整型，而是被作为负数解释输出。​

最后

以上就是无辜手套为你收集整理的剑指offer的python实现（持续更新......）面试题3：数组中重复的数字面试题4：二维数组中查找面试题5：替换空格面试题6：从尾到头打印链表面试题7：重建二叉树面试题8：二叉树的下一个节点面试题9：用两个栈实现队列面试题10：斐波那契数列面试题11：旋转数组的最小数字面试题14：剪绳子面试题15：二进制中1的个数面试题16：数值的整数次方面试题21：调整数组顺序使奇数位于偶数前面面试题22：链表中倒数第k个节点面试题27：二叉树的镜像面试题28：对称的二叉树面试题30：包含min函数的的全部内容，希望文章能够帮你解决剑指offer的python实现（持续更新......）面试题3：数组中重复的数字面试题4：二维数组中查找面试题5：替换空格面试题6：从尾到头打印链表面试题7：重建二叉树面试题8：二叉树的下一个节点面试题9：用两个栈实现队列面试题10：斐波那契数列面试题11：旋转数组的最小数字面试题14：剪绳子面试题15：二进制中1的个数面试题16：数值的整数次方面试题21：调整数组顺序使奇数位于偶数前面面试题22：链表中倒数第k个节点面试题27：二叉树的镜像面试题28：对称的二叉树面试题30：包含min函数的所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。