给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1

作者:谢高升 发布:2021-02-19 浏览:45次

给定一个由若干 0 和 1 组成的数组 A,我们最多可以将 K 个值从 0 变成 1 。


返回仅包含 1 的最长(连续)子数组的长度。

示例 1:


输入:A = [1,1,1,0,0,0,1,1,1,1,0], K = 2

输出:6

解释: 

[1,1,1,0,0,1,1,1,1,1,1]

粗体数字从 0 翻转到 1,最长的子数组长度为 6。

示例 2:


输入:A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3

输出:10

解释:

[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]

粗体数字从 0 翻转到 1,最长的子数组长度为 10

PHP代码如下

class Solution
{
    public static $max=0;
    /**
     * @param Integer[] $A
     * @param Integer $index //0的位置
     * @param Integer $K
     * @return Integer
     */
    function longestOnes($A,$index, $K) {
        if($K==0|| $index==count($A) ){
            $tmp=0;//开始统计计数连续1的个数
            for($i=0;$i<count($A);$i++){
                if($A[$i]==1){
                    $tmp++;
                    self::$max = max(self::$max, $tmp);
                }
                else{
                    //中间有0 计数清0
                    $tmp=0;
                }
            }
            return self::$max ;//结束
        }
        // 从上次0的位置开始循环
        for($j=$index;$j<count($A);$j++){
           // echo $index.'---'."\n";
            if($A[$j]==0){
                $A[$j]=1;
                $this->longestOnes($A,$j,$K-1);

                $A[$j]=0;
            }elseif ($j==count($A)-1){
                 $this->longestOnes($A,$j,$K-1);
            }
        }

        return self::$max;
    }

}
$a = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1];
$obj = new Solution();
$count =  $obj->longestOnes($a,0,3);
echo $count."\n";

image.png

标签: php
感谢博主,喝杯咖啡~