RominYue’s Blog

A lifeway of coders

Leetcode Problem 6-10

| Comments

源代码push到了github上,戳这里

Problem 6: ZigZag Conversion

题目描述:将一个字符串按照”之”字型排列(英语字母’N’型),按行输出新的字符串
解法:和乘坐电梯类似,需要一个bool型变量判断是向上走还是向下走.
时间复杂度O(n), 空间复杂度O(1)

注意: 需要特判当nrows == 1的时候,否则可能会出现Runtime Error.

Problem 7: Reverse Integer

题目描述:将一个int型数字翻转,输出结果. 比如321,输出123
解法:整除法,每除以10就会得到一位数字. 时间复杂度O(n), 空间复杂度O(1)
注意: (1)正负数的问题 (2)前导0的问题 (3)整型溢出,比如1000000003,翻转后3000000001,溢出

Problem 8: String to Integer (atoi)

题目描述:自己动手实现c语言函数 atoi函数. 要注意一下几点:

1
2
3
4
5
6
字符串前面连续的空格
整数还是负数,可能出现 "+2" "-2" 的测试数据
贪婪匹配最多的数字,比如 "123abc",那么返回 123
字符串全是空格,或是空串,返回0
其他不合法的输入,比如 "+-2" "  a234" ,返回0
int型溢出,返回INT_MAX,INT_MIN

Problem 9: Palindrome Number

题目描述:判断一个int型整数是否是回文数字
解法:可以把数字转换为字符串,判断字符串是否是回文的.或者计算他的 reverse integer,形如Problem 7,判断两者是否相等.
用第二种方法的时候,需要注意一下几点:

1
2
负数有没有回文数字一说? :没有
翻转数字溢出了怎么办? 可以用long long保存中间结果,也可以这样认为,如果他是回文数字,翻转之后一定在int范围内,所以那些翻转会溢出的肯定不是回文数字,翻转前后必然不相等.

Problem 10: Regular Expression Matching

题目描述:给定一个字符串和一个正则表达式,问这个正则表达式是否匹配这个字符串
解法:此题比较难.用到递归.子问题是”当前ss字符串已经匹配到s的位置,pp字符串已匹配到p的位置,接下来该如何匹配”. 显然,有一下几种情况:

1
2
3
4
递归出口:p走到头的时候,看看s有没有走到头
下面就分两种情况讨论:
  (1)*(p+1) != '*'的时候,就是说p指针下一个位置不是可扩展字符的时候,只需比较当前两指针的字符,注意 '.' 可以和任意字符匹配,除了字符串末尾的'\0'字符.
  (2)否则,就需要尝试匹配多次.(比如a*,可以扩展为空字符,a,aa...) 首先考虑空字符,只需要看看(s,p+2)是否匹配就行.然后在考虑多字符匹配.

Comments