该问题和求单调递增子序列有点像,但不一样。
其主要区别就是在于连不连续,如果不要求连续(单调递增子序列)在实现时的算法是动态规划,比较复杂。
本文描述的问题是子序列连续的问题,相比而言会简单很多,原理和求最大值是一样的。
具体描述为给定一个字符串,求一个子串,该子串满足:
1. 连续
2. 该子串递增
3. 是最长的单调连续递增的子串
例如:zxuhababcba
结果:abc
代码如下:
#!/bin/bash ## the input str for test inputStr="zxuhababcba"; strLength=${#inputStr}; ## record the max monotone increasing sub str maxSubStrLength=0; maxStartPos=0; ## record the position of current monotone increasing sub str currentStartPos=0; ## find the result for((i=1;i<strLength;i++)) do j=$((i-1)); if [ "${inputStr:$i:1}" \< "${inputStr:$j:1}" ]; then currentSubStrLength=$((i-currentStartPos)); if [ $currentSubStrLength -gt $maxSubStrLength ]; then maxSubStrLength=$currentSubStrLength; maxStartPos=$currentStartPos; fi currentStartPos=$i; fi done lastLength=$((strLength-currentStartPos)); if [ $lastLength -gt $maxSubStrLength ]; then maxSubStrLength=$lastLength; maxStartPos=$currentStartPos; fi echo "original string is : ${inputStr}"; echo -n "max increasing subStr : " for((i=0;i<$maxStartPos;i++)) do echo -n " "; done echo "${inputStr:$maxStartPos:$maxSubStrLength}";
在扫描过程中,记下目前为止最长的单调递增序列的开始和长度,并在当扫描中出现“拐弯”情况时,将新的递增子序列与当前记录中的最长单调递增子序列比较。
运行结果为:
该方法和给定一个数组,求数组中最大元素的方法是一回事。
此外,如果你想求最长单调递减子序列,则只需要改变上述代码中的一个字符就可以了,你知道是哪个吗?哈哈^_^
欢迎来拍!!!
相关推荐
主要是bash语法的例程,在记录学习笔记的时候做练习用的。学习记录请参考:https://blog.csdn.net/xiaodouhao123456/article/details/109473083,及其所在专栏中的其他笔记。
NULL 博文链接:https://lujinan858.iteye.com/blog/437004
bash写的字符串常用函数,这个可以看看。资源分就免了
该文档介绍了shell编程中对字符串处理的一些基本命令, 如sed, cut, awk等等
本文档是自己总结的关于 bash shell 的字符串的操作合集, 并生成了可以复制内容的pdf 以保持排版
第一、找出字符或者字符串的类型,是数字、字母还是其他特定字符,是可打印字符,还是不可打印字符(一些控制字符)。 第二、找出组成字符串的字符个数和字符串的存储结构(比如数组)。 第三、对串的常规操作:求子串、...
主要介绍了Bash Shell字符串操作总结,包含取长度、截取、查找位置、替换等等,需要的朋友可以参考下
1. 字符串声明 概述 字符串的基本操作 脚本 1 # 声明字符串 str01=str01 echo ${str01} # 单引号也可以 # 不过后面的例子, 通常是用 双引号, 具体原因, 以后会解释\nstr02='str02' echo ${str02} # 对引号的转义,...
需要对字符串查找其中某个字符最后出现的位置,这个在PHP (strrpos)或者Perl (rindex)里面都有现成函数可用的功能,在Shell里面居然一时想不出个道道来。在论坛上发贴也没人解答(不知道是问题太简单还是真的很高深...
Bash漏洞——Shellshock浅析.pdf 学习资料 复习资料 教学资源
linux bash字符串处理大全,需要的朋友可以参考下
用Bash Shell的for循环,每次递增数是500就行了。 代码如下:#!/bin/bash##每次递增的数ADD_NUM=500 #递增1的话取消下行注释,并相应的注释另一句for的开头的#for ((i=1;i<=29500;i++)) #递增定义的数for ((i=1;i...
BASH中文手册.pdfBASH中文手册.pdf
本书介绍shell脚本编程,主要针对Bourne shell与POSIX兼容的shell,...bash shell几乎总是会包含在GNU/Linux操作系统中,也包含在了大多数商业Unix中。另外,KornShell也被广泛用于大部分这样的闭源或开源操作系统中。
细绳 用Bash编写的字符串处理程序。使用它source path/to/string/source.bashawk -F : ' {print $5} ' /etc/passwd | string_title可用功能 string_camelcase_underscore string_lower 小写的字符串。 传递字符串...
Bash Shell提供了很多字符串和文件处理的命令。如awk、expr、grep、sed等命令,还有文件的排序、合并和分割等一系列的操作命令。grep、sed和awk内容比较多故单独列出,本文只涉及字符串的处理和部分文本处理命令。
Bash中文手册,适合Linux shell入门级使用!
2..bashrc文件会在bash shell调用另一个bash shell时读取,也就是在shell中再键入bash命令启动一个新shell时就会去读该文件。这样可有效分离登录和子shell所需的环境。但一般 来说都会在.bash_profile里调用.bashrc...