Leetcode 01
Table of Contents
1. Two Sum
4. Median of Two Sorted Arrays
这个题目求两个数组的 median，这两个数组为有序数组。 这个题目还是比较简单的，假如有数组 L1 和 L2，它们的长度和为 L。如果将 L1 和 L2 插入到一个有序数组 L3 中， 那么这个 median 就是如下的表示：
median = L3[L/2] + L3[L/2+1] / 2.0 if L % 2 == 0 else L3[L/2+1]
所以我们要做的就是找到上面表达式中的数的过程。
5. Longest Palindromic Substring
这个题目是求最长回文子串。
这个问题的最初做法是遍历一遍字符，以每个字符为中心，求它的左右是否相同。但是这种做法没法找到类似
abbbbd
这样的例子。
在后面我看到了一个聪明的解决方法：
string expandAroundCenter(string s, int c1, int c2) {
int l = c1, r = c2;
int n = s.length();
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l--;
r++;
}
return s.substr(l+1, r-l-1);
}
string longestPalindromeSimple(string s) {
int n = s.length();
if (n == 0) return "";
string longest = s.substr(0, 1); // a single char itself is a palindrome
for (int i = 0; i < n-1; i++) {
string p1 = expandAroundCenter(s, i, i);
if (p1.length() > longest.length())
longest = p1;
string p2 = expandAroundCenter(s, i, i+1);
if (p2.length() > longest.length())
longest = p2;
}
return longest;
}
一个 N3 的做法是选择所有可能的起点和终点，然后遍历一遍。
如果使用 DP，O(N2) time and O(N2) space:
Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.
P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )
P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )
代码的表示如下：
string longestPalindromeDP(string s) {
int n = s.length();
int longestBegin = 0;
int maxLen = 1;
bool table[1000][1000] = {false};
for (int i = 0; i < n; i++) {
table[i][i] = true;
}
for (int i = 0; i < n-1; i++) {
if (s[i] == s[i+1]) {
table[i][i+1] = true;
longestBegin = i;
maxLen = 2;
}
}
for (int len = 3; len <= n; len++) {
for (int i = 0; i < n-len+1; i++) {
int j = i+len-1;
if (s[i] == s[j] && table[i+1][j-1]) {
table[i][j] = true;
longestBegin = i;
maxLen = len;
}
}
}
return s.substr(longestBegin, maxLen);
}
参考：
6. ZigZag Conversion
这个题目还是比较简单的，基本的想法遍历一下字符串，然后确定这个字符串属于哪一个层。 同时在遍历的过程中我们要保存下来，最后合并一下就可以了。
这个是我写的 python 版本，有些难看，但是很好理解。
class Solution(object):
def convert(self, s, numRows):
if numRows == 1 or numRows >= len(s):
return s
m = {}
for i in range(numRows):
m[str(i)] = []
count = 0
inc = True
for i in range(len(s)):
m[str(count)].append(s[i])
if count == numRows -1 :
inc = False
elif count == 0:
inc = True
if inc:
count += 1
else:
count -= 1
sr = ''
for i in range(numRows):
sr += ''.join(m[str(i)])
return sr
7. Reverse Integer
这个问题算是简单的。其中 python 版的竟然 3 行就可以搞定。
def reverse(self, x):
s = cmp(x, 0)
r = int(`s*x`[::-1])
return s*r * (r < 2**31)
这个问题的关键是，32 为 int 的限制，也就是范围要搞清楚。
下面是我写的版本，非常的啰嗦，但是逻辑简单：
def reverse(self, x):
tail = 0
result = 0
flag = 1
if x < 0:
flag = -1
x = -x
while x:
tail = x % 10
newResult = result * 10 + tail
if newResult >= 2 ** 31:
return 0
else:
result = newResult
x = x / 10
return flag*result
8. String to Integer(atoi)
这个题目要注意一些特殊情况，还有重要的是边界要考虑清楚。
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
if len(str) == 0:
return 0
ls = list(str.strip())
sign = -1 if ls[0] == '-' else 1
if ls[0] in ['-', '+']:
del ls[0]
ret, i = 0, 0
while i < len(ls) and ls[i].isdigit():
ret = ret * 10 + ord(ls[i]) - ord('0')
i += 1
return max(-2**31, min(ret * sign, 2 ** 31 - 1))
9. Palindrome Number
这个题目非常的简单，就是判断一个数是否为回文数。 简单的思路就是，把数字翻转一下就可以了，然后判断一下是否相等。刚开始的做法以为正负号是不用考虑的，后来发现为负的肯定不是了。
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
if not x:
return True
if int(str(x)[::-1]) == x:
return True
return False
leetcode 提交同样的代码发现运行时间差的好多。