每日一练 — 2022.01.13

一，跳跃游戏 II

1，程序简介

• 给定一个非负整数数组，你最初位于数组的第一个位置。

• 数组中的每个元素代表你在该位置可以跳跃的最大长度。

• 你的目标是使用最少的跳跃次数到达数组的最后一个位置。

示例:

• 输入: [2,3,1,1,4]
• 输出: 2
• 解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

说明:

• 假设你总是可以到达数组的最后一个位置。

2，程序代码

# -*- coding: utf-8 -*-
"""
Created on Thu Jan 13 21:38:07 2022
Function: 跳跃游戏 II
@author: 小梁aixj
"""
class Solution:def jump(self, nums):if len(nums) <= 1:return 0end = 0 + nums[0]start = 0step = 1maxDis = 0 + nums[0]while end < len(nums) - 1:for i in range(start + 1, end + 1):maxDis = max(maxDis, nums[i] + i)start = endend = maxDisstep += 1return step
# %%
s = Solution()
print(s.jump(nums = [2,3,0,1,4]))

3，运行结果

二，恢复二叉搜索树

1，程序简介

• 给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

进阶：

1. 使用 O(n) 空间复杂度的解法很容易实现。
2. 你能想出一个只使用常数空间的解决方案吗？

示例 1：

• 输入：root = [1,3,null,null,2]
• 输出：[3,1,null,null,2]
• 解释：3 不能是 1 左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

• 输入：root = [3,1,4,null,null,2]
• 输出：[2,1,4,null,null,3]
• 解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

• 树上节点的数目在范围 [2, 1000] 内
• $-2^{31}<=Node.val<=2^{31}-1$

2，程序代码

# -*- coding: utf-8 -*-
"""
Created on Thu Jan 13 21:38:36 2022
Function: 恢复二叉搜索树
@author: 小梁aixj
"""
import sys
class TreeNode(object):def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef to_list(self, count):queue = []queue.append(self)result = []while len(queue) > 0:if count == 0:breaknode = queue.pop(0)if node is None:result.append('null')else:count -= 1result.append(node.val)queue.append(node.left)queue.append(node.right)return result
class List2Tree(object):def __init__(self, nums: list):self.nums = numsself.queue = []if len(nums) == 1:self.root = TreeNode(self.nums.pop(0))else:a = self.nums.pop(0)b = self.nums.pop(0)c = self.nums.pop(0)self.root = TreeNode(a)if b is not None:self.root.left = TreeNode(b)else:self.root.left = bif c is not None:self.root.right = TreeNode(c)else:self.root.right = cself.queue.append(self.root.left)self.queue.append(self.root.right)def convert(self):while len(self.nums) > 0 and len(self.queue) > 0:node = self.queue.pop(0)if node is not None:num = self.nums.pop(0)if num is not None:node.left = TreeNode(num)else:node.left = numif len(self.nums) > 0:num = self.nums.pop(0)else:num = Noneif num is not None:node.right = TreeNode(num)else:node.right = numself.queue.append(node.left)self.queue.append(node.right)return self.root
class Solution(object):def __init__(self):self.first = self.second = Noneself.pre = TreeNode(-sys.maxsize - 1)def recoverTree(self, root):length = len(root)root = List2Tree(root).convert()self.traverse(root)self.first.val, self.second.val = self.second.val, self.first.valreturn root.to_list(length)def traverse(self, root):if root is None:returnself.traverse(root.left)if self.pre.val >= root.val:if self.first is None:self.first = self.preif self.first is not None:self.second = rootself.pre = rootself.traverse(root.right)
# %%
s = Solution()
print(s.recoverTree(root=[1, 3, None, None, 2]))

3，运行结果

三，四数之和

1，程序简介

• 给定一个包含 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$

2，程序代码

# -*- coding: utf-8 -*-
"""
Created on Thu Jan 13 21:38:56 2022
Function: 四数之和
@author: 小梁aixj
"""
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 = 0while i < N-3:if i > 0 and nums[i] == nums[i-1]:i += 1continuej = i+1while j < N-2:if j > i+1 and nums[j] == nums[j-1]:j += 1continuek = j+1l = N-1while k < l:if k > j+1 and nums[k] == nums[k-1]:k += 1continuewhile k < l and (target - nums[i] - nums[j] - nums[k] - nums[l]) < 0:l -= 1if k >= l:breakif target == nums[i] + nums[j] + nums[k] + nums[l]:results.append([nums[i],nums[j],nums[k],nums[l]])k += 1j += 1i += 1return results
# %%
s = Solution()
print(s.fourSum(nums = [1,0,-1,0,-2,2], target = 0))

3，运行结果