当前位置:网站首页>力扣第 305 场周赛复盘
力扣第 305 场周赛复盘
2022-08-09 06:39:00 【奋斗吧!骚年!】
这里写目录标题
1.算术三元组的数目
题目描述
代码分析
我的解题思路就是模拟,两个for循环(因为数据范围小,比较快就做出来了)
看题解,还有哈希表和三指针。
哈希表:先用哈希表保存所有值,遍历所有值的时候,看是否有nums[i] -diff和nums[i]+diff即可,真的确实简单。
三指针:利用三个指针遍历三个点,因为是严格递增,所以当找到遍历下个结点时,其余两个指针也是在原本基础上加,这样对于空间是O(1),注意需要判断指针是否在范围内。
AC代码
class Solution {
public:
int vis[205];
int arithmeticTriplets(vector<int>& nums, int diff) {
memset(vis,0,sizeof(vis));
int res=0;
int size=nums.size();
for(int i=0;i<size;i++)
{
int pre=nums[i];
int mid=1;
for(int j=i+1;j<size;j++)
{
if(vis[j])continue;
if(nums[j]-pre>diff)break;
else if(nums[j]-pre==diff)
{
pre=nums[j];
mid++;
vis[j]=1;
}
}
if(mid>=3)res+=mid-2;
}
return res;
}
};
// 哈希表
class Solution {
public:
int arithmeticTriplets(vector<int>& nums, int diff) {
unordered_map<int,int> m;
int res=0;
for(auto it:nums)m[it]++;
for(auto it:nums)
if(m[it-diff]&&m[it+diff])res++;
return res;
}
};
// 三指针
class Solution {
public:
int arithmeticTriplets(vector<int>& nums, int diff) {
int i=0,j=1,k=2,res=0;
int size=nums.size();
for(i=0;i<size;i++)
{
while(j<size&&nums[j]-nums[i]<diff)j++;
if(j==size||nums[j]-nums[i]!=diff)continue;
while(k<size&&nums[k]-nums[j]<diff)k++;
if(k<size&&nums[j]-nums[i]==diff&&nums[k]-nums[j]==diff)res++;
}
return res;
}
};
2.受限条件下可到达节点的数目
题目描述
代码分析
这道题其实就是考图的遍历,用BFS和DFS都可以,我用的BFS。
我们用数组保存结点是否访问,那么受限的点我们标记已经访问即可
AC代码
class Solution {
public:
unordered_map<int,vector<int>> m;
int vis[100010];
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
memset(vis,0,sizeof(vis));
// 邻接表存图
for(auto it:edges)
{
int a=it[0],b=it[1];
m[a].push_back(b);
m[b].push_back(a);
}
// 将不能到达的点置为已访问
for(auto it:restricted)vis[it]=1;
queue<int> q;
q.push(0);
vis[0]=1;
while(!q.empty())
{
int s=q.front();
for(auto it:m[s])
{
if(!vis[it])q.push(it);
vis[it]=1;
}
q.pop();
}
int res=0;
for(int i=0;i<n;i++)if(vis[i])res++;
return res-restricted.size();
}
};
3.检查数组是否存在有效划分
题目描述
代码分析
这道题使用动态规划,dp[i] 表示从起点到当前点是否可以有效划分
这道题只要想到走阶梯就可以了,我们可以走两步或者走三步,问是否能到达终点
那么根据题目给出的三个条件就可以写出三个状态转移方程(解题下标是从下标0开始,这里为了方便从1开始)
1.dp[i-2]&&nums[i]==nums[i-1]
2.dp[i-3]&&nums[i]-nums[i-1]==1&&nums[i-1]-nums[i-2]==1
3.dp[i-3]&&nums[i]==nums[i-1]&&nums[i-1]==nums[i-2]
意思就是如果在红色箭头处可以划分为true,那么当前黑色箭头处也就为true
AC代码
class Solution {
public:
int dp[100010];
bool validPartition(vector<int>& nums) {
memset(dp,0,sizeof(dp));
dp[0]=1;
for(int i=1;i<nums.size();i++)
{
if(dp[i-1]&&nums[i]==nums[i-1])dp[i+1]=1;
if(i>1)
{
if(dp[i-2]&&nums[i]-nums[i-1]==1&&nums[i-1]-nums[i-2]==1)dp[i+1]=1;
if(dp[i-2]&&nums[i]==nums[i-1]&&nums[i-1]==nums[i-2])dp[i+1]=1;
}
}
if(dp[nums.size()])return true;
else return false;
}
};
4.最长理想子序列
题目描述
代码分析
使用哈希表对DP进行空间优化
哈希表保存以某个字母为结尾的最大值,当前最大值就遍历哈希表中范围的字母即可
AC代码
class Solution {
public:
unordered_map<int,int> m;
int longestIdealString(string s, int k) {
int res=1;
m[s[0]]=1;
for(int i=1;i<s.size();i++)
{
// 求出当前字母绝对值差的范围
int minc=s[i]-k,maxc=s[i]+k;
if(minc<'a')minc='a';
if(maxc>'z')maxc='z';
// 用中间
int mid=1;
for(int j=minc;j<=maxc;j++)
{
mid = max(mid,m[j]+1);
}
m[s[i]]=mid;
res=max(res,m[s[i]]);
}
return res;
}
};
总结感想
这次其实总体来说都不难,但是我在第三题想了很久没想出来(其实如果想到走阶梯那么很快就想出来了),动态规划的题不能细想,太往里面想容易出不来。其他的题虽然做出来了,但是还是要学习大佬们更简单的做法。
多总结反思,多刷题!!!
边栏推荐
猜你喜欢
一道很简答但是没答对的SQL题
Import the pycharm environment package into another environment
图论,二叉树,dfs,bfs,dp,最短路专题
中英文说明书丨TRC 交替醇(Catalogue NumberA575760)
The solution that does not work and does not take effect after VScode installs ESlint
C语言实现顺序栈和链队列
db.sqlite3没有“as Data Source“解决方法
缓存技术使用
安装flask
Xilinx Zynq ZynqMP DNA
随机推荐
Redis 2 - 高级
io.lettuce.core。RedisCommandTimeoutException命令超时
网络学习总结
ByteDance Written Exam 2020 (Douyin E-commerce)
电学知识的疑问
longest substring without repeating characters
物理层课后作业
Altium designer software commonly used the most complete package library, including schematic library, PCB library and 3D model library
pycharm环境包导入到另外一个环境
db.sqlite3 has no "as Data Source" workaround
The working principle of the transformer (illustration, schematic explanation, understand at a glance)
语句加锁分析
mmdetection源码解析--ResNet18
The division principle summary within the collection
workbench 数据导出
常用Oracle命令
uniapp实现防抖搜索
如何操作数据库
中英文说明书丨TRC D-阿卓糖(D-Altrose)
P7阿里面试题2020.07 之滑动窗算法(阿里云面试)