Tiimmi的学习日志 3
2021.11.5 打卡
力扣每日一题 2021.11.5
1218. 最长定差子序列【中等】
给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。
子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。
示例 1：
输入：arr = [1,2,3,4], difference = 1 输出：4 解释：最长的等差子序列是 [1,2,3,4]。示例 2：
输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2 输出：4 解释：最长的等差子序列是 [7,5,3,1]。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 分析：动态规划
我们从头遍历数组，遇到一个数 x，判断 x-d 在不在数组里面即可知道，能不能形成以 x 为结尾的等差数组，同时，我们记录下来以 x 结尾的等差数组的长度，这样，在后续的遍历过程中，我们就可以使用得上这个长度了。
我们来举个例子，假设给定数组为 [1,5,3,6,5,7]，等差 d=2，辅助数组为 dp，求解的过程如下：
- 遍历到 1，发现 1-2=-1 不在 dp 数组，记录 dp[1] = 1，表示以 1 结尾的等差数列只有 1 个数；
- 遍历到 5，发现 5-2=3 不在 dp 数组，记录 dp[5]=1；
- 遍历到 3，发现 3-2=1 在 dp 数组且以 1 结尾的等差数列长度为 1，所以，记录 dp[3]=dp[3-2]+1=2，表示以 3 结尾的等差数列长度为 2；
- 遍历到 6，发现 6-2=4 不在 dp 数组，记录 dp[6]=1；
- 遍历到 5，发现 5-2=3 在 dp 数组，记录 dp[5]=dp[5-2]+1=3；
- 遍历到 7，发现 7-2=5 在 dp 数组，记录 dp[7]=dp[7-2]+1=4；
- 取 dp 数组中的最大值，即 4，所以，最长等差子序列的长度为 4。
这其实就是动态规划的递推过程，所以，我们可以定义动态规划如下：
- 状态定义：dp[x] 表示以 x 结尾的最长等差子序列的长度；
- 状态转移：dp[x]=dp[x-d]+1；
- 初始值：无；
- 返回值：max（dp）
代码：
class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
dp = defaultdict(int)
for v in arr:
dp[v] = dp[v - difference] + 1
return max(dp.values())
备注：defaultdict()：作用是在于，当字典里的key不存在但被查找时，返回的不是keyError而是一个默认值，默认值根据参数类型，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0
2021.11.6 打卡
力扣每日一题 2021.11.6
268. 丢失的数字【简单】
给定一个包含
[0, n]中n个数的数组nums，找出[0, n]这个范围内没有出现在数组中的那个数。示例 1：
输入：nums = [3,0,1] 输出：2 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字， 因为它没有出现在 nums 中。示例 2：
输入：nums = [0] 输出：1 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字， 因为它没有出现在 nums 中。。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
- 分析：位运算、排序
排序：
- 将数组排序，判断
num[i] != i,若找不到这个i，返回len(nums)即可 - 代码：
class Solution:
def missingNumber(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums)):
if nums[i] != i:
return i
return len(nums)
位运算：
-
res = 0先与nums的0 - length异或一次，再与num[i]异或一次，最终res就是缺失的数字 - 代码：
class Solution:
def missingNumber(self, nums: List[int]) -> int:
res = 0
for i in range(len(nums) + 1)：
res ^= i
for n in nums:
res ^= n
return res