一、算法与数据结构
1、二叉树
1. 重建二叉树
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，输入前序遍历序列{1,2,4, 7,3,5, 6, 8}和中序遍历序列{4, 7,2,1,5,3,8, 6}，则重建如下图所示的二叉树并输出它的头节点。
前序遍历：访问顺序为根节点、左子节点、右子节点。
中序遍历：访问顺序为左子节点、根节点、右子节点。
后序遍历：访问顺序为左子节点、右子节点、根节点。
根据前序遍历的特点，第一个数必定是根节点，根据中序遍历的特点，只要找到序列当中的根节点，在根节点的左边序列是左子树，在根节点的右边序列是右子树。
- 创建一个二叉树类。
- 编写递归函数，先写出满足最小分割的序列，也就是说如果前序遍历序列和中序遍历序列只有两个数值的时候，那么就可以得到叶子节点，并返回这个只有两层的子二叉树。
- 如果分割的序列不只是两个数值，那么就需要继续分割子序列，递归调用，直到分割为只有两个数值为止。
- 这也有特殊情况，也就是根节点在最后边、最左边或者是根节点的右边只有一个数值、根节点的左边只有一个数值，那么就可以构造叶子节点了。
- 最后依次返回得到这颗二叉树。
## 创建二叉树类
class Node():
def __init__(self, item):
self.element = item
self.leftNode = None
self.rightNode = None
## 构建二叉树
def struct_tree(pre_list, middle_list):
if len(pre_list) == 2:
# 根节点
node = Node(pre_list[0])
#左叶子节点
if pre_list[0] == middle_list[1]:
left_node = Node(pre_list[1])
node.leftNode = left_node
else:
# 右叶子节点
right_node = Node(pre_list[1])
node.rightNode = right_node
## 添加父节点
if node.leftNode != None:
node.leftNode.parentNode = node
if node.rightNode != None:
node.rightNode.parentNode = node
return node
else:
## 递归调用
for i in range(len(middle_list)):
if middle_list[i] == pre_list[0]:
middle_root_index = i
# 根节点
node = Node(pre_list[0])
# 左子树
if middle_root_index > 1:
left_pre_list = pre_list[1 : middle_root_index + 1]
left_middle_list = middle_list[0 : middle_root_index]
node.leftNode = struct_tree(left_pre_list, left_middle_list)
elif middle_root_index == 1:
left_node = Node(middle_list[0])
node.leftNode = left_node
# 右子树
if middle_root_index < len(pre_list) - 2:
right_pre_list = pre_list[middle_root_index + 1 : ]
right_middle_list = middle_list[middle_root_index + 1 : ]
node.rightNode = struct_tree(right_pre_list, right_middle_list)
elif middle_root_index == len(pre_list) - 2:
right_node = Node(middle_list[len(pre_list) - 1])
node.rightNode = right_node
## 添加父节点
if node.leftNode != None:
node.leftNode.parentNode = node
if node.rightNode != None:
node.rightNode.parentNode = node
return node
pre_list = [1, 2, 4, 7, 3, 5, 6, 8]
middle_list = [4, 7, 2, 1, 5, 3, 8, 6]
node = struct_tree(pre_list, middle_list)
print('根节点：', node.element)
根节点： 12. 二叉树中序遍历的下一个节点
给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点?
树中的节点除了有两个分别指向左、右子节点的指针，还有一个指向父节点的指针。这颗二叉树如下图所示：
- 如果一个节点有右子树，那么它的下一个节点就是它的右子树中的最左子节点。
- 如果节点没有右子树的情形，并且该节点是它父节点的左子节点，那么它的下一个节点就是它的父节点。
- 如果一个节点既没有右子树，并且它还是它父节点的右子节点，那么这种情形就比较复杂。我们可以沿着指向父节点的指针一直向上遍历，直到找到一个是它父节点的左子节点的节点。如果这样的节点存在，那么这 个节点的父节点就是我们要找的下一个节点。
例如 i 节点，我们沿着指向父节点的指针向上遍历，先到达节点 e。由于节点 e 是它父节点 b 的右节点，我们继续向上遍历到达节点 b。节点 b 是它父节点 a 的左子节点，因此节点 b 的父节点 a 就是节点i的下一个节点。
## 创建二叉树类
class Node():
def __init__(self, item):
self.element = item
self.parentNode = None
self.leftNode = None
self.rightNode = None
## 构建二叉树
def struct_tree(pre_list, middle_list):
if len(pre_list) == 2:
# 根节点
node = Node(pre_list[0])
#左叶子节点
if pre_list[0] == middle_list[1]:
left_node = Node(pre_list[1])
node.leftNode = left_node
else:
# 右叶子节点
right_node = Node(pre_list[1])
node.rightNode = right_node
## 添加父节点
if node.leftNode != None:
node.leftNode.parentNode = node
if node.rightNode != None:
node.rightNode.parentNode = node
return node
else:
## 递归调用
for i in range(len(middle_list)):
if middle_list[i] == pre_list[0]:
middle_root_index = i
# 根节点
node = Node(pre_list[0])
# 左子树
if middle_root_index > 1:
left_pre_list = pre_list[1 : middle_root_index + 1]
left_middle_list = middle_list[0 : middle_root_index]
node.leftNode = struct_tree(left_pre_list, left_middle_list)
elif middle_root_index == 1:
left_node = Node(middle_list[0])
node.leftNode = left_node
# 右子树
if middle_root_index < len(pre_list) - 2:
right_pre_list = pre_list[middle_root_index + 1 : ]
right_middle_list = middle_list[middle_root_index + 1 : ]
node.rightNode = struct_tree(right_pre_list, right_middle_list)
elif middle_root_index == len(pre_list) - 2:
right_node = Node(middle_list[len(pre_list) - 1])
node.rightNode = right_node
## 添加父节点
if node.leftNode != None:
node.leftNode.parentNode = node
if node.rightNode != None:
node.rightNode.parentNode = node
return node
pre_list = ['a', 'b', 'd', 'e', 'h', 'i', 'c', 'f', 'g']
middle_list = ['d', 'b', 'h', 'e', 'i', 'a', 'f', 'c', 'g']
node = struct_tree(pre_list, middle_list)
## start 查找下一个节点
def next_node(current_node):
input_element = current_node.element
## 第一种情况
if current_node.rightNode != None:
current_node = current_node.rightNode
while current_node.leftNode != None:
current_node = current_node.leftNode
else:
print(input_element, '在中序遍历序列中的下一个节点是：', current_node.element)
## 第二种情况
elif current_node.rightNode == None and current_node is current_node.parentNode.leftNode:
print(input_element, '在中序遍历序列中的下一个节点是：', current_node.parentNode.element)
## 第三种情况
elif current_node.rightNode == None and current_node is current_node.parentNode.rightNode:
current_node = current_node.parentNode
while not (current_node is current_node.parentNode.leftNode):
current_node = current_node.parentNode
else:
print(input_element, '在中序遍历序列中的下一个节点是：', current_node.parentNode.element)
current_node = node.leftNode
print('中序遍历序列', middle_list)
next_node(current_node)
中序遍历序列 ['d', 'b', 'h', 'e', 'i', 'a', 'f', 'c', 'g']
b 在中序遍历序列中的下一个节点是： h测试用例：
print('中序遍历序列', middle_list)
## 节点是没有右子树，但它是父节点的左子节点
current_node = node.leftNode.leftNode
next_node(current_node)
## 节点是没有右子树，但它是父节点的右子节点
current_node = node.leftNode.rightNode.rightNode
next_node(current_node)
中序遍历序列 ['d', 'b', 'h', 'e', 'i', 'a', 'f', 'c', 'g']
d 在中序遍历序列中的下一个节点是： b
i 在中序遍历序列中的下一个节点是： a3. 二叉树的按层打印
class Tree():
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def printlayer(root):
last = root
queue = []
queue.append(root)
while queue:
root = queue.pop(0)
print(root.val, end='')
if root.left:
nlast = root.left
queue.append(root.left)
if root.right:
nlast = root.right
queue.append(root.right)
if root == last and queue:
last = nlast4. 二叉树的前中后序的递归，非递归及Morris遍历
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
# def create_tree(root):
# element = input("Enter a key: ")
# if element == '#':
# root = None
# else:
# root = TreeNode(element)
# print(root)
# root.left = create_tree(root.left)
# print(1)
# root.right = create_tree(root.right)
# print(2)
# return root
#
# print(create_tree([None]))
class Tree():
def __init__(self):
self.root = None
def add(self, item):
node = TreeNode(item)
if self.root == None:
self.root = node
return
queue = [self.root]
while queue:
cur = queue.pop(0)
if cur.left == None:
cur.left = node
return
else:
queue.append(cur.left)
if cur.right == None:
cur.right = node
return
else:
queue.append(cur.right)
# 广度遍历
def breadth_travel(self):
if self.root == None:
return
queue = [self.root]
while queue:
cur = queue.pop(0)
print(cur.val, end='')
if cur.left != None:
queue.append(cur.left)
if cur.right != None:
queue.append(cur.right)
# 深度遍历
# 先序
def preorder(self, node):
if node == None:
return
print(node.val, end='')
self.preorder(node.left)
self.preorder(node.right)
# 中序
def middleorder(self, node):
if node == None:
return
self.middleorder(node.left)
print(node.val, end='')
self.middleorder(node.right)
def postorder(self, node):
if node == None:
return
self.postorder(node.right)
self.postorder(node.left)
print(node.val, end='')
if __name__ == "__main__":
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)
tree.add(7)
tree.add(8)
tree.add(9)
tree.breadth_travel()
tree.preorder(tree.root)
tree.middleorder(tree.root)
tree.postorder(tree.root)5. 二叉树的序列化和反序列化
# 先序
class Tree():
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def preorder(root):
if not root:
return '#!'
res = root.val + ['!']
res += preorder(root.left)
res += preorder(root.right)
return res
tree = Tree([1])
print(preorder(tree))
# 反序列化(先序)
def recoByPreString(prestr):
def reconpreorder(values):
key = values.pop(0)
if key == "#":
return None
root = Tree(key)
root.left = reconpreorder(values)
root.right = reconpreorder(values)
return root
values = prestr.split('!')
return reconpreorder(values)6. 判断t1树中是否有与t2树拓扑结构完全相同的子树
class Tree():
def __init__(self, val=None):
self.val = val
self.left = None
self.right = None
def Top(t1, t2):
def issubTosub(t1, t2):
if not t1 and not t2:
return True
if t1.val != t2.val:
return False
return issubTosub(t1.left, t2.left) and issubTosub(t1.right, t2.right)
if not t1 or not t2:
return False
return Top(t1, t2) or Top(t1.left, t2) or Top(t1.right, t2)7. 二叉树倒序
# x = input().split()
# y = input().split()
# z = input().split()
#
# res = []
# for i in x:
# for j in y:
# for k in z:
# n = i.replace(j, k)
# res.append(n)
#
# print(" ".join(res))
# res = []
# x = input()
# for i in range(len(x)-1):
# # print(i)
# if int(x[i]) % 3 == 0 or int(x[i]) == 0:
# res.append(x[i])
# elif int(x[i] + x[i + 1]) % 3 == 0:
# res.append(x[i] + x[i + 1])
# print(len(res))
# x = input()
# y = input()
# y = set(y)
# y = list(y)
# m = (int(y[0]) * int((x[0] + x[1]))) / int(x[0])
# print("%.2f" % m)
x = input()
res1 = []
m = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(len(x)):
if x[i] == 0:
res1.append(i)
for i in res1:
for j in range(len(m)):
if j == i:
m.remove(m[j])
print(m)8. 重建二叉树
要求：用前序和中序遍历结果构建二叉树，遍历结果中不包含重复值。
思路：前序的第一个元素是根结点的值，在中序中找到该值，中序中该值的左边的元素是根结点的左子树，右边是右子树，然后递归的处理左边和右边。
提示：二叉树结点，以及对二叉树的各种操作。
def construct_tree(preorder=None, inorder=None):
"""
构建二叉树
"""
if not preorder or not inorder:
return None
index = inorder.index(preorder[0])
left = inorder[0:index]
right = inorder[index+1:]
root = TreeNode(preorder[0])
root.left = construct_tree(preorder[1:1+len(left)], left)
root.right = construct_tree(preorder[-len(right):], right)
return root2、链表问题
1. 打印两个有序链表的公共部分
class Node():
def __init__(self, val=None):
self.val = val
self.next = None
def compare(head1, head2):
if head1 == None or head2 == None:
return []
res = []
while head1 != None and head2 != None:
if head1.val > head2.val:
head2 = head2.next
elif head1.val < head2.val:
head1 = head1.next
else:
print(head1)
res.append(head1)
head1 = head1.next
head2 = head2.next
return res
node = Node([1, 3, 4, 7])
node1 = Node([2, 3, 5, 7, 9])
print(compare(node, node1))2. 复制含有随机指针节点的链表
class RandNode:
def __init__(self, data):
self.val = data
self.next = None
self.rand = None
def copyListWithRand(head):
if head == None:
return None
map = {}
cur = head
while cur != None:
map[cur] = RandNode(cur.val)
cur = cur.next
cur = head
while cur != None:
map[cur].next = None if cur.next == None else map[cur.next]
map[cur].next = None if cur.ramd == None else map[cur.rand]
cur = cur.next
return map[head]3. 将单链表的每Ｋ个节点之间逆序
# 每隔 k 个就逆序，用栈结构
def reverseNode(head, k):
def reverse(stack, pre, next):
while stack:
cur = stack.pop()
if pre != None:
cur = cur.next
pre = cur
# pre.next = next
return pre
if head == None or head.next == None or k < 2:
return head
stack = []
cur = head
newHaed = head
pre = None
while cur != None:
next = cur.next
stack.append(cur)
if len(stack) == k:
pre = reverse(stack, pre, next)
newHead = cur if newHaed == head else newHaed
cur = next
return newHaed4. 将单向链表按某值划分成左边小，中间相等，右边大的形式
# 将所有的节点放置到一个数组中，对这个数组进行partition调整（快排调整过程），再将每个数组中每个节点串起来即可。
# 快排-递归
def list(head, pivot):
def partition(nodeArr, pivot):
left = - 1
right = len(nodeArr)
index = 0
while index < right:
if nodeArr[index].val < pivot:
left += 1
nodeArr[left], nodeArr[index] = nodeArr[index], nodeArr[left]
index += 1
elif nodeArr[index].val == pivot:
index += 1
else:
right -= 1
nodeArr[index], nodeArr[right] = nodeArr[right], nodeArr[index]
if head == None or head.next == None:
return head
cur = head
n = 0
while cur != None:
n += 1
cur = cur.next
nodeArr = []
cur = head
while cur != None:
nodeArr.append(cur)
cur = cur.next
partition(nodeArr, pivot)
for i in range(n - 1):
nodeArr[i].next = nodeArr[i + 1]
nodeArr[-1].next = None
return nodeArr[0]5. 节点删除方式
# 链表里删元素，但是不知道元素的头结点和链表本身结构
def dele(node):
if node == None:
return None
next = node.next
if next == None:
return []
node.val = next.val
node.next = next.next6. 判断两个无环链表是否相交，相交则返回第一个相交节点
class Node():
def __init__(self, val=None):
self.val = val
self.next = None
def Loop(head1, head2):
n1 = 0
n2 = 0
cur1 = head1
cur2 = head2
while cur1 != None:
n1 += 1
cur1 = cur1.next
print(n1)
while cur2 != None:
n2 += 1
cur2 = cur2.next
print(n2)
n = abs(n1 - n2)
print(n)
cur1 = head1
cur2 = head2
if n1 > n2:
while n > 0:
cur1 = cur1.next
else:
while n > 0:
cur2 = cur2.next
while cur1 != cur2:
cur1 = cur1.next
cur2 = cur2.next
return cur1
# node1 = Node([1, 2, 3])
# node2 = Node([2, 3])
# print(Loop(node1, node2))7. 判断两个有环链表是否相交，相交则返回第一个相交节点
# 在环外面就相交，或者在环上相交（可能在同一个交点上，可能不在同一个交点上）
def bothLoop(head1, node1, head2, node2):
if head1 == None or head2 == None:
return None
if node1 == node2:
cur1 = head1
cur2 = head2
n = 0
while cur1 != node1:
n += 1
cur1 = cur1.next
while cur2 != node2:
n -= 1
cur2 = cur2.next
if cur1 != cur2:
return None
cur1 = head1 if n >= 0 else head2
cur2 = head1 if cur1 == head2 else head2
n = abs(n)
while n != 0:
n -= 1
cur1 = cur1.next
while cur1 != cur2:
cur1 = cur1.next
cur2 = cur2.next
return cur1
else:
cur1 = node1.next
while cur1 != node1:
if cur1 == node2:
return node1
cur = cur1.next
return None
def noLoop(head1, head2):
if head1 == None or head2 == None:
return None
cur1 = head1
cur2 = head2
n = 0
while cur1.next != None:
n += 1
cur1 = cur1.next
while cur2.next != None:
n -= 1
cur2 = cur2.next
if cur1 != cur2:
return None
cur1 = head1 if n >= 0 else head2
cur2 = head1 if cur1 == head2 else head2
n = abs(n)
while n != 0:
cur1 = cur1.next
n -= 1
while cur1 != cur2:
cur1 = cur1.next
cur2 = cur2.next
return cur1
def getLoopNode(head):
if head == None or head.next == None or head.next.next == None:
return None
slow = head.next
fast = head.next.next
while slow != fast:
if fast.next == None or fast.next.next == None:
return None
slow = slow.next
fast = fast.next.next
fast = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
class Node:
def __init__(self, val=None):
self.val = val
self.next = None
def getIntersectNode(head1, head2):
if head1 == None or head2 == None:
return None
# 判断环的入口在哪里
node1 = getLoopNode(head1)
node2 = getLoopNode(head2)
if node1 == None and node2 == None:
return noLoop(head1, head2)
# 在环之前就相等，node1 = node2，在环中相等，
if node1 != None and node2 != None:
return bothLoop(head1, node1, head2, node2)
return None8. 判断一个链表是否为回文结构
def huiwen(arr):
if arr == None or len(arr) < 2:
return arr
stack = []
cur = arr
while cur != None:
stack.append(cur.val)
cur = cur.next
while stack:
if stack.pop().val != arr.val:
return False
arr = arr.next
return True9. 判断一个链表是否有环，如果有的话返回第一个进环的节点
class Node():
def __init__(self, val=None):
self.val = val
self.next = None
def getloopmeet(head):
fast = head.next
slow = head.next.next
while fast != slow:
if fast != None or slow != None:
return None
fast = fast.next.next
slow = slow.next
fast = head
while fast != slow:
fast = fast.next
slow = slow.fast
return fast10. 向有环的环形链表中插入新节点
# 指针给的是节点值
class Node():
def __init__(self, value=None):
self.value = value
self.next = None
def insertnum(head, num):
node = Node(num)
if head == None:
node.next = node
return node
node = head
pre = node
cur = node.next
while cur != head:
if pre.value > num and cur.value <= num:
break
pre = pre.next
cur = cur.next
# num 小于节点值，pre只跑到最后一个节点，node跑道头结点
pre.next = node
node.next = cur
# 是按顺序来的，返回的是 head 或者 node ，是有顺序决定的
return head if head.value < num else node
node = Node()
node.insertnum([[1, 2, 3], 5])11. 在单链表中删除指定值的节点
def remove(head, num):
if head == None:
return None
stack = []
while head != None:
if head.val != num:
stack.append(head)
head = head.next
while stack:
# 这是一个链接操作
stack[-1].next = head
head = stack.pop()
return head12. 从尾到头打印单链表
输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表节点定义如下：
- 创建链表类。
- 链表的头部是最新的节点，所以要从尾部开始输出链表，必需要借助于栈，因为栈基于后进先出的原则，符合从尾到头打印链表，所以要创建一个栈类，存放栈数据。
- 链表从头部开始压数据入栈，再使用栈类进行出栈操作。
链表的时间复杂度：O(n)，数组的查询时间复杂度为：O(1) 。
方法1：可以使用列表模拟。
def print_links(links):
stack = []
while links:
stack.append(links.val)
links = links.next
while stack:
print stack.pop()方法2：直接递归。
def print_link_recursion(links):
if links:
print_link_recursion(links.next)
print links.val方法三：栈的实现，后进先出。
class Stack():
def __init__(self):
self.stack = []
self.top = -1
def push(self, x): # 入栈之前检查是否满了
self.stack.append(x)
self.top += 1
def pop(self): # 出栈之前检查是否为空
if self.isempty():
return None
else:
self.top = self.top - 1
return self.stack[self.top + 1]
def isempty(self):
return self.top == -1
def showstack(self):
print(self.stack)方法四：链表实现。
## 链表
class Node():
def __init__(self, data, next = None):
self.data = data
self.next = next
## 创建链表
head = None
for i in range(10):
head = Node(i, head)
## 链表入栈
probe = head
stack = Stack()
while probe != None:
stack.push(probe.data)
probe = probe.next
## 链表出栈
while True:
stack_data = stack.pop()
if stack_data == None:
break
else:
print(stack_data, end=',')测试用例：
## 输入的链表是None
head = Node(None, None)
## 链表入栈
probe = head
stack = Stack()
while probe != None:
stack.push(probe.data)
probe = probe.next
## 链表出栈
while True:
stack_data = stack.pop()
if stack_data == None:
break
else:
print(stack_data, end=',')13. 圆圈中最后剩下的数字
0,1,,n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，因此最后剩下的数字是 3。
这就是一个约瑟夫环问题。
解题思路：
解题的一种方法是可以用环形链表来模拟圆圈，然后循环就可以解决了。但会发现环形链表重复遍历了很多遍，总的时间复杂度是 O(mn)。
还有一种方法是查看数字之间的规律，如下所述：
- 首先我们定义一个关于 n 和m的方程 F(n,m)，表示每次在 n 个数字 0 到 n-1 中删除第 m 个数字最后剩下的数字。在这 n 个数字中，第一个被删除的数字是 (m-1)%n。为了简单起见，我们把 (m-1)%n 记为 k。
- 删除 k 之后剩下的 n-1 个数字，并且下一次删除从数字 k+1 开始计数循环删除第 m 个数字，直到只剩下一个数字为止。我们可以定义这样的式子，F(n,m)=F(n-1,m)
- 找规律: 接下来我们把删除过后的数字与从 0 开始计数的 n-2 的序列进行一一映射。
- 会发现一个映射规律公式，P(x)=(x-k-1)%n。它表示如果映射前的数字是x，那么映射后的数字是 (x-k-1)%n。同样的，逆映射就是 Q(x)=(x+k+1)%n。
- 接下来就是带入 F(n-1,m)。
F(n-1,m) = Q[F(n-1,m)] = [F(n-1,m)+k+1]%n。
把 k=(m-1)%n 代入：
F(n,m)=F(n-1,m) = [F(n-1,m)+m]%n
- 最终我们就可以得到如下式子：
- 根据这个公式我们就可以进行编程实现了，递归和循环都可以。
class Solution:
def lastRemaining(self, n: int, m: int) -> int:
if n == 1:
return 0
last = 0
for i in range(2, n + 1):
last = (last + m) % i
return last
n = 5
m = 3
s = Solution()
print(s.lastRemaining(n, m))
结果如下:
33、栈和队列
1. 队列的最大值
请定义一个队列并实现函数 max 得到队列里的最大值，要求函数 max、push_back 和 pop_front 的时间复杂度都是 O(1)。也就是对以下函数进行填充并满足要求。
class MaxQueue:
def __init__(self):
def max_value(self) -> int:
def push_back(self, value: int) -> None:
def pop_front(self) -> int:例如输入，第一个列表表示调用函数的顺序，第二列表示调用函数时所带的参数：
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]输出为：
[null,null,null,2,1,2]解题思路：
- 定义两个队列，A 队列存放的是输入的队列，B 队列存放的是可能的最大值队列。
- 例如输入 [2,3,1,2,6,2,5,1] 队列，首先先输入个 2，那么 A 队列里就有 2，B 队列里也是2。
- 然后是输入 3，A 队列就有 [2,3]，B 队列里的 2 比 3 小，所以就要把 B 队列清空并赋值 3。
- 接下来输入 1，A = [2,3,1]，B队列就要考虑了，因为 1 比 3 小，说明当 A 队列里的 3 出队列之后，后面的 1 有可能是最大值，所以我们要把 1 加入到 B 队列里，接下来依次进行，会发现 B 队列永远都是按照从大到小排序好的。
- 所以，当我们需要 pop_front A队列的时候，就需要比较 A 队列里的第一个元素和 B 队列里的第一个元素，如果相等，删除 B 队列里的头部元素。
class MaxQueue:
def __init__(self):
self.queue = [] # 输入队列
self.max_queue = [] # 可能最大值队列
def max_value(self) -> int:
if len(self.queue) == 0:
return -1
return self.max_queue[0]
def push_back(self, value: int) -> None:
self.queue.append(value)
## 判断是否要删除 最大值 队列
if len(self.max_queue) == 0:
self.max_queue.append(value)
else:
while len(self.max_queue) != 0 and self.max_queue[-1] < value:
self.max_queue.pop()
self.max_queue.append(value)
return None
def pop_front(self) -> int:
if len(self.queue) == 0:
return -1
queue_front = self.queue[0]
## 判断头部元素是否相等
if queue_front == self.max_queue[0]:
del self.max_queue[0]
del self.queue[0]
return queue_front
# 以下是调用函数
input_behavior = ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
input_num = [[],[1],[2],[],[],[]]
result = []
for i, behavior in enumerate(input_behavior):
if behavior == 'MaxQueue':
maxQueue = MaxQueue()
result.append(None)
if behavior == 'push_back':
result.append(maxQueue.push_back(input_num[i][0]))
if behavior == 'max_value':
result.append(maxQueue.max_value())
if behavior == 'pop_front':
result.append(maxQueue.pop_front())
print(result)
结果如下:
[None, None, None, 2, 1, 2]2. 构造数组的MaxTree
# 每一棵树的父节点是他左边第一个比他大的数和他右边第一个比他大的数中较小的那个值
# 如果这个数是整个树中的最大值，那么他就作为整个数的头结点出现
class Node():
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def getMaxtree(self, arr):
narr = [Node(arr[i]) for i in range(len(arr))]
lBigMap = {}
rBigMap = {}
stack = []
# 对输入的元素进行判断，输入元素大于栈顶元素，那么栈顶元素弹出直到小于输入元素
for i in range(len(narr)):
curNode = narr[i]
while stack and stack[-1].value < curNode.value:
cur = stack.pop()
lBigMap[cur] = stack[-1] if stack else None
rBigMap[cur] = curNode
stack.append(curNode)
# 上面的循环条件是两个，但是实际上最后还是会剩下来栈里面的几个元素
while stack:
cur = stack.pop()
lBigMap[cur] = stack[-1] if stack else None
rBigMap[cur] = None
head = None
for i in range(len(narr)):
curNode = narr[i]
left = lBigMap[curNode]
right = rBigMap[curNode]
if left == None and right == None:
head = curNode
elif left == None:
if right.left == None:
right.left = curNode
else:
right.right = curNode
elif right == None:
if left.left == None:
left.left = curNode
else:
left.right = curNode
else:
parent = left if left.value < right.value else right
if parent.left == None:
parent.left = curNode
else:
parent.right = curNode
return head
node = Node(None)
print(node.getMaxtree([3, 1, 2]))3. 两个栈组成一个队列
要求：用两个栈实现队列，分别实现入队和出队操作 思路：一个栈负责入队，另一个负责出队，出栈为空则从入栈中导入到出栈中。
方法一：
class TwostackQueue():
def __init__(self):
self.stackpush = []
self.stackpop = []
def add(self,Newnum):
self.stackpush.append(Newnum)
def push(self):
while self.stackpush:
self.stackpop.append(self.stackpush.pop())
return self.stackpop.pop()
queue = TwostackQueue()
queue.add([1,2,3])
print(queue.push())方法二：
class MyQueue(object):
def __init__(self):
self.stack = []
self.stack2 = []
def push(self, val):
self.stack.append(val)
def pop(self):
if self.stack2:
return self.stack2.pop()
while self.stack:
self.stack2.append(self.stack.pop())
return self.stack2.pop() if self.stack2 else u'队列为空'方法三：
队列的声明如下，请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能。
- 创建一个栈类。
- 创建一个队列类，该队列类包含两个栈stack1和stack2，当需要添加元素到队列时，其实就是往stack1中入栈。
- 如果是要消费队列时，需要先判断stack2是否为空，如果为空，那么就把stack1中的数据逐个出栈并对stack2入栈，这样就使得先进来的数据在stack2的栈顶，实现了队列的先进先出原则；如果不为空，那么stack2直接出栈。
## 栈的实现 后进先出
class Stack():
def __init__(self):
self.stack = []
self.top = -1
def push(self, x): # 入栈之前检查是否满了
self.stack.append(x)
self.top += 1
def pop(self): # 出栈之前检查是否为空
if self.isempty():
return None
else:
self.top = self.top - 1
pop_value = self.stack[self.top + 1]
del self.stack[self.top + 1]
return pop_value
def isempty(self):
return self.top == -1
def showstack(self):
print(self.stack)
def get_deep(self):
return self.top + 1
## 两个栈实现一个队列
class Queue():
def __init__(self):
self.stack_one = Stack()
self.stack_two = Stack()
self.deep = 0
## 向队列添加数据
def append(self, x):
self.stack_one.push(x)
self.deep += 1
## 取出队列的数据
def get_head(self):
if self.isempty():
return None
elif self.stack_two.isempty():
while not self.stack_one.isempty():
self.stack_two.push(self.stack_one.pop())
self.deep = self.deep - 1
return self.stack_two.pop()
def isempty(self):
return self.deep == 0
queue = Queue()
queue.append('a')
queue.append('b')
queue.append('c')
print(queue.get_head())
print(queue.get_head())
queue.append('d')
print(queue.get_head())
print(queue.get_head())
a
b
c
d测试用例：
## 往空队列里添加元素和删除元素
queue = Queue()
queue.append('a')
print(queue.get_head())
print(queue.get_head())
a
None4. 如何仅用递归函数和栈操作逆序一个栈
def recur(stack):
def getandremove(stack):
result = stack.pop()
if len(stack) == 0:
return result
else:
i = getandremove(stack)
stack.append(result)
return i
if len(stack) == 0:
return
i = getandremove(stack)
recur(stack)
stack.append(i)
return stack
print(recur([1,2,3,4]))5. 设计一个有getMin功能的栈
class Newstack():
def __init__(self):
self.stackData = []
self.stackMin = []
def push(self, newNum):
self.stackData.append(newNum)
if self.stackMin == [] or newNum <= self.getMin():
self.stackMin.append(newNum)
def getMin(self):
if len(self.stackMin) == 0:
return []
return self.stackMin[-1]
def pop(self):
value = self.stackData.pop()
if self.getMin() == value:
self.stackMin.pop()
return value
s = Newstack()
print(s.push(1))
print(s.pop())
print(s.push(2))
print(s.push(3))
print(s.getMin())
print(s.push(1))6. 生成窗口最大值数组
# 双端队列
# 队列存的是数组的下标
def getwindows(arr, w):
deque = []
res = []
for i in range(len(arr)):
while deque and arr[deque[-1]] <= arr[i]:
deque.pop()
deque.append(i)
if deque[0] <= i - w:
deque.pop(0)
if i - w + 1 >= 0:
res.append(arr[deque[0]])
return res
print(getwindows([4, 3, 5, 4, 3, 3, 6, 7], 3))7. 用一个栈实现另一个栈的排序
# class so():
# def __init__(self):
# self.stack = []
# self.help = []
#
# def add(self, Newnum):
# self.stack.append(Newnum)
#
# def sor(self):
# while self.stack:
# num = self.stack.pop()
# if self.help == [] or num > self.help[-1]:
# self.help.append(num)
# else:
# while num < self.help[-1]:
# self.stack.append(self.help.pop())
# self.help.append(num)
#
# return self.help
def sor(stack):
help = []
while stack:
cur = stack.pop()
while len(help) != 0 and help[-1] < cur:
stack.append(help.pop())
help.append(cur)
while help:
stack.append(help.pop())
return stack
print(sor([3,2,5,4,1]))4、字符串与数组
1. 如何将一个字符串转换为一个个标准字符
For I in str：
Print（i）counter函数是对字符串进行操作的，如果是数字输入没用的。
2. 实现单一字符串拼接成整体字符串
Result = ‘’.join(s1) + ‘’.join(s2)3. 把字符串中的空格替换成'20%'
方法1：直接使用Python字符串的内置函数。
>>> ' a b '.replace(' ', '20%')方法2: 使用正则表达式。
>>> import re
>>> ret = re.compile(' ')
>>> ret.sub('20%', ' a b ')4. 斐波那契数列
写一个函数，输入n,求斐波那契( Fibonacci)数列的第n项。斐波那契数列公式如下：
递归虽然有简洁的优点，但它同时也有显著的缺点。递归由于是函数调用自身，而函数调用是有时间和空间的消耗的:每一次函数调用，都需要在内存栈中分配空间以保存参数、返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间。这就不难理解上述的例子中递归实现的效率不如循环。也有可能会栈溢出。
我们不难发现，在这棵树中有很多节点是重复的，而且重复的节点数会随着 n 的增大而急剧增加，这意味着计算量会随着 n 的增大而急剧增大。事实上，用递归方法计算的时间复杂度是以 n 的指数的方式递增的。读者不妨求斐波那契数列的第100项试试，感受一下这样递归会慢到什么程度。
def Fibonacci(n):
if n < 0:
return None
else:
f_value = [0, 1]
if n in [0, 1]:
return f_value[n]
else:
for i in range(2, n + 1):
f_value[i % 2] = f_value[0] + f_value[1]
return f_value[n % 2]
Fibonacci(10)
55方法二：用生成器。
def fib(num):
a, b = 0, 1
for i in xrange(num):
yield b
a, b = b, a + b5. 青蛙跳台阶问题
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。
首先我们考虑最简单的情况。如果只有 1 级台阶，那显然只有一种跳法。如果有 2 级台阶，那就有两种跳法: 一种是分两次跳，每次跳 1 级;另一种就是一次跳 2 级。
接着我们再来讨论一般情况。我们把 n 级台阶时的跳法看成 n 的函数,记为 f(n)。当 n>2 时，第一次跳的时候就有两种不同的选择:一是第一次只跳 1 级，此时跳法数目等于后面剩下的 n-1 级台阶的跳法数目，即为 f(n- 1);二是第一次跳 2 级，此时跳法数目等于后面剩下的 n -2 级台阶的跳法数目，即为 f(n-2)。因此，n 级台阶的不同跳法的总数 f(n)=f(n- 1)+f(n -2) 。分析到这里，我们不难看出这实际上就是斐波那契数列了。
6. 二进制中1的个数
要求：求一个整数的二进制表示中，1的个数。
思路：二进制表示中，最后的那个1被减去后，低位都变为0，高位不变，按位与就可以去掉这个1。
def num_of_1(n):
ret = 0
while n:
ret += 1
n = n & n-1
return ret7. 字符串替换空格
请实现一个函数，把字符串中的每个空格替换成“%20”。例如，输入“We are happy.”，则输出“We%20are%20happy.”。
- 首先遍历输入字符串有多少个空格。
- 根据空格数可以计算新字符串的长度，并且创建该长度的数组
- 再次遍历字符串，如果碰到空格，就把空格前面的字符串赋给新数组，并添加上需要替换空格的字符。
- 把新创建的数组变换成字符串。
时间复杂度：O(n)。
## start
def replace_space_str(input_str, replace_str):
if input_str == '' or input_str == None or replace_str == None:
print('输入字符串不合法！')
return
##遍历输入字符串找出空格数
space_num = 0
for char in input_str:
if char == ' ':
space_num += 1
## 创建新字符串数组
new_len = len(input_str) + (len(replace_str) - 1) * space_num
new_str = new_len * [None]
index = 0
index_new_str = 0
for i in range(len(input_str)):
if input_str[i] == ' ':
ri_index_new_str = index_new_str + i - index
new_str[index_new_str : ri_index_new_str] = list(input_str[index : i])
new_str[ri_index_new_str : ri_index_new_str + len(replace_str)] = list(replace_str)
index_new_str = ri_index_new_str + len(replace_str)
index = i + 1
if i == len(input_str) - 1:
new_str[index_new_str : len(new_str)] = list(input_str[index : i + 1])
print(''.join(new_str))
input_str = 'We are happy.'
replace_str = '%20'
replace_space_str(input_str, replace_str)测试用例：
## 输入的字符串中包含空格（空格位于字符串的最前面；空格位于字符串的最后面；空格位于字符串的中间；字符串中有连续多个空格）。
input_str = ' We are happy. '
replace_str = '%20'
replace_space_str(input_str, replace_str)
## 输入的字符串中没有空格。
input_str = 'Wearehappy.'
replace_str = '%20'
replace_space_str(input_str, replace_str)
## 字符串是None
input_str = None
replace_str = '%20'
replace_space_str(input_str, replace_str)
## 字符串是空串
input_str = ''
replace_str = '%20'
replace_space_str(input_str, replace_str)
## 字符串只有一个空格字符
input_str = ' '
replace_str = '%20'
replace_space_str(input_str, replace_str)
%20We%20are%20%20happy.%20
Wearehappy.
输入字符串不合法！
输入字符串不合法！
%208. 把字符串转化成整数
要求：把字符串转化成整数。
测试用例：正负数和0，空字符，包含其他字符。
备注：使用raise抛出异常作为非法提示。
def str_to_int(string):
if not string: # 空字符返回异常
raise Exception('string cannot be None', string)
flag = 0 # 用来表示第一个字符是否为+、-
ret = 0 # 结果
for k, s in enumerate(string):
if s.isdigit(): # 数字直接运算
val = ord(s) - ord('0')
ret = ret * 10 + val
else:
if not flag:
if s == '+' and k == 0: # 避免中间出现+、-
flag = 1
elif s == '-' and k == 0:
flag = -1
else:
raise Exception('digit is need', string)
else:
raise Exception('digit is need', string)
if flag and len(string) == 1: # 判断是不是只有+、-
raise Exception('digit is need', string)
return ret if flag >= 0 else -ret9. python中的二位数组 = 二维列表
array = [[1,2,3],[4,5,6]]2行3列：
List是没有add的方法的，在python中向list中添加元素的方法：
- append() 追加单个元素到List的尾部，只接受一个参数，参数可以是任何数据类型，被追加的元素在List中保持着原结构类型。
- extend() 将一个列表中每个元素分别添加到另一个列表中，只接受一个参数；extend()相当于是将list B 连接到list A上。首先是在尾部插，第二接受的是一个list，字符串也可以。
- insert() 将一个元素插入到列表中，但其参数有两个（如insert(1,”g”)），第一个参数是索引点，即插入的位置，第二个参数是插入的元素。
- + 加号，将两个list相加，会返回到一个新的list对象，注意与前三种的区别。前面三种方法（append, extend, insert）可对列表增加元素的操作，他们没有返回值，是直接修改了原数据对象。 注意：将两个list相加，需要创建新的list对象，从而需要消耗额外的内存，特别是当list较大时，尽量不要使用“+”来添加list，而应该尽可能使用List的append()方法。
index是从0开始计数的。
在python中尽量不要用迭代，是真的慢。
我在在线编程模拟器上发现，list是有len()的，但是你传进来的不知道是啥玩意，直接用len( )肯定不对，要先转成len( )，然后在做计算。
10. 二维数组中的查找
二维数组中，每行从左到右递增，每列从上到下递增，给出一个数，判断它是否在数组中。
思路：从左下角或者右上角开始比较。
def find_integer(matrix, num):
"""
:param matrix: [[]]
:param num: int
:return: bool
"""
if not matrix:
return False
rows, cols = len(matrix), len(matrix[0])
row, col = rows - 1, 0
while row >= 0 and col <= cols - 1:
if matrix[row][col] == num:
return True
elif matrix[row][col] > num:
row -= 1
else:
col += 1
return False11. 旋转数组的最小数字
要求：把递增数组的前面部分数字移到队尾，求数组中的最小值，例如 [3,4,5,6,1,2]。
思路：使用二分法，但要考虑[1, 0, 0, 1]这种数据，只能顺序查找。
def find_min(nums):
if not nums:
return False
length = len(nums)
left, right = 0, length - 1
while nums[left] >= nums[right]:
if right - left == 1:
return nums[right]
mid = (left + right) / 2
if nums[left] == nums[mid] == nums[right]:
return min(nums)
if nums[left] <= nums[mid]:
left = mid
if nums[right] >= nums[mid]:
right = mid
return nums[0]12. 找出数组中重复的数字
在一个长度为 n 的数组里的所有数字都在 0 ~ n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。
请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3, 1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
- 按照数组下标取数的时间复杂度为 O(1)
解题思路：
- 从头到尾依次扫描这个数组中的每个数字。
- 当扫描到下标为 i 的数字时，首先比较这个数字(用 m 表示)是不是等于 i，如果是，则接着扫描下一个数字;如果不是，则再拿它和第 m 个数字进行比较。
- 如果它和第 m 个数字相等，就找到了一个重复的数字(该数字在下标为 i 和 m 的位置都出现了);
- 如果它和第 m 个数字不相等，就把第 i 个数字和第 m 个数字交换，把 m 放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现一一个重复的数字。
from typing import List
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
self.result = []
self.flag = True
for i in range(len(nums)):
if self.flag:
self.compare(i, nums)
else:
return
if self.flag:
print('重复数字为：', self.result)
if len(self.result) != 0 : return(self.result[0])
## 定义比较函数
def compare(self, i, nums):
if nums[i] == i:
pass
else:
## 异常判断
try:
if nums[i] == nums[nums[i]]:
self.result.append(nums[i])
else:
temp = nums[i]
nums[i] = nums[nums[i]]
nums[temp] = temp
self.compare(i, nums)
except:
print('输入数组不合规！')
self.flag = False
input_array = [2, 3, 1, 0, 2, 5, 5]
s = Solution()
s.findRepeatNumber(input_array)输出为：
重复数字为： [2, 5]。
测试用例：
## 长度为n的数组里包含一个或者多个重复的数字
input_array = [4,3,2,4,5,5]
s.findRepeatNumber(input_array)
## 数组中不包含重复数字
input_array = [4,1,2,0,5,3,6]
s.findRepeatNumber(input_array)
## 无效输入测试用例--空数组
input_array = []
s.findRepeatNumber(input_array)
## 无效输入测试用例--长度为n的数组中包含0——n-1 之外的数字
input_array = [1,7,1,2,2]
s.findRepeatNumber(input_array)输出为：
重复数字为： [5, 4]
重复数字为： []
重复数字为： []
输入数组不合规！
13. 不修改数组找出重复的数字
在一个长度为 n+1 的数组里的所有数字都在 1~n 的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。
解题思路：
- 我们把从 1~n 的数字从中间的数字 m 分为两部分，前面一半为 1~m,后面一半为 m+1~n。
- 如果 1~m 的数字的数目超过 m ,那么这一半的区间里一定包含重复的数字;否则，另一半 m+1~n 的区间里一定包含重复的数字。
- 我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。
代码按照二分查找的思路，如果输入长度为 n 的数组，那么遍历数组将被调用 O(logn) 次，每次需要 O(n) 的时间，因此总的时间复杂度是 O(nlogn) ,空间复杂度为 0(1) 。和最前面提到的需要 0(n) 的辅助空间的算法相比，这种算法相当于以时间换空间。
from typing import List
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
if len(nums) == 0:
print('输入数组不合法！')
return
start_n = 1
end_n = len(nums) - 1
flag = True
## 循环
while flag:
middle = int((end_n - start_n) / 2)
if middle == 0:
flag = False
middle = start_n + middle
left_n = 0
right_n = 0
## 开始比较数字，分区域统计
for num in nums:
if num <= middle and num >= start_n:
left_n += 1
elif num > middle and num <= end_n:
right_n += 1
elif end_n + start_n == len(nums):
print('输入数组不合法！')
flag = False
## 两边区域个数比较
if left_n > middle - start_n + 1:
end_n = middle
if flag == False:
print('重复数字为：',start_n)
elif right_n > end_n - middle:
start_n = middle + 1
if flag == False:
print('重复数字为：',end_n)
input_array = [2, 3, 5, 3, 4, 6, 3, 7]
s = Solution()
s.findRepeatNumber(input_array)结果如下：
重复数字为： 3。
测试用例：
## 长度为n的数组里包含一个或者多个重复的数字
input_array = [2, 3, 5, 4, 1, 4, 3, 7]
s.findRepeatNumber(input_array)
## 数组中不包含重复数字
input_array = [2, 3, 5, 4, 1, 6, 8, 7]
s.findRepeatNumber(input_array)
## 输入空数组
input_array = []
s.findRepeatNumber(input_array)结果如下：
重复数字为： 3
输入数组不合法！
输入数组不合法！
14. 二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。存在输出True，不存在输出False。
- 首先选取数组中右上角的数字。如果该数字等于要查找的数字，则查找过程结束；
- 如果该数字大于要查找的数字，则剔除这个数字所在的列；
- 如果该数字小于要查找的数字，则剔除这个数字所在的行。
## start
def two_array_research(two_array, research_num):
if len(two_array) == 0:
print('输入数组不合规！')
return
row_n = 0
column_n = len(two_array[0]) - 1
flag = True
while flag:
if two_array[row_n][column_n] == research_num:
print('True')
flag = False
elif two_array[row_n][column_n] > research_num:
column_n = column_n - 1
elif two_array[row_n][column_n] < research_num:
row_n += 1
## 判断下标是否越界
if row_n >= len(two_array) or column_n < 0:
print('False')
flag = False
two_array = [[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]]
research_num = 15
two_array_research(two_array, research_num)
True测试用例：
## 二维数组中包含查找的数字（查找的数字是数组中的最大值和最小值；查找的数字介于数组中的最大值和最小值之间）。
two_array = [[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]]
research_num = 15
two_array_research(two_array, research_num)
research_num = 1
two_array_research(two_array, research_num)
research_num = 7
two_array_research(two_array, research_num)
## 二维数组中没有查找的数字（查找的数字大于数组中的最大值；查找的数字小于数组中的最小值；查找的数字在数组的最大值和最小值之间但数组中没有这个数字）。
two_array = [[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]]
research_num = 16
two_array_research(two_array, research_num)
research_num = 0
two_array_research(two_array, research_num)
research_num = 3
two_array_research(two_array, research_num)
## 输入空数组
two_array = []
research_num = 15
two_array_research(two_array, research_num)
True
True
True
False
False
False
输入数组不合规！15. 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
解题思路：
- 找到数组中间的数字。
- 如果该数字大于目标数字，那么查找上一半的数组重复步骤1.
- 如果该数字小于目标数字，那么查找下一半的数组重复步骤1.
- 如果该数字等于目标数字，那么就返回下标。
- 重复以上步骤后发现没有符合的，那么就返回-1。
时间复杂度O()，以下代码可提交至LeetCode：
class Solution:
def search(self, nums: list, target: int) -> int:
low = 0
hight = len(nums) - 1
while low <= hight:
mid = int((low + hight) / 2)
guess = nums[mid]
if guess == target:
return mid
elif guess > target:
hight = mid - 1
else:
low = mid + 1
return -1
if __name__ == '__main__':
nums = [i for i in range(10000)]
target = 4567
solution = Solution()
n = solution.search(nums, target)
print(f'查找到数字{target}的下标为：{n}')
输出为:
查找到数字4567的下标为：45675、堆与树
树就是不包含回路的连通无向图，任意两个节点间有且只有一条路径。
二叉树要么为空，要么有根节点、左子树和右子树组成。
堆是什么？ 是一种特殊的完全二叉树
所有父节点的值都比子节点的值要小，称之为最小堆。反之，最大堆。
这是个很重要的性质，如果现在要求一组数中的最小值，可以首先将这组数安排最小堆排列起来，组成一个完全二叉树，最小值在最上面，现在要插入一个数，先插入到最顶端，然后与左右子树比较，比子树小，就交换。
1. 树中两个结点的最低公共祖先
要求：求普通二叉树中两个结点的最低公共祖先。
方法一：先求出两个结点到根结点的路径，然后从路径中找出最后一个公共结点。
备注：文件fifty.py中包含该代码的具体测试数据。
class Solution(object):
def __init__(self, root, node1, node2):
self.root = root # 树的根结点
self.node1 = node1
self.node2 = node2 # 需要求的两个结点
@staticmethod
def get_path(root, node, ret):
"""获取结点的路径"""
if not root or not node:
return False
ret.append(root)
if root == node:
return True
left = Solution.get_path(root.left, node, ret)
right = Solution.get_path(root.right, node, ret)
if left or right:
return True
ret.pop()
def get_last_common_node(self):
"""获取公共结点"""
route1 = []
route2 = [] # 保存结点路径
ret1 = Solution.get_path(self.root, self.node1, route1)
ret2 = Solution.get_path(self.root, self.node2, route2)
ret = None
if ret1 and ret2: # 路径比较
length = len(route1) if len(route1) <= len(route2) else len(route2)
index = 0
while index < length:
if route1[index] == route2[index]:
ret = route1[index]
index += 1
return ret二、高质量代码
1、代码的完整性
1. 数值的整数次方
要求：求一个数的整数次方。
思路：需要考虑次方是正数、负数和0，基数是0。
浮点数相等不能直接用==。
def power(base, exponent):
if equal_zero(base) and exponent < 0:
raise ZeroDivisionError
ret = power_value(base, abs(exponent))
if exponent < 0:
return 1.0 / ret
else:
return ret
def equal_zero(num):
if abs(num - 0.0) < 0.0000001:
return True
def power_value(base, exponent):
if exponent == 0:
return 1
if exponent == 1:
return base
ret = power_value(base, exponent >> 1)
ret *= ret
if exponent & 1 == 1:
ret *= base
return ret2. 打印1到最大的n位数
要求：输入n，打印出从1到最大的n位数。
思路：Python中已经对大整数可以进行自动转换了，所以不需要考虑大整数溢出问题。
def print_max_n(n):
for i in xrange(10 ** n):
print i3. O(1)时间删除链表结点
要求：O(1)时间删除链表结点。
思路：如果有后续结点，后续结点的值前移，删除后续结点，如果没有，只能顺序查找了。
def delete_node(link, node):
if node == link: # 只有一个结点
del node
if node.next is None: # node是尾结点
while link:
if link.next == node:
link.next = None
link = link.next
else:
node.val = node.next.val
n_node = node.next
node.next = n_node.next
del n_node4. 调整数组顺序使奇数位于偶数前面
思路：使用两个指针，前后各一个，为了更好的扩展性，可以把判断奇偶部分抽取出来。
def reorder(nums, func):
left, right = 0, len(nums) - 1
while left < right:
while not func(nums[left]):
left += 1
while func(nums[right]):
right -= 1
if left < right:
nums[left], nums[right] = nums[right], nums[left]
def is_even(num):
return (num & 1) == 02、代码的鲁棒性
1. 链表中倒数第k个结点
要求：求单链表中的倒数第k个结点。
思路：使用快慢指针，快的先走k-1步，需要考虑空链表以及k为0。
def last_kth(link, k):
if not link or k <= 0:
return None
move = link
while move and k-1 >= 0:
move = move.next
k -= 1
while move:
move = move.next
link = link.next
if k == 0:
return link.val
return None2. 反转链表
要求：反转链表。
思路：需要考虑空链表，只有一个结点的链表。
def reverse_link(head):
if not head or not head.next:
return head
then = head.next
head.next = None
last = then.next
while then:
then.next = head
head = then
then = last
if then:
last = then.next
return head3. 合并两个排序的链表
要求：合并两个排序的链表。
思路：使用递归。
def merge_link(head1, head2):
if not head1:
return head2
if not head2:
return head1
if head1.val <= head2.val:
ret = head1
ret.next = merge_link(head1.next, head2)
else:
ret = head2
ret.next = merge_link(head1, head2.next)
return ret4. 树的子结构
要求：判断一棵二叉树是不是另一个的子结构。
思路：使用递归。
def sub_tree(tree1, tree2):
if tree1 and tree2:
if tree1.val == tree2.val:
return sub_tree(tree1.left, tree2.left) and sub_tree(tree1.right, tree2.right)
else:
return sub_tree(tree1.left, tree2) or sub_tree(tree1.right, tree2)
if not tree1 and tree2:
return False
return True三、时间和空间复杂度
1、时间效率
1. 数组中出现次数超过一半的数字
思路: 使用hash，key是数字，value是出现的次数。
注意: 列表的len方法的时间复杂度是O(1) 。
def get_more_half_num(nums):
hashes = dict()
length = len(nums)
for n in nums:
hashes[n] = hashes[n] + 1 if hashes.get(n) else 1
if hashes[n] > length / 2:
return n2. 最小的k个数
要求：求数组中出现次数超过一半的数字。
思路：使用heapq，该模块是一个最小堆，需要转化成最大堆，只要在入堆的时候把值取反就可以转化成最大堆(仅适用于数字)。
思路二: 数组比较小的时候可以直接使用heapq的nsmallest方法。
import heapq
def get_least_k_nums(nums, k):
# 数组比较小的时候可以直接使用
return heapq.nsmallest(k, nums)
class MaxHeap(object):
def __init__(self, k):
self.k = k
self.data = []
def push(self, elem):
elem = -elem # 入堆的时候取反，堆顶就是最大值的相反数了
if len(self.data) < self.k:
heapq.heappush(self.data, elem)
else:
least = self.data[0]
if elem > least:
heapq.heapreplace(self.data, elem)
def get_least_k_nums(self):
return sorted([-x for x in self.data])3. 连续子数组的最大和
思路：动态规划问题。
def max_sum(nums):
ret = float("-inf") # 负无穷
if not nums:
return ret
current = 0
for i in nums:
if current <= 0:
current = i
else:
current += i
ret = max(ret, current)
return ret4. 从1到n整数中1出现的次数
要求：求从1到n整数的十进制表示中，1出现的次数。
思路：获取每个位数区间上所有数中包含1的个数，然后分别对高位分析，然后递归的处理低位数。
def get_digits(n):
# 求整数n的位数
ret = 0
while n:
ret += 1
n /= 10
return ret
def get_1_digits(n):
"""
获取每个位数之间1的总数
:param n: 位数
"""
if n <= 0:
return 0
if n == 1:
return 1
current = 9 * get_1_digits(n-1) + 10 ** (n-1)
return get_1_digits(n-1) + current
def get_1_nums(n):
if n < 10:
return 1 if n >= 1 else 0
digit = get_digits(n) # 位数
low_nums = get_1_digits(digit-1) # 最高位之前的1的个数
high = int(str(n)[0]) # 最高位
low = n - high * 10 ** (digit-1) # 低位
if high == 1:
high_nums = low + 1 # 最高位上1的个数
all_nums = high_nums
else:
high_nums = 10 ** (digit - 1)
all_nums = high_nums + low_nums * (high - 1) # 最高位大于1的话，统计每个多位数后面包含的1
return low_nums + all_nums + get_1_nums(low)5. 把数组排成最小的数
要求：把数组中的值拼接，找出能产生的最小的数[321,32,3]，最小的数是321323。
思路：Python中不需要考虑大整数，需要自己定义一个数组排序规则，直接调用库函数就可以。
def cmp(a, b):
return int(str(a)+str(b)) - int(str(b)+str(a))
def print_mini(nums):
print int(''.join([str(num) for num in sorted(nums, cmp=cmp)]))2、时间效率与空间效率的平衡
1. 丑数 LeetCode
要求：只含有2、3、5因子的数是丑数，求第1500个丑数。
思路: 按顺序保存已知的丑数，下一个是已知丑数中某三个数乘以2，3，5中的最小值。
class Solution(object):
def nthUglyNumber(self, n):
"""
:type n: int
:rtype: int
"""
ugly = [1]
t2 = t3 = t5 = 0
while len(ugly) < n:
while ugly[t2] * 2 <= ugly[-1]:
t2 += 1
while ugly[t3] * 3 <= ugly[-1]:
t3 += 1
while ugly[t5] * 5 <= ugly[-1]:
t5 += 1
ugly.append(min(ugly[t2]*2, ugly[t3]*3, ugly[t5]*5))
return ugly[-1]2. 第一个只出现一次的字符
要求：求字符串中第一个只出现一次的字符。
思路: 使用两个hash，一个记录每个字符穿线的次数，另一个记录每个字符第一次出现的位置。
def first_not_repeating_char(string):
if not string:
return -1
count = {}
loc = {}
for k, s in enumerate(string):
count[s] = count[s] + 1 if count.get(s) else 1
loc[s] = loc[s] if loc.get(s) else k
ret = float('inf')
for k in loc.keys():
if count.get(k) == 1 and loc[k] < ret:
ret = loc[k]
return ret3. 数组中的逆序对
要求：在一个数组中，前面的数字比后面的大，就是一个逆序对，求总数。
思路: 归并排序,先把数组依次拆开，然后合并的时候统计逆序对数目，并排序。
import copy
def get_inverse_pairs(nums):
if not nums:
return 0
start, end = 0, len(nums) - 1
tmp = copy.deepcopy(nums)
return inverse_pairs(tmp, start, end)
def inverse_pairs(tmp, start, end):
if start == end: # 递归结束条件
return 0
mid = (end - start) / 2 # 分别对左右两边递归求值
left = inverse_pairs(tmp, start, start+mid)
right = inverse_pairs(tmp, start+mid+1, end)
count = 0 # 本次逆序对数目
l_right, r_right = start + mid, end
t = []
while l_right >= start and r_right >= start + mid + 1:
if tmp[l_right] > tmp[r_right]:
t.append(tmp[l_right])
count += (r_right - mid - start)
l_right -= 1
else:
t.append(tmp[r_right])
r_right -= 1
while l_right >= start:
t.append(tmp[l_right])
l_right -= 1
while r_right >= start+mid+1:
t.append(tmp[r_right])
r_right -= 1
tmp[start:end+1] = t[::-1]
return count + left + right4. 两个链表的第一个公共结点
思路: 先获取到两个链表的长度，然后长的链表先走多的几步，之后一起遍历。
文件thirty_seven.py中包含了设置链表公共结点的代码，可以用来测试。
def get_first_common_node(link1, link2):
if not link1 or not link2:
return None
length1 = length2 = 0
move1, move2 = link1, link2
while move1: # 获取链表长度
length1 += 1
move1 = move1.next
while move2:
length2 += 1
move2 = move2.next
while length1 > length2: # 长链表先走多的长度
length1 -= 1
link1 = link1.next
while length2 > length1:
length2 -= 1
link2 = link2.next
while link1: # 链表一起走
if link1 == link2:
return link1
link1, link2 = link1.next, link2.next
return None四、面试题解题思路
1、画图让抽象问题形象化
1. 二叉树的镜像
思路一：可以按层次遍历，每一层从右到左。
思路二：使用递归。
def mirror_bfs(root):
ret = []
queue = deque([root])
while queue:
node = queue.popleft()
if node:
ret.append(node.val)
queue.append(node.right)
queue.append(node.left)
return ret
def mirror_pre(root):
ret = []
def traversal(root):
if root:
ret.append(root.val)
traversal(root.right)
traversal(root.left)
traversal(root)
return ret2. 顺时针打印矩阵
每一圈的开始位置总是坐上角元素[0, 0], [1, 1]...
def print_matrix(matrix):
"""
:param matrix: [[]]
"""
rows = len(matrix)
cols = len(matrix[0]) if matrix else 0
start = 0
ret = []
while start * 2 < rows and start * 2 < cols:
print_circle(matrix, start, rows, cols, ret)
start += 1
print ret
def print_circle(matrix, start, rows, cols, ret):
row = rows - start - 1 # 最后一行
col = cols - start - 1
# left->right
for c in range(start, col+1):
ret.append(matrix[start][c])
# top->bottom
if start < row:
for r in range(start+1, row+1):
ret.append(matrix[r][col])
# right->left
if start < row and start < col:
for c in range(start, col)[::-1]:
ret.append(matrix[row][c])
# bottom->top
if start < row and start < col:
for r in range(start+1, row)[::-1]:
ret.append(matrix[r][start])2、举例让抽象问题具体化
1. 包含min函数的栈
要求：栈的push，pop，min操作的时间复杂度都是O(1)。
思路：使用一个辅助栈保存最小值。
class MyStack(object):
def __init__(self):
self.stack = []
self.min = []
def push(self, val):
self.stack.append(val)
if self.min and self.min[-1] < val:
self.min.append(self.min[-1])
else:
self.min.append(val)
def pop(self):
if self.stack:
self.min.pop()
return self.stack.pop()
return None
def min(self):
return self.min[-1] if self.min else None2. 栈的压入弹出序列
要求：判断给定的两个序列中，后者是不是前者的弹出序列，给定栈不包含相同值。
思路：使用一个辅助栈, 如果辅助栈栈顶元素不等于出栈元素，则从入栈中找改值，直到入栈为空
如果最后出栈序列为空，则是入栈的弹出序列值。
def pop_order(push_stack, pop_stack):
if not push_stack or not pop_stack:
return False
stack = []
while pop_stack:
pop_val = pop_stack[0]
if stack and stack[-1] == pop_val:
stack.pop()
pop_stack.pop(0)
else:
while push_stack:
if push_stack[0] != pop_val:
stack.append(push_stack.pop(0))
else:
push_stack.pop(0)
pop_stack.pop(0)
break
if not push_stack:
while stack:
if stack.pop() != pop_stack.pop(0):
return False
if not pop_stack:
return True
return False3. 从上往下打印二叉树
思路：广度优先搜索，按层次遍历。
def bfs(tree):
if not tree:
return None
stack = [tree]
ret = []
while stack:
node = stack.pop(0)
ret.append(node.val)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return ret4. 二叉搜索树的后序遍历序列
要求：判断给定的整数数组是不是二叉搜索树的后序遍历序列。
整数数组中不包含重复值。
整数序列的最后一个值是根结点，然后比根结点小的值是左子树，剩下的是右子树，递归左右子树。
def is_post_order(order):
length = len(order)
if length:
root = order[-1]
left = 0
while order[left] < root:
left += 1
right = left
while right < length - 1:
if order[right] < root:
return False
right += 1
left_ret = True if left == 0 else is_post_order(order[:left])
right_ret = True if left == right else is_post_order(order[left:right])
return left_ret and right_ret
return False5. 二叉树中和为某一值的路径
要求：输入一棵二叉树和一个值，求从根结点到叶结点的和等于该值的路径。
深度优先搜索变形：
def find_path(tree, num):
ret = []
if not tree:
return ret
path = [tree]
sums = [tree.val]
def dfs(tree):
if tree.left:
path.append(tree.left)
sums.append(sums[-1]+tree.left.val)
dfs(tree.left)
if tree.right:
path.append(tree.right)
sums.append(sums[-1] + tree.right.val)
dfs(tree.right)
if not tree.left and not tree.right:
if sums[-1] == num:
ret.append([p.val for p in path])
path.pop()
sums.pop()
dfs(tree)
return ret3、分解让复杂问题简单化
1. 复杂链表的复制
要求：链表中除了指向后一个结点的指针之外，还有一个指针指向任意结点
分为三步完成：
- 复制每个结点，并把新结点放在老结点后面，如1->2,复制为1->1->2->2；
- 为每个新结点设置other指针；
- 把复制后的结点链表拆开；
class Solution(object):
@staticmethod
def clone_nodes(head):
# 结点复制
move = head
while move:
tmp = Node(move.val)
tmp.next = move.next
move.next = tmp
move = tmp.next
return head
@staticmethod
def set_nodes(head):
# other指针设置
move = head
while move:
m_next = move.next
if move.other:
m_next.other = move.other.next
move = m_next.next
return head
@staticmethod
def reconstruct_nodes(head):
# 结点拆分
ret = head.next if head else Node
move = ret
while head:
head = move.next
if head:
move.next = head.next
move = move.next
return ret
@staticmethod
def clone_link(head):
# 结果
h = Solution.clone_nodes(head)
h = Solution.set_nodes(h)
ret = Solution.reconstruct_nodes(h)
return ret2. 二叉搜索树与双向链表
要求：将二叉搜索树转化成一个排序的双向链表，只调整树中结点的指向。
思路：中序遍历，根结点的left指向左子树的最后一个(最大)值，right指向右子树的(最小)值。
注意：题目构造了一个普通二叉树用来测试，构造时按照二叉搜索树的顺序输入结点，空结点用None表示。
class Solution(object):
@staticmethod
def convert(tree):
"""结点转换"""
if not tree:
return None
p_last = Solution.convert_nodes(tree, None)
while p_last and p_last.left: # 获取链表头结点
p_last = p_last.left
return p_last
@staticmethod
def convert_nodes(tree, last):
if not tree:
return None
if tree.left:
last = Solution.convert_nodes(tree.left, last)
if last:
last.right = tree
tree.left = last
last = tree
if tree.right:
last = Solution.convert_nodes(tree.right, last)
return last3. 字符串的排列
要求：求输入字符串的全排列。
思路：递归完成，也可以直接使用库函数。
def my_permutation(s):
str_set = []
ret = [] # 最后的结果
def permutation(string):
for i in string:
str_tem = string.replace(i, '')
str_set.append(i)
if len(str_tem) > 0:
permutation(str_tem)
else:
ret.append(''.join(str_set))
str_set.pop()
permutation(s)
return ret4、知识迁移
1. 数字在排序数组中出现的次数
思路：使用二分法分别找到数组中第一个和最后一个出现的值的坐标，然后相减。
def get_k_counts(nums, k):
first = get_first_k(nums, k)
last = get_last_k(nums, k)
if first < 0 and last < 0:
return 0
if first < 0 or last < 0:
return 1
return last - first + 1
def get_first_k(nums, k):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] < k:
if mid + 1 < len(nums) and nums[mid+1] == k:
return mid + 1
left = mid + 1
elif nums[mid] == k:
if mid - 1 < 0 or (mid - 1 >= 0 and nums[mid-1] < k):
return mid
right = mid - 1
else:
right = mid - 1
return -1
def get_last_k(nums, k):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) / 2
if nums[mid] < k:
left = mid + 1
elif nums[mid] == k:
if mid + 1 == len(nums) or (mid + 1 < len(nums) and nums[mid+1] > k):
return mid
left = mid + 1
else:
if mid - 1 >= 0 and nums[mid-1] == k:
return mid - 1
right = mid - 1
return -12. 二叉树的深度
思路：分别递归的求左右子树的深度。
def get_depth(tree):
if not tree:
return 0
if not tree.left and not tree.right:
return 1
return 1 + max(get_depth(tree.left), get_depth(tree.right))3. 数组中只出现一次的数字
要求：数组中除了两个只出现一次的数字外，其他数字都出现了两遍。
思路：按位异或，在得到的值中找到二进制最后一个1，然后把数组按照该位是0还是1分为两组。
def get_only_one_number(nums):
if not nums:
return None
tmp_ret = 0
for n in nums: # 获取两个值的异或结果
tmp_ret ^= n
last_one = get_bin(tmp_ret)
a_ret, b_ret = 0, 0
for n in nums:
if is_one(n, last_one):
a_ret ^= n
else:
b_ret ^= n
return [a_ret, b_ret]
def get_bin(num): # 得到第一个1
ret = 0
while num & 1 == 0 and ret < 32:
num = num >> 1
ret += 1
return ret
def is_one(num, t): # 验证t位是不是1
num = num >> t
return num & 0x014. 和为s的两个数字VS和为s的连续正数序列和为s的两个数字
要求：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使其和为s。
思路：设置头尾两个指针，和大于s，尾指针减小，否砸头指针增加。
def sum_to_s(nums, s):
head, end = 0, len(nums) - 1
while head < end:
if nums[head] + nums[end] == s:
return [nums[head], nums[end]]
elif nums[head] + nums[end] > s:
end -= 1
else:
head += 1
return None5. 和为s的连续整数序列
要求：输入一个正数s， 打印出所有和为s的正整数序列(至少两个数)。
思路：使用两个指针，和比s小，大指针后移，比s大，小指针后移。
def sum_to_s(s):
a, b = 1, 2
ret = []
while a < s / 2 + 1:
if sum(range(a, b+1)) == s:
ret.append(range(a, b+1))
a += 1
elif sum(range(a, b+1)) < s:
b += 1
else:
a += 1
return ret6. 翻转单词顺序与左旋转字符串翻转单词顺序
要求：翻转一个英文句子中的单词顺序，标点和普通字符一样处理。
思路: Python中字符串是不可变对象，不能用书中的方法，可以直接转化成列表然后转回去。
def reverse_words(sentence):
tmp = sentence.split()
return ' '.join(tmp[::-1]) # 使用join效率更好，+每次都会创建新的字符串7. 左旋转字符串
思路：把字符串的前面的若干位移到字符串的后面。
def rotate_string(s, n):
if not s:
return ''
n %= len(s)
return s[n:] + s[:n]5、抽象建模
1. n个骰子的点数
要求：求出n个骰子朝上一面之和s所有可能值出现的概率。
思路：n出现的可能是前面n-1到n-6出现可能的和，设置两个数组，分别保存每一轮。
def get_probability(n):
if n < 1:
return []
data1 = [0] + [1] * 6 + [0] * 6 * (n - 1)
data2 = [0] + [0] * 6 * n # 开头多一个0，方便按照习惯从1计数
flag = 0
for v in range(2, n+1): # 控制次数
if flag:
for k in range(v, 6*v+1):
data1[k] = sum([data2[k-j] for j in range(1, 7) if k > j])
flag = 0
else:
for k in range(v, 6*v+1):
data2[k] = sum([data1[k-j] for j in range(1, 7) if k > j])
flag = 1
ret = []
total = 6 ** n
data = data2[n:] if flag else data1[n:]
for v in data:
ret.append(v*1.0/total)
print data
return ret2. 扑克牌的顺子
要求：从扑克牌中随机抽取5张牌，判断是不是顺子，大小王可以当任意值。
思路：使用排序。
import random
def is_continus(nums, k):
data = [random.choice(nums) for _ in range(k)]
data.sort()
print data
zero = data.count(0)
small, big = zero, zero + 1
while big < k:
if data[small] == data[big]:
return False
tmp = data[big] - data[small]
if tmp > 1:
if tmp - 1 > zero:
return False
else:
zero -= tmp - 1
small += 1
big += 1
else:
small += 1
big += 1
return True3. 圆圈中最后剩下的数字
要求：0到n-1排成一圈，从0开始每次数m个数删除，求最后剩余的数。
思路：当 n > 1 时： f(n,m) = [f(n-1, m)+m]%n,当 n = 1 时： f(n,m)=0，关键是推导出关系表达式。
def last_num(n, m):
ret = 0
if n == 1:
return 0
for i in range(2, n+1):
ret = (m + ret) % i
return ret6、发散思维
1. 求1+2...+n
要求：不能使用乘除、for、while、if、else等。
方法一：使用range和sum。
方法二：使用reduce。
def get_sum1(n):
return sum(range(1, n+1))
def get_sum2(n):
return reduce(lambda x, y: x+y, range(1, n+1))2. 不用加减乘除做加法
要求：不用加减乘除做加法。
方法一：使用位运算，Python中大整数会自动处理，因此对carry需要加个判断。
方法二：使用sum。
def bit_add(n1, n2):
carry = 1
while carry:
s = n1 ^ n2
carry = 0xFFFFFFFF & ((n1 & n2) << 1)
carry = -(~(carry - 1) & 0xFFFFFFFF) if carry > 0x7FFFFFFF else carry
n1 = s
n2 = carry
return n1
def add(n1, n2):
return sum([n1, n2])