2. Add Two Numbers
问题描述：
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
1
2
3
|
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
|
大概是说给定两个链表表示的非负整数，返回他们相加后的结果，同样是用链表表示。
这道题还是比较直观的，将链表的每个对应节点相加并且保存进位就好了。以下是我的
实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
final_res = res = ListNode(0)
carry = 0
while (l1 or l2 or carry):
if not l1:
l1 = ListNode(0)
if not l2:
l2 = ListNode(0)
current_sum = l1.val + l2.val + carry
if current_sum >= 10:
res.val = current_sum - 10
carry = 1
else:
res.val = current_sum
carry = 0
l1 = l1.next
l2 = l2.next
if (l1 or l2 or carry):
res.next = ListNode(0)
res = res.next
return final_res
|
3. Longest Substring Without Repeating Characters
问题描述：
Examples:
1
2
3
4
5
6
|
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.
|
找出一个字符串的最大不含重复字母的子字符串。直观的，我们可以用暴力搜索的方法，就是找出
该字符串的每一个连续非重复子字符串，然后算一下哪个子字符串最大。但是这样的时间复杂度是
O(n^2),没有被accept。转念想想因为是连续的子字符串，那么想象一个窗口在字符串上移动，一点点
的增大，记录最大的值就是我们的最大无重复字符的子字符串了。
算法描述如下:
- 开始时窗口长度为0
- 窗口右端加1，若无重复，跳转到1，若有重复，跳转到2，右端到达尾端时停止
- 窗口左端加1，若有重复，跳转到2，若无重复，跳转到1，左端到达尾端时停止
在此期间的最长不重复子字符串便被记录下来了。
为了更直观一点，举个例子：
假如输入是pwwkew，那么输出应该便是3(wke或kew),以下是窗口的变化情况和最大值的记录情况:
1
2
3
4
5
6
7
8
9
10
|
window max_length
p 1
pw 2
pww 2
ww 2
w 2
wk 2
wke 3
wkew 3
kew 3
|
下面是我的代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
CostTime: 60mins
:type s: str
:rtype: int
pwwkew
"""
if not s:
return 0
l, r = 0, 1
max_sub = 0
last_window = ''
while l < len(s):
if s[r-1:r] not in last_window:
last_window += s[r-1:r]
r += 1
max_sub = max(max_sub,len(last_window))
else:
l += 1
last_window = s[l:r-1]
return max_sub
|
后来翻评论区，看到有大神用相同的思路实现的更简洁的代码，学到了学到了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
start = maxLength = 0
usedChar = {}
for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i
return maxLength
|
5. Longest Palindromic Substring
问题描述：
Example:
1
2
3
4
|
Input: "babad"
Output: "bab"
|
Note: “aba” is also a valid answer.
Example:
1
2
|
Input: "cbbd"
Output: "bb"
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution(object):
'''
cost:90mins
'''
def helper(self,l, r, s):
while (l >= 0 and r<len(s) and s[l] == s[r]):
l -= 1
r += 1
return s[l+1:r]
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
sbabadsss,
cbbd
"""
if not s:
return 0
max_palindrome = ''
for i in range(len(s)):
max_palindrome = max(self.helper(i, i ,s),self.helper(i, i+ 1, s),max_palindrome)
return max_palindrome
|
6. ZigZag Conversion
问题描述：
1
2
3
|
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”.
将一个字符串按"zip_zag"方式排列后，再按行取，得到新的字符串。
这道题目的zip_zag是个坑，因为给出的例子是三行这么特殊的例子，我开始的时候以为
转折的地方总是一个字母，后来才发现不是。下面是"zip_zag"的规律：
1
2
3
4
5
6
7
8
9
|
/*n=numRows
Δ=2n-2 1 2n-1 4n-3
Δ= 2 2n-2 2n 4n-4 4n-2
Δ= 3 2n-3 2n+1 4n-5 .
Δ= . . . . .
Δ= . n+2 . 3n .
Δ= n-1 n+1 3n-3 3n-1 5n-5
Δ=2n-2 n 3n-2 5n-4
*/
|
知道了规律，实现代码就容易了，值得注意的是当numRows为1或者2时需要特殊处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution(object):
def convert(self, s, numRows):
"""
:type s: str
:type numRows: int
:rtype: str
"""
start = 0
temp = []
res = ''
if numRows == 1 or numRows==2:
zip_zag = numRows
else:
zip_zag = numRows - 2
while start < len(s):
temp.append(s[start:start+numRows])
start += numRows
if s[start:start+zip_zag]:
temp.append(s[start:start+zip_zag])
start += zip_zag
for i in range(numRows):
for j,v in enumerate(temp):
if j % 2 == 0:
if len(v) > i:
res += v[i]
else:
if numRows == 1or numRows == 2:
if len(v) > i:
res += v[i]
elif i!=0 and i!=numRows-1 and len(v) > zip_zag - i:
res += v[zip_zag - i]
return res
|
15. 3Sum
问题描述：
Note: The solution set must not contain duplicate triplets.
1
2
3
4
5
6
|
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
l, r = 0, len(nums) - 1
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
result.append([nums[i],nums[l],nums[r]])
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return result
|
16. 3Sum Closest
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
result = float('inf')
l, r = 0, len(nums) - 1
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
l, r = i + 1, len(nums) - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < target:
result = s if abs(s - target) < abs(result - target) else result
l += 1
elif s > target:
result = s if abs(s - target) < abs(result - target) else result
r -= 1
else:
result = s if abs(s - target) < abs(result - target) else result
while l < r and nums[l] == nums[l + 1]:
l += 1
while l < r and nums[r] == nums[r - 1]:
r -= 1
l += 1
r -= 1
return result
|
17. Letter Combinations of a Phone Number
问题描述：
A mapping of digit to letters (just like on the telephone buttons) is given below.
1
2
|
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
|
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
rf = {'2':['a','b','c'],'3':['d','e','f'],'4':['g','h','i'],'5':['j','k','l'],'6':['m','n','o'],'7':['p','q','r','s'],'8':['t','u','v'],'9':['w','x','y','z']}
result = []
temp = []
if len(digits) == 1:
return rf[digits]
for i,v in enumerate(digits):
if v not in rf:
return []
if i < len(digits) - 1:
if i == 0:
temp = rf[v]
current_res = []
for j in temp:
for k in rf[digits[i+1]]:
current_res.append(j+k)
temp = current_res
return temp
|
92. Reverse Linked List II
问题描述：
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
1->2->
"""
if m == n:
return head
pre = None
node_start = head
for i in range(1,m):
pre = head
head = head.next
pre2 = None
node_end = head
for i in range(m,n+1):
next_node = head.next
head.next = pre2
pre2 = head
head = next_node
node_end.next = head
if m != 1: # 当m不从第一位开始时
pre.next = pre2
return node_start
else:
node_end.next = head
return pre2
|