2022-12-26：有一个数组包含0、1、2三种值， 有m次修改机会，第一种将所有连通的1变为0，修改次数-1， 第二种将所有连通的2变为1或0，修改次数-2， 返回m次修改机会的情况下，让最大的0

2022-12-26：有一个数组包含0、1、2三种值，
有m次修改机会，第一种将所有连通的1变为0，修改次数-1，
第二种将所有连通的2变为1或0，修改次数-2，
返回m次修改机会的情况下，让最大的0连通区，最长能是多少？
1 <= arr长度 <= 10^6，
0 <= 修改机会 <= 10^6。

答案2022-12-26：

六个辅助数组。
时间复杂度：O(N)。

代码用shell编写。代码如下：

#!/bin/bash

# 时间复杂度O(N^3)的方法

# 为了验证

# public static int maxZero1(int[] arr, int k)

function maxZero1(){

    eval local arrt=\$$1

    local arr=(`echo $arrt | tr ',' ' '`)

    local k=$2

    local n=${#arr[*]}

    local ans=0

    local i=0

    while [ $i -lt $n ]

    do

        let local j=n-1

        while [ $j -ge $i ]

        do

            local t=$(cost1 arrt $i $j)

            if [ $t -le $k ];then

                ans=$(get_max $ans $[$j-$i+1])

                break

            fi

            let j--

        done

        let i++

    done

    echo $ans

}

# 为了验证

# public static int cost1(int[] arr, int l, int r)

function cost1() {

    eval local arrt=\$$1

    local arr=(`echo $arrt | tr ',' ' '`)

    local l=$2

    local r=$3

	local num0=0

	local num2=0

	let local n=r-l+1

    local i=$l

    while [ $i -le $r ]

    do

        if [ ${arr[$i]} == 0 ];then

            let num0++

        fi

        if [ ${arr[$i]} == 2 ];then

            let num2++

        fi

        let i++

    done

    if [ $num0 == $n ];then

        echo -n 0

        return 0

    fi

    if [ $num2 == $n ];then

        echo -n 2

        return 0

    fi

    local area2=0

    if [ ${arr[$l]} == 2 ];then

        area2=1

    fi

    local i=$l

    while [ $i -lt $r ]

    do

        if [ ${arr[$i]} != 2 ] && [ ${arr[$[$i+1]]} == 2 ];then

            let area2++

        fi

        let i++

    done

	local has1=0

	local areaHas1No0=0

    local i=$l

    while [ $i -le $r ]

    do

        if [ ${arr[$i]} == 0 ];then

            if [ $has1 == 1 ];then

                let areaHas1No0++

            fi

            has1=0

        fi

        if [ ${arr[$i]} == 1 ];then

            has1=1

        fi

        let i++

    done

    if [ $has1 == 1 ];then

        let areaHas1No0++

    fi

    let local ans=2*$area2+areaHas1No0

    echo -n $ans

    return 0

}

function get_max()

{

    if [ $1 -gt $2 ];then

        echo -n $1

    else

        echo -n $2

    fi

}

# 正式方法

# 时间复杂度O(N)

left10=()

left2x=()

right10=()

right2x=()

area2s=()

area1s=()

for i in {0..1000000}

do

    left10[$i]=0

    left2x[$i]=0

    right10[$i]=0

    right2x[$i]=0

    area2s[$i]=0

    area1s[$i]=0

done

# public static int maxZero2(int[] arr, int k)

function maxZero2() {

    eval local arrt=\$$1

    local arr=(`echo $arrt | tr ',' ' '`)

    local k=$2

    local n=${#arr[*]}

    local last=-1

    local i=0

    while [ $i -lt $n ]

    do

        if [ ${arr[$i]} == 0 ];then

            let last=i

        fi

        if [ ${arr[$i]} == 1 ];then

            let left10[i]=last

        fi

        let i++

    done

    let last=-1

    local i=0

    while [ $i -lt $n ]

    do

        if [ ${arr[$i]} != 2 ];then

            let last=i

        fi

        if [ ${arr[$i]} == 2 ];then

            let left2x[i]=last

        fi

        let i++

    done

    let last=n

    let i=n-1

    while [ $i -ge 0 ]

    do

        if [ ${arr[$i]} == 0 ];then

            let last=i

        fi

        if [ ${arr[$i]} == 1 ];then

            let right10[i]=last

        fi

        let i--

    done

    let last=n

    let i=n-1

    while [ $i -ge 0 ]

    do

        if [ ${arr[$i]} != 2 ];then

            let last=i

        fi

        if [ ${arr[$i]} == 2 ];then

            let right2x[i]=last

        fi

        let i--

    done

    local area2=0

    if [ ${arr[0]} == 2 ];then

        let area2=1

    fi

    local i=0

    while [ $i -lt $[$n-1] ]

    do

        if [ ${arr[$i]} != 2 ];then

            let area2s[i]=area2

            if [ ${arr[$[$i+1]]} == 2 ];then

                let area2++

            fi

        fi

        let i++

    done

    # let local t=n-1

    if [ ${arr[$[$n-1]]} != 2 ];then

        let area2s[$[$n-1]]=area2

    fi

    local has1=0

    local area1=0

    local i=0

    while [ $i -lt $n ]

    do

        if [ ${arr[$i]} == 0 ];then

            if [ $has1 == 1 ];then

                let area1++

            fi

            let has1=0

            let area1s[i]=area1

        fi

        if [ ${arr[$i]} == 1 ];then

            let has1=1

        fi

        let i++

    done

    local ans=0

    local right=0

    local left=0

    while [ $left -lt $n ]

    do

        while [ $right -lt $n ] && [ $(cost2 arrt $left $right) -le $k ]

        do

            let right++

        done

        let local t=right-left

        ans=$(get_max $ans $t)

        let t=left+1

        right=$(get_max $right $t)

        let left++

    done

    echo -n $ans

  	return 0

}

# public static int cost2(int[] arr, int left, int right)

function cost2() {

    eval local arrt=\$$1

    local arr=(`echo $arrt | tr ',' ' '`)

    local left=$2

    local right=$3

    if [ ${arr[$left]} == 2 ] && [ ${right2x[$left]} -gt $right ];then

        echo -n 2

        return 0

    fi

    local area2=0

    if [ ${arr[$left]} == 2 ];then

        let area2=1

    fi

    if [ ${arr[$right]} == 2 ];then

        let area2++

    fi

    if [ ${arr[$left]} == 2 ];then

        let left=right2x[left]

    fi

    if [ ${arr[$right]} == 2 ];then

        let right=left2x[right]

    fi

    let area2+=area2s[right]-area2s[left]

    local area1=0

    if [ ${arr[$left]} == 0 ] && [ ${arr[$right]} == 0 ];then

        let area1=area1s[right]-area1s[left]

    elif [ ${arr[$left]} == 0 ];then

        let area1++

        let right=left10[right]

        let area1+=area1s[right]-area1s[left]

    elif [ ${arr[$right]} == 0 ];then

        let area1++

        let left=right10[left]

        let area1+=area1s[right]-area1s[left]

    else

        if [ ${right10[$left]} -gt $right ];then

            let area1++

        else

  			let area1+=2

  			let left=right10[left];

  			let right=left10[right];

  			let area1+=area1s[right]-area1s[left];

        fi

    fi

    let local ans=2*area2+area1

    echo -n $ans

  	return 0

}

# public static int[] randomArray(int n)

function random_array()

{

    local n=$1

    local ans=()

    local i=0

    while [ $i -lt $n ]

    do

        let ans[$i]=$RANDOM%3

        let i++

    done

    echo -n ${ans[*]}

    return 0

}

# public static void main(String[] args)

function main()

{

    local n=5

    local testTimes=5

    printf "测试开始\r\n"

    local i=1

    while [ $i -le $testTimes ]

    do

        local arrt=$(random_array $n)

        local k=1

        printf "arrt=$arrt,k=$k\r\n"

        local arr=(`echo $arrt | tr ',' ' '`)

        local ans1=$(maxZero1 arrt $k)

        local ans2=$(maxZero2 arrt $k)

        if [ $ans1 != $ans2 ]

        then

            printf "错误ans1 = %s\r\n" $ans1

            printf "错误ans2 = %s\r\n" $ans2

            break

        fi

        printf "==ans = %s\r\n" $ans1

        printf "$i end===============\r\n"

        i=$[$i+1]

    done

    printf "测试结束\r\n"

}

main

贪心验证如下：

#!/bin/bash

I32MAX=2147483647

# public static int getMin(int a, int b)

function get_min()

{

    if [ $1 -lt $2 ];then

        echo $1

    else

        echo $2

    fi

}

# public static int best1(int[] arr)

function best1()

{

    eval local arrt=\$$1

    local arr=(`echo $arrt | tr ',' ' '`)

    local zero=0

    local two=0

    local n=${#arr[*]}

    local i=0

    while [ $i -lt $n ]

    do

        if [ ${arr[$i]} == 0 ];then

            let zero++

        fi

        if [ ${arr[$i]} == 2 ];then

            let two++

        fi

        let i++

    done

    if [ $zero == $n ];then

        echo -n 0

        return 0

    fi

    if [ $two == $n ];then

        echo -n 2

        return 0

    fi

    local ans=$I32MAX

    local i=0

    while [ $i -lt $n ]

    do

        if [ ${arr[$i]} != 0 ] && ([ $i == 0 ] || [ ${arr[$[$i-1]]} != ${arr[$i]} ])

        then

            if [ ${arr[$i]} == 2 ]

            then

                local temp1=$(change arrt $i 1)

                temp1a=$(best1 temp1)

                local temp0=$(change arrt $i 0)

                temp0a=(`echo -n $temp0 | tr ',' ' '`)

                temp0a=$(best1 temp0)

                local temp=$(get_min $temp1a $temp0a)

                let temp=temp+2

                ans=$(get_min $ans $temp)

            else

                local temp=$(change arrt $i 0)

                local tempa=(`echo -n $temp | tr ',' ' '`)

                temp=$(best1 temp)

                let temp++

                ans=$(get_min $ans $temp)

            fi

        fi

        let i++

    done

    echo -n $ans

    return 0

}

# public static int[] change(int[] arr, int i, int to)

function change()

{

    eval local arr=\$$1

    arr=(`echo $arr | tr ',' ' '`)

    local i=$2

    local to=$3

    local l=$i

    local r=$i

    while [ $l -ge 0 ] && [ ${arr[$l]} == ${arr[$i]} ]

    do

        let l--

    done

    while [ $r -lt ${#arr[*]} ] && [ ${arr[$r]} == ${arr[$i]} ]

    do

        let r++

    done

    local ans=()

    i=0

    while [ $i -lt ${#arr[*]} ]

    do

        let ans[i]=arr[i]

        let i++

    done

    let i=l+1

    while [ $i -lt $r ]

    do

        let ans[i]=to

        let i++

    done

    # 返回ans

    echo -n ${ans[*]}

}

# public static int cost(int[] arr, int l, int r)

function cost()

{

    eval local arr=\$$1

    local arr=(`echo $arr | tr ',' ' '`)

    local l=$2

    local r=$3

    local num0=0

    local num2=0

    let local n=r-l+1

    let local i=l

    while [ $i -le $r ]

    do

        if [ ${arr[$i]} == 0 ];then

            let num0++

        fi

        if [ ${arr[$i]} == 2 ];then

            let num2++

        fi

        let i++

    done

    if [ $num0 == $n ];then

        echo -n 0

        return 0

    fi

    if [ $num2 == $n ];then

        echo -n 2

        return 0

    fi

    local area2=0

    if [ ${arr[$l]} == 2 ];then

        let area2=1

    fi

    local i=$l

    while [ $i -lt $r ]

    do

        local j=i+1

        if [ ${arr[$i]} != 2 ] && [ ${arr[$j]} == 2 ]

        then

            let area2++

        fi

        let i++

    done

    local has1=0

    local areaHas1No0=0

    i=$l

    while [ $i -le $r ]

    do

        if [ ${arr[$i]} == 0 ];then

            if [ $has1 == 1 ];then

                let areaHas1No0++

            fi

            has1=0

        fi

        if [ ${arr[$i]} == 1 ];then

            let has1=1

        fi

        let i++

    done

    if [ $has1 == 1 ];then

        let areaHas1No0++

    fi

    let local ans=2*$area2+areaHas1No0

    echo -n $ans

    return 0

}

# public static int[] randomArray(int n)

function random_array()

{

    local n=$1

    local ans=()

    local i=0

    while [ $i -lt $n ]

    do

        let ans[$i]=$RANDOM%3

        let i++

    done

    echo -n ${ans[*]}

    return 0

}

# public static void main(String[] args)

function main()

{

    local n=5

    local testTimes=5

    printf "测试开始\r\n"

    local i=0

    while [ $i -lt $testTimes ]

    do

        local arr=$(random_array $n)

        printf "arr=$arr\r\n"

        local arrt=(`echo $arr | tr ',' ' '`)

        local ans1=$(best1 arr)

        local ans2=$(cost arr 0 $[${#arrt[*]}-1])

        if [ $ans1 != $ans2 ]

        then

            printf "错误ans1 = %s\r\n" $ans1

            printf "错误ans2 = %s\r\n" $ans2

            break

        fi

        printf "==ans1 = %s\r\n" $ans1

        printf "==ans2 = %s\r\n" $ans2

        printf "$i end===============\r\n"

        i=$[$i+1]

    done

    printf "测试结束\r\n"

}

main

# public static void main(String[] args)

function main1()

{

    local n=5

    local testTimes=1

    printf "测试开始\r\n"

    local i=0

    while [ $i -lt $testTimes ]

    do

        local arr=$(random_array $n)

        printf "main arr = $arr\r\n"

        local arrt=(`echo $arr | tr ',' ' '`)

        local ans2=$(cost arr 0 $[${#arrt[*]}-1])

        printf "ans2 = %s\r\n" $ans2

        printf "end===============\r\n"

        i=$[$i+1]

    done

    printf "测试结束\r\n"

}

2022-12-26：有一个数组包含0、1、2三种值， 有m次修改机会，第一种将所有连通的1变为0，修改次数-1， 第二种将所有连通的2变为1或0，修改次数-2， 返回m次修改机会的情况下，让最大的0的相关教程结束。