1. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。
出处：
https://edu.csdn.net/practice/23497451
代码：
from typing import List class Solution: def letterCombinations(self, digits: str) -> List[str]: letters = [ [], [], ['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i'], ['j', 'k', 'l'], ['m', 'n', 'o'], ['p', 'q', 'r', 's'], ['t', 'u', 'v'], ['w', 'x', 'y', 'z'], ] combinations = [] i = 0 for d in digits: letter = letters[int(d)] if i == 0: for l in letter: combinations.append([l]) else: added = [] for c in combinations: j = 0 origin_c = [] origin_c += c for l in letter: if j == 0: c.append(l) else: new_c = [] new_c += origin_c new_c.append(l) added.append(new_c) j += 1 combinations += added i += 1 output = [] for c in combinations: output.append(''.join(c)) return output # %% s = Solution() print(s.letterCombinations(digits = "23")) print(s.letterCombinations(digits = "")) print(s.letterCombinations(digits = "2"))
输出：
['ad', 'bd', 'cd', 'ae', 'af', 'be', 'bf', 'ce', 'cf']
[]
['a', 'b', 'c']
2. 矩形区域不超过 K 的最大数值和
给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。
题目数据保证总会存在一个数值和不超过 k 的矩形区域。
示例 1：
输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
示例 2：
输入：matrix = [[2,2,-1]], k = 3
输出：3
提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-100 <= matrix[i][j] <= 100
-10^5 <= k <= 10^5
进阶：如果行数远大于列数，该如何设计解决方案？
出处：
https://edu.csdn.net/practice/23497450
代码：
from typing import List import bisect class Solution: def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int: m = len(matrix) Row, Col = len(matrix), len(matrix[0]) res = float("-inf") for ru in range(Row): col_sum = [0 for _ in range(Col)] for rd in range(ru, Row): for c in range(Col): if matrix[rd][c] == k: return k col_sum[c] += matrix[rd][c] presum = [0] cur_sum = 0 for colsum in col_sum: cur_sum += colsum idx = bisect.bisect_left(presum, cur_sum - k) if idx < len(presum): res = max(res, cur_sum - presum[idx]) if res == k: return k bisect.insort(presum, cur_sum) return res # %% s = Solution() print(s.maxSumSubmatrix(matrix = [[1,0,1],[0,-2,3]], k = 2)) print(s.maxSumSubmatrix(matrix = [[2,2,-1]], k = 3))
输出：
2
3
3. 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定的有序链表： [-10, -3, 0, 5, 9],一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
出处：
https://edu.csdn.net/practice/23497449
代码：
class ListNode: def __init__(self, val=0): self.val = val self.next = None class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: arr = [] cur = head while cur: arr.append(cur.val) cur = cur.next return self.dfs(arr) def dfs(self, arr): if not arr: return m = len(arr) // 2 root = TreeNode(arr[m]) root.left = self.dfs(arr[:m]) root.right = self.dfs(arr[m + 1 :]) return root def list2ListNode(lst: list) -> ListNode: cur = res = ListNode() for i in lst: cur.next = ListNode(i) cur = cur.next return res.next def levelOrderList(root) -> list: if not root: return [] queue = [root] res = [] while queue: level = [] for _ in range(len(queue)): node = queue.pop(0) if node: level.append(node.val) queue.append(node.left) queue.append(node.right) else: level.append(None) res.extend(level) while res[-1]==None: res.pop() return res if __name__ == '__main__': s = Solution() nums = [-10, -3, 0, 5, 9] head = list2ListNode(nums) root = s.sortedListToBST(head) print(levelOrderList(root))
输出：
[0, -3, 9, -10, None, 5]
