18.四个数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
class Solution:
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
result = []
N = len(nums)
if N < 4:
return result
nums = sorted(nums)
for i in range(N - 3):
if sum(nums[i:i + 4]) > target or sum(nums[-4:]) < target:
break
if nums[i] + sum(nums[-3:]) < target:
continue
if i > 0 and nums[i] == nums[i - 1]:
continue
target2 = target - nums[i]
for j in range(i + 1, N - 2):
if sum(nums[j:j + 3]) > target2 or sum(nums[-3:]) < target2:
break
if nums[j] + sum(nums[-2:]) < target2:
continue
if j > i + 1 and nums[j] == nums[j - 1]:
continue
target3 = target2 - nums[j]
left = j + 1
right = N - 1
while (left < right):
if nums[left] + nums[right] == target3:
result.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]: left += 1;
while left < right and nums[right] == nums[right - 1]: right -= 1;
left += 1
right -= 1
elif nums[left] + nums[right] < target3:
left += 1
else:
right -= 1
return result
19 删除链表中倒数第n个节点
class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: Li
"""
dao_n, first = head
for i in range(n):
first = first.next
if not first:
return dao_n.next
while first:
dao_n = dao_n.next
first = first.next
dao_n.next = dao_n.next.next
return head
20 有效括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}"
输出: true
class Solution:
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
dict = {"]": "[", "}": "{", ")": "("}
for char in s:
if char in dict.values():
stack.append(char)
elif char in dict.keys():
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []
21合并两个有序链表
class Solution:
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
dumy = ListNode(0)
cur = dumy
while l1 or l2:
if l1 and l2:
if l1.val > l2.val:
cur.next = l2
l2 = l2.next
else:
cur.next = l1
l1 = l1.next
elif l1:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
return dumy.next
22 括号生成
class Solution:
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]22
"""
if n == 0:
return []
left = right = n
result = []
self.generate(left, right, result, '')
return result
def generate(self, left, right, result, string):
if left == 0 and right == 0:
result.append(string)
return
if left:
self.generate(left - 1, right , result, string+'(')
if left < right:
self.generate(left, right - 1, result, string+')')
a = Solution()
print(a.generateParenthesis(4))
23合并K个排序链表
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def mergeKLists(self, lists):
pre = cur = ListNode(0)
heap = []
for i in range(len(lists)):
if lists[i]:
heapq.heappush(heap, (lists[i].val, i, lists[i]))
while heap:
node = heapq.heappop(heap)
idx = node[1]
cur.next = node[2]
cur = cur.nextb
if cur.next:
heapq.heappush(heap, (cur.next.val, idx, cur.next))
return pre.next