2022-12-24:给定一个字符串s,其中都是英文小写字母,如果s中的子串含有的每种字符都是偶数个,那么这样的子串就是达标子串
2023-02-26 09:49:36 时间
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
相关文章
- Linux Page Cache调优在Kafka中的应用
- 一篇文章教你从入门到精通 Google 指纹验证功能
- 8天学通MongoDB——第八天 驱动实践
- 8天学通MongoDB——第七天 运维技术
- 8天学通MongoDB——第六天 分片技术
- 8天学通MongoDB——第五天 主从复制
- 8天学通MongoDB——第四天 索引操作
- 8天学通MongoDB——第三天 细说高级操作
- 8天学通MongoDB——第二天 细说增删查改
- 8天学通MongoDB——第一天 基础入门
- PHP实现常见排序
- PHP天坑总结
- mac必备软件Go2shell
- 在github的某次commit中close或者fix某个issue
- 将你的PHP程序升级到PHP7.0
- go下载
- Centos搭建GIT服务器
- golang使用multiconfig后导致glog无法接受命令行参数
- 关闭OSX的rootless和修改MAMP的php.ini配置
- nginx+php 上传大文件