有一个数组包含0、1、2三种值，有m次修改机会，第一种将所有连通的1变为0，修改次数-1，第二种将所有连通的2变为1或0，修改次数-2，返回m次修改机会的情况下，让最大的0连通区，最长能是多少？-天翼云

有一个数组包含0、1、2三种值，有m次修改机会，第一种将所有连通的1变为0，修改次数-1，第二种将所有连通的2变为1或0，修改次数-2，返回m次修改机会的情况下，让最大的0连通区，最长能是多少？

2024-05-08 07:02:21 阅读次数：29

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

六个辅助数组。
时间复杂度：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

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

贪心验证如下：

#!/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"
}

活动

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

有一个数组包含0、1、2三种值， 有m次修改机会，第一种将所有连通的1变为0，修改次数-1， 第二种将所有连通的2变为1或0，修改次数-2， 返回m次修改机会的情况下，让最大的0连通区，最长能是多少？

有一个数组包含0、1、2三种值， 有m次修改机会，第一种将所有连通的1变为0，修改次数-1， 第二种将所有连通的2变为1或0，修改次数-2， 返回m次修改机会的情况下，让最大的0连通区，最长能是多少？

相关文章

Redis缓存淘汰算法详解

基于局部保留降维与空谱特征融合的高光谱图像分类算法研究

【机器学习】简单易懂的聚类算法K-Means

一文让你了解常见的加密算法以及摘要算法

【数据结构】图的详细分析（全）

【操作系统】常见面试题集锦（全）

【leetcode】动态规划 - 最小路径和

【代码随想录】栈与队列专栏（java版本）

java中常见的限流算法详细解析

一致性哈希算法的原理与应用剖析

作者介绍

最新文章

基于局部保留降维与空谱特征融合的高光谱图像分类算法研究

一文让你了解常见的加密算法以及摘要算法

【机器学习】简单易懂的聚类算法K-Means

java中常见的限流算法详细解析

数学建模--什么是数学建模？数学建模应该怎么准备？

K-Means聚类算法基本知识（附Demo）

热门文章

Lc70_爬楼梯

Lc216_组合总和III

输出1234无重复的三位数

利用函数求出一个数组最大三个数的乘积

冒泡排序法解析

猜字母问题

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

超级水王问题。扩展1：摩尔投票。扩展2：给定一个正数K，返回所有出现次数＞N/K的数。

[leetcode] 240. Search a 2D Matrix II

[leetcode] 11. Container With Most Water

推荐算法的介绍与应用

下一个排列。实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。

Lc59_ 螺旋矩阵 II

有一个数组包含0、1、2三种值，有m次修改机会，第一种将所有连通的1变为0，修改次数-1，第二种将所有连通的2变为1或0，修改次数-2，返回m次修改机会的情况下，让最大的0连通区，最长能是多少？

有一个数组包含0、1、2三种值，有m次修改机会，第一种将所有连通的1变为0，修改次数-1，第二种将所有连通的2变为1或0，修改次数-2，返回m次修改机会的情况下，让最大的0连通区，最长能是多少？

下一个排列。实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。