class Solution {
public:
int captureForts(vector<int>& forts) {
}
};
6273. 最多可以摧毁的敌人城堡数目
给你一个长度为 n ，下标从 0 开始的整数数组 forts ，表示一些城堡。forts[i] 可以是 -1 ，0 或者 1 ，其中：
-1 表示第 i 个位置 没有 城堡。0 表示第 i 个位置有一个 敌人 的城堡。1 表示第 i 个位置有一个你控制的城堡。现在，你需要决定，将你的军队从某个你控制的城堡位置 i 移动到一个空的位置 j ，满足：
0 <= i, j <= n - 1min(i,j) < k < max(i,j) 的 k ，都满足 forts[k] == 0 。当军队移动时，所有途中经过的敌人城堡都会被 摧毁 。
请你返回 最多 可以摧毁的敌人城堡数目。如果 无法 移动你的军队，或者没有你控制的城堡，请返回 0 。
示例 1：
输入：forts = [1,0,0,-1,0,0,0,0,1] 输出：4 解释： - 将军队从位置 0 移动到位置 3 ，摧毁 2 个敌人城堡，位置分别在 1 和 2 。 - 将军队从位置 8 移动到位置 3 ，摧毁 4 个敌人城堡。 4 是最多可以摧毁的敌人城堡数目，所以我们返回 4 。
示例 2：
输入：forts = [0,0,1,-1] 输出：0 解释：由于无法摧毁敌人的城堡，所以返回 0 。
提示：
1 <= forts.length <= 1000-1 <= forts[i] <= 1原站题解
php 解法, 执行用时: 4 ms, 内存消耗: 19 MB, 提交时间: 2023-09-02 11:20:23
class Solution {
/**
* @param Integer[] $forts
* @return Integer
*/
function captureForts($forts) {
$j = -1;
$n = count($forts);
for ( $i = 0; $i < $n; $i++ ) {
if ( $forts[$i] != -1 ) {
$j = $i;
break;
}
}
if ( $j == -1 ) return 0;
$res = 0;
for ( $i = 0; $i < $n; $i++ ) {
if ( abs($forts[$i]-$forts[$j]) == 2 ) {
$res = max($res, $i-$j-1);
}
if ( $forts[$i] != 0 ) {
$j = $i;
}
}
return $res;
}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 15 MB, 提交时间: 2022-12-25 11:50:29
'''
把子数组1和-1之间的元素看成一对闭区间, 问题变成求解区间里0的最大数量
遍历数组遇到1或-1更新指针j
'''
class Solution:
def captureForts(self, forts: List[int]) -> int:
j = -1
n = len(forts)
for i in range(n):
if forts[i] != -1:
j=i
break
if j == -1:
return 0
res = 0
for i in range(n):
if abs(forts[i]-forts[j]) == 2:
res = max(res, i-j-1)
if forts[i] != 0:
j = i
return res
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2022-12-25 11:49:44
func captureForts(forts []int) int {
j:=-1
for i:=range forts {
if forts[i]!=0 {
j=i
break
}
}
if j == -1 {
return 0
}
res:=0
for i:=range forts {
if x := forts[i] - forts[j]; x==2||x==-2{
if i-j-1>res {
res = i-j-1
}
}
if forts[i] != 0 {
j=i
}
}
return res
}
python3 解法, 执行用时: 40 ms, 内存消耗: 15 MB, 提交时间: 2022-12-25 11:48:55
class Solution:
def captureForts(self, F: List[int], S={(1, 0, -1), (-1, 0, 1)}) -> int:
G = [(c, len([*g])) for c, g in groupby(F)]
return max((t for (a, _), (b, t), (c, _) in zip(G, G[1:], G[2:]) if (a, b, c) in S), default=0)
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2022-12-25 11:47:54
func captureForts(forts []int) (ans int) {
for i, x := range forts {
if x != 1 {
continue
}
j := i - 1
for j >= 0 && forts[j] == 0 {
j--
}
if j >= 0 && forts[j] < 0 {
ans = max(ans, i-j-1)
}
j = i + 1
for j < len(forts) && forts[j] == 0 {
j++
}
if j < len(forts) && forts[j] < 0 {
ans = max(ans, j-i-1)
}
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 48 ms, 内存消耗: 15 MB, 提交时间: 2022-12-25 11:47:38
'''
对每个1，向左向右找-1, 且中间必须都是0
'''
class Solution:
def captureForts(self, forts: List[int]) -> int:
ans = 0
for i, x in enumerate(forts):
if x != 1: continue
j = i - 1
while j >= 0 and forts[j] == 0: j -= 1
if j >= 0 and forts[j] < 0: ans = max(ans, i - j - 1)
j = i + 1
while j < len(forts) and forts[j] == 0: j += 1
if j < len(forts) and forts[j] < 0: ans = max(ans, j - i - 1)
return ans