网站建设规划范文,哪些做网站的公司,wordpress文章字号,阜新小程序 阜新网站建设开发题目总思路#xff1a;
要判断是否对称#xff0c;只需要判断两个放法得到的图形是否相同#xff08;竖着放#xff0c;横着放#xff09;#xff0c;这两个放法有个很重要的特性#xff1a;就是数组中大于1的个数#xff0c;就是横着放时#xff0c;第一竖排的高度。…题目总思路
要判断是否对称只需要判断两个放法得到的图形是否相同竖着放横着放这两个放法有个很重要的特性就是数组中大于1的个数就是横着放时第一竖排的高度。那么我们只需要比较两个放法得到的图形高度是否全部一致。 方法一 :记忆性标记
1.思路
因为题目输入是一个从大到小的序列那么假如一个元素大于5那么他也一定大于4利用这个特性我们用一个变量 idx记录上一次遍历到哪里下一此接着遍历将个数累加即可。
2.代码
#include iostream
#includecstring
#includealgorithm
#includevector
using namespace std;const int N2e510;int h[N] ;
void Solved(){int n;cinn;for(int i1;in;i) cinh[i];//cnt统计符合条件的元素数量int idx1, cnt0;bool flagtrue;for(int in;i1;i--){while(idxnh[idx]i){idx,cnt;}if(cnt!h[i]) {flagfalse;break;}}if(flag) coutYESendl;else coutNOendl;}int main()
{int t;cint;while(t--) {Solved();}return 0;
}
二 方法二 :
1.思路可以利用差分思想因为一个程度为 x的木块他横着放能为这个图形的 [1,n]这个范围每一个高度增加 1。
2.代码
#include iostream
#includecstring
#includealgorithm
#includevector
using namespace std;const int N2e510;
typedef long long ll;
int h[N] ,temp[N];
void Solved(){memset(temp,0,sizeof temp);int n;cinn;for(int i1;in;i) cinh[i];//注意特判不然会数组越界。if(h[1]n){coutNOendl;return;}//差分思想for(int i1;in;i){temp[1];temp[h[i]1]--;}//差分数组求前缀和for(int i1;in;i) temp[i]temp[i-1];bool flagtrue;for(int i1;in;i){if(temp[i]!h[i]){flagfalse;break;}}if(flag) coutYESendl;else coutNOendl;
}int main()
{int t;cint;while(t--) {Solved();}return 0;
}
三方法三·二分找大于某个长度的元素数量。
代码
#include iostream
#includecstring
#includealgorithm
#includevector
using namespace std;const int N2e510,M1e910;
typedef long long ll;
int h[N] ,temp[N];
void Solved(){memset(temp,0,sizeof temp);int n;cinn;for(int i1;in;i) cinh[i];bool flagtrue;for(int in;i1;i--){int l1,rn;while(lr){int mid(lr1)1;if(h[mid]i) lmid;else rmid-1;}if(l!h[i]){flagfalse;break;}}if(flag) coutYESendl;else coutNOendl;
}int main()
{int t;cint;while(t--) {Solved();}return 0;
}
