1. 特殊数组的特征值
思路
懒得思考，直接暴力
代码
class Solution {
public:
int specialArray(vector
<int>& nums
) {
for(int i
=1;i
<1010;i
++)
{
int cnt
= 0;
for(int j
=0;j
<nums
.size();j
++)
{
if(nums
[j
]>=i
)
cnt
++;
}
if(cnt
==i
)
return cnt
;
}
return -1;
}
};
2. 奇偶树
思路
层序遍历（bfs）。设置一些必要的标记，遍历一遍，判断一下就行了。
代码
typedef struct P
{
TreeNode
* node
;
int level
;
}P
;
class Solution {
public:
bool isEvenOddTree(TreeNode
* root
) {
queue
<P
> que
;
que
.push({root
,0});
int prevlevel
= -1;
int lastval
= 0;
while(que
.size())
{
TreeNode
* nex
= que
.front().node
;
int level
= que
.front().level
;
que
.pop();
if(level
!=prevlevel
)
{
if(level
%2==1&&nex
->val
%2==1)
return false;
if(level
%2==0&&nex
->val
%2==0)
return false;
prevlevel
= level
;
lastval
= nex
->val
;
}
else{
if(level
%2==1)
{
if(nex
->val
%2==1||nex
->val
>=lastval
)
return false;
lastval
= nex
->val
;
}
else{
if(nex
->val
%2==0||nex
->val
<=lastval
)
return false;
lastval
= nex
->val
;
}
}
if(nex
->left
)
que
.push({nex
->left
,level
+1});
if(nex
->right
)
que
.push({nex
->right
,level
+1});
}
return true;
}
};
3. 可见点的最大数目
思路
是个几何题，比赛时WA了8次过了前103个点（共120）。需要注意的细节很多。代码参考https://leetcode-cn.com/problems/maximum-number-of-visible-points/solution/atan2jiu-wan-shi-liao-by-time-limit/
代码
const double PI
= 3.1415926;
class Solution {
public:
int visiblePoints(vector
<vector
<int>>& points
, int angle
, vector
<int>& location
) {
int ans
= 0;
vector
<double> angles
;
int x
= location
[0];
int y
= location
[1];
for(auto point
: points
)
{
int dx
= point
[0] - x
;
int dy
= point
[1] - y
;
if(dx
==0&&dy
==0)
ans
++;
else
angles
.emplace_back(atan2(dy
,dx
));
}
sort(angles
.begin(),angles
.end());
int n
= angles
.size();
for(int i
=0;i
<n
;i
++)
angles
.emplace_back(angles
[i
]+2*PI
);
int res
= 0;
double angg
= angle
*PI
/180;
for(int i
=0,j
=0;i
<angles
.size();i
++)
{
while(j
<angles
.size()&&(fabs(angles
[j
]-angles
[i
]-angg
)<1e-8||angles
[j
]-angles
[i
]<angg
))
j
++;
res
= max(j
-i
+ans
,res
);
}
return res
;
}
};
