目录
题目:
示例:
分析:
代码:
题目:
示例:
分析:
这道题难在阅读理解,题目看得我匪夷所思,错了好多个测试用例才明白题目说的是什么。
我简单翻译一下就是寻找1和-1之间0最多的数量,1和-1之间只能有0。
我们可以套两层循环,第一层for循环去寻找1,如果找到了1,那么我们开始在当前下标往左右两边寻找最近的-1,并且统计0的数量,需要注意的是如果先碰到了1,那么表示我们无法落脚,也就不能更新答案,因为题目说的我们只能在-1的地方落脚,并且1到-1之间只能有0。
在结束往右寻找的时候,我们可以把往右寻找的下标赋值给第一层循环的下标,因为我们结束往右寻找的时候,下标所在的位置要么是1要么是-1,赋值给第一层循环可以少遍历几次,不过题目中给的数据量比较小,所以这个小优化是可有可无的。
具体操作可以参考下面的代码和动图。
代码:
class Solution {
public:int captureForts(vector<int>& forts) {int res=0;int n=forts.size();for(int i=0;i<n;i++){if(forts[i]==1){ //遇到了自己的城堡int t=0,index=i-1;while(index>=0){ //去寻找左边能摧毁的敌人城堡数量if(forts[index]==1) break; //先遇到自己的城堡则表示左边没有落脚点if(forts[index]==-1){ //当遇到空地就结束寻找并更新答案res=max(res,t);break;}t++;index--;}t=0,index=i+1;while(index<n){ //去寻找右边能摧毁的敌人城堡数量if(forts[index]==1) break;if(forts[index]==-1){res=max(res,t);break;}t++;index++;}//i=index-1; //小小优化一下,可有可无}}return res;}
};