当前位置：首页 > news >正文

2024/4/9

news 来源：原创 2024/5/16 19:51:48

概况

C++常用vector<vector<int> res(m,vector<int>(n,0));来初始化一个m*n且内部初始值为0的二维数组

P8665 [2018 省 A] 航班时间

本题需要读取比较复杂格式的数据以及，含前导0的数据，此时应当使用scanf，以及不能关闭同步流,全部化成秒防止出现复杂的借位问题,%02d表示读两位若前面有0则也读入,输出则是前面补0

#include <bits/stdc++.h>
using namespace std;int get(){int h1,m1,s1,h2,m2,s2,day=0;scanf("%02d:%02d:%02d %02d:%02d:%02d",&h1,&m1,&s1,&h2,&m2,&s2);if(getchar()==' '){//没有读到空格就是换行符scanf("(+%d)",&day);}return 24*3600*day+h2*3600+m2*60+s2-(h1*3600+m1*60+s1);
}int main(){int n;scanf("%d",&n);while(n--){int sec=(get()+get())/2;printf("%02d:%02d:%02d\n",sec/3600,sec%3600/60,sec%60);}return 0;
}

P8681 [2019 省 AB] 完全二叉树的权值

经典BFS题，将当前层内结点权值之和相加，并更新最大权值的层数即可

#include <bits/stdc++.h>
using namespace std;
int n,ans=1;
const int N=1e5+7;
int a[N];void solve(){queue<int> q;int w=a[1],dep=0;q.push(1);while(q.size()){int t=q.size(),tmp=0;//tmp存当前层的权重dep++;//深度加一for(int i=0;i<t;i++){int d=q.front();//取出子节点q.pop();tmp+=a[d];if(2*d<=n) q.push(2*d);if(2*d+1<=n) q.push(2*d+1);}if(tmp>w) w=tmp,ans=dep;//更新}
}int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];solve();cout<<ans;
}

leetcode 746.使用最小花费爬楼梯

本题明确最顶层是由下一层和下二层中花费最小的花费而来，同时站在一号台阶和零号台阶没有花费，所以初始化为0，更据状态转移方程从前往后循环即可

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(1001,0);//表示第i层阶梯的最低花费dp[0]=0;dp[1]=0;//两个台阶不用花费for(int i=2;i<=cost.size();i++){//循环size到最顶层dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}return dp[cost.size()];}
};

leetcode 62.不同路径

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m,vector<int>(n,0));dp[0][0]=1;for(int i=0;i<m;i++)for(int j=0;j<n;j++){if(i-1>=0) dp[i][j]+=dp[i-1][j];if(j-1>=0) dp[i][j]+=dp[i][j-1];}return dp[m-1][n-1];}
};

这种写法不太规范，一般都是先初始化dp[i][0]和dp[0][j]为1也就是刚开始右边和下面一条路径都是一种方案，接着遍历1到m和1到n dp[i][j]=dp[i-1][j]+dp[i][j-1]即可

leetcode 63.不同路径II

本题初始化时要特判条件可能起点就有障碍物，因此起点值的初始化要进行特判

其他只需在递推时判断当前点是否是障碍物即可

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m=obstacleGrid.size(),n=obstacleGrid[0].size();vector<vector<int>> dp(m,vector<int>(n,0));if(!obstacleGrid[0][0])dp[0][0]=1;else dp[0][0]=0;for(int i=1;i<m;i++) if(!obstacleGrid[i][0]) dp[i][0]=dp[i-1][0];for(int i=1;i<n;i++) if(!obstacleGrid[0][i]) dp[0][i]=dp[0][i-1];//初始化for(int i=1;i<m;i++)for(int j=1;j<n;j++){if(!obstacleGrid[i][j]) dp[i][j]=dp[i-1][j]+dp[i][j-1];}return dp[m-1][n-1];}
};