👏👏👏又到了每周拼手速的时刻了！这周题目难度适中 冲！
第一题
5079.三个有序数组的交集
-
给出三个均为 严格递增排列 的整数数组 arr1，arr2 和 arr3。
-
返回一个由 仅 在这三个数组中 同时出现 的整数所构成的有序数组。
- 示例：
输入: arr1 = [1,2,3,4,5], arr2 = [1,2,5,7,9], arr3 = [1,3,4,5,8]
输出: [1,5]
解释: 只有 1 和 5 同时在这三个数组中出现.
思路
直接创建一个比较大的数组，遍历三遍，每次遍历到的数字都在相应位置上+1，如果数组中有值为3，说明三个数组中都有
时间复杂度O(n) 比较快
当然也可以直接循环一遍查看是否这个数都在两个数组中，但是这样就是O(nlogn)，会相对慢一些
Python solution
class Solution:
def arraysIntersection(self, arr1: List[int], arr2: List[int], arr3: List[int]) -> List[int]:
res = [0] * 2010
res1 = []
for i in arr1:
res[i]+=1
for i in arr2:
res[i]+=1
for i in arr3:
res[i]+=1
for j in range(len(res)):
if res[j] == 3:
res1.append(j)
return res1
第二题
5080. 查找两棵二叉搜索树之和
-
给出两棵二叉搜索树，请你从两棵树中各找出一个节点，使得这两个节点的值之和等于目标值 Target。
-
如果可以找到返回 True，否则返回 False。
- 示例 1：
输入：root1 = [2,1,4], root2 = [1,0,3], target = 5
输出：true
解释：2 加 3 和为 5 。
- 示例 2：
输入：root1 = [0,-10,10], root2 = [5,1,7,0,2], target = 18
输出：false
思路
暂时没有想到更好的了
首先，把两个二叉搜索树变成set，所使用到的函数就如上图t2s和_t2s所示。然后在两个set中进行类似twosum的操作
但是可以利用二叉搜索树的性质，即所有左子树的节点值都小于根节点，右子树的节点的值都大于根节点。但是这道题好像这样做就麻烦了，索性转成数组省事一点。
Python Solution
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def _t2s(self, root, s):
if root:
s.add(root.val)
self._t2s(root.left, s)
self._t2s(root.right, s)
def t2s(self, root):
s = set()
self._t2s(root,s)
return s
def twoSumBSTs(self, root1: TreeNode, root2: TreeNode, target: int) -> bool:
t1 = self.t2s(root1)
t2 = self.t2s(root2)
for i in t1:
if target - i in t2:
return True
return False
第三题
5081. 步进数
-
如果一个整数上的每一位数字与其相邻位上的数字的绝对差都是 1，那么这个数就是一个「步进数」。
-
例如， 321 是一个步进数，而 421 不是。
-
给你两个整数，low 和 high，请你找出在 [low, high] 范围内的所有步进数，并返回 排序后 的结果。
- 实例：
输入：low = 0, high = 21
输出：[0,1,2,3,4,5,6,7,8,9,10,12,21]
思路
找出从low到high的范围里满足进步数要求的数字。
使用一个queue来存储所有数字，具体实现就是从1开始，queue中添加10，01；对于2，添加12，21.....
并且要满足所有添加的数字小于high.
最后sorted一遍就可以了
不知道python里的queue咋用，还是用回老本行cpp吧。
Cpp Solution
class Solution {
public:
vector<int> countSteppingNumbers(int low, int high) {
vector<int> res;
queue<int> q;
int i,j;
for(i=1;i<10&&i<=high;i++)q.push(i);
if(!low)res.push_back(0);
while(!q.empty())
{
i=q.front();
q.pop();
if(i>=low) res.push_back(i);
j=i%10;
if(j&&i*10LL+j-1<=high)q.push(i*10+j-1);
if(j<9&&i*10LL+j+1<=high)q.push(i*10+j+1);
}
sort(res.begin(),res.end());
return res;
}
};
第四题
5099.验证回文字符串III
-
给出一个字符串 s 和一个整数 k，请你帮忙判断这个字符串是不是一个「K 回文」。
-
所谓「K 回文」：如果可以通过从字符串中删去最多 k 个字符将其转换为回文，那么这个字符串就是一个「K 回文」。
- 示例：
输入：s = "abcdeca", k = 2
输出：true
解释：删除字符 “b” 和 “e”。
思路
首先先把给定的字符串s逆序得到s2,把s与s2进行比较。
dp方程就是用来记录到了最后一位，s与s2有多少位能够相等，如果加上了k还能够大于字符串本身的长度，那么就是“K回文”。
用python写好像很方便 索性又换回python了
Python Solution
class Solution:
def isValidPalindrome(self, s: str, k: int) -> bool:
s2 = s[::-1]
n = len(s)
dp = [[0] * (n+1) for i in range(n+1)]
for i in range(1,n+1):
for j in range(1,n+1):
if s[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] +1
else:
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
if dp[-1][-1] +k >= n:
return True
return False
总结
每周的双周赛难度适中，比较适合新手打。不过这一周香港局势动荡，学校也停课了，在家呆着真窝心啊。