16 最接近的三数之和
Question
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
Answer
#
# @lc app=leetcode.cn id=16 lang=python3
#
# [16] 最接近的三数之和
#
# @lc code=start
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
if (not nums or n < 3):
return None
nums.sort()
res = float("inf")
for i in range(n):
if (i > 0 and nums[i] == nums[i - 1]):
continue
L = i + 1
R = n - 1
while (L < R):
cur_sum = nums[i] + nums[L] + nums[R]
if (cur_sum == target):
return target
if (abs(cur_sum - target) < abs(res - target)):
res = cur_sum
if (cur_sum - target < 0):
L += 1
else:
R -= 1
return res
# @lc code=end
17 电话号码的字母组合
Question
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
Answer
#
# @lc app=leetcode.cn id=17 lang=python3
#
# [17] 电话号码的字母组合
#
# @lc code=start
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
d_dict={
'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']
}
ans_a = []
ans_b = []
for d in digits:
if ans_a == []:
for s in d_dict[d]:
ans_a.append(s)
else:
for s in d_dict[d]:
for i in range(len(ans_a)):
ans_b.append(ans_a[i] + s)
if ans_b != []:
ans_a = ans_b
ans_b = []
return ans_a
# @lc code=end
18 四数之和
Question
给定一个包含 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]
]
Answer
#
# @lc app=leetcode.cn id=18 lang=python3
#
# [18] 四数之和
#
# @lc code=start
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
if not nums or len(nums) < 4:
return []
nums.sort()
res = []
for a in range(len(nums) - 3):
if a > 0 and nums[a] == nums[a - 1]:
continue
for b in range(a + 1, len(nums) - 2):
if b > a + 1 and nums[b] == nums[b - 1]:
continue
c = b + 1
d = len(nums) - 1
while c < d:
sum = nums[a] + nums[b] + nums[c] + nums[d]
if sum == target:
res.append([nums[a], nums[b], nums[c], nums[d]])
while c < d and nums[c] == nums[c + 1]:
c += 1
while c < d and nums[d] == nums[d - 1]:
d -= 1
c += 1
d -= 1
elif sum < target:
c += 1
else:
d -= 1
return res
# @lc code=end
19 删除链表的倒数第N个节点
Question
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
Answer
#
# @lc app=leetcode.cn id=19 lang=python3
#
# [19] 删除链表的倒数第N个节点
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
node_no = 0
node = head
while node is not None:
node = node.next
node_no += 1
node_no -= n + 1
node = head
if node_no == -1:
head = head.next
else:
while(node_no):
node = node.next
node_no -= 1
node.next = node.next.next
return head
# @lc code=end
PS: 两边扫描，第一遍拿到删除点位置，第二遍找到删除点进行删除。
22 括号生成
Question
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
Answer
#
# @lc app=leetcode.cn id=22 lang=python3
#
# [22] 括号生成
#
# @lc code=start
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
dp = [[] for _ in range(n + 1)]
dp[0] = [""]
for i in range(1, n + 1):
for p in range(i):
l1 = dp[p]
l2 = dp[i - 1 - p]
for k1 in l1:
for k2 in l2:
dp[i].append("({0}){1}".format(k1, k2))
return dp[n]
# @lc code=end
PS：动态规划的理解方法，可以参考这篇题解。
24 两两交换链表中的节点
Question
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
Answer
#
# @lc app=leetcode.cn id=24 lang=python3
#
# [24] 两两交换链表中的节点
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
node_id = 0
head_pre = head
big_node = None
ans = head.next
while (head.next):
head = head.next
node_id += 1
if node_id % 2 == 1:
head_pre.next = head.next
if big_node is not None:
big_node.next = head
head.next = head_pre
head = head.next
big_node = head
head_pre = head
return ans
# @lc code=end
PS：注意只有零个节点或者一个节点的极端情况。
29 两数相除
Question
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
- 被除数和除数均为 32 位有符号整数。
- 除数不为 0。
- 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231 − 1]。本题中，如果除法结果溢出，则返回 231 − 1。
Answer
#
# @lc app=leetcode.cn id=29 lang=python3
#
# [29] 两数相除
#
# @lc code=start
class Solution:
def divide(self, dividend: int, divisor: int) -> int:
i, a, b = 0, abs(dividend), abs(divisor)
if a == 0 or a < b:
return 0
while b <= a:
b = b << 1
i = i + 1
else:
res = (1 << (i - 1)) + self.divide(a - (b >> 1), abs(divisor))
if (dividend ^ divisor) < 0:
res = -res
return min(res, (1 << 31) - 1)
# @lc code=end
PS：来自评论区算法，实在是太强了。