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]
🌟 每日一练刷题专栏 🌟
✨持续,努力奋斗做强刷题搬运工!
👍 点赞,你的认可是我坚持的动力!
🌟 收藏,你的青睐是我努力的方向!
✎ 评论,你的意见是我进步的财富!
☸ 主页:https://hannyang.blog.csdn.net/