2022-12-26:有一个数组包含0、1、2三种值, 有m次修改机会,第一种将所有连通

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

在这里插入图片描述

本作品采用《CC 协议》,转载必须注明作者和本文链接
微信公众号:福大大架构师每日一题。最新面试题,涉及golang,rust,mysql,redis,云原生,算法,分布式,网络,操作系统。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!