面试题3：数组中重复数字
# 使用set，时间复杂度O(n),空间复杂度O(n)
class Solution(object):
def findRepeatNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
a = set([])
for num in nums:
if num in a:
return num
a.add(num)
# 桶思想，时间复杂度O(n),空间复杂度O(1)
class Solution(object):
def findRepeatNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
for i in range(len(nums)):
val = nums[i]
if val != i and val == nums[val]:
return val
nums[i], nums[val] = nums[val], nums[i]
面试题4：二维数组中的查找
# 从右上往左下推
class Solution(object):
def findNumberIn2DArray(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if matrix == [] or matrix == [[]]:
return False
c = len(matrix[0])-1
l = 0
while True:
if matrix[l][c] == target:
return True
if matrix[l][c] > target:
c -= 1
else:
l += 1
if l > len(matrix)-1 or c < 0:
return False
面试题5：替换空格
class Solution(object):
def replaceSpace(self, s):
"""
:type s: str
:rtype: str
"""
l = [''] * len(s)
for i in range(len(s)):
if s[i] == ' ':
l[i] = '%20'
else:
l[i] = s[i]
return ''.join(l)
面试题6：从尾到头打印链表
# 非递归
class Solution(object):
def reversePrint(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
result = []
while head:
result.append(head.val)
head = head.next
return result[::-1]
# 递归
class Solution(object):
def reversePrint(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
result = []
def helper(root):
if not root:
return
helper(root.next)
result.append(root.val)
helper(head)
return result
面试题7：重建二叉树
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
def helper(inc_start, inc_end):
if inc_start == inc_end:
return None
inc_value = preorder[self.pre_index]
root = TreeNode(inc_value)
self.pre_index += 1
root.left = helper(inc_start, inc_value_map[inc_value])
root.right = helper(inc_value_map[inc_value] + 1, inc_end)
return root
self.pre_index = 0
inc_value_map = {v: k for k, v in enumerate(inorder)}
return helper(0, len(inorder))
面试题9：用两个栈实现队列
class CQueue(object):
def __init__(self):
self.l1 = []
self.l2 = []
def appendTail(self, value):
"""
:type value: int
:rtype: None
"""
self.l2.append(value)
def deleteHead(self):
"""
:rtype: int
"""
if not self.l1:
if not self.l2:
return -1
for i in range(len(self.l2)):
self.l1.append(self.l2.pop())
return self.l1.pop()面试题10-I：斐波那契数列
class Solution(object):
def fib(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 0
a = 0
b = 1
while n != 1:
a, b = b, a+b
n -= 1
return b % 1000000007
面试题10-II：青蛙跳台阶问题
class Solution(object):
def numWays(self, n):
"""
:type n: int
:rtype: int
"""
if n == 0:
return 1
a = 1
b = 1
while n != 1:
a, b = b, a+b
n -= 1
return b % 1000000007