面试题3 数组中找出重复的数字
长度n+1的数组，范围[1,n]，其中至少有一个数字是重复的，要求找出任一重复的数字
def get_duplication(nums, length):
# 求原数组中，[left, right] 有几个元素
def count_range(left, right):
if left > right:
return 0
count = 0
for i in range(len(nums)):
if left <= nums[i] <= right:
count += 1
return count
l, r = 1, length
mid = -1
while l <= r:
# 如果不加此判断，会产生死循环
if (l+r)//2 == mid:
break
mid = (l + r) // 2
l_count = count_range(l, mid)
if l_count > mid - l + 1:
r = mid
# [l, r]双闭区间，l_count 不满足，则 mid 也有可能是重复的，所以 mid 不能排除
else:
l = mid + 1
# 如果 l_count 满足条件，mid 是可以排除的
return mid
if __name__ == '__main__':
print(get_duplication([1, 2, 3, 2], 3))
print(get_duplication([1], 1))
面试题7 重建二叉树
from queue import Queue
class TreeNode():
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
class Solution():
def ConstructCore(self, preorder, inorder):
if len(preorder) == 0 or len(inorder) == 0:
return None
root = TreeNode(preorder[0])
for i in range(len(inorder)):
if inorder[i] == preorder[0]:
root.left = self.ConstructCore(preorder[1:i + 1], inorder[0:i])
root.right = self.ConstructCore(
preorder[i + 1:], inorder[i + 1:])
break
return root
def convert2list(self, root):
res = []
queue = Queue()
queue.put(root)
while not queue.empty():
cur = queue.get()
if cur:
res.append(cur.value)
queue.put(cur.left)
queue.put(cur.right)
else:
res.append(None)
return res
if __name__ == '__main__':
s = Solution()
preorder = [1, 2, 4, 7, 3, 5, 6, 8]
inorder = [4, 7, 2, 1, 5, 3, 8, 6]
tree = s.ConstructCore(preorder, inorder)
print(s.convert2list(tree))
面试题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 pNode
if pNode.right: # 该节点有右子树
left_node = pNode.right
# 下一个节点是右子树最左的节点
while left_node.left:
left_node = left_node.left
return left_node
while pNode.next: # 该节点有父节点
parent = pNode.next
if parent.left == pNode: # 该节点是其父节点的左节点
return parent # 下一个节点是其父节点
pNode = parent # 否则继续寻找
面试题9 用两个栈实现队列
class Que():
def __init__(self, data = []):
self.stack1 = [] # 出队用
self.stack2 = [] # 进队用
for item in data:
self.appendTail(item)
def appendTail(self, value):
if isinstance(value, list):
for i in value:
self.stack2.append(i)
else:
self.stack2.append(value)
def deleteHead(self):
if not self.stack1:
if not self.stack2:
return
while self.stack2:
self.stack1.append(self.stack2.pop())
return self.stack1.pop()
def __repr__(self):
return str(self.stack1[::-1] + self.stack2)
if __name__ == '__main__':
queue = Que([1, 2])
print(queue.deleteHead())
queue.appendTail([3, 4])
print(queue)
面试题12 矩阵中的路径
class Solution:
def hasPath(self, matrix, rows, cols, path):
for i in range(rows):
for j in range(cols):
# 如果 matrix[i*rows+j] 等于 path[0]，
# 继续寻找 (i, j) 上下左右四个点是否等于 path[1]
if matrix[i * rows + j] == path[0]:
if self.find_path(list(matrix), rows, cols, path[1:], i, j):
return True
return False
def find_path(self, matrix, rows, cols, path, i, j):
if not path:
return True
# 遍历过的需要标记
matrix[i * rows + j] = 0
# 判断(i, j)上下左右四个点是否相等
# 如果相等，继续转化成子问题
if j + 1 < cols and matrix[i * rows + j + 1] == path[0]:
return self.find_path(matrix, rows, cols, path[1:], i, j + 1)
elif j - 1 >= 0 and matrix[i * cols + j - 1] == path[0]:
return self.find_path(matrix, rows, cols, path[1:], i, j - 1)
elif i + 1 < rows and matrix[(i + 1) * cols + j] == path[0]:
return self.find_path(matrix, rows, cols, path[1:], i + 1, j)
elif i - 1 >= 0 and matrix[(i - 1) * cols + j] == path[0]:
return self.find_path(matrix, rows, cols, path[1:], i - 1, j)
else:
return False
if __name__ == '__main__':
solution = Solution()
matrix = 'ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS'
rows = 5
cols = 8
path = 'SGGFIECVAASABCEHJIGQEMS'
ans = solution.hasPath(matrix, rows, cols, path)
print(ans)
面试题13 机器人的运动范围
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.vis = {}
def movingCount(self, threshold, rows, cols):
return self.moving(threshold, rows, cols, 0, 0)
def moving(self, threshold, rows, cols, row, col):
rowans, colans = 0,0
rowtemp, coltemp = row, col
while rowtemp > 0:
rowans = rowans + rowtemp%10
rowtemp = rowtemp//10
while coltemp > 0:
colans = colans + coltemp%10
coltemp = coltemp//10
if rowans + colans>threshold: # 如果数字之和大于k
return 0
if row >= rows or col >= cols or row < 0 or col < 0: # 如果(row, cos)越界
return 0
if (row, col) in self.vis: # 如果已访问
return 0
self.vis[(row, col)] = 1
return 1 + self.moving(threshold, rows, cols, row - 1, col) +\
self.moving(threshold, rows, cols, row + 1,col) + \
self.moving(threshold, rows,cols, row,col - 1) + \
self.moving(threshold, rows, cols, row, col + 1)
if __name__=='__main__':
solution=Solution()
threshold=10
rows,cols=1,100
ans=solution.movingCount(threshold,rows,cols)
print(ans)
面试题14 割绳子
长度为n的绳子，割成几段，我们可以把它转化成一个子问题，即割成两段，两段乘积最大。状态转移方程：
f(n) = max(f(i)*f(n-i))
f(i)表示长度为i的绳子，所能取得的最大乘积
def maxProductAtferCutting(length):
if length < 2:
return 0
if length == 2:
return 1
if length == 3:
return 2
# products 数组存储绳子长度为i时，所能得到的最大乘积
# 由于必须割一刀，所以 length < 4 时，需要特殊处理，提前 return
products = [0] * (length + 1)
for i in range(4):
products[i] = i
for i in range(4, length + 1):
res = 0
for j in range(1, i // 2 + 1):
product = products[j] * products[i - j]
res = max(product, res)
products[i] = res
return products[-1]
print(maxProductAtferCutting(8))
面试题16 数值的整数次方
def power(base, n):
if base == 0 or base == 1:
return 1
if n == 0:
return 1
if n == -1: # 考虑n小于0的情况
return 1 / base
result = power(base, n >> 1)
result *= result
if n & 1 == 1: # 判断是否是奇数
result *= base
return result
print(power(-2, -1))
面试题17 打印从1到最大的n位数
全排列
def print_1to_max(n):
def helper(n, tmp):
if n == 0:
print_num(tmp)
return # IMPORTANT
for i in range(10):
helper(n - 1, tmp + str(i))
def print_num(strs):
i = 0
while i < len(strs):
if strs[i] != '0':
break
i += 1
if i < len(strs):
print(strs[i:])
helper(n, "")
print_1to_max(3)
面试题40 最小的 k 个数
方法一：快排思想
def minimum_k(nums, k):
n = len(nums)
if n == 0 or k > n or k <= 0:
return
start, end = 0, n - 1
def partition(nums, start, end):
pivot = nums[start]
j = start
for i in range(start + 1, end + 1):
if nums[i] < pivot:
j += 1
nums[i], nums[j] = nums[j], nums[i]
nums[j], nums[start] = nums[start], nums[j]
return j
index = partition(nums, start, end)
while index != k - 1:
if index < k - 1:
end = index - 1
else:
start = index + 1
index = partition(nums, start, end)
return nums[:index + 1]
print(minimum_k([4, 5, 1, 6, 2, 7, 3, 8], 4))
方法二：使用堆，或红黑树 1）使用 heapq
import heapq
def minimum_k(nums, k):
n = len(nums)
if n == 0 or k > n or k <= 0:
return
return heapq.nsmallest(k, nums)
print(minimum_k([4, 5, 1, 6, 2, 7, 3, 8], 4))
2）自己写堆
def minimum_k(nums, k):
n = len(nums)
if n == 0 or k > n or k <= 0:
return
res = nums[:k]
# 构建最大堆
def heap_build(res):
n = len(res)
for i in range((n - 2) // 2, -1, -1):
heapify(res, i)
return res
def heapify(res, i):
n = len(res)
while True:
max_pos = i
if i * 2 + 1 < n and res[i * 2 + 1] > res[max_pos]:
max_pos = i * 2 + 1
if i * 2 + 2 < n and res[i * 2 + 2] > res[max_pos]:
max_pos = i * 2 + 2
if max_pos == i:
break
res[max_pos], res[i] = res[i], res[max_pos] # IMPORTANT
i = max_pos
heap_build(res)
for i in range(k, len(nums)):
# print(f"i = {i}, res = {res}")
if nums[i] > res[0]:
continue
res[0] = nums[i]
heapify(res, 0)
return res
print(minimum_k([4, 5, 1, 6, 2, 7, 3, 8], 4))
面试题46 把数字翻译成字符串
def how_many(num):
if num <= 0:
return 0
num = str(num)
n = len(num)
memo = {}
# 第 i，i+1 位数字拼接起来是否在[10, 25]范围内
def can_trans(i):
if i < n - 1 and 10 <= int(num[i:i + 2]) <= 25:
return 1
else:
return 0
# dp[i] 表示以 第i数字开头的不同翻译的数量
def dp(i):
if i not in memo:
# 处理边界
if i >= n-1:
memo[i] = 1
return memo[i]
# dp(i) = dp(i+1) + can_trans(i)*dp(i+2)
memo[i] = dp(i + 1) + can_trans(i) * dp(i + 2)
return memo[i]
dp(0)
return memo[0]
print(how_many(25))
print(how_many(1))
print(how_many(12258))
面试题48 最长不含重复字符的子字符串
19年浦发秋招机试上机题 方法一：双指针
# i, j 左右两个指针，cache 存储 i, j 两个指针之间（包括i, j）字母的个数
# j 右移，如果新加入的字母已存在，那么移动左指针，直到
# cache[strs[j]] = 0，再新加入 cache 中
# 保证 cache 中每个字母的个数都不大于1
def find_no_dup(strs):
cache = {}
i, j = 0, 0
n = len(strs)
if n == 0:
return 0
max_len = 1
while j < n:
if cache.get(strs[j], 0) > 0:
while cache.get(strs[j], 0) != 0:
cache[strs[i]] -= 1
i += 1
cache[strs[j]] = 1
max_len = max(j - i + 1, max_len)
j += 1
return max_len
print(find_no_dup('ababab'))
print(find_no_dup('aaaaaaaaaaa'))
print(find_no_dup('abcdefg'))
print(find_no_dup('pwawbcdec'))
print(find_no_dup(''))
方法二：动态规划（剑指offer P237)
def max_no_dup_len(strs):
n = len(strs)
if n <= 1:
return n
cache = {} # 存储上一个字母出现的位置
cache[strs[0]] = 0
# dp[i]表示以i个字符结尾的最长相异子字符串的长度
dp = [1] * n
for i in range(1, n):
# 若该字符串没有出现过，dp[i] = dp[i - 1] + 1
if strs[i] not in cache:
cache[strs[i]] = i
dp[i] = dp[i - 1] + 1
else:
# 若该字符串在之前出现过：
# 1、出现的位置较远，即 d > dp[i - 1]，不影响 dp[i]
# 如 i = 8， r出现的位置较远
# 2、出现在dp[i-1]所表示的相异字符串的内部，则dp[i] = d
# 如 i = 5，a出现的位置较近，dp[5] = 5 - 2 = 3
d = i - cache[strs[i]]
cache[strs[i]] = i
if d > dp[i - 1]:
dp[i] = dp[i - 1] + 1
else:
dp[i] = d
print(dp)
return max(dp)
print(max_no_dup_len('arabcacfr'))
面试题55 二叉树的深度，及判断是否是平衡二叉树
def depth(tree):
if not tree:
return 0
left = depth(tree.left)
right = depth(tree.right)
return 1 + max(left, right)
# 递归的解法，容易写，但是一个节点会被遍历多次
def isBalanced(tree):
if not tree:
return True
l_depth = depth(tree.left)
r_depth = depth(tree.right)
if abs(l_depth - r_depth) > 1:
return False
else:
return isBalanced(tree.left) and isBalanced(tree.right)
class Tree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
t = Tree(0)
t.left = Tree(1)
t.right = Tree(2)
print(depth(t))
print(isBalanced(t))
面试题56 数组中数字出现的次数
找出数组中只出现一次的两个数字
def find_appear_twice(nums):
def first_bit1(n): # 找出二进制最右为1的位数
index = 0
while n & 1 == 0:
n >> 1
index += 1
return index
def is_bit1(n, index): # 判断二进制从右到左第index位是否为1
n = n >> index
return n & 1
n = len(nums)
if n < 2:
return
# 找出这两个数字异或的结果，这个数的二进制至少一位为1
tmp = 0
for num in nums:
tmp = tmp ^ num
index = first_bit1(tmp)
nums1, nums2 = [], []
for num in nums:
if is_bit1(num, index):
nums1.append(num)
else:
nums2.append(num)
res1, res2 = 0, 0
for num in nums1:
res1 = res1 ^ num
for num in nums2:
res2 = res2 ^ num
return res1, res2
print(find_appear_twice([1, 1, 2, 3, 4, 4, 5, 5]))
面试题62 约瑟夫环
def LastRemaining(n, m):
if n < 1 or m < 1:
return -1
last = 0
for i in range(2, n+1):
last = (last + m) % i
return last
递推规律：
f(n, m) = [f(n-1, m) + m] % n
n = 1, f(1, m) = 0
f(2, m) = [f(1, m) + m] % 2
f(3, m) = [f(2, m) + m] % 3
...
f(n, m) = [f(n-1, m) + m] % n
