做LeetCode题的感悟 (1-10题)
做LeetCode题的感悟 (1-10题)
5. Longest Palindromic Substring
这道题我做出来了,但是复杂度高达为O(n^3)。
最后查看别人答案之后,发现,利用动态规划来解析这题才是正道,复杂度能只用O(n^2)。
6. ZigZag Conversion
这道题重点在于构建数学模型,数学模型建立的好就会很简单,数学模型建立的不好感觉算法就会比较复杂。
对于这种题目更偏向于数学算法,更常用的是归纳法,构建了相应的模型之后,开始找不同位置的数据和String的char索引的关系,然后构建一个完善的算法。
首先我们可固定的是行的行数。因此,我们计算出第一排的数据在String对应的索引的位置,之后再找它对应的每列的数据的规律。
这里用ABCDR…来做String,进行分析。
按照我们这个模型
行的规律是:numRows =1 和numRows = 2比较特殊(特殊的特殊处理),其他的规律很统一,就是开始的每个下表都是numRows*2;但是中间有一个是没有字母的。
接下来时列的规律:index先升后降。
有了这些规律就可以写了。(其实模型建立出来之后,就是自己找到对应的规律就好了,因为可以用到的规律很多。重点是将这些规律抽象为数据计算)
上面的又点复杂,后面转念一想,算了,还是先转成矩阵,然后再处理好了。然后调整了下模型:
这样每次我处理就可以按照奇数行和偶数行来处理了。
8. String to Integer (atoi)
这道题比较烦,因为你根本不知道atoi是什么意思。只能大概理解之后去验证。难怪通过率那么低。
Atoi经过理解就是:
1、 如果前面有空格,忽略空格
2、 如果被非数字的字符阶段就取最大的可以转化为数字的字符。如果是异常数字,则返回0;
3、 超过int型最大值则取最大值
比如测试用例里面:
" -0012a42" 期待值为-12
”+-2“ 期望值为0
10.Regular Expression Matching
这道题很恶心。因为排列组合的形式有很多。本来以为完成了,但是总有一个奇怪形式的测试数据出来,让原来以为完美地系统出现问题。
Eg: aaa a*a
aada ab*a*cd*a
a .
a ab*
abc ab*c*
bbbba .*a*a
bbbba .*c*a*a
bbbba .*c*ca
“” .*
"aasdfasdfasdfasdfas" "aasdf.*asdf.*asdf.*asdf.*s"
我的原则是:在有*的时候所有和*相关的都在*判断那里做处理,只有.而没有*那么需要判断.的前后有么有*,没有就自己处理。
直到这个测试集出现:
"aasdfasdfasdfasdfas" "aasdf.*asdf.*asdf.*asdf.*s"
.* 我的匹配算法,比较贪婪,会一直匹配下去,这里我没有方法进行处理,尤其是这种多个.*同时出现的情况。如此,只能去看别人的算法了。
参看:
https://www.programcreek.com/2012/12/leetcode-regular-expression-matching-in-java/
这里使用递归是正道,奈何我递归并不熟练~~~