1
2022-12-26：有一个数组包含 0、1、2 三种值， 有 m 次修改机会，第一种将所有连通的 1 变为 0，修改次数 -1， 第二种将所有连通的 2 变为 1 或 0，修改次数 -2， 返回 m 次修改机会的情况下，让最大的 0
作者：福大大架构师每日一题
- 2022-12-26 北京
本文字数：5777 字
阅读完需：约 19 分钟
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]=0done
# 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
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/f0f36dd03a7ffe1e71180b236】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
还未添加个人签名 2021-02-15 加入
还未添加个人简介
评论