1. 对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
出处：
https://edu.csdn.net/practice/26912045
代码：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def insertionSortList(head: ListNode) -> ListNode: dummy = ListNode(float('-inf'), head) tail = dummy cur = head while cur: if tail.val <= cur.val: # 若链表尾节点值小于等于当前节点，不需要移动 tail.next = cur tail = cur cur = cur.next else: # 在已排序部分找到插入位置 prev = dummy while prev.next.val < cur.val: prev = prev.next # 插入节点 tail.next = cur.next cur.next = prev.next prev.next = cur cur = tail.next return dummy.next def createList(lst): head = ListNode(lst[0]) p = head for i in lst[1:]: node = ListNode(i) p.next = node p = p.next return head def traversalList(head): while head: print(head.val, end="->") head = head.next print("nill") #%% lst1 = [4, 2, 1, 3] lst2 = [-1, 5, 3, 4, 0] head1 = createList(lst1) traversalList(head1) sorted_head1 = insertionSortList(head1) traversalList(sorted_head1) head2 = createList(lst2) traversalList(head2) sorted_head2 = insertionSortList(head2) traversalList(sorted_head2)
输出：
4->2->1->3->nill
1->2->3->4->nill
-1->5->3->4->0->nill
-1->0->3->4->5->nill
2. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
示例 3：
输入：root = []
输出：true
提示：
树中的节点数在范围 [0, 5000] 内
-10^4 <= Node.val <= 10^4
出处：
https://edu.csdn.net/practice/26912046
代码：
# 定义二叉树节点 class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution(object): def isBalanced(self, root): if not root: return True left_depth = self.get_depth(root.left) right_depth = self.get_depth(root.right) if abs(left_depth - right_depth) > 1: return False else: return self.isBalanced(root.left) and self.isBalanced(root.right) def get_depth(self, root): if root is None: return 0 else: return max(self.get_depth(root.left), self.get_depth(root.right)) + 1 def listToTree(lst): if not lst: return None root = TreeNode(lst[0]) queue = [root] i = 1 while i < len(lst): node = queue.pop(0) if lst[i] is not None: node.left = TreeNode(lst[i]) queue.append(node.left) i += 1 if i < len(lst) and lst[i] is not None: node.right = TreeNode(lst[i]) queue.append(node.right) i += 1 return root # %% s = Solution() null = None nums = [3,9,20,null,null,15,7] root = listToTree(nums) print(s.isBalanced(root)) nums = [1,2,2,3,3,null,null,4,4] root = listToTree(nums) print(s.isBalanced(root))
输出：
True
False
3. 找出素数对
任意输入一个大于10的偶数，编程找出所有和等于该偶数的素数对
以下程序实现了这一功能，请你填补空白处内容：
```python
h = 0 def a(h): x = 0 for j in range(2, h): if h % j == 0: x = 1 break if x == 0: return 1 n = int(input("输入任意大于10的偶数：")) for i in range(n,n+1): h = 0 if i % 2 == 0: for k in range(2, i): if a(k) == 1 and a(i - k) == 1: ________________; ```
出处：
https://edu.csdn.net/practice/26912047
代码：
def a(h): if h < 2: return 0 x = 0 for j in range(2, h): if h % j == 0: x = 1 break if x == 0: return 1 n = int(input("输入任意大于10的偶数：")) prime_pairs = [] for i in range(n, n+1): h = 0 if i % 2 == 0: for k in range(2, i): if a(k) == 1 and a(i - k) == 1: prime_pairs.append((k, i - k)) print(prime_pairs)
输出：
输入任意大于10的偶数：100
[(3, 97), (11, 89), (17, 83), (29, 71), (41, 59), (47, 53), (53, 47), (59, 41), (71, 29), (83, 17), (89, 11), (97, 3)]
