1. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：
链表数组如下：[1->4->5, 1->3->4, 2->6]
将它们合并到一个有序链表中得到1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
出处：
https://edu.csdn.net/practice/23630877
代码：
class ListNode(object): def __init__(self, x): self.val = x self.next = None class LinkList: def __init__(self): self.head = None def initList(self, data): self.head = ListNode(data[0]) r = self.head p = self.head for i in data[1:]: node = ListNode(i) p.next = node p = p.next return r def convert_list(self, head): ret = [] if head == None: return node = head while node != None: ret.append(node.val) node = node.next return ret class Solution(object): def mergeKLists(self, lists): if lists is None: return None elif len(lists) == 0: return None return self.mergeK(lists, 0, len(lists) - 1) def mergeK(self, lists, low, high): if low == high: return lists[int(low)] elif low + 1 == high: return self.mergeTwolists(lists[int(low)], lists[int(high)]) mid = (low + high) / 2 return self.mergeTwolists(self.mergeK(lists, low, mid), self.mergeK(lists, mid + 1, high)) def mergeTwolists(self, l1, l2): l = LinkList() if type(l1) == list: l1 = l.initList(l1) if type(l2) == list: l2 = l.initList(l2) if l1 is None: return l2 if l2 is None: return l1 head = curr = ListNode(-1) while l1 is not None and l2 is not None: if l1.val <= l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next if l1 is not None: curr.next = l1 if l2 is not None: curr.next = l2 return head.next # %% l = LinkList() list1 = [[1, 4, 5], [1, 3, 4], [2, 6]] for i,lst in enumerate(list1): list1[i] = l.initList(lst) s = Solution() print(l.convert_list(s.mergeKLists(list1)))
输出：
[1, 1, 2, 3, 4, 4, 5, 6]
2. 有效的数独
请你判断一个 9x9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
示例 1：
输入：
board = [["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
输出：true
示例 2：
输入：
board = [["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 '.'
出处：
https://edu.csdn.net/practice/23630878
代码：
from typing import List class Solution: def isValidSudoku(self, board): """ :type board: List[List[str]] :rtype: bool """ raw = [{},{},{},{},{},{},{},{},{}] col = [{},{},{},{},{},{},{},{},{}] cell = [{},{},{},{},{},{},{},{},{}] for i in range(9): for j in range(9): num = (3*(i//3) + j//3) temp = board[i][j] if temp != ".": if temp not in raw[i] and temp not in col[j] and temp not in cell[num]: raw [i][temp] = 1 col [j][temp] = 1 cell [num][temp] =1 else: return False return True # %% s = Solution() board = [["5","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] print(s.isValidSudoku(board)) board = [["8","3",".",".","7",".",".",".","."], ["6",".",".","1","9","5",".",".","."], [".","9","8",".",".",".",".","6","."], ["8",".",".",".","6",".",".",".","3"], ["4",".",".","8",".","3",".",".","1"], ["7",".",".",".","2",".",".",".","6"], [".","6",".",".",".",".","2","8","."], [".",".",".","4","1","9",".",".","5"], [".",".",".",".","8",".",".","7","9"]] print(s.isValidSudoku(board))
输出：
True
Fasle
3. 求根节点到叶节点数字之和
给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：
例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25
示例 2：
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5
代表数字 495
从根到叶子节点路径 4->9->1
代表数字 491
从根到叶子节点路径 4->0
代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026
提示：
树中节点的数目在范围 [1, 1000] 内
0 <= Node.val <= 9
树的深度不超过 10
出处：
https://edu.csdn.net/practice/23630879
代码：
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None class Solution: def sumNumbers(self, root: TreeNode) -> int: def dfs(root: TreeNode, sumNumber: int) -> int: if not root: return 0 tmpsum = sumNumber * 10 + root.val if not root.left and not root.right: return tmpsum else: return dfs(root.left, tmpsum) + dfs(root.right, tmpsum) return dfs(root, 0) def listToTree(lst: list) -> TreeNode: 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() nums = [1,2,3] root = listToTree(nums) print(s.sumNumbers(root)) nums = [4,9,0,5,1] root = listToTree(nums) print(s.sumNumbers(root))
输出：
25
1026
