5079.三个有序数组的交集
解法1：map
思路：
因为是严格递增不存在一个数组中存在两个相同的数
用map存每个数字出现的次数，若该数字次数达到3次添加到结果数组中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
vector<int> arraysIntersection(vector<int>& arr1, vector<int>& arr2, vector<int>& arr3) {
map<int,int> m;
int n=arr1.size();
for(int i=0;i<n;i++)
{
m[arr1[i]]++;
m[arr2[i]]++;
m[arr3[i]]++;
}
vector<int> res;
for(map<int,int>::iterator ite=m.begin();ite!=m.end();ite++)
{
if(ite->second==3)
{
res.push_back(ite->first);
}
}
return res;
}
};
|
5080.查找两棵二叉搜索树之和
解法1：map
用map存第一棵树对应的target-root->val值，第二颗数查找这个值，若找到直接返回true
即转化为类似的两数之和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
map<int,int> m;
int tar;
public:
bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
tar=target;
midbfs(root1);
return midbfs2(root2);
}
void midbfs(TreeNode *root)
{
if(root!=NULL)
{
midbfs(root->left);
m[tar-root->val]++;
midbfs(root->right);
}
}
bool midbfs2(TreeNode *root)
{
if(root!=NULL)
{
if(m[root->val]!=0)
return true;
return midbfs2(root->left)||midbfs2(root->right);
}
return false;
}
};
|
5081.步进数
解法1：预处理+二分
找规律，发现除0-9这10个数，后面的步进数都是从1开始向后遍历加上一位和末位相差1的数，
例如根据1可以向后10，12，根据2可以向后添加21，23。根据这个规律我们就能快速找到所有小于high的步进数。
现在我们要找到从那个步进数开始是大于low的，这样我们可以采用二分查找，找到第一个大于low的或找到步进数的最后一位。
后处理判断找到的值是否大于low，
1.若小于表示在low-high内没有步进数
2.若大于将找到的步进数数组从left到结束添加到结果数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public:
vector<int> countSteppingNumbers(int low, int high) {
vector<int> res;
for(int i=0;i<=9;i++){res.push_back(i);}
int i=1,cur,k,temp;
while(1)
{
cur=res[i];
k=cur%10;
if(k-1>=0)
{
temp=cur*10+k-1;
if(temp>high)
break;
res.push_back(temp);
}
if(k+1<=9)
{
temp=cur*10+k+1;
if(temp>high)
break;
res.push_back(temp);
}
i++;
}
int left=0,right=res.size()-1;
while(left<right)
{
int mid=left+(right-left)/2;
if(res[mid]<low)
{
left=mid+1;
}
else right=mid;
}
vector<int> anb;
if(res[left]<low) return anb;
vector<int> ans(res.begin()+left,res.end());
return ans;
}
};
|
5099.验证回文字符串 III
解法1：动态规划
问题的本质就是找一个最长回文子序列。
思路：
先创建一个字符串t是s的翻转字符串。这样我们就可以将问题转为找s和t的最长公共子序列
若最长公共子序列长度>=n-k则符合要求。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
bool isValidPalindrome(string s, int k) {
int n=s.size();
string t=s;
reverse(t.begin(),t.end());
vector<vector<int>> dp(n+1,vector<int>(n+1,0));
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(s[i]==t[j]) dp[i+1][j+1]=dp[i][j]+1;
else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
}
}
return dp[n][n]>=n-k;
}
};
|