2022-12-24:给定一个字符串s,其中都是英文小写字母, 如果s中的子串含有的每种字符都是偶数个

2022-12-24:给定一个字符串s,其中都是英文小写字母,
如果s中的子串含有的每种字符都是偶数个,
那么这样的子串就是达标子串,子串要求是连续串。
返回s中达标子串的最大长度。
1 <= s的长度 <= 10^5,
字符种类都是英文小写。
来自微软。

答案2022-12-24:

shell编写的代码真慢。
map存status最早状态的序号+status整型存26个字母的状态。
注意还没遍历的时候map[0]=-1,这是最早的状态。
时间复杂度:O(N)。
空间复杂度:O(N)。

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

#!/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 "测试开始\r\n"
    local i=0
    while [ $i -lt $testTimes ]
    do
        printf "i = %d\r\n" $i
        local s=$(randomString $n $v)
        printf "s = %s\r\n" $s
        local ans1=$(maxLen1 s)
        local ans2=$(maxLen2 s)
        if [ $ans1 != $ans2 ] 
        then 
            printf "%s\r\n" s
            printf "%s\r\n" ans1
            printf "%s\r\n" ans2
            break
        fi
        printf "ans = %s\r\n" $ans1
        printf "end===============\r\n" 
        i=$[$i+1]
    done
    printf "测试结束\r\n"

}

main maxLen1

在这里插入图片描述

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

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
未填写
文章
464
粉丝
21
喜欢
37
收藏
22
排名:461
访问:1.9 万
私信
所有博文
社区赞助商