1. 将有序数组转换为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 按 严格递增 顺序排列
出处：
https://edu.csdn.net/practice/25855136
代码：
class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def levelOrder(self): if not self: return [] res, que = [], [self] while que: cur = que.pop(0) if cur: res.append(cur.val) que.append(cur.left) que.append(cur.right) else: res.append(None) while res[-1] is None: res.pop() return res class Solution: def sortedArrayToBST(self, nums): """ :type nums: List[int] :rtype: TreeNode """ if not nums: return None mid = len(nums) // 2 root = TreeNode(nums[mid]) root.left = self.sortedArrayToBST(nums[:mid]) root.right = self.sortedArrayToBST(nums[mid + 1:]) return root # %% s = Solution() nums = [-10,-3,0,5,9] print(s.sortedArrayToBST(nums).levelOrder())
输出：
[0, -3, 9, -10, None, 5]
2. 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
提示：
0 <= nums.length <= 200
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
出处：
https://edu.csdn.net/practice/25855137
代码：
class Solution(object): def fourSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[List[int]] """ nums.sort() results = [] N = len(nums) i = 0 while i < N-3: if i > 0 and nums[i] == nums[i-1]: i += 1 continue j = i+1 while j < N-2: if j > i+1 and nums[j] == nums[j-1]: j += 1 continue k = j+1 l = N-1 while k < l: if k > j+1 and nums[k] == nums[k-1]: k += 1 continue while k < l and (target - nums[i] - nums[j] - nums[k] - nums[l]) < 0: l -= 1 if k >= l: break if target == nums[i] + nums[j] + nums[k] + nums[l]: results.append([ nums[i], nums[j], nums[k], nums[l] ]) k += 1 j += 1 i += 1 return results # %% s = Solution() print(s.fourSum(nums = [1,0,-1,0,-2,2], target = 0))
输出：
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
3. 排序数组查找元素的首末位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9
出处：
https://edu.csdn.net/practice/25855138
代码：
class Solution(object): def searchRange(self, nums, target): length = len(nums) if length == 0: return [-1, -1] min = 0 max = length - 1 while min <= max: pos = (min + max) / 2 pos = int(pos) if nums[pos] > target: max = pos - 1 elif nums[pos] < target: min = pos + 1 else: for i in range(min, max + 1): if nums[i] == target: if min < i and nums[min] != nums[i]: min = i max = i return [min, max] return [-1, -1] # %% s = Solution() print(s.searchRange(nums = [5,7,7,8,8,10], target = 8))
输出：
[3, 4]
