8000 add 4Sum · jiaxinhuang/python-test-code@82b8595 · GitHub
[go: up one dir, main page]
Skip to content

Commit 82b8595

Browse files
jiaxinhuangjiaxinhuang
committed
add 4Sum
1 parent dd90ee3 commit 82b8595

File tree

4 files changed

+162
-0
lines changed

4 files changed

+162
-0
lines changed

‎leetcode/4Sum.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# 题目说明
2+
3+
这题是找出和为给定`target`的四数字组，并且是不重复的组合，这里复用前面`3Sum`的代码，添加一个`target`的值限定范围，实现代码如下：
4+
5+
```python
6+
class Solution(object):
7+
def fourSum(self, nums, target):
8+
"""
9+
:type nums: List[int]
10+
:type target: int
11+
:rtype: List[List[int]]
12+
"""
13+
res = []
14+
if len(nums) < 4:
15+
return res
16+
nums.sort()
17+
for i in range(len(nums) - 3):
18+
if i > 0 and nums[i] == nums[i-1]:
19+
continue
20+
tempT = target - nums[i]
21+
tempL = self.threeSum(nums[i+1:], tempT)
22+
if tempL:
23+
for tl in tempL:
24+
tl.insert(0, nums[i])
25+
res.append(tl)
26+
return res
27+
28+
def threeSum(self, nums, target):
29+
"""
30+
:type nums: List[int]
31+
:rtype: List[List[int]]
32+
"""
33+
if len(nums) < 3:
34+
return []
35+
else:
36+
res = set()
37+
for i in range(len(nums) - 2):
38+
if i >= 1 and nums[i] == nums[i - 1]:
39+
continue
40+
d = {}
41+
for x in nums[i+1:]:
42+
if x not in d:
43+
d[target-nums[i] - x] = 1
44+
else:
45+
res.add((nums[i], target-nums[i]-x, x))
46+
return map(list, res)
47+
```
48+

‎leetcode/4Sum.py

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月17日
4+
5+
@author: huangjiaxin
6+
'''
7+
class Solution(object):
8+
def fourSum(self, nums, target):
9+
"""
10+
:type nums: List[int]
11+
:type target: int
12+
:rtype: List[List[int]]
13+
"""
14+
res = []
15+
if len(nums) < 4:
16+
return res
17+
nums.sort()
18+
for i in range(len(nums) - 3):
19+
if i > 0 and nums[i] == nums[i-1]:
20+
continue
21+
tempT = target - nums[i]
22+
tempL = self.threeSum(nums[i+1:], tempT)
23+
if tempL:
24+
for tl in tempL:
25+
tl.insert(0, nums[i])
26+
res.append(tl)
27+
return res
28+
29+
def threeSum(self, nums, target):
30+
"""
31+
:type nums: List[int]
32+
:rtype: List[List[int]]
33+
"""
34+
if len(nums) < 3:
35+
return []
36+
else:
37+
res = set()
38+
for i in range(len(nums) - 2):
39+
if i >= 1 and nums[i] == nums[i - 1]:
40+
continue
41+
d = {}
42+
for x in nums[i+1:]:
43+
if x not in d:
44+
d[target-nums[i] - x] = 1
45+
else:
46+
res.add((nums[i], target-nums[i]-x, x))
47+
return map(list, res)
48+
49+
50+
if __name__ == '__main__':
51+
S = [1, 0, -1, 0, -2, 2]
52+
target = 0
53+
print Solution().fourSum(S, target)

‎leetcode/RemoveNthNodeFromEndofList.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
# 题目说明
2+
3+
这题是要删除一个列表最后第$n$个元素，这里使用快、慢两个指针做差异化处理，等快指针走到第$n$个元素时，慢指针再出发，等到快指针走到终点时，慢指针刚好走到要被删除元素的前一个位置，等式关系为$L-(L-n)$，其中$L$代表的是列表的总长度，注意当$n=L$时需要特别出力，因为`head`并没有`pre`点，直接返回`head.next`即可。实现代码如下：
4+
5+
```python
6+
# Definition for singly-linked list.
7+
class ListNode(object):
8+
def __init__(self, x):
9+
self.val = x
10+
self.next = None
11+
12+
class Solution(object):
13+
def removeNthFromEnd(self, head, n):
14+
"""
15+
:type head: ListNode
16+
:type n: int
17+
:rtype: ListNode
18+
"""
19+
fast = slow = head
20+
for i in range(n):
21+
fast = fast.next
22+
if not fast:
23+
return head.next
24+
while fast.next:
25+
fast = fast.next
26+
slow = slow.next
27+
slow.next = slow.next.next
28+
return head
29+
```
30+

‎leetcode/RemoveNthNodeFromEndofList.py

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#-*- coding:utf-8 -*-
2+
'''
3+
Created on 2017年5月18日
4+
5+
@author: huangjiaxin
6+
'''
7+
8+
# Definition for singly-linked list.
9+
class ListNode(object):
10+
def __init__(self, x):
11+
self.val = x
12+
self.next = None
13+
14+
class Solution(object):
15+
def removeNthFromEnd(self, head, n):
16+
"""
17+
:type head: ListNode
18+
:type n: int
19+
:rtype: ListNode
20+
"""
21+
fast = slow = head
22+
for i in range(n):
23+
fast = fast.next
24+
if not fast:
25+
return head.next
26+
while fast.next:
27+
fast = fast.next
28+
slow = slow.next
29+
slow.next = slow.next.next
30+
return head
31+

0 commit comments

Comments
 (0)
0