力扣(2024.06.11)
1. 15——三数之和
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。注意:答案中不可以包含重复的三元组。
标签:数组,双指针,排序
代码:
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums) - 2):
num1 = nums[i]
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
num2 = nums[left]
num3 = nums[right]
if num1 + num2 + num3 0:
right = right - 1
elif num1 + num2 + num3 == 0:
res.append([num1, num2, num3])
left = left + 1
while left < right and nums[left] == nums[left - 1]:
left = left + 1
right = right - 1
while left < right and nums[right] == nums[right + 1]:
right = right - 1
return res
2. 16——最接近的三数之和
给你一个长度为 n
的整数数组 nums
和 一个目标值 target
。请你从 nums
中选出三个整数,使它们的和与 target
最接近。返回这三个数的和。假定每组输入只存在恰好一个解。
标签:数组,双指针,排序
代码:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
diff = float("inf")
res = 0
for i in range(len(nums) - 2):
num1 = nums[i]
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
num2 = nums[left]
num3 = nums[right]
if num1 + num2 + num3 target:
right = right - 1
elif num1 + num2 + num3 == target:
return target
if abs(num1 + num2 + num3 - target) < diff:
diff = abs(num1 + num2 + num3 - target)
res = num1 + num2 + num3
return res
3. 17——电话号码的字母组合
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
标签:哈希表,字符串,回溯
代码:
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
haxi = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
"6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
res = []
def backtrack(combination, digits):
if digits == "":
res.append(combination)
else:
for i in haxi[digits[0]]:
backtrack(combination + i, digits[1:])
if digits == "":
return []
else:
backtrack("", digits)
return res
4. 18——四数之和
给你一个由 n
个整数组成的数组 nums
,和一个目标值 target
。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]
(若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a
、b
、c
和d
互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按任意顺序返回答案 。
标签:数组,双指针,排序
代码:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
res = []
for i in range(len(nums) - 3):
num1 = nums[i]
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 2):
num2 = nums[j]
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = len(nums) - 1
while left < right:
num3 = nums[left]
num4 = nums[right]
if num1 + num2 + num3 + num4 target:
right = right - 1
elif num1 + num2 + num3 + num4 == target:
res.append([num1, num2, num3, num4])
left = left + 1
while left < right and nums[left] == nums[left - 1]:
left = left + 1
right = right - 1
while left < right and nums[right] == nums[right + 1]:
right = right - 1
return res
5. 19——删除链表的倒数第N个结点
给你一个链表,删除链表的倒数第 n
个结点,并且返回链表的头结点。
标签:链表,双指针
代码:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
slow = fast = dummy = ListNode()
dummy.next = head
for i in range(n):
fast = fast.next
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next