最近正在找实习，发现自己的算法实在是不能再渣渣，在网上查了一下，发现大家都在刷leetcode的题，于是乎本渣渣也开始了刷题之路，主要用的是python写的代码。写个日记记录一下每天刷题的心路历程，顺便记录学习到的知识。
#1.TwoSum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
一开始想的是两个for循环，暴力枚举，于是写出了如下代码...
# coding: utf-8
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(0, len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
上面算法复杂度为O(n^2),本来没抱太大希望，结果放上去居然AC了。然后去评论区看了一下，全是O(n)的解法。定义一个字典d{}，先计算m = target - nums[i]，如果字典里没有键为n的值，则存入d[num[i]] = i，如果下次遇到目标数，我们就可以通过字典找到另一个加数的索引值，返回[d[m], i]，这样就做到了以空间换时间。写出下面的代码：
# coding: utf-8
class Solution:
def twoSum(self, nums, target):
"""
:typenums: List[int]
:typetarget: int
:rtype: List[int]
"""
d = {}
for i, vin enumerate(nums):
m = target - v
if d.get(m)is not None:
return [d[m], i]
else:
d[v] = i
两个代码的运行时间比为5392ms:76ms...
#2.Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input:(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:7 -> 0 -> 8
Explanation:342 + 465 = 807.
这题想到的是直接法，遍历两个输入链表，用字符串存起来，逆序，然后转换为整数相加，把结果再逆序存进链表中，非常直接的解法了。。。时间复杂度O(n)，代码如下
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 is None or l2 is None:
return None
n1 = ""
n2 = ""
p = l1
q = l2
while p is not None:
n1 += str(p.val)
p = p.next
while q is not None:
n2 += str(q.val)
q = q.next
n1 = n1[::-1]
n2 = n2[::-1]
res = str(int(n1) + int(n2))
head = ListNode(0)
p = None
pre = None
res = res[::-1]
for i, s in enumerate(res):
if i == 0:
head.val = int(s)
p = head
else:
p = ListNode(int(s))
pre.next = p
pre = p
return head
提交之后AC了，但我觉得这肯定不是最优解，因为这里逆序了三遍，数量大的时候还速度会很慢，于是去看了题解，意思是设定一个进位carry=0，在一个while循环，如果p->val + q->val + carry > 10，那么next.val加上和除以10的商的整数部分，当前节点值为其模10后的余数。还学到了一个python的函数divmod(a, b)，返回的是(a//b, a %b)，即a除以b的商整数部分，a对b取模。重写代码如下
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
carry = 0
head = p = ListNode(0)
while l1 or l2 or carry:
v1 = v2 = 0
if l1:
v1 = l1.val
l1 = l1.next
if l2:
v2 = l2.val
l2 = l2.next
carry, val = divmod(v1+v2+carry, 10)
p.next = ListNode(val)
p = p.next
return head.next
新代码简短精悍！比原来的简单多啦，但是不知道为什么runtime比原来还多一点...虽然只多了32ms，但是还是有些失望难道白优化了？？不管了，反正代码好看很多。
#3.Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
最长非重复子串问题，看起来很简单，一开始居然想错了，想成了求两个相同字符串之间的距离的最大值，哗啦哗啦写了以下代码：
# coding: utf-8
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0
maxium = 1
d = {}
for t in s:
d[t] = 1
for key in d.keys():
d[key] = d[key] + 1 if key != t else d[key]
maxium = d[key] if d[key] > maxium else maxium
return maxium
结果当然是哗啦哗啦的WA了，其实问题没有那么复杂，是我一心想着最优化然而想到的算法是错的。WA了几次之后发现不对劲，其实思路一开始就是错的。从头开始想，这题其实回归纯真、暴力就好（没错，我的想法就是很暴力）。定义空字符串res，从头开始遍历输入的字符串，遇到res中没有的字符就加进去，有的话就截取上一个相同的字符之后的字符串再加入新的字符，每趟循环计算一次res的长度，获取最大值。重写的代码如下:
# coding: utf-8
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
maxium = 0
res = ""
for t in s:
if t not in res:
res += t
else:
i = res.index(t)
res = res[i+1:] + t
maxium = len(res) if len(res) > maxium else maxium
return maxium
放上去果然AC了，简单，粗暴。如果所有问题都可以这么暴力就好了。时间复杂度是O(n)，因为用到了python的not in和index还有字符串复制，如果换成其他语言可能更加复杂一些。
#4.Median of Two Sorted Arrays
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
| left | Ci | right |
|---|---|---|
| a0, a1...ai-1 | i | ai, ai+2...an |
| b0, b1...bj-1 | j | bj, bj+2...bm |
两个有序数组求它们合并之后的中值，要求时间复杂度为O(log(m+n))，思来想去只能想到O((m+n)/2)的算法，也就是暴力枚举的方法。于是出去搜索了一下，发现这是一个经典的分治算法，在这里复述一下他的思路。
我们可以通过割的方法将一个有序数组分为两个部分，比如说[1, 4, 7, 9]这个数组，我们在位置C上割一刀，割完后数组左边有C个数,那么数组左边部分最大的数就是nums[C-1]，假设C=2，那么这个数组就被分为[1, 4, / 7, 9]两个部分。如果数组的长度为单数呢？在[2, 3, 5]上令割C=2，那么3将同时属于左右两部分，结果为[2, 3,/ 3, 4]。在单个数组中，要求数组的中值，我们可以在C=len(nums)/2的位置割一刀，求出中值为左边最大的数，即mid = nums[len(nums)/2 - 1]。
下面我们来看有两个数组的情况。我们要求两个数组的中值，就是求两个数组合并后在C = len(nums1)+len(nums2)/2 位置上割一刀，左边部分的最大值。其实我们不用真的合并这两个数组，而是用二分的方法求出割的位置，怎么求呢？
| left | Ci | right |
|---|---|---|
| a0, a1...ai-1 | i | ai, ai+2...an |
| b0, b1...bj-1 | j | bj, bj+2...bm |
上表表示分别在i和j的位置割两个数组，我们令上表中的L1 = ai-1,L2 = bj-1, R1 = ai, R2 = bj。显然R1 > L1， R2 > L2。若L1 < R1 && L2 < R2，那么表示左边的数全部小于右边的数，如果此时左边共有k个数，那么左边最大的数就为我们要求的数。
为了统一计算数组长度为奇数或偶数的情况，我们引入“虚拟数组“的概念。用‘#’填充数组，比如[1, 4, 7, 9]填充为[#, 1, #, 4, #, 7, #, 9 #]，这样无论数组的长度为奇数还是偶数，填充后数组长度必为2n+1的奇数。这样做的好处是，当我们确定割的位置时，割的左边对应原数组位置总为L = (C - 1)/2，右边的位置总为C/2，比如在数组[#, 1, #, 4, #, 7, #, 9 #]中：
若割的位置为4，则L = (4 - 1) / 2 = 1，R = 4 / 2 = 2，而1和2正好是原数组中4和7的位置。
我们不用真正的在数组中添加#，只需要在二分开始的时候将高位设置为2n+1就可以。
如果我们使用虚拟数组的时候，那么合并后的数组总长度为2n+2m+2，中值位置为n+m+1。令i为nums1的割位置，j为nums2的割位置，那么当取得中值时必有i+j = n+m+1，因此我们只要找到同时符合 nums1[(i-1)/2] < nums2[j/2] && num2[(j-1)/2] < nums1[i/2]的i和j，就能找到中值。思路已经明确了，我们可以开始写代码
# coding: utf-8
import sys
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
n = len(nums1)
m = len(nums2)
if n > m:
return self.findMedianSortedArrays(nums2, nums1)
L1, L2, R1, R2, low = 0, 0, 0, 0, 0
high = 2*n
while low <= high:
c1 = int((low + high)/2)
c2 = m + n - c1
L1 = nums1[int((c1-1)/2)] if not c1 == 0 else -sys.maxsize
L2 = nums2[int((c2-1)/2)] if not c2 == 0 else -sys.maxsize
R1 = nums1[int(c1/2)] if not c1 == 2*n else sys.maxsize
R2 = nums2[int(c2/2)] if not c2 == 2*m else sys.maxsize
if L1 > R2:
high = c1 - 1
elif L2 > R1:
low = c1 + 1
else:
break
return (max(L1, L2) + min(R1, R2)) / 2.0
最终AC了，真的好难想啊，代码也不好写，不过又学到了一些东西，也算是有一点进步吧。
#5.Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example:
Input: "cbbd"
Output: "bb"
最长回文子串问题，想到的是从中心开始往两边搜索的思路，思路分成两部分，分别计算子串长度为奇数即aba形态和子串长度为偶数即abba形态的最长长度，取其最大值。首先用一个for循环遍历每一个可能的中心点，然后用一个while循环从中心点出发，如果两边的字符相同则count+2，否则跳出循环，记录count的最大值和最长子串的起始位置，最后返回子串[start:start+maxium]，写出代码：
# coding: utf-8
class Solution:
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
maxium = 1
start = 0
for i in range(len(s)):
# aba
j = i - 1
k = i + 1
count = 1
while j >= 0 and k < len(s) and s[j] == s[k]:
count += 2
if count > maxium:
maxium = count
start = j
j -= 1
k += 1
for i in range(len(s)):
# abba
j = i
k = i + 1
count = 0
while j >= 0 and k < len(s) and s[j] == s[k]:
count += 2
if count > maxium:
maxium = count
start = j
j -= 1
k += 1
return s[start:start+maxium]
时间复杂度为O(n^2)，提交后AC了。然后取看题解，有一种Manacher的算法，时间复杂度为O(n)，看了半节课没看懂，在这贴个链接以后有时间再看[Manacher算法详解]。(https://www.cnblogs.com/z360/p/6375514.html)
#6.ZigZag Conversion
The string
"PAYPALISHIRING"is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H N
A P L S I I G
Y I R
And then read line by line:"PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3) should return"PAHNAPLSIIGYIR".
这题找规律，首尾两行的规律比较好找，中间的行数规律有奇偶数之分，分析了一会写了代码：
# coding: utf-8
class Solution:
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
n = len(s)
if numRows == 1 or n == 0:
return s
step = 2*numRows - 2
res = []
for i in range(numRows):
rs = ""
if i % (numRows-1) == 0:
# the first or the last row
index = i % numRows
while index < n:
rs += s[index]
index += step
res.append(rs)
else:
# the middle rows
index = i % numRows
count = 0
while index < n:
rs += s[index]
if count % 2 == 0:
index += step - 2 * (i % numRows)
else:
index += 2 * (i % numRows)
count += 1
res.append(rs)
result = ""
for i in range(numRows):
result += res[i]
return result
提交之后AC了，时间复杂度是O(n*m)，但是觉得自己找规律的时间有点长，希望能再提高吧。
#7.Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
翻转整数，先把输入转化为字符串，如果有符号，先把符号提取出来，然后将剩下的字符串翻转后再加上符号，最后判断是不是在32位int的范围内，python的代码几行就写好了。
# coding: utf-8
class Solution:
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
s = str(x)
index = 1 if s[0] == "-" or s[0] == "+" else 0
s = s[0] + s[index:][::-1] if index else s[::-1]
res = int(s)
if -2147483648 < res < 2147483647:
return res
else:
return 0
果断AC了，时间复杂度O(n)，翻转字符串还是比较耗时的，不过这也算简单题，如果用其他语言应该复杂一点。
#8.String to Integer (atoi)
Implement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.
Requirements for atoi:
The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.
The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.
If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.
If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
实现一个atoi函数，题目好长，主要是考虑的情况有很多，其实也不是很难，就是要注意一些地方，还好python的isdigit()函数和try except帮了大忙，代码写好很快就AC了，算法复杂度是O(n)
# coding: utf-8
class Solution:
def isIntegerNumber(self, s):
"""
:type s: str
:rtype: bool
"""
if s.isdigit() or s == "-" or s == "+":
return True
else:
return False
def myAtoi(self, st):
"""
:type st: str
:rtype: int
"""
r = ""
status = False
for c in st:
if not status:
if c == " ":
continue
elif not self.isIntegerNumber(c):
break
elif self.isIntegerNumber(c):
status = True
r += c
else:
if c.isdigit():
r += c
else:
break
try:
r = int(r)
if r > 2147483647:
return 2147483647
elif r < -2147483648:
return -2147483648
else:
return r
except:
return 0
#9. Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
题目很短！就是判断一个数是否回文数，要求不使用额外的空间。不能用额外的空间，那就不能将它转换为字符串来做了，想了一个用除和模做的方法。首先计算它的数量级（10的多少次方），然后不断将这个数除以其数量级，比较取整后的商和它与10的模，如果不相等表示该数的第一个数和最后一个数字不同，返回false。如果相等，则将该数减去其先前求出的商*数量级，再减去先前求出的模，然后除以10，得到去头去尾的一个新数，继续判断其是否为回文串。根据这个思路写出的代码：
# coding: utf-8
class Solution:
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
if x < 0:
return False
l_size = 1
s_size = 10
while x / l_size >= 10:
l_size *= 10
while x > 0:
first = x // l_size
last = x % s_size
if last != first:
return False
x -= l_size * first
x -= last
x /= 10
l_size /= 100
return True
一次就AC了，说明这个方法还是管用的，而且没有用到多余的空间。
#10. Regular Expression Matching
实现一个能匹配.和*的正则表达式引擎，太难了。。。想了一个晚上，要考虑的情况太多，先放弃这一题。
#11. Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container and n is at least 2.
一开始理解错了题目，以为是求梯形面积，WA一次之后发现题目不是这个意思，其实是求两块木板之间能装多少水的面积，也就是短板的高度*x坐标的差。很快就写了一个O(n^2)的思路，放上去果然超时了。
#include <cmath>
class Solution {
public:
int maxArea(vector<int>& height) {
int maxium = 0;
for (int i=0; i<height.size(); i++){
for (int j=i+1; j<height.size();j++){
int m = height[j] < height[i]? height[j] : height[i];
int area = m * (j - i);
if (area > maxium)maxium = area;
}
}
return maxium;
}
};
然后想了一个O(n)的思路，先定义一个一维数组，里面放的是该坐标能找到的最长的木板的左边，然后从左到右遍历木板，如果遇到比自己能找到最长的木板更长的木板，则递归更新该数组。我是这么想的，因为是从左到右的遍历，所以如果在右边找到更长的木板，那么面积一定比原来找到的那个木板更大（我现在知道哪里错了，前提条件应该是数组存的木板比自身短）。写出以下代码：
#include <cmath>
class Solution {
public:
vector<int> highestPos;
int maxArea(vector<int>& height) {
highestPos.resize(height.size());
for(int i=0;i<height.size()-1;i++){
if(height[highestPos[i]] < height[i+1]){
changeHighestIndex(i, i+1);
}
}
int maxium = 0;
for(int i=0;i<height.size();i++){
int lowest = height[i] < height[highestPos[i]] ? height[i] : height[highestPos[i]];
int area = lowest * abs(i-highestPos[i]);
if(area > maxium)maxium = area;
}
return maxium;
}
void changeHighestIndex(int i, int newPos){
if(highestPos[i] != newPos){
int tmp = highestPos[i];
highestPos[i] = newPos;
changeHighestIndex(tmp, newPos);
}
}
};
放上去WA了，思考一会之后发现这个思路应该太复杂了，其实我可以从两边向中间遍历，记录最大值就好，这个思路清晰简单，写出来的代码也很简单。时间复杂度是O(n)，一次就AC了。
#include <cmath>
class Solution {
public:
int maxArea(vector<int>& height) {
int low = 0;
int high = height.size() - 1;
int maxium = 0;
while(low < high){
int lowest = height[low] < height[high] ? height[low] : height[high];
int area = lowest * (high - low);
maxium = area > maxium ? area : maxium;
if(height[low] > height[high]){
high--;
}else{
low++;
}
}
return maxium;
}
};
#12. Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
将整数转换为罗马数字字符串，为此还学习了一波罗马数字。挺简单的题，结果边界值0的时候卡住了，改了挺久，不应该啊。
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
string intToRoman(int num) {
string all[4][10] = {
{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
{"", "M", "MM", "MMM"}
};
int size = 10;
string res = "";
int count = 0;
while(num*10 / size){
int left = num % size;
res = all[count][left*10/size] + res;
num = num - left*10 / size;
size *= 10;
count += 1;
}
return res;
}
};
#13. Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
上一题的反向，我觉得更简单一些，代码很快就AC了，时间复杂度O(n)。
class Solution {
public:
int romanToInt(string s) {
int worth[26];
int a = 'A';
worth['M'-a] = 1000;
worth['D'-a] = 500;
worth['C'-a] = 100;
worth['L'-a] = 50;
worth['X'-a] = 10;
worth['V'-a] = 5;
worth['I'-a] = 1;
int i = s.length()-1;
int total = 0;
while(i>=0){
if(i==0){
total += worth[s[i]-a];
break;
}
int A = worth[s[i]-a];
int B = worth[s[i-1]-a];
if(A<=B){
total += A;
i -= 1;
}else{
total = total + A - B;
i -= 2;
}
}
return total;
}
};
#14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
寻找给出字符串列表的最长共同前缀，思路是一开始最长的前缀是第一个字符串，然后遍历每一个字符串，如果某个字符串在某位和当前的最长前缀不同，则最长前缀截取为前面相同的部分，写出代码：
# coding: utf-8
class Solution:
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if len(strs) == 0:
return ""
prefix = strs[0]
for v in strs:
if len(prefix) == 0:
return ""
if len(v) < len(prefix):
prefix = prefix[:len(v)]
for i in range(len(prefix)):
if v[i] != prefix[i]:
prefix = prefix[:i]
break
return prefix
处理空字符串的情况后之后就AC了，时间复杂度O(n)，这题不是很难。
#15. 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
找出给出数组中的三个数，使得它们的和为0，要求结果去掉相同的情况。这题和第一题有点像，所以我想沿用第一题的思路，设置一个以差值为键的字典，这样将O(n3)的问题化为O(n2)。然而这题的结果有很多，这种做法会出现很多重复的代码，去重虽然能实现但是太复杂，于是看了别人是怎么做的。首先将数组排序，然后固定一个数，用两个指针指向该数右边最大和最小的两个数，计算当前三个数的和，如果比0小则low指针右移，比0大则high指针左移，和0相等则记录到答案中。记录一次后要将low和high指针移动到下一个不相等的数，避免重复记录。写出的代码也很简洁易懂：
# coding: utf-8
class Solution:
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
dic = {}
res = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
low = i + 1
high = len(nums) - 1
while low < high:
s = nums[i] + nums[low] + nums[high]
if s < 0:
low += 1
elif s > 0:
high -= 1
else:
res.append([nums[i], nums[low], nums[high]])
while low < high and nums[low] == nums[low+1]:
low += 1
while low < high and nums[high] == nums[high-1]:
high -= 1
low += 1
high -= 1
return res
代码一次AC，时间复杂度还是O(n^2)。
#16. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
和上题差不多，要求变为求给出与目标数最接近的三个数的和。沿用上题的思路，很快就写好了代码：
# coding: utf-8
class Solution:
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
closest = 0
minium = -1
nums.sort()
for i in range(len(nums)):
low = i + 1
high = len(nums) - 1
while low < high:
s = nums[i] + nums[low] + nums[high]
d = abs(s - target)
if d == 0:
return target
if minium == -1 or d < minium:
minium = d
closest = s
if s < target:
low += 1
else:
high -= 1
return closest
处理好边界问题后代码就AC了，时间复杂度还是O(n^2)。
#17. Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
image
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
给出几个数字，要求给出数字对应的字母最多能组合的字符串。这是一个经典的backtracking（回溯算法）的题目。当一个题目，存在各种满足条件的组合，并且需要把它们全部列出来时，就可以考虑backtracking了。一开始想得没有思路，看了提示用队列解决。于是设计了一个队列，对于每个输入的数字，当队列中有元素的长度小于当前的处理的数字个数时，取出该元素，然后在队尾中分别加入该元素分别和当前数字对应的所有字母组成的新串。根据这个思路写出代码：
# coding: utf-8
class Solution:
numbers = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
queue = [""]
if len(digits) == 0:
return []
for i, v in enumerate(digits):
while len(queue[0]) == i:
tmp = queue.pop(0)
for s in self.numbers[int(v)]:
queue.append(tmp+s)
return queue
代码很短，时间复杂度是O(n)，基本上是一个枚举算法。
