2022-12-24：给定一个字符串s，其中都是英文小写字母， 如果s中的子串含有的每种字符都是偶数个， 那么这样的子串就是达标子串，子串要求是连续串。 返回s

2022-12-24：给定一个字符串s，其中都是英文小写字母，

如果s中的子串含有的每种字符都是偶数个，

那么这样的子串就是达标子串，子串要求是连续串。

返回s中达标子串的最大长度。

1 <= s的长度 <= 10^5，

字符种类都是英文小写。

来自微软。

答案2022-12-24：

shell编写的代码真慢。

map存status最早状态的序号 status整型存26个字母的状态。

注意还没遍历的时候map0=-1，这是最早的状态。

时间复杂度：O(N)。

空间复杂度：O(N)。

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

代码语言：text复制

#!/bin/bash

# public static int getMax(int a, int b)
function getMax()
{
    if [ $1 -gt $2 ];then
        echo $1
    else
        echo $2
    fi
}

# public static boolean ok(String s, int l, int r)
function ok(){
    eval s=$$1
    local l=$2
    local r=$3
    if [ $[($r-$l 1)&1] == 1 ] 
    then 
        return 0
    fi

    local cnts=()
    local i=0
    while [ $i -lt 26 ]
    do
        cnts[$i]=0
        i=$[$i 1]
    done

    i=$l
    while [ $i -le $r ]
    do
        local c=${s:$i:1}
        local num=$(echo $c| tr -d "n" | od -An -t dC)
        num=$[$num-97]
        cnts[$num]=$[${cnts[$num]} 1]
        i=$[$i 1]
    done

    i=0
    while [ $i -lt 26 ]
    do
        if [ $[${cnts[$i]}&1] == 1 ] 
        then 
            return 0
        fi
        i=$[$i 1]
    done

    return 1
}

# public static int maxLen1(String s)
function maxLen1(){
    eval s=$$1
    local n=${#s}
    local ans=0
    local i=0
    while [ $i -lt $n ]
    do
        local j=$[$n-1]
        while [ $j -ge $i ]
        do
            ok s $i $j
            if [ $? == 1 ] 
            then 
                ans=$(getMax $ans $[$j-$i 1])
            fi
            j=$[$j-1]
        done
        i=$[$i 1]
    done

    echo $ans
}

# public static int maxLen2(String s)
function maxLen2(){
    eval s=$$1
    local n=${#s}
    declare -A map
    map[0]=-1
    local status=0
    local ans=0
    local i=0
    while [ $i -lt $n ]
    do
        local c=${s:$i:1}
        local num=$(echo $c| tr -d "n" | od -An -t dC)
        num=$[$num-97]
        num=$[1<<$num]
        status=$[($status)^($num)]
        if [ "${map[$status]}" = "" ] 
        then 
            map[$status]=$i
        else
            ans=$(getMax $ans $[$i-${map[$status]}])
        fi
        i=$[$i 1]
    done

    echo $ans
}

# 为了测试
# public static String randomString(int n, int v) 
function randomString(){
    local n=$1
    local v=$2
    local i=0
    local ans=""
    while [ $i -lt $n ]
    do
        local temp=$RANDOM%$v
        temp=$[$temp 97]
        local a=$(echo $temp | awk '{printf("%c", $1)}')
        ans=$ans$a
        i=$[$i 1]
    done
    echo $ans
}

# 为了测试
function main(){
    local s="moonfdd"
    echo $(maxLen1 s)
    echo $(maxLen2 s)

    local n=6
    local v=6
    local testTimes=5
    printf "测试开始rn"
    local i=0
    while [ $i -lt $testTimes ]
    do
        printf "i = %drn" $i
        local s=$(randomString $n $v)
        printf "s = %srn" $s
        local ans1=$(maxLen1 s)
        local ans2=$(maxLen2 s)
        if [ $ans1 != $ans2 ] 
        then 
            printf "%srn" s
            printf "%srn" ans1
            printf "%srn" ans2
            break
        fi
        printf "ans = %srn" $ans1
        printf "end===============rn" 
        i=$[$i 1]
    done
    printf "测试结束rn"
    
}

main maxLen1

在这里插入图片描述

shell

0 人点赞