devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

python刷题大杂烩_以下哪个表达式可将列表my_list中最大的两个数相加

作者：Monodyee | 2024-03-29 02:23:33

赞

踩

以下哪个表达式可将列表my_list中最大的两个数相加

1、python小试

题目：输出2~100之间的素数

  1. def find_prime_number(start, end):
  2.     prime_number_list = []
  3.     i = start
  4.  
  5.     while i < end:
  6.         j = 2
  7.         while j <= i // 2:
  8.             if i % j == 0:
  9.                 break
  10.             j += 1
  11.         if j > i // 2:
  12.             prime_number_list.append(i)
  13.         i += 1
  14.  
  15.     return prime_number_list
  16.  
  17. prime_number = find_prime_number(2, 100)
  18. print(prime_number)

思路：素数就是找不到1之外可以整除的数。假如可以找到，那么必定有一个值不大于原值的1/2。

2、栈和队列

2.1 设计一个有getMin功能的栈

题目：实现一个特殊的栈，在实现栈的基本功能的基础上，再返回栈中最小元素的操作

要求：pop、push、getMin操作的时间复杂度都是O(1)

  1. data_stack_list = []
  2. min_stack_list = []
  3.  
  4. def push(x):
  5.     data_stack_list.append(x)
  6.     if len(min_stack_list) == 0:
  7.         min_stack_list.append(x)
  8.     else:
  9.         before_min_data = min_stack_list[-1]
  10.         if x < before_min_data:
  11.             min_stack_list.append(x)
  12.         else:
  13.             min_stack_list.append(before_min_data)
  14.  
  15. def pop():
  16.     top_data = data_stack_list.pop()
  17.     min_stack_list.pop()
  18.     return top_data
  19.  
  20. def getMin():
  21.     if len(min_stack_list) == 0:
  22.         return -1
  23.     else:
  24.         return min_stack_list[-1]
  25.  
  26. push(4)
  27. push(5)
  28. push(2)
  29. push(3)
  30. push(1)
  31. print(getMin())
  32. pop()
  33. print(getMin())
  34. pop()
  35. print(getMin())
  36. pop()
  37. print(getMin())
  38. pop()
  39. print(getMin())
  40. pop()
  41. print(getMin())

思路：需要两个栈，一个栈正常存放、取出数据，另一个栈每个值都对应第一个栈中每个元素的最小值。

2.2 由两个栈组成队列

题目：编写一个类，用两个栈实现队列，支持队列的基本操作add、poll、peek

  1. stack_1 = []
  2. stack_2 = []
  3.  
  4. def add(x):
  5.     stack_1.append(x)
  6.  
  7. def pop():
  8.     while len(stack_1) > 0:
  9.         data = stack_1.pop()
  10.         stack_2.append(data)
  11.     first_data = stack_2.pop()
  12.     while len(stack_2) > 0:
  13.         data = stack_2.pop()
  14.         stack_1.append(data)
  15.     return first_data
  16.  
  17. def peek():
  18.     if len(stack_1) == 0:
  19.         return -1
  20.     else:
  21.         return stack_1[-1]
  22.  
  23. add(1)
  24. add(2)
  25. add(3)
  26. add(4)
  27. add(5)
  28. print(peek())
  29. pop()
  30. print(peek())
  31. pop()
  32. print(peek())

思路：两个栈，第一个栈负责装数据。当pop数据时，把第一个栈的数据一次放入第二个栈，然后pop第二个栈的栈顶元素，接着把第二个栈的数据再装回第一个栈。

2.3 仅用递归函数和栈操作实现栈的逆序

题目：只能用递归函数实现，不能使用其他数据结构

  1. stack = [1,2,3,4,5]
  2.  
  3. def get_and_remove_last_element(stack):
  4.     data = stack.pop()
  5.  
  6.     if len(stack) == 0:
  7.         return data
  8.     else:
  9.         last = get_and_remove_last_element(stack)
  10.         stack.append(data)
  11.  
  12.     return last
  13.  
  14. def reverse_stack(stack):
  15.     data = get_and_remove_last_element(stack)
  16.  
  17.     if len(stack) == 0:
  18.         stack.append(data)
  19.     else:
  20.         reverse_stack(stack)
  21.         stack.append(data)
  22.     return stack
  23.  
  24. stack = reverse_stack(stack)
  25. print(stack)

思路：需要两个递归函数。第一个递归函数每次返回栈底的数据，其他放回栈中。第二个递归函数实现栈的逆序。

2.4 生成窗口最大值数组

题目：有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。实现：返回一个数组，数组中每个元素为每次窗口内的最大值，时间复杂度为O(1)。

  1. from collections import deque
  2.  
  3. arr = [4,3,5,3,4,4,6,7]
  4. w = 3
  5.  
  6. def get_window_max_arr(arr, w):
  7.     queue = deque()
  8.     max_arr = []
  9.  
  10.     size = len(arr)
  11.     for i in range(0, size):
  12.         if len(queue) == 0:
  13.             queue.append(i)
  14.         else:
  15.             while len(queue) > 0 and arr[queue[-1]] < arr[i]:
  16.                 queue.pop()
  17.             queue.append(i)
  18.  
  19.         if queue[0] == i - w:
  20.             queue.popleft()
  21.  
  22.         if i >= w - 1:
  23.             max_arr.append(arr[queue[0]])
  24.  
  25.     return max_arr
  26.  
  27. max_arr = get_window_max_arr(arr, w)
  28. print(max_arr)

思路：需要一个双端队列，存放的是数组下标值（注意不是数组元素）。每次扫描一个新的数组元素时，和deque最后一个元素对比，pop队尾元素直到其值不小于该新元素。如果队首坐标值过期则pop队首元素。窗口最大值为队首对应的数组元素值。

2.5 单调栈结构

题目：给定一个不含有重复值的数组arr，找到一个i位置左边和右边离i位置最近且比arr[i]小的位置，返回所有位置相应的信息，时间复杂度为O(1)

  1. import numpy as np
  2.  
  3. arr = np.array([3,4,1,5,6,2,7])
  4.  
  5. def find_nearest_index(arr):
  6.     size = arr.size
  7.     stack = []
  8.     nearest_arr = [(-1, -1)] * size
  9.  
  10.     for i in range(size):
  11.         if len(stack) == 0:
  12.             stack.append(i)
  13.         else:
  14.             if arr[stack[-1]] < arr[i]:
  15.                 stack.append(i)
  16.             else:
  17.                 while len(stack) > 0 and arr[stack[-1]] > arr[i]:
  18.                     data = stack.pop()
  19.                     if len(stack) > 0:
  20.                         tup = (stack[-1], i)
  21.                     else:
  22.                         tup = (-1, i)
  23.                     nearest_arr[data] = tup
  24.                 stack.append(i)
  25.  
  26.     while len(stack) > 0:
  27.         data = stack.pop()
  28.         if len(stack) > 0:
  29.             tup = (stack[-1], -1)
  30.         else:
  31.             tup = (-1, -1)
  32.         nearest_arr[data] = tup
  33.  
  34.     return nearest_arr
  35.  
  36. nearest_arr = find_nearest_index(arr)
  37. print(nearest_arr)

思路：构造一个单调栈，从栈顶到栈底从大到小排序。当新进入一个元素打破这个排序，对于弹出栈的元素，栈底元素为其左边想要的值，当前压栈值为其右边想要的值。当全部元素完成入栈后，再逐一出栈再判断一遍。

2.6 求最大子矩阵的大小

题目：给定一个整型矩阵map，其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量。

  1. import numpy as np
  2.  
  3. map1 = np.array([[1,0,1,1], [1,1,1,1], [1,1,1,0]])
  4. map2 = np.array([[1,1,1,0]])
  5.  
  6. def find_biggest_map_number(map):
  7.     flag_map = np.zeros_like(map)
  8.  
  9.     for i in range(len(map)):
  10.         for j in range(len(map[0])):
  11.             if i == 0:
  12.                 flag_map[i][j] = 0 if map[i][j] == 0 else 1
  13.             else:
  14.                 flag_map[i][j] = flag_map[i - 1][j] + 1 if map[i][j] == 1 else 0
  15.  
  16.     biggest_num = 0
  17.     for i in range(len(map)):
  18.         for j in range(len(map[0])):
  19.             if map[i][j] == 0:
  20.                 break
  21.  
  22.             flag_num = flag_map[i][j]
  23.             good_num = 1
  24.  
  25.             for k in range(1, j + 1):
  26.                 num = flag_map[i][j - k]
  27.                 if num  >= flag_num:
  28.                     good_num += 1
  29.                 else:
  30.                     break
  31.             for k in range(1, len(map[0]) - j):
  32.                 num = flag_map[i][j + k]
  33.                 if num >= flag_num:
  34.                     good_num += 1
  35.                 else:
  36.                     break
  37.             cur_num = flag_num * good_num
  38.             if biggest_num < cur_num:
  39.                 biggest_num = cur_num
  40.  
  41.     return biggest_num
  42.  
  43. num = find_biggest_map_number(map1)
  44. print(num)

思路：首先是以行为单位遍历数组，并且以当前行 为矩阵底部的话，计算矩阵的高度是多少。这样计算出二维数组中每个元素对应矩阵的高度height值。 第二遍扫描数组，计算出当前元素左边不少于当前height值的个数，再计算当前元素右边不少于当前height值的个数，然后当前值height值乘以总个数即为矩阵的大小。

3 链表

3.1 打印两个有序链表的公共部分

题目：给定两个有序列表的头指针head1和head2，打印两个链表的公共部分

  1. class Node:
  2.     def __init__(self, val, next=None):
  3.         self.val = val
  4.         self.next = next
  5.  
  6. head1 = Node(0)
  7. head2 = Node(0)
  8.  
  9. head11 = Node(1)
  10. head12 = Node(3)
  11. head13 = Node(5)
  12. head14 = Node(7)
  13. head15 = Node(9)
  14. head21 = Node(2)
  15. head22 = Node(3)
  16. head23 = Node(5)
  17. head24 = Node(8)
  18. head25 = Node(10)
  19.  
  20. head1.next = head11
  21. head11.next = head12
  22. head12.next = head13
  23. head13.next = head14
  24. head14.next = head15
  25. head2.next = head21
  26. head21.next = head22
  27. head22.next = head23
  28. head23.next = head24
  29. head24.next = head25
  30.  
  31. def find_common(head1, head2):
  32.     p = head1
  33.     q = head2
  34.     common_data = []
  35.  
  36.     while p != None and q != None:
  37.         if p.val < q.val:
  38.             p = p.next
  39.         elif p.val > q.val:
  40.             q = q.next
  41.         else:
  42.             common_data.append(p.val)
  43.             p = p.next
  44.             q = q.next
  45.  
  46.     return common_data
  47.  
  48. common_data = find_common(head1, head2)
  49. print(common_data)

思路：因为是有序的链表，所以比较简单，不解读了。

3.2 在单链表中删除倒数第K个节点

题目： 实现函数，可以删除单链表中倒数第K个节点

  1. class Node:
  2.     def __init__(self, val, next=None):
  3.         self.val = val
  4.         self.next = next
  5.  
  6. head1 = Node(1)
  7. head2 = Node(2)
  8. head3 = Node(3)
  9. head4 = Node(4)
  10. head5 = Node(5)
  11. head6 = Node(6)
  12. head7 = Node(7)
  13. head8 = Node(8)
  14. head9 = Node(9)
  15. head10 = Node(10)
  16. head1.next = head2
  17. head2.next = head3
  18. head3.next = head4
  19. head4.next = head5
  20. head5.next = head6
  21. head6.next = head7
  22. head7.next = head8
  23. head8.next = head9
  24. head9.next = head10
  25.  
  26. def delete_K_Node(head1, K):
  27.     p = head1
  28.     while p != None:
  29.         K -= 1
  30.         p = p.next
  31.  
  32.     if K >= 0 :
  33.         return head1
  34.     else:
  35.         p = head1
  36.         while K < -1:
  37.             K += 1
  38.             p = p.next
  39.         p.next = p.next.next
  40.         return head1
  41.  
  42. head_new = delete_K_Node(head1, 3)
  43. while head_new != None:
  44.     print(head_new.val)
  45.     head_new = head_new.next

思路：链表从前往后数，每数一次减1。如果最后值大于等于0，则不需要删除K节点。否则第一次数完后得到N，第二次再从前往后数，每数一次加1，等到值为-1时，下一个即为要删除的节点。

3.3  两个单链表生成相加链表

题目：给定两个链表的头节点head1和head2，请生成代表两个整数相加值的结果链表

  1. class Node:
  2.     def __init__(self, val, next=None):
  3.         self.val = val
  4.         self.next = next
  5.  
  6. head11 = Node(9)
  7. head12 = Node(9)
  8. head13 = Node(0)
  9. head11.next = head12
  10. head12.next = head13
  11. head21 = Node(1)
  12. head22 = Node(3)
  13. head21.next = head22
  14.  
  15. def add_node(head1, head2):
  16.     head_stack_1 = []
  17.     head_stack_2 = []
  18.  
  19.     p = head1
  20.     q = head2
  21.  
  22.     while p != None:
  23.         head_stack_1.append(p.val)
  24.         p = p.next
  25.  
  26.     while q != None:
  27.         head_stack_2.append(q.val)
  28.         q = q.next
  29.  
  30.     big_flag = 0
  31.     r = None
  32.     while len(head_stack_1) > 0 and len(head_stack_2) > 0:
  33.         data_1 = head_stack_1.pop()
  34.         data_2 = head_stack_2.pop()
  35.         sum = data_1 + data_2 + big_flag
  36.         if sum >= 10:
  37.             big_flag = 1
  38.         else:
  39.             big_flag = 0
  40.         k = Node(sum % 10, r)
  41.         r = k
  42.  
  43.     p = head_stack_1 if len(head_stack_1) > 0 else head_stack_2
  44.     while len(p) > 0:
  45.         data = p.pop()
  46.         sum = data + big_flag
  47.         k = Node(sum % 10, r)
  48.         r = k
  49.  
  50.     if sum >= 10:
  51.         k = Node(1, r)
  52.         r = k
  53.  
  54.     return r
  55.  
  56. result = add_node(head11, head21)
  57. while result != None:
  58.     print(result.val)
  59.     result = result.next

思路：把链表分别放入stack中，然后再取值相加，生成的结果直接加到结果链表中。不可以采用字符串转为int的方法，假如字符串很长可能会溢出。

3.4 将单链表的每K个节点之间逆序

题目：给定一个单链表head，实现一个调整单链表的函数，使得每K个节点之间逆序，如果最后不够K个节点，则不调整最后几个节点。

  1. class Node:
  2.     def __init__(self, val, next=None):
  3.         self.val = val
  4.         self.next = next
  5.  
  6. head1 = Node(1)
  7. head2 = Node(2)
  8. head3 = Node(3)
  9. head4 = Node(4)
  10. head5 = Node(5)
  11. head6 = Node(6)
  12. head7 = Node(7)
  13. head8 = Node(8)
  14. head1.next = head2
  15. head2.next = head3
  16. head3.next = head4
  17. head4.next = head5
  18. head5.next = head6
  19. head6.next = head7
  20. head7.next = head8
  21.  
  22. def reverse_list_node(head, K):
  23.     stack = []
  24.     p = head
  25.     new_head = Node(None)
  26.     r = new_head
  27.  
  28.     while p != None:
  29.         i = 0
  30.         q = p
  31.         for _ in range(K):
  32.             stack.append(p)
  33.             if p != None:
  34.                 p = p.next
  35.                 i += 1
  36.  
  37.         while len(stack) > 0 and i == K:
  38.             r.next = Node(stack.pop().val)
  39.             r = r.next
  40.  
  41.         if i < K:
  42.            while q != None:
  43.                 r.next = Node(q.val)
  44.                 q = q.next
  45.                 r = r. next
  46.  
  47.     return new_head.next
  48.  
  49. result = reverse_list_node(head1, 3)
  50. while result != None:
  51.     print(result.val)
  52.     result = result.next

思路：逆序使用栈结构。每个K个节点装入stack并弹出并连接到结果链表中，如果某次装入stack的长度不够K则直接连接到结果链表中。

3.5 将搜索二叉树转换成双向链表

题目：有一颗搜索二叉树，将其转换为一个有序的双向链表

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. class ListNode:
  8.     def __init__(self, val, next=None, last=None):
  9.         self.val = val
  10.         self.next = next
  11.         self.last = last
  12.  
  13. node1 = Node(1)
  14. node3 = Node(3)
  15. node2 = Node(2, node1, node3)
  16. node5 = Node(5)
  17. node4 = Node(4, node2, node5)
  18. node8 = Node(8)
  19. node9 = Node(9, node8)
  20. node7 = Node(7, left=None, right=node9)
  21. node6 = Node(6, node4, node7)
  22.  
  23. middle_list = []
  24.  
  25. def search(root, middle_list):
  26.     if root.left is None and root.right is None:
  27.         middle_list.append(root.val)
  28.         return
  29.  
  30.     if root.left is not None:
  31.         search(root.left, middle_list)
  32.  
  33.     middle_list.append(root.val)
  34.  
  35.     if root.right is not None:
  36.         search(root.right, middle_list)
  37.  
  38. def create_double_link(root, middle_list):
  39.     search(root, middle_list)
  40.     new_head = ListNode(None)
  41.     p = new_head
  42.     while len(middle_list) > 0:
  43.         q = ListNode(middle_list.pop(0))
  44.         p.next = q
  45.         q.last = p
  46.         p = p.next
  47.  
  48.     return new_head.next
  49.  
  50. result = create_double_link(node6, middle_list)
  51. while result != None:
  52.     print(result.val)
  53.     result = result.next

思路：中序遍历搜索二叉树，遍历过程中将值放入队列，然后遍历队列构造双向链表。

4 二叉树

4.1 递归方式先序、中序、后续遍历二叉树

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node1 = Node(1)
  8. node3 = Node(3)
  9. node2 = Node(2, node1, node3)
  10. node5 = Node(5)
  11. node4 = Node(4, node2, node5)
  12. node8 = Node(8)
  13. node9 = Node(9, node8)
  14. node7 = Node(7, left=None, right=node9)
  15. node6 = Node(6, node4, node7)
  16.  
  17. # 先序遍历
  18. def preOrder(root):
  19.     if root.left is None and root.right is None:
  20.         print(root.val)
  21.         return
  22.     print(root.val)
  23.  
  24.     if root.left != None:
  25.         preOrder(root.left)
  26.     if root.right != None:
  27.         preOrder(root.right)
  28.  
  29. # 中序遍历
  30. def inOrder(root):
  31.     if root.left is None and root.right is None:
  32.         print(root.val)
  33.         return
  34.  
  35.     if root.left != None:
  36.         inOrder(root.left)
  37.     print(root.val)
  38.     if root.right != None:
  39.         inOrder(root.right)
  40.  
  41. # 后序遍历
  42. def posOrder(root):
  43.     if root.left is None and root.right is None:
  44.         print(root.val)
  45.         return
  46.  
  47.     if root.left != None:
  48.         posOrder(root.left)
  49.     if root.right != None:
  50.         posOrder(root.right)
  51.     print(root.val)
  52.  
  53. print("---------先序遍历-----------")
  54. preOrder(node6)
  55. print("---------中序遍历-----------")
  56. inOrder(node6)
  57. print("---------后序遍历-----------")
  58. posOrder(node6)

4.2 非递归方式先序、中序、后续遍历二叉树

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node1 = Node(1)
  8. node3 = Node(3)
  9. node2 = Node(2, node1, node3)
  10. node5 = Node(5)
  11. node4 = Node(4, node2, node5)
  12. node8 = Node(8)
  13. node9 = Node(9, node8)
  14. node7 = Node(7, left=None, right=node9)
  15. node6 = Node(6, node4, node7)
  16.  
  17. # 先序遍历
  18. def preOrder(root):
  19.     stack = []
  20.     stack.append(root)
  21.  
  22.     while len(stack) > 0:
  23.         node = stack.pop()
  24.         print(node.val)
  25.         if node.right != None:
  26.             stack.append(node.right)
  27.         if node.left != None:
  28.             stack.append(node.left)
  29.  
  30. # 中序遍历
  31. def inOrder(root):
  32.     stack = []
  33.     stack.append(root)
  34.     return_flag = 0
  35.  
  36.     while len(stack) > 0:
  37.         node = stack[-1]
  38.         if node.left != None and return_flag == 0:
  39.             stack.append(node.left)
  40.         else:
  41.             print(node.val)
  42.             stack.pop()
  43.             return_flag = 1
  44.             if node.right != None:
  45.                 stack.append(node.right)
  46.                 return_flag = 0
  47.  
  48. # 后序遍历
  49. def posOrder(root):
  50.     stack1 = []
  51.     stack2 = []
  52.  
  53.     stack1.append(root)
  54.  
  55.     while len(stack1) > 0:
  56.         node = stack1.pop()
  57.         stack2.append(node)
  58.         if node.left != None:
  59.             stack1.append(node.left)
  60.         if node.right != None:
  61.             stack1.append(node.right)
  62.  
  63.     while len(stack2) > 0:
  64.         print(stack2.pop().val)
  65.  
  66. print("---------先序遍历-----------")
  67. preOrder(node6)
  68. print("---------中序遍历-----------")
  69. inOrder(node6)
  70. print("---------后序遍历-----------")
  71. posOrder(node6)

思路：

（1）先序：构造一个栈，压入root，循环从栈中弹出node并打印，然后再将右子树、左子树压入栈

（2）中序：构造一个栈，压入root，循环放入节点的左子树直至没有，逐一弹出并放入右子树。有一个返回标志，防止再压入左子树。

（3）后序：构造两个栈，压入root，循环从栈1中弹出node并放入栈2，弹出后再将node的左子树、右子树放入栈1。最后栈2的元素就是后序的顺序。

4.3 打印二叉树的边界节点

题目：给定一颗二叉树的头节点head，实现二叉树边界节点的逆时针打印。

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node13 = Node(13)
  8. node14 = Node(14)
  9. node11 = Node(11, node13, node14)
  10. node8 = Node(8, left=None, right=node11)
  11. node7 = Node(7)
  12. node4 = Node(4, node7, node8)
  13. node2 = Node(2, left=None, right=node4)
  14. node15 = Node(15)
  15. node16 = Node(16)
  16. node12 = Node(12, node15, node16)
  17. node9 = Node(9, node12)
  18. node10 = Node(10)
  19. node5 = Node(5, node9, node10)
  20. node6 = Node(6)
  21. node3 = Node(3, node5, node6)
  22. node1 = Node(1, node2, node3)
  23.  
  24. # 求不包括head的高度
  25. def get_height(head, height):
  26.     if head is None:
  27.         return 0
  28.     left_height = get_height(head.left, height + 1) if head.left != None else height
  29.     right_height = get_height(head.right, height + 1) if head.right != None else height
  30.     return max(left_height, right_height)
  31.  
  32. height = get_height(node1, 1)
  33. edge_map = [[-1 for x in range(2)] for y in range(height)]
  34.  
  35. # 求边界数组信息
  36. def set_edge_map(head, height, edge_map):
  37.     if head == None:
  38.         return
  39.  
  40.     edge_map[height][0] = edge_map[height][0] if edge_map[height][0] != -1 else head.val
  41.     edge_map[height][1] = head.val
  42.     set_edge_map(head.left, height + 1, edge_map)
  43.     set_edge_map(head.right, height+1, edge_map)
  44.  
  45. set_edge_map(node1, 0, edge_map)
  46.  
  47. # 顺序打印左边边界
  48. for i in range(height):
  49.     print(edge_map[i][0])
  50.  
  51. # 找到不再边界数组中的叶子节点
  52. def find_leaf_not_in_edge_map(head, height, edge_map):
  53.     if head == None:
  54.         return
  55.  
  56.     if head.left == None and head.right == None and head.val != edge_map[height][0] and head.val != edge_map[height][1]:
  57.         print(head.val)
  58.  
  59.     find_leaf_not_in_edge_map(head.left, height+1, edge_map)
  60.     find_leaf_not_in_edge_map(head.right, height+1, edge_map)
  61.  
  62. find_leaf_not_in_edge_map(node1, 0, edge_map)
  63.  
  64. # 逆序打印右边边界
  65. for i in range(0, height - 1):
  66.     print(edge_map[height-1-i][1])

思路：先求树的高度，然后构造一个存放边界值的二维数组array(需要有一维长度信息即height值。在先序遍历树时，将第一次获得的左边的值放入array[height][0]不再更新，将每次获得的值放入array[height][1]不断更新。然后再寻找没有包含在array中的叶子节点。

4.4 二叉树的序列化和反序列化

题目：给定一颗二叉树头节点head，已知二叉树节点值得类型时32位整型。设计一种二叉树序列化和反序列化得方案

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node1 = Node(1)
  8. node3 = Node(3)
  9. node2 = Node(2, node1, node3)
  10. node5 = Node(5)
  11. node4 = Node(4, node2, node5)
  12. node8 = Node(8)
  13. node9 = Node(9, node8)
  14. node7 = Node(7, left=None, right=node9)
  15. node6 = Node(6, node4, node7)
  16.  
  17. queue = []
  18.  
  19. # 二叉树序列化
  20. def serialize_tree(head, queue):
  21.     if head == None:
  22.         queue.append('#')
  23.         return
  24.  
  25.     queue.append(str(head.val))
  26.  
  27.     serialize_tree(head.left, queue)
  28.     serialize_tree(head.right, queue)
  29.  
  30. serialize_tree(node6, queue)
  31.  
  32. data = queue.pop(0)
  33. root = Node(int(data))
  34. p = root
  35.  
  36. # 二叉树反序列化
  37. def deserialize_tree(head, p, queue):
  38.     if len(queue) == 0:
  39.         return
  40.  
  41.     data = queue.pop(0)
  42.     if data != '#':
  43.         head.left = Node(int(data))
  44.         deserialize_tree(head.left, p, queue)
  45.  
  46.     data = queue.pop(0)
  47.     if data != '#':
  48.         head.right = Node(int(data))
  49.         deserialize_tree(head.right, p, queue)
  50.  
  51. deserialize_tree(root, p, queue)
  52. # root即为所要的二叉树

思路：序列化时，先序遍历二叉树写入queue中，无值就用"#"替代。反序列化时，递归取值，按照先序遍历的方式构造二叉树。

4.5 二叉树按层打印与ZigZag打印

题目：按层遍历，以及S型遍历

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node1 = Node(1)
  8. node3 = Node(3)
  9. node2 = Node(2, node1, node3)
  10. node5 = Node(5)
  11. node4 = Node(4, node2, node5)
  12. node8 = Node(8)
  13. node9 = Node(9, node8)
  14. node7 = Node(7, left=None, right=node9)
  15. node6 = Node(6, node4, node7)
  16.  
  17. # 按层次打印二叉树
  18. def print_tree_layer(root):
  19.     queue = []
  20.     queue.append(root)
  21.  
  22.     while len(queue) > 0:
  23.         node = queue.pop(0)
  24.         print(node.val)
  25.         if node.left != None:
  26.             queue.append(node.left)
  27.         if node.right != None:
  28.             queue.append(node.right)
  29.  
  30. print("------------层次遍历-----------")
  31. print_tree_layer(node6)
  32.  
  33. # 按zigzag打印二叉树
  34. def print_tree_zigzag(root):
  35.     stack1 = [] # 右左
  36.     stack2 = [] # 左右
  37.  
  38.     stack1.append(root)
  39.  
  40.     while len(stack1) > 0 or len(stack2) > 0:
  41.         while len(stack1) > 0:
  42.             node = stack1.pop()
  43.             print(node.val)
  44.  
  45.             if node.left != None:
  46.                 stack2.append(node.left)
  47.             if node.right != None:
  48.                 stack2.append(node.right)
  49.  
  50.         while len(stack2) > 0:
  51.             node2 = stack2.pop()
  52.             print(node2.val)
  53.  
  54.             if node2.right != None:
  55.                 stack1.append(node2.right)
  56.             if node2.left != None:
  57.                 stack1.append(node2.left)
  58.  
  59. print("------------zigzag遍历-----------")
  60. print_tree_zigzag(node6)

思路：层次遍历使用一个queue即可。S型遍历使用两个stack，stack1从右子树往左子树压入数据，弹出时打印，弹出后从左子树往右子树输入stack2；然后stack2弹出时打印，再压入stack1直到stack1和stack2都为空。

4.6 判断t1树是否包含t2树全部的拓扑结构

题目：给定彼此独立的两棵树头节点t1和t2，判断t1树是否包含t2树全部的拓扑结构

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node1_8 = Node(8)
  8. node1_9 = Node(9)
  9. node1_4 = Node(4, node1_8, node1_9)
  10. node1_10 = Node(10)
  11. node1_5 = Node(5, node1_10)
  12. node1_2 = Node(2, node1_4, node1_5)
  13. node1_6 = Node(6)
  14. node1_7 = Node(7)
  15. node1_3 = Node(3, node1_6, node1_7)
  16. node1_1 = Node(1, node1_2, node1_3)
  17.  
  18. node2_8 = Node(8)
  19. node2_4 = Node(4, node2_8)
  20. node2_5 = Node(5)
  21. node2_2 = Node(2, node2_4, node2_5)
  22.  
  23. def judge_contain(head1, head2):
  24.     if head2 == None:
  25.         return 1
  26.     if head1 == None and head2 != None:
  27.         return 0
  28.  
  29.     if head1.val != head2.val:
  30.         left_flag = judge_contain(head1.left, head2)
  31.         right_flag = judge_contain(head1.right, head2)
  32.         return max(left_flag, right_flag)
  33.     else:
  34.         left_flag = judge_contain(head1.left, head2.left)
  35.         right_flag = judge_contain(head1.right, head2.right)
  36.         if left_flag == 1 and right_flag == 1:
  37.             return 1
  38.         else:
  39.             return 0
  40.  
  41. result = judge_contain(node1_2, node2_2)
  42. print(result)

思路：递归return判断，t2树到达叶子节点则为true，t1树到达叶子节点而t2树未到达则为false。中间过程中，如果节点值不一样，则左子树和t2开始判断，右子树也和t2开始判断，有一个为true则为true；如果节点值一样，则逐一向下判断，只有其左右子树都为true时才为true。

4.7 判断二叉树是否为平衡二叉树

题目：平衡二叉树，要么是一棵空树，要么任何一个节点的左右子树高度差的绝对值不超过1。给定一棵二叉树的头节点head，判断这棵二叉树是否为平衡二叉树。

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node8 = Node(8)
  8. node5 = Node(5, node8)
  9. node4 = Node(4)
  10. node2 = Node(2, node4, node5)
  11. node6 = Node(6)
  12. node7 = Node(7)
  13. node3 = Node(3, node6, node7)
  14. node1 = Node(1, node2, node3)
  15.  
  16. def get_height(head, height):
  17.     if head == None:
  18.         return 1
  19.  
  20.     left_height = get_height(head.left, height + 1) if head.left != None else height
  21.     right_height = get_height(head.right, height + 1) if head.right != None else height
  22.  
  23.     return max(left_height, right_height)
  24.  
  25. def judge_balance_tree(head, flag):
  26.     if head == None:
  27.         return 1
  28.     left_height = get_height(head.left, flag) if head.left != None else 0
  29.     right_height = get_height(head.right, flag) if head.right != None else 0
  30.     if abs(left_height - right_height) <= 1:
  31.         flag = min(1, flag)
  32.     else:
  33.         flag = min(0, flag)
  34.     return flag
  35.  
  36. result = judge_balance_tree(node1, 1)
  37. print(result)

思路：函数一可以获取每个节点的高度。函数二通过左右子树的高度判断是否为平衡二叉树，只要有一个节点不是则整棵树都不是。

4.8 在二叉树中找到两个节点的最近公共祖先

题目：给定一棵二叉树的头节点head，以及这棵树中的两个节点o1和o2，青返回o1和o2的最近公共祖先节点。

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node4 = Node(4)
  8. node5 = Node(5)
  9. node2 = Node(2, node4, node5)
  10. node8 = Node(8)
  11. node7 = Node(7, node8)
  12. node6 = Node(6)
  13. node3 = Node(3, node6, node7)
  14. node1 = Node(1, node2, node3)
  15.  
  16. map = {}
  17. map.update({node1.val : []})
  18.  
  19. def preOrder(head, map):
  20.     if head == None:
  21.         return
  22.  
  23.     print(head.val)
  24.     if head.left != None:
  25.         map.update({head.left.val : [head.val] + map.get(head.val)})
  26.         preOrder(head.left, map)
  27.     if head.right != None:
  28.         map.update({head.right.val : [head.val] + map.get(head.val)})
  29.         preOrder(head.right, map)
  30. preOrder(node1, map)
  31.  
  32. def find_nearest_ancetor(head1, head2):
  33.     path1 = map.get(head1.val)
  34.     path2 = map.get(head2.val)
  35.  
  36.     for data1 in path1:
  37.         for data2 in path2:
  38.             if data1 == data2:
  39.                 return data1
  40.  
  41.  
  42. result = find_nearest_ancetor(node6, node8)
  43. print('---------ancetor--------------')
  44. print(result)

思路：先序遍历二叉树，构造一个dict，key为某个节点，value为key对应的所有按顺序的祖先列表。寻找两个节点的祖先时，就是依次在两个列表中。

4.9 二叉树节点间的最大距离

题目：从二叉树的节点A出发，可以向上或者向下走，但沿途的节点只能经过一次，当到达节点B时，路径上的节点数叫做A到B的距离。

  1. class Node:
  2.     def __init__(self, val, left=None, right=None):
  3.         self.val = val
  4.         self.left = left
  5.         self.right = right
  6.  
  7. node4 = Node(4)
  8. node5 = Node(5)
  9. node2 = Node(2, node4, node5)
  10. node6 = Node(6)
  11. node7 = Node(7)
  12. node3 = Node(3, node6, node7)
  13. node1 = Node(1, node2, node3)
  14.  
  15. map = {}
  16. map.update({node1.val : []})
  17.  
  18. def preOrder(head, map):
  19.     if head == None:
  20.         return
  21.  
  22.     print(head.val)
  23.     if head.left != None:
  24.         map.update({head.left.val : [head.val] + map.get(head.val)})
  25.         preOrder(head.left, map)
  26.     if head.right != None:
  27.         map.update({head.right.val : [head.val] + map.get(head.val)})
  28.         preOrder(head.right, map)
  29. preOrder(node1, map)
  30.  
  31. def find_node_distance(head1, head2):
  32.     path1 = [head1.val] + map.get(head1.val)
  33.     path2 = [head2.val] + map.get(head2.val)
  34.  
  35.     for i in range(1, len(path1) + 1):
  36.         for j in range(0, len(path2)):
  37.             if path1[i - 1] == path2[j]:
  38.                 return i + j
  39.  
  40. print('----------distance------------')
  41. result = find_node_distance(node5, node6)
  42. print(result)

思路：先找到两点间的最近公共祖先，然后计算两个节点到公共祖先的距离再求和。

4.10 通过先序和中序数组生成后序数组

题目：一颗二叉树所有节点值都不同，给定这棵树的先序和中序数组，不要重建整棵树直接生成后序数组。

  1. pre_order = [1,2,4,5,8,3,6,7]
  2. mid_order = [4,2,8,5,1,6,3,7]
  3. post_order = []
  4.  
  5. def find_post_order(pre_order, mid_order, post_order):
  6.     if pre_order == None or len(pre_order) == 0:
  7.         return
  8.  
  9.     first_elem = pre_order[0]
  10.     post_order.append(first_elem)
  11.  
  12.     for i in range(len(mid_order)):
  13.         if first_elem == mid_order[i]:
  14.             break
  15.     pre_left = pre_order[1 : i + 1]
  16.     pre_right = pre_order[i+1:]
  17.     mid_left = mid_order[0 : i]
  18.     mid_right = mid_order[i+1:]
  19.  
  20.     find_post_order(pre_right, mid_right, post_order)
  21.     find_post_order(pre_left, mid_left, post_order)
  22.  
  23. find_post_order(pre_order, mid_order, post_order)
  24. post_order.reverse()
  25. print(post_order)

思路：通过先序找到head节点，然后在中序中根据head分成左右两边，然后先序的右边和中序的右边继续递归，接着先序的左边和中序的左边继续递归。

5 递归和动态规划

5.1 斐波那契数列问题

题目：给定整数N，代表台阶数，一次可以跨2个或1个台阶，有多少种走法。

  1. def calc_step(n):
  2.     if n == 0:
  3.         return 0
  4.     elif n == 1:
  5.         return 1
  6.     elif n == 2:
  7.         return 2
  8.     else:
  9.         return calc_step(n-1) + calc_step(n-2)
  10.  
  11. result = calc_step(5)
  12. print(result)

思路：先确定前两步的走法数量，后续就是前一步跳1个台阶或者前两步跳2个台阶，所以是前一步走法+前两步走法。

5.2 矩阵的最小路径和

题目：给定一个矩阵m，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，返回所有的路径中最小的路径和。

  1. # 时间复杂度为O(MN)2
  2. def get_min_path_num(matrix, i, j):
  3.     if i == 0 and j == 0:
  4.         path  = matrix[i][j]
  5.         return path
  6.     elif i == 0 and j > 0:
  7.         path = get_min_path_num(matrix, i, j - 1) + matrix[i][j]
  8.         return path
  9.     elif i > 0 and j == 0:
  10.         path = get_min_path_num(matrix, i - 1, j) + matrix[i][j]
  11.         return path
  12.     else:
  13.         up = get_min_path_num(matrix, i - 1, j)
  14.         left = get_min_path_num(matrix, i, j - 1)
  15.         path = min(up, left) + matrix[i][j]
  16.         return path
  17.  
  18. # 时间复杂度为O(MN)
  19. def get_min_path_num2(matrix):
  20.     dp = [[-1 for j in range(len(matrix[0]))]  for i in range(len(matrix))]
  21.  
  22.     dp[0][0] = matrix[0][0]
  23.  
  24.     for i in range(1, len(matrix[0])):
  25.         dp[0][i] = dp[0][i-1] + matrix[0][i]
  26.  
  27.     for j in range(1, len(matrix)):
  28.         dp[j][0] = dp[j-1][0] + matrix[j][0]
  29.  
  30.     for i in range(1, len(matrix)):
  31.         for j in range(1, len(matrix[0])):
  32.             dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]
  33.  
  34.     return dp[len(matrix)-1][len(matrix[0])-1]
  35.  
  36. matrix = [[1,3,5,9], [8,1,3,4], [5,0,6,1], [8,8,4,0]]
  37. result = get_min_path_num(matrix, len(matrix) - 1, len(matrix[0]) - 1)
  38. print(result)
  39. result2 = get_min_path_num2(matrix)
  40. print(result2)

思路：先确定左上角的值，然后确定第一排和第一列的值，其余的值通过找上面和左边的最小值得到。我这边有两种方法，其中第一种方法时间复杂度为O(MN)2，第二种方法时间复杂度为O(MN)。

备注：递归的时间复杂度=递归的次数 * 每次递归中的操作次数。

5.3 换钱的最少货币数

题目：给定数组arr，arr中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个整数aim，代表要找的钱数，求组成aim的最少货币数。

  1. arr = [5, 2, 3]
  2. aim = 20
  3.  
  4. def find_least_money_num(arr, aim):
  5.     dp = [-1] * (aim + 1)
  6.     dp[0] = 0
  7.  
  8.     for data in arr:
  9.         if data <= aim:
  10.             dp[data] = 1
  11.  
  12.     for i in range(aim + 1):
  13.         for j in arr:
  14.             if i - j >= 0 and dp[i-j] >= 0:
  15.                 if dp[i] != -1:
  16.                     dp[i] = min(dp[i-j] + 1, dp[i])
  17.                 else:
  18.                     dp[i] = dp[i-j] + 1
  19.  
  20.     result = dp[aim] if dp[aim] != None else -1
  21.     return result
  22.  
  23. result = find_least_money_num(arr, aim)
  24. print(result)

思路：动态规划方法，从0到aim逐一求解最优质。

动态规划（避免暴力递归）的套路步骤：

1）找到什么可变参数可以代表一个递归状态，也就是哪些参数一旦确定，返回值就确定了。

2）把可变参数的所有组合映射成一张表，有1个可变参数就是一维表，2个可变参数就是二维表...

3）最终答案要的是表中的哪个位置，在表中标出。

4）根据递归过程的base case，把这张表最简单、不需要依赖其他位置的那些位置填好值。

5）填好表，返回最终答案在表中位置的值。

5.4 机器人到达指定位置方法数

题目：假设有排成一行的N个位置，记为1~N，N一定大于或等于2。开始时机器人在其中的M位置上，机器人可以往左走或往右走，如果机器人来到1位置，那么下一步只能往右来到2位置；如果机器人来到N位置，那么下一步只能往左来到N-1位置，规定机器人必须走K步，最终能来到P位置的方法有多少种。给定四个参数N、M、K、P，返回方法数。

  1. # 暴力递归法，时间复杂度过高
  2. method_num = 0
  3. def find_walk_method_num(n, m, k, p, cur_pos):
  4.     global method_num
  5.  
  6.     if k == 0:
  7.         if cur_pos == m:
  8.             method_num += 1
  9.         return
  10.  
  11.     if cur_pos == 1:
  12.         find_walk_method_num(n, m, k - 1 ,p, 2)
  13.     elif cur_pos == n:
  14.         find_walk_method_num(n, m, k - 1, p, n - 1)
  15.     else:
  16.         find_walk_method_num(n, m, k - 1, p, cur_pos - 1)
  17.         find_walk_method_num(n, m, k - 1, p, cur_pos + 1)
  18.  
  19. # 动态规划方法，构造二维数组逐一求解
  20. def find_walk_method_num2(n, m, k, p):
  21.     dp = [[0 for j in range(n)] for i in range(k + 1)]
  22.     dp[0][p - 1] = 1
  23.  
  24.     for i in range(1, k + 1):
  25.         for j in range(n):
  26.             if j == 0:
  27.                 dp[i][j] = dp[i - 1][j + 1]
  28.             elif j == n - 1:
  29.                 dp[i][j] = dp[i - 1][j - 1]
  30.             else:
  31.                 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
  32.     
  33.     return dp[k][m - 1]
  34.  
  35. print("--------------method1------------------")
  36. find_walk_method_num(7, 4, 9, 5, 5)
  37. print(method_num)
  38. print("--------------method2------------------")
  39. result = find_walk_method_num2(7, 4, 9, 5)
  40. print(result)

思路：找到可变参数 “当前位置” 和 “剩余步数”，然后构造二维数组，根据dp的套路计算出二维数组中所有的值。

5.5 换钱的方法数

题目：给定数组arr,arr中所有的值都为正数且不重复，每个值代表一种面值的货币，每种面值的货币可以使用任意张。再给定一个整数aim，代表要找的钱数，求换钱有多少种方法。

  1. arr = [5, 10, 25, 1]
  2. aim = 15
  3.  
  4. # 暴力递归
  5. def change_money(arr, index, aim):
  6.     res = 0
  7.  
  8.     if index == len(arr):
  9.         if aim == 0:
  10.             return 1
  11.         else:
  12.             return 0
  13.  
  14.     for i in range(0, aim // arr[index] + 1, 1):
  15.         res += change_money(arr, index + 1, aim - arr[index] * i)
  16.  
  17.     return res
  18.  
  19. print('---------------暴力求解法---------------------')
  20. result = change_money(arr, 0, aim)
  21. print(result)
  22.  
  23.  
  24. # 记忆优化搜索
  25. map = {}
  26. def change_money2(arr, index, aim):
  27.     res = 0
  28.     global map
  29.  
  30.     if index == len(arr):
  31.         if aim == 0:
  32.             return 1
  33.         else:
  34.             return 0
  35.  
  36.     for i in range(0, aim // arr[index] + 1, 1):
  37.         backup_res = map.get(str(index + 1) + '_' + str(aim - arr[index] * i))
  38.         if backup_res != None:
  39.             res += backup_res
  40.         else:
  41.             cur_res = change_money2(arr, index + 1, aim - arr[index] * i)
  42.             map.update({str(index + 1) + '_' + str(aim - arr[index] * i): cur_res})
  43.             res += cur_res
  44.     return res
  45.  
  46. print('---------------记忆优化搜索---------------------')
  47. result = change_money2(arr, 0, aim)
  48. print(result)

思路：第一种方法，就是每种货币组合的穷举，当第一张货币n为m张时，用其他货币组成aim-n*m的方法数，不停的递归。

第二种方法就是增加了记忆方法，解决第一种方法在递归时重复计算的问题。比如aim=1000，arr=[5,10,20,50]，2张5元和0张10元 或者 0张5元1张10元，都需要计算剩余20、50组成990元的方法数。

5.6 最长递增子序列

题目：给定数组arr，返回arr的最长递增子序列。

  1. arr = [2,1,5,3,6,4,8,9,7]
  2.  
  3. def find_longest_ascend(arr):
  4.     dp = [0] * len(arr)
  5.     dp[0] = 1
  6.     map = {}
  7.     biggest_index = 0
  8.     biggest_value = 0
  9.     res = []
  10.  
  11.     for i in range(1, len(arr)):
  12.         max_num = 0
  13.         for j in range(i):
  14.             if arr[j] < arr[i] and dp[j] >= max_num:
  15.                     max_num = dp[j]
  16.                     map.update({i : j})
  17.         dp[i] = max_num + 1
  18.         if dp[i] >= biggest_value:
  19.             biggest_value = dp[i]
  20.             biggest_index = i
  21.  
  22.     index = biggest_index
  23.     while index != None:
  24.         res.append(arr[index])
  25.         index = map.get(index)
  26.  
  27.     res.reverse()
  28.     return res
  29.  
  30. result = find_longest_ascend(arr)
  31. print(result)

思路：构造dp数组，每个代表以当前点结尾的最长子序列长度。每次计算时，遍历当前值(值1)之前的所有值，找到比值1小且最接近的值2，让值1做值2的后面一位数，值1的dp值为值2对应的dp值+1。

5.7 最长公共子序列问题

题目：给定两个字符串str1和str2，返回两个字符串的最长公共子序列。

  1. str1 = '1A2C3D4B56'
  2. str2 = 'B1D23CA45B6A'
  3.  
  4. # dp not pefect版本
  5. def find_same_str(str1, str2):
  6.     len1 = len(str1)
  7.     len2 = len(str2)
  8.     biggest_len = 0
  9.     res = []
  10.  
  11.     dp = [[0 for j in range(len1)] for i in range(len2)]
  12.     for i in range(len1):
  13.         if str2[0] == str1[i]:
  14.             dp[0][i] = 1
  15.  
  16.     for i in range(len2):
  17.         if str1[0] == str2[i]:
  18.             dp[i][0] = 1
  19.  
  20.     for i in range(0, len2):
  21.         for j in range(0, len1):
  22.             if str2[i] == str1[j]:
  23.                 max_num = 0
  24.                 for ii in range(i):
  25.                     for jj in range(j):
  26.                         max_num = max(dp[ii][jj], max_num)
  27.                 dp[i][j] = max_num + 1
  28.  
  29.                 if dp[i][j] > biggest_len:
  30.                     biggest_len = dp[i][j]
  31.  
  32.     for i in range(0, len2):
  33.         for j in range(0, len1):
  34.             if dp[len2 - i - 1][len1 - j - 1] == biggest_len:
  35.                 res.append(str2[len2 - i - 1])
  36.                 biggest_len -= 1
  37.                 break
  38.         if biggest_len == 0:
  39.             break
  40.  
  41.     res.reverse()
  42.     return ''.join(res)
  43.  
  44.  
  45. print('----------动态规划非完美版-----------------')
  46. result = find_same_str(str1, str2)
  47. print(result)
  48.  
  49.  
  50. def find_same_str2(str1, str2):
  51.     len1 = len(str1)
  52.     len2 = len(str2)
  53.     res = []
  54.     dp = [[0 for j in range(len1)] for i in range(len2)]
  55.  
  56.     for i in range(len1):
  57.         dp[0][i] = (dp[0][i-1] + 1 if i > 0 else 1) if str2[0] == str1[i] else dp[0][i-1]
  58.  
  59.     for i in range(1, len2):
  60.         for j in range(len1):
  61.             if str2[i] == str1[j]:
  62.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + 1 if j > 0 else dp[i-1][j] + 1
  63.             else:
  64.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) if j > 0 else dp[i-1][j]
  65.  
  66.     biggest_num = dp[len2-1][len1-1]
  67.  
  68.     for i in range(len2):
  69.         for j in range(len1):
  70.             if dp[len2-i-1][len1-j-1] == biggest_num:
  71.                 if str2[len2-i-1] == str1[len1-j-1]:
  72.                     res.append(str2[len2-i-1])
  73.                     biggest_num -=1
  74.             else:
  75.                 break
  76.  
  77.     res.reverse()
  78.  
  79.     return ''.join(res)
  80.  
  81. print('----------动态规划完美版-----------------')
  82. result = find_same_str2(str1, str2)
  83. print(result)

思路：

方法1：构建dp二维数组，第一行和第一行则值相等时设为1。然后从(2,2)位置开始遍历，每次取以(0,0)点为左上角，以当前点为左下角的矩形区域内较大值+1得到当前dp的值。dp构建完毕后，从dp数组右下角开始搜索需要的元素。

方法2：构建dp二维数组，初始化第一行，后续每行元素的值取dp数组上边和左边最大值，如果字符相等再加1。dp构建完毕后，从右下角开始搜索，每次找字符相等的元素。

5.8 最长公共子串问题

题目：给定两个字符串str1和str2，返回两个字符串的最长公共子串。

  1. str1 = '1AB2345CD'
  2. str2 = '12345EF'
  3.  
  4. def find_common_substring(str1, str2):
  5.     len1 = len(str1)
  6.     len2 = len(str2)
  7.     biggest_num = 0
  8.     res = []
  9.  
  10.     dp = [[0 for j in range(len1)] for i in range(len2)]
  11.  
  12.     for i in range(len1):
  13.         if str2[0] == str1[i]:
  14.             dp[0][i] = 1
  15.  
  16.     for i in range(1, len2):
  17.         for j in range(len1):
  18.             if j == 0 or str2[i] != str1[j]:
  19.                 dp[i][j] = dp[i-1][j]
  20.             else:
  21.                 dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + 1)
  22.  
  23.             if dp[i][j] > biggest_num:
  24.                 biggest_num = dp[i][j]
  25.  
  26.     flag = 0
  27.     for i in range(len2):
  28.         for j in range(len1):
  29.             if dp[i][j] == biggest_num and flag == 0:
  30.                 for k in range(biggest_num):
  31.                     res.append(str2[i-k])
  32.                 flag = 1
  33.  
  34.     res.reverse()
  35.  
  36.     return ''.join(res)
  37.  
  38. result = find_common_substring(str1, str2)
  39. print(result)

思路：标准dp套路，第一排初始化时值相同就赋1，后续几排取“上方值”和“斜对角+1”的较大值。然后在dp二维数组中找到最大的值，返回一遍斜对角的值就可以了。

5.9 最小编辑代价

题目：给定两个字符串str1和str2，再给定三个整数ic、dc和rc，分别代表插入、删除和替换一个字符的代价，返回将str1和str2编辑成str2d额最小代价。

  1. str1 = 'ab12cd3'
  2. str2 = 'abcdf'
  3. ic = 5
  4. dc = 3
  5. rc = 2
  6.  
  7. def calc_edit_cost(str1, str2, ic, dc, rc):
  8.     len1 = len(str1)
  9.     len2 = len(str2)
  10.     dp = [[0 for j in range(len2 + 1)]  for i in range(len1 + 1)]
  11.  
  12.     dp[0][0] = 0
  13.     for i in range(1, len2+1):
  14.         dp[0][i] = dp[0][i-1] + ic
  15.     for i in range(1, len1+1):
  16.         dp[i][0] = dp[i-1][0] + dc
  17.  
  18.     for i in range(1, len1+1):
  19.         for j in range(1, len2+1):
  20.             rc_cost =  dp[i-1][j-1] if str1[i-1] == str2[j-1] else dp[i-1][j-1] + rc
  21.             ic_cost = dp[i][j-1] + ic
  22.             dc_cost = dp[i-1][j] + dc
  23.             dp[i][j] = min(rc_cost, ic_cost, dc_cost)
  24.  
  25.     return dp[len1][len2]
  26.  
  27. result = calc_edit_cost(str1, str2, ic, dc, rc)
  28. print(result)

思路：构建dp数组，横纵维度各多出一个位置。每个位置，从上边删除得到，从左边插入得到，从斜对角替换得到（如果相同就不用替换了），每次寻找3个方向最小值得到dp值。

6 字符串问题

6.1 判断两个字符串是否互为旋转词

题目：如果一个字符串为str，把字符串str前面任意的部分挪到后面形成的字符串叫做str的旋转词。给定两个字符串a和b，判断a和b是否互为旋转词。

  1. str1 = '2ab1'
  2. str2 = 'ab12'
  3.  
  4. def is_rotate(str1, str2):
  5.     if len(str1) != len(str2):
  6.         return 0
  7.  
  8.     str = str1 + str1
  9.  
  10.     for i in range(len(str)):
  11.         for j in range(len(str2)):
  12.             if i+j < len(str) and str[i+j] != str2[j]:
  13.                 break
  14.             if j == len(str2) - 1:
  15.                 return 1
  16.     return 0
  17.  
  18. result = is_rotate(str1, str2)
  19. print(result)

思路：将某一个字符串*2拼接在一起，然后判断另一个字符串是否在这个拼接的大字符串里面。

6.2 翻转字符串

题目：给定一个字符类型的数组chas，请在单词间做逆序调整。只要做到单词的顺序逆序即可，对空格的位置没有特别要求。

  1. chas = ['d','o','g',' ','l','o','v','e','s',' ','p', 'i','g']
  2.  
  3. def reverse_word(chas):
  4.     left = 0
  5.     right = len(chas) - 1
  6.  
  7.     while left < right:
  8.         temp = chas[left]
  9.         chas[left] = chas[right]
  10.         chas[right] = temp
  11.         left += 1
  12.         right -= 1
  13.  
  14.     return chas
  15.  
  16. def reverse_chas(chas):
  17.     res = []
  18.     i = j = 0
  19.     reversed_chas = reverse_word(chas)
  20.  
  21.     while j < len(reversed_chas):
  22.         if reversed_chas[j] != ' ':
  23.             j += 1
  24.         else:
  25.             new_words = reverse_word(reversed_chas[i:j])
  26.             res += new_words + [' ']
  27.             i = j + 1
  28.             j += 1
  29.  
  30.     new_words = reverse_word(reversed_chas[i:j])
  31.     res += new_words
  32.  
  33.     return res
  34.  
  35. result = reverse_chas(chas)
  36. print(result)

思路：头尾两个指针实现整个数组翻转，然后再针对单个单词再翻转一次。

6.3 数组中两个字符串的最小距离

题目：给定一个字符串数组strs，再给定两个字符串str1和str2，返回在strs中str1和str2的最小距离，如果str1或str2为null，或不在strs中，返回-1。

  1. strs = ['13', '3', '3', '23', '2', '3', '99', '13']
  2. str1 = '13'
  3. str2 = '23'
  4.  
  5. def find_min_distance(strs, str1, str2):
  6.     if str1 == None or str2 == None:
  7.         return -1
  8.  
  9.     min_distance = -1
  10.     str1_index = str2_index = -1
  11.  
  12.     for i in range(len(strs)):
  13.         if strs[i] == str1:
  14.             str1_index = i
  15.             if str2_index != -1:
  16.                 distance = str1_index - str2_index
  17.                 if min_distance == -1:
  18.                     if str1_index != -1 and str2_index != -1:
  19.                         min_distance = distance
  20.                 elif min_distance > distance:
  21.                     min_distance = distance
  22.  
  23.         if strs[i] == str2:
  24.             str2_index = i
  25.             if str1_index != -1:
  26.                 distance = str2_index - str1_index
  27.                 if min_distance == -1:
  28.                     if str1_index != -1 and str2_index != -1:
  29.                         min_distance = distance
  30.                 elif min_distance > distance:
  31.                     min_distance = distance
  32.  
  33.     return min_distance
  34.  
  35. result = find_min_distance(strs, str1, str2)
  36. print(result)

思路：用两个index分别标记str1和str2在strs中的位置，每次识别到其中一个就开始计算两者间的距离，取最短距离即可。

6.4 字符串的转换路径问题

题目：给定两个字符串，记为start和to，再给定一个字符串列表list，list中一定包含to，list中没有重复字符串。所有的字符串都是小写的。规定start每次只能改变一个字符，最终的目标是彻底变成to，但是每次变成的新字符串必须在list中存在，请返回所有最短的变换路径。

  1. start = 'abc'
  2. end = 'cab'
  3. list = ['cab', 'acc', 'cbc', 'ccc', 'cac', 'cbb', 'aab', 'abb']
  4.  
  5. total_path_list = []
  6.  
  7. # 计算两个字符串的差异个数
  8. def calc_diff(str1, str2):
  9.     num = 0
  10.     for i in range(len(str1)):
  11.         if str1[i] != str2[i]:
  12.             num += 1
  13.     return num
  14.  
  15. # 求出所有的路径
  16. def get_all_path(start, end, list, path_list):
  17.     if start == end:
  18.         total_path_list.append(path_list.copy())
  19.         return
  20.  
  21.     if len(path_list) == 0:
  22.         path_list.append(start)
  23.  
  24.     for str in list:
  25.         if calc_diff(start, str) == 1:
  26.             if str in path_list:
  27.                 return
  28.             cur_path = path_list + [str]
  29.             get_all_path(str, end, list, cur_path)
  30.  
  31. # 求最短的路径
  32. def get_shortest_path(start, end, list):
  33.     shortest_paths = []
  34.     min_path_num = -1
  35.  
  36.     get_all_path(start, end, list, [])
  37.     for path in total_path_list:
  38.         if min_path_num == -1:
  39.             min_path_num = len(path)
  40.         elif min_path_num > len(path):
  41.             min_path_num = len(path)
  42.  
  43.     for path in total_path_list:
  44.         if len(path) == min_path_num:
  45.             shortest_paths.append(path)
  46.  
  47.     return shortest_paths
  48.  
  49. paths = get_shortest_path(start, end, list)
  50. for path in paths:
  51.     print(path)

思路：首先通过查找start所有可能的下一个节点next，然后将next作为start继续查找下一个节点直到为end。通过递归操作找出所有的路径，并且避免陷入死循环。然后在所有路径中找到最短的路径。

6.5 括号字符串的有效性和最长有效长度

题目：给定一个括号字符串str，返回最长的有效括号子串。

  1. def judge_valid_bracket(str):
  2.     stack = []
  3.  
  4.     for i in range(len(str)):
  5.         if str[i] != '(' and str[i] != ')':
  6.             return 0
  7.         if str[i] == '(':
  8.             stack.append(str[i])
  9.         if str[i] == ')':
  10.             if len(stack) == 0:
  11.                 return 0
  12.             chas = stack.pop()
  13.             if chas != '(' or chas == None:
  14.                 return 0
  15.  
  16.     if len(stack) == 0:
  17.         return 1
  18.     else:
  19.         return 0
  20.  
  21. def find_longest_valid_bracket(str):
  22.     size = len(str)
  23.     longest_num = 0
  24.  
  25.     for i in range(size):
  26.         for j in range(i+1, size + 1):
  27.             str_new = str[i:j]
  28.             if judge_valid_bracket(str_new) == 1:
  29.                 if j - i + 1 > longest_num:
  30.                     longest_num = j - i
  31.  
  32.     return longest_num
  33.  
  34. str = '()(()()('
  35. result = find_longest_valid_bracket(str)
  36. print(result)

思路：首先构造一个函数判断一个str是否为有效括号字符串，通过stack的方法。然后遍历字符串，通过两个指针控制start和end，依次判断是否为有效括号，找出最长的长度。

6.6 找到字符串的最长无重复字符子串

题目：给定一个字符串str，返回str的最长无重复字符子串的长度。

  1. def find_distinct_len(str):
  2.     distinct_len = 0
  3.     letter_set = set()
  4.  
  5.     for i in range(len(str)):
  6.         if str[i] not in letter_set:
  7.             letter_set.add(str[i])
  8.             distinct_len += 1
  9.         else:
  10.             return 0
  11.     return distinct_len
  12.  
  13. def find_longest_len(str):
  14.     longest_len = 0
  15.  
  16.     for i in range(len(str)):
  17.         for j in range(i+1, len(str) + 1):
  18.             str_len = j - i
  19.             if str_len <= longest_len:
  20.                 continue
  21.             sub_str = str[i : j]
  22.             distinct_len = find_distinct_len(sub_str)
  23.             if distinct_len > longest_len:
  24.                 longest_len = distinct_len
  25.  
  26.     return longest_len
  27.  
  28. str = 'abcd'
  29. result = find_longest_len(str)
  30. print(result)

思路：两个指针遍历数组，每个子串分别判断是否无重复，每次无重复的子串记录长度，下次遍历时如果子串长度小于该长度则不需要判断，算小小的优化。

6.7 最小包含子串的长度

题目：给定字符串str1和str2，求str1的子串中含有str2所有字符的最小子串长度

  1. def judge_contain_str(str1, str2):
  2.     if len(str1) < len(str2):
  3.         return 0
  4.  
  5.     i = 0
  6.     j = 0
  7.     while i < len(str1):
  8.         if str1[i] == str2[j]:
  9.             j += 1
  10.             if j == len(str2):
  11.                 return 1
  12.         i += 1
  13.  
  14.     return 0
  15.  
  16.  
  17. def find_shortest_substr_len(str1, str2):
  18.     shortest_len = 0
  19.  
  20.     for i in range(len(str1)):
  21.         for j in range(i+1, len(str1)+1):
  22.             if shortest_len > 0 and shortest_len <= j - i:
  23.                 continue
  24.  
  25.             sub_str = str1[i : j]
  26.             res = judge_contain_str(sub_str, str2)
  27.             if res == 1:
  28.                 if shortest_len == 0 or shortest_len > j - i:
  29.                     shortest_len = j - i
  30.  
  31.     return shortest_len
  32.  
  33. str1 = '12345'
  34. str2 = '344'
  35.  
  36. result = find_shortest_substr_len(str1, str2)
  37. print(result)

思路：str2不是取set集合。移动两个指针，判断str2的指针是否到结尾来判断包含关系。

6.8 回文最少分割数

题目：给定一个字符串str，返回把str全部切成回文子串的最小分割数。

  1. def judge_huiwen(str):
  2.     size = len(str)
  3.  
  4.     for i in range(size // 2):
  5.         if str[i] != str[size - 1 - i]:
  6.             return 0
  7.     return 1
  8.  
  9. def find_huiwen_split_num(str):
  10.     if str == '' or str == None:
  11.         return 0
  12.  
  13.     str_len = len(str)
  14.     split_num = 0
  15.  
  16.     i  = 0
  17.     while i < str_len:
  18.         for j in range(1, str_len + 1):
  19.             sub_str = str[i : str_len - j + 1]
  20.             if judge_huiwen(sub_str) == 1:
  21.                 split_num += 1
  22.                 i = str_len - j + 1
  23.                 break
  24.  
  25.     return split_num - 1
  26.  
  27. str = 'A'
  28. result = find_huiwen_split_num(str)
  29. print(result)

思路：首先构造判断回文的函数，然后逐步判断长度缩小的子串（从结尾开始缩小）是否为回文，最后仅剩一个字符时肯定为回文，下一轮迭代从上一个回文的下一个字符开始判断，继续逐步缩小子串再判断，直到字符串全部遍历完毕。

7 数组和矩阵问题

7.1 转圈打印矩阵

题目：给定一个整型矩阵matrix，请按照转圈的方式打印它。

  1. matrix1 = [[1,2,3],[4,5,6], [7,8,9], [10,11,12]]
  2. matrix2 = [[1,2,3,4,5], [6,7,8,9,10], [11,12,13,14,15], [16,17,18,19,20]]
  3. matrix3 = [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]]
  4.  
  5. def print_matrix(matrix):
  6.     width = len(matrix[0])
  7.     height = len(matrix)
  8.  
  9.     min_len = max(width, height)
  10.  
  11.     for k in range(min_len // 2):
  12.  
  13.         for i in range(0, width - 1 - k * 2):
  14.             print(matrix[k][i + k])
  15.         for i in range(height - 1 - k * 2):
  16.             print(matrix[i + k][width - 1 - k])
  17.         for i in range(width - 1 - k * 2):
  18.             print(matrix[height - 1 - k][width - i - 1 - k])
  19.         for i in range(height - 1 - k * 2):
  20.             print(matrix[height - i - 1 - k][k])
  21.  
  22. print_matrix(matrix3)

思路：一圈一圈打印。

7.2 将正方形顺时针转动90度

题目：给定一个N*N的矩阵matrix，把这个矩阵调整成顺时针转动90度后的形式。

  1. matrix = [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16]]
  2.  
  3. def rotate_90(matrix):
  4.     size = len(matrix)
  5.     matrix_new = [[-1 for j in range(size)] for i in range(size)]
  6.  
  7.     for i in range(size):
  8.         for j in range(size):
  9.             matrix_new[j][size - 1 - i] = matrix[i][j]
  10.  
  11.     return matrix_new
  12.  
  13. result = rotate_90(matrix)
  14. print(result)

思路：计算映射关系，(x,y) -> (y, N-1-x)

7.3 之字形打印矩阵

题目：给定一个矩阵matrix，按照“之”字形订地方式打印这个矩阵。

  1. matrix = [[1,2,3,4], [5,6,7,8], [9,10,11,12]]
  2.  
  3. def print_matrix(matrix):
  4.     i = j = 0
  5.     height = len(matrix)
  6.     width = len(matrix[0])
  7.  
  8.     print(matrix[i][j])
  9.  
  10.     flag = 1
  11.     for sum in range(1, height + width - 1):
  12.         if flag == 1:  # 正向
  13.             flag = -1
  14.             for i in range(sum + 1):
  15.                 row = i
  16.                 column = sum - i
  17.                 if row < height and column < width:
  18.                     print(matrix[row][column])
  19.                 if row >= height:
  20.                     break
  21.         else:  # 反向
  22.             flag = 1
  23.             stack = []
  24.             for i in range(sum + 1):
  25.                 row = i
  26.                 column = sum - i
  27.                 if row < height and column < width:
  28.                     stack.append(matrix[row][column])
  29.                 if row >= height:
  30.                     break
  31.             while len(stack) > 0:
  32.                 print(stack.pop())
  33.  
  34. print_matrix(matrix)

思路：全部按照从右上方到左下方的方向打印，分奇偶行，如果是偶数行就反方向输出。

7.4 找到无序数组中最小的k个数

题目：给定一个无序的整型数组arr，找到其中最小的k个数。

  1. arr = [1,2,7,3,6,9,8,4,4,2,1,10,0]
  2. k = 4
  3.  
  4. def find_min_k_number(arr, k):
  5.     stack1 = []
  6.     stack2 = []
  7.  
  8.     for i in range(len(arr)):
  9.         if len(stack1) == 0:
  10.             stack1.append(arr[i])
  11.         else:
  12.             if stack1[-1] > arr[i]:
  13.                 while len(stack1) > 0 and stack1[-1] > arr[i]:
  14.                     stack2.append(stack1.pop())
  15.                 stack1.append(arr[i])
  16.                 while len(stack1) < k and len(stack2) > 0:
  17.                     stack1.append(stack2.pop())
  18.                 stack2.clear()
  19.             else:
  20.                 if len(stack1) < k:
  21.                     stack1.append(arr[i])
  22.     return stack1
  23.  
  24. result = find_min_k_number(arr, k)
  25. print(result)

思路：通过两个stack模拟最大堆，每次对比栈顶元素，大于则直接忽略，小于则替换堆里面的元素。

7.5 需要排序的最短子数组长度

题目：给定一个无序数组arr，求出需要排序的最短子数组长度。

  1. arr = [1,5,3,4,2,6,7]
  2.  
  3. def get_shortest_length(arr):
  4.     min_index = max_index = -1
  5.     arr_min = arr[-1]
  6.     arr_max = arr[0]
  7.  
  8.     for i in range(1, len(arr)):
  9.         if arr[i] >= arr_max:
  10.             arr_max = arr[i]
  11.         else:
  12.             max_index = i
  13.  
  14.     for i in range(len(arr) - 1, 0, -1):
  15.         if arr[i] <= arr_min:
  16.             arr_min = arr[i]
  17.         else:
  18.             min_index = i - 1
  19.  
  20.     return max_index - min_index
  21.  
  22. result = get_shortest_length(arr)
  23. print(result)

思路：找出错误位置的最左边和最右边，从右往左遍历，遍历的过程记录右侧出现过的数的最小值，记录排序出错的最左边的位置。从左往右遍历，遍历的过程记录左侧出现过的数的最大值，记录排序出错的最右边的位置。

7.6 最长的可整合子数组的长度

题目：给定一个整型数组arr，请返回其中最大可整合子数组的长度。

  1. arr = [5,5,3,2,6,4,3]
  2.  
  3. # 判断是否为整合数组
  4. def judge_combine(arr):
  5.     arr_max = arr_min = arr[0]
  6.     data_set = set()
  7.     data_set.add(arr[0])
  8.  
  9.     for i in range(1, len(arr)):
  10.         if arr[i] in data_set:
  11.             return 0
  12.         if arr[i] > arr_max:
  13.             arr_max = arr[i]
  14.         if arr[i] < arr_min:
  15.             arr_min = arr[i]
  16.     if arr_max - arr_min == len(arr) - 1:
  17.         return 1
  18.     else:
  19.         return 0
  20.  
  21. def find_longest_length(arr):
  22.     longest_len = 0
  23.  
  24.     for end in range(len(arr), 0 , -1):
  25.         for start in range(0, end):
  26.             distance = end - start
  27.             if distance <= longest_len:
  28.                 break
  29.             sub_str = arr[start : end]
  30.             res = judge_combine(sub_str)
  31.             if res == 1 and distance > longest_len:
  32.                 longest_len = distance
  33.  
  34.     return longest_len
  35.  
  36. result = find_longest_length(arr)
  37. print(result)

思路：可整合数组的判断，不能有重复，且最大值和最小值的差刚好是数组的长度。然后遍历数组，移动start和end指针判断是否为可整合数组，保留最大的长度。

7.7 未排序正数数组中累加和为给定值的最长子数组长度

题目：给定一个数组arr，该数组无序，但每个值均为正数，再给定一个正数k。求arr的所有子数组中所有元素相加和为k的最长子数组长度。

  1. arr = [1,2,1,1,1]
  2. k = 3
  3.  
  4. def find_longest_len(arr, k):
  5.     left = right = 0
  6.     arr_len = 0
  7.  
  8.     while left < len(arr) and right < len(arr):
  9.         sub_str = arr[left : right + 1]
  10.         str_sum = sum(sub_str)
  11.  
  12.         if str_sum == k:
  13.             if right - left + 1 > arr_len:
  14.                 arr_len = right - left + 1
  15.             right += 1
  16.         elif str_sum < k:
  17.             right += 1
  18.         else:
  19.             left += 1
  20.  
  21.     return arr_len
  22.  
  23. result = find_longest_len(arr, k)
  24. print(result)

思路：两个指针left和right指定子串长度，如果子串和小于k则right右移一位，子串和大于k则left右移一位，如果和等于k则记录下长度。

7.8 未排序数组中累加和为给定值的最长子数组系列问题

题目：给定一个无序数组arr，其中元素可正、可负、可0。给定一个整数k，求arr所有的子数组中累加和为k的最长子数组长度。

  1. arr = [-4,-2,1,-3,2,6,7]
  2. k = 5
  3.  
  4. def find_longest_len(arr, k):
  5.     map = {}
  6.     sum = 0
  7.     longest_len = 0
  8.  
  9.     for i in range(len(arr)):
  10.         sum += arr[i]
  11.         if map.get(sum - k) is not None:
  12.             str_len = i - map.get(sum - k)
  13.             if str_len > longest_len:
  14.                 longest_len = str_len
  15.         if map.get(sum) is None:
  16.             map.update({sum : i})
  17.  
  18.     return longest_len
  19.  
  20. result = find_longest_len(arr, k)
  21. print(result)

思路：某一段子串arr[i...j]的和为arr[0...j]与arr[0...i]之间的差，构造map记录每个sum第一次出现的坐标，然后找到sum-k在arr中的位置。

变换题型：

（1）给定一个无序数组arr，其中元素可正、可负、可0。求arr所有的子数组中正数与负数个数相等的最长子数组长度。

（2）给定一个无序数组arr，其中元素只是1或0。求arr所有的子数组中0和1个数相等的最长子数组长度。

7.9 奇数下标都是奇数或者偶数下标都是偶数

题目：给定一个长度不大于2的数组arr，实现一个函数调整arr，要么让所有的偶数下标都是偶数，要么让所有的奇数下标都是奇数。

  1. arr = [2,2,2,2,2,1,1]
  2.  
  3. def adjust_arr(arr):
  4.     arr_len = len(arr)
  5.     arr_new = [None] * arr_len * 2
  6.     arr_new2 = [None] * arr_len
  7.     q_index = 0
  8.     o_index = 1
  9.  
  10.     for i in range(len(arr)):
  11.         if (i + 1) % 2 == 1:  # 奇数位
  12.             if arr[i] % 2 == 1:  # 是奇数
  13.                 arr_new[q_index] = arr[i]
  14.                 q_index += 2
  15.             else:
  16.                 arr_new[o_index] = arr[i]
  17.                 o_index += 2
  18.         else:  # 偶数位
  19.             if arr[i] % 2 == 0: # 是偶数
  20.                 arr_new[o_index] = arr[i]
  21.                 o_index += 2
  22.             else:
  23.                 arr_new[q_index] = arr[i]
  24.                 q_index += 2
  25.  
  26.     index = 0
  27.     for i in range(len(arr_new)):
  28.         if arr_new[i] != None:
  29.             arr_new2[index] = arr_new[i]
  30.             index += 1
  31.  
  32.     return arr_new2
  33.  
  34. result = adjust_arr(arr)
  35. print(result)

思路：构建1个长度是2*len的arr_new以及奇数位置指针和偶数位置指针，然后遍历原数组，在arr_new中奇数位放入奇数，偶数位放入偶数。最后在arr_new中去掉None就得到了调整后的数组。

7.10 子数组的最大累加和问题

题目：给定一个数组arr，返回子数组的最大累加和。

  1. def find_biggest_sum(arr):
  2.     min_index = 0
  3.     max_index = 0
  4.     arr_min = arr[0]
  5.     arr_max = arr[0]
  6.     sum = arr[0]
  7.     biggest_sum = sum
  8.  
  9.     for i in range(1, len(arr)):
  10.         sum += arr[i]
  11.  
  12.         if sum > arr_max:
  13.             arr_max = sum
  14.             max_index = i
  15.         if sum < arr_min:
  16.             arr_min = sum
  17.             min_index = i
  18.  
  19.         if max_index > min_index:
  20.             cur_biggest_sum = arr_max - arr_min
  21.         else:
  22.             cur_biggest_sum = arr_max
  23.  
  24.         if cur_biggest_sum > biggest_sum:
  25.             biggest_sum = cur_biggest_sum
  26.  
  27.     return biggest_sum
  28.  
  29. arr = [1,-2,3,5,-2,6,-1]
  30. result = find_biggest_sum(arr)
  31. print(result)

思路：arr[i...j]是最大累加和，则arr[...i]是最小累加和，arr[...j]是最大累加和，max_index一定要在min_index的后面才能最大值减最小值，否则只保留最大值。每移动一步，计算当前步的局部最大累加和，最后取全局的最大累加和。

7.11 数组中子数组的最大累乘积

题目：给定一个double类型的数组arr，其中的元素可正、可负、可0，返回子数组累乘积的最大乘积。

  1. def find_max_product(arr):
  2.     arr_max = arr[0]
  3.     arr_min = arr[0]
  4.     res = arr[0]
  5.  
  6.     for i in range(1, len(arr)):
  7.         max_end = arr_max * arr[i]
  8.         min_end = arr_min * arr[i]
  9.         arr_max = max(max_end, min_end, arr[i])
  10.         arr_min = min(max_end, min_end, arr[i])
  11.         res = max(res, arr_max)
  12.  
  13.     return res
  14.  
  15. arr = [-2.5,4,0,3,0.5,8,-1]
  16. result = find_max_product(arr)
  17. print(result)

思路：不断地累乘积，最大值可能是（之前最小值*当前值（负值），之前最大值*当前值，当前值）的最大值。

7.12 不包含本位置值的累乘数组

题目：给定一个整型数组arr，返回不包含本位置得累乘数组。

  1. arr1 = [2,3,1,4]
  2. arr2 = [2,0,1,4]
  3. arr3 = [2,0,1,0,4]
  4.  
  5. def get_cum_multiply(arr):
  6.     product = 1
  7.     non_zero_product = 1
  8.     zero_num = 0
  9.     arr_new = [0] * len(arr)
  10.  
  11.     for i in range(len(arr)):
  12.         product *= arr[i]
  13.         if arr[i] != 0:
  14.             non_zero_product *= arr[i]
  15.         else:
  16.             zero_num += 1
  17.  
  18.     if product != 0:
  19.         for i in range(len(arr)):
  20.             arr_new[i] = product / arr[i]
  21.     else:
  22.         for i in range(len(arr)):
  23.             if zero_num == 1 and arr[i] == 0:
  24.                 arr_new[i] = non_zero_product
  25.             else:
  26.                 arr_new[i] = 0
  27.  
  28.     return arr_new
  29.  
  30. result = get_cum_multiply(arr3)
  31. print(result)

思路：先得到所有值累乘得结果，然后分数组中0有0个、1个、1个以上的情况分别进行处理。

7.13 求最短通路值

题目：用1个整型矩阵matrix表示一个网络，1代表有路，0代表无路，每一个位置只要不越界，都有上下左右4个方向，求从最左上角到最右下角的最短通路值。

  1. import sys
  2.  
  3. matrix = [[1,0,1,1,1], [1,0,1,0,1], [1,1,1,0,1], [0,0,1,0,1]]
  4. matrix2 = [[1,0], [1,1]]
  5.  
  6. def find_shortest_num(matrix, i, j, path_set):
  7.     if i == len(matrix) - 1 and j == len(matrix[0]) - 1:
  8.         return 1
  9.  
  10.     path_set.add(str(i) + '_' + str(j))
  11.  
  12.     up_sum = down_sum = left_sum = right_sum = sys.maxsize
  13.  
  14.     # 上
  15.     if i - 1 >= 0 and matrix[i - 1][j] == 1 and str(i - 1) + '_' + str(j) not in path_set:
  16.         up_sum = find_shortest_num(matrix, i - 1, j, path_set)
  17.     # 下
  18.     if i + 1 <= len(matrix) - 1 and matrix[i + 1][j] == 1 and str(i + 1) + '_' + str(j) not in path_set :
  19.         down_sum = find_shortest_num(matrix, i + 1, j, path_set)
  20.     # 左
  21.     if j - 1 >= 0 and matrix[i][j - 1] == 1 and str(i) + '_' + str(j - 1) not in path_set:
  22.         left_sum = find_shortest_num(matrix, i, j - 1, path_set)
  23.     # 右
  24.     if j + 1 <= len(matrix[0]) - 1 and matrix[i][j + 1] == 1 and str(i) + '_' + str(j + 1) not in path_set:
  25.         right_sum = find_shortest_num(matrix, i, j + 1, path_set)
  26.  
  27.     shortest_sum = min(up_sum, down_sum, left_sum, right_sum) + 1
  28.     return shortest_sum
  29.  
  30. path_set = set()
  31. shortest_sum = find_shortest_num(matrix, 0, 0, path_set)
  32. print(shortest_sum)

思路：递归搜索，在每个点上查看上下左右：

（1）是否有1

（2）是否越界

（3）是否曾经到过（否则会陷入死循环）

如果没有则找到下一个点继续搜索，直到到达最右下角。

8、其他

8.1 求两个数的最大公约数

  1. M = 10
  2. N = 5
  3.  
  4. def gcd(M, N):
  5.     min_num = min(M, N)
  6.     max_num = 1
  7.  
  8.     for i in range(2, min_num + 1):
  9.         if M % i == 0 and N % i == 0:
  10.             max_num = i
  11.  
  12.     return max_num
  13.  
  14. max_num = gcd(M, N)
  15. print(max_num)
  16.  
  17. def gcd2(M, N):
  18.     if N == 0:
  19.         return M
  20.     else:
  21.         return gcd2(N, M % N)
  22.  
  23. max_num = gcd2(M, N)
  24. print(max_num)

思路：两种方法，方法一：从1开始逐一找公约数，比较费时。方法二：使用辗转相除法，如果q和r分别是m除以n的商及余数，即m=nq+r，那么m和n的最大公约数等于n和r的最大公约数。

8.2 有关阶乘的问题

题目：给定一个非负整数N，返回N!结果的末尾为0的数量。

  1. # 原始方法
  2. def get_zero_num(num):
  3.     if num < 0:
  4.         return 0
  5.  
  6.     res = 0
  7.     for i in range(5, num + 1, 5):
  8.         cur = i
  9.         while cur % 5 == 0:
  10.             res += 1
  11.             cur /= 5
  12.  
  13.     return res
  14.  
  15. # result = get_zero_num(1000000000)
  16. # print(result)
  17.  
  18. # 进阶方法
  19. def get_zero_num2(num):
  20.     if num < 0:
  21.         return 0
  22.  
  23.     res = 0
  24.     cur = 5
  25.     while cur < num:
  26.         res += int(num / cur)
  27.         cur *= 5
  28.  
  29.     return res
  30. result2 = get_zero_num2(1000000000)
  31. print(result2)

思路：0的个数和因子5的个数相关。方法1是从5到num（每一步加5）分别计算每个数因子5的个数。方法2中，分别计算1个因子5的数量，2个因子5（25）的数量，3个因子5（125）的数量...，然后数量累加即可。

8.3 判断一个点是否在矩形内部

题目：在二维坐标系中，给定4个点代表的矩形，再给定一个点(x,y)，判断(x,y)是否在矩形中。

  1. def judge_in_rectangle(x1, y1, x2, y2, x3, y3, x4, y4, x, y):
  2.     res1 = (x - x1) * (x4 - x1) + (y - y1) * (y4 - y1)
  3.     res2 = (x - x1) * (x2 - x1) + (y - y1) * (y2 - y1)
  4.     res3 = (x - x3) * (x4 - x3) + (y - y3) * (y4 - y3)
  5.     res4 = (x - x3) * (x2 - x3) + (y - y3) * (y2 - y3)
  6.  
  7.     if res1 >= 0 and res2 >= 0 and res3 >= 0 and res4 >= 0:
  8.         return 1
  9.     else:
  10.         return 0
  11.  
  12. result = judge_in_rectangle(0, 2, 2, 2, 2, 0, 0, 0, 2.1, 1.9)
  13. print(result)

思路：

8.4 判断一个点是否在三角形内部

题目：给定3个点代表三角形，再给定一个点(x,y)，判断(x,y)是否在三角形中。

  1. import math
  2.  
  3. def get_len(x1, y1, x2, y2):
  4.     return math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))
  5.  
  6. def get_area(x1, y1, x2, y2, x3, y3):
  7.     a = get_len(x1, y1, x2, y2)
  8.     b = get_len(x1, y1, x3, y3)
  9.     c = get_len(x2, y2, x3, y3)
  10.     p = (a + b + c) / 2
  11.     return math.sqrt(p * (p - a) * (p - b) * (p - c))
  12.  
  13. def similar(a, b):
  14.     if abs(a - b) <= 0.00001:
  15.         return 1
  16.  
  17. def judge_in_side(x1, y1, x2, y2, x3, y3, x, y):
  18.     s = get_area(x1, y1, x2, y2, x3, y3)
  19.     s1 = get_area(x1, y1, x2, y2, x, y)
  20.     s2 = get_area(x1, y1, x3, y3, x, y)
  21.     s3 = get_area(x2, y2, x3, y3, x, y)
  22.  
  23.     s_sum = s1 + s2 + s3
  24.     if (s_sum > s and similar(s_sum, s) == 1) or s_sum <= s:
  25.         return 1
  26.     else:
  27.         return 0
  28.  
  29. result = judge_in_side(0, 0, 1, 1, 2, 0, 1, 0.5)
  30. print(result)

思路：利用海伦公式可以根据边长计算三角形面积，如果点在三角形内部则理论上点和三组三角形两个点构成的三角形面积之和等于原三角形面积，计算上考虑double精度的情况。

8.5 设计有setAll功能的哈希表

题目：哈希表常见的三个操作put、get和containsKey时间复杂度为O(1)。现在想加一个setAll功能，就是把所有记录的value都设成统一的值，时间复杂度也是O(1)。

  1. import time
  2.  
  3. class Data:
  4.     def __init__(self, data):
  5.         self.data = data
  6.         self.one_time = time.time()
  7.  
  8.  
  9. class MyValue:
  10.     my_dict = {}
  11.     one_time = None
  12.     one_value = None
  13.  
  14.     def put(self, key, value):
  15.         one_data = Data(value)
  16.         self.my_dict.update({key : one_data})
  17.  
  18.     def containsKey(self, key):
  19.         if key in self.my_dict:
  20.             return 1
  21.         else:
  22.             return 0
  23.  
  24.     def setAll(self, value):
  25.         self.one_time = time.time()
  26.         self.one_value = value
  27.  
  28.     def get(self, key):
  29.         if self.containsKey(key) == 0:
  30.             return None
  31.  
  32.         my_data = self.my_dict.get(key)
  33.         if self.one_time is None or  my_data.one_time > self.one_time:
  34.             return my_data.data
  35.         else:
  36.             return self.one_value
  37.  
  38. my_value = MyValue()
  39. print(my_value.get("haha"))
  40. my_value.put("haha", 10)
  41. my_value.put("hoho", 10)
  42. print(my_value.get("haha"))
  43. my_value.setAll(20)
  44. print(my_value.get("haha"))
  45. print(my_value.get("hoho"))

思路：用记录每条数据的生成时间，setAll可以设置全局变量的时间，如果每条记录的时间大于全局时间则返回自己的value，否则返回全局变量的value。

8.6 最大的leftMax与rightMax之差的绝对值

题目：给定一个整型数组arr，可以划分成左右两个部分。求这么多划分方案中，左部分中的最大值减去右部分最大值的绝对值，最大是多少？

  1. def get_max_difference(arr):
  2.     arr_len = len(arr)
  3.     left_max_arr = [-1] * arr_len
  4.     right_max_arr = [-1] * arr_len
  5.  
  6.     cur_left_max = -1
  7.     for i in range(arr_len):
  8.         cur_left_max = max(cur_left_max, arr[i])
  9.         left_max_arr[i] = cur_left_max
  10.  
  11.     cur_right_max = -1
  12.     for i in range(arr_len - 1, -1, -1):
  13.         cur_right_max = max(cur_right_max, arr[i])
  14.         right_max_arr[i] = cur_right_max
  15.  
  16.     cur_max = -1
  17.     for i in range(1, arr_len - 1):
  18.         diff = abs(left_max_arr[i] - right_max_arr[i])
  19.         cur_max = max(cur_max, diff)
  20.  
  21.     return cur_max
  22.  
  23. arr = [2,7,3,1,1]
  24. result = get_max_difference(arr)
  25. print(result)

思路：两个数组，数组一是在从左往右遍历时记录累计最大值，数组二是在从右往左遍历时记录累计最大值，最后遍历时计算数组一和数组二的差后取最大的差值。

8.7 累加出整个范围所有的数最少还需几个数

题目：给定一个有序的正数数组arr和一个正数range，如果可以自由选择arr中的数字，想累加得到1~range范围上所有的数，返回arr最少还缺几个数。

  1. arr = [3,17,21,78]
  2. K = 67
  3.  
  4. def find_num(arr, K):
  5.     lack_num_arr = []
  6.     cur_max = 0
  7.  
  8.     for num in arr:
  9.         while cur_max < num - 1:
  10.             lack_num_arr.append(cur_max + 1)
  11.             cur_max = cur_max + cur_max + 1
  12.         cur_max += num
  13.  
  14.         if cur_max >= K:
  15.             break
  16.  
  17.     while cur_max < K:
  18.         lack_num_arr.append(cur_max + 1)
  19.         cur_max = cur_max + cur_max + 1
  20.  
  21.     return lack_num_arr
  22.  
  23. result = find_num(arr, K)
  24. print(result)
  25. print(len(result))

思路：如果已经搞定了1~touch范围上的所有数，下一个缺的数就是touch+1，有了touch+1之后，就可以搞定1~touch+touch+1范围上的所有数。随着touch的扩大，最终会达到或超过range。

8.8 认识过滤器

题目：不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64B。现在想要实现一个网页过滤系统，利用该系统可以根据网页的URL判断该网页是否在黑名单上。


答：利用布隆过滤器。
它由很长的二进制向量和一系列（多个）hash函数组成，主要用于判断一个元素是否在一个集合中（存在一定的误差）。hash函数可以调用包中的hash方法，通过不同的seed可以得到一系列的hash函数。通过hash值对向量长度取余数可以得到hash对应向量的位置信息。
添加元素：
（1）将要添加的元素给K个哈希函数
（2）得到对应于位数组上的k个位置
（3）将这k个位置设为1
查询元素：
（1）将要查询的元素给k个哈希函数
（2）得到对应于位数组上的k个位置
（3）如果k个位置有一个为0，则肯定不在集合中
（4）如果k个位置全部为1，则可能在集合中。

8.9 只用2GB内存在20亿个整数中找到出现次数最多的数

题目：有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数。

答：哈希表存放32位整数的结果，则key占用4B，value也是4B，则哈希表中一条记录需要占用8B。当哈希表记录数为20亿个时，需要至少16GB的内存。
解决方法是把20亿个数的大文件用哈希函数分成16个小文件，则同一种数不可能被散列到不同的小文件上，同事每个小文件中不同的数一定不会大于2亿种（1.6GB内存）。然后对每个小文件用哈希表来统计其中每种数出现的次数，这样就得到了16个小文件中各自出现次数最多的数，还有各自的次数统计。接下来只要选出这16个小文件各自的第一名中谁出现的次数最多即可。
 

8.10 40亿个非负整数中找到未出现的数

题目：32位无符号整数的范围是0~4294967295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有未出现过的数。可以使用最多1GB的内存，怎么找到所有未出现过的数？

答：假如使用哈希表记录40亿条，存一个32位整数需要4B，则最差情况需要40亿*4B=160亿字节=16GB。解决方案是使用bit map存放出现过的数，申请一个长度为4294967295的bit类型的数组bitArr，8个bit为1B，此时占用16GB/32=500MB。然后遇到某个数，就把bitArr相应位置的值设置为1。最后遍历完bitArr之后，没出现过的数就都可以找出来了。

8.11 找到100亿个URL中重复的URL

题目：有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL。

答：把大文件通过哈希函数分配到机器上，或者通过哈希函数把大文件拆分成小文件，然后处理每一个小数量的集合的重复文件。
 

8.12 搜索词汇的TOP K问题

题目：某搜索公司一天的用户搜索词汇是海量的，请设计一种求出每天热门top 100词汇的可行办法：

答：哈希分流 + 堆排序

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/333156
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号