【PythonCode】力扣Leetcode16~20题Python版

力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台，很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。
在Leetcode上刷题，可以选择各种主流的编程语言，如C++、JAVA、Python、Go等。还可以在线编程，实时执行代码，如果代码通过了平台准备的测试用例，就可以通过题目。
本系列中的文章从Leetcode的第1题开始，记录我用Python语言提交的代码和思路，供Python学习参考。

16. 最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
示例 2：
输入：nums = [0,0,0], target = 1
输出：0
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

代码实现：

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n = len(nums)
        if n == 3 or target <= nums[0] + nums[1] + nums[2]:
            return nums[0] + nums[1] + nums[2]
        if target >= nums[n-1] + nums[n-2] + nums[n-3]:
            return nums[n-1] + nums[n-2] + nums[n-3]
        result = nums[0] + nums[1] + nums[2]
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            j, k = i + 1, n - 1
            while j < k:
                if abs(nums[i] + nums[j] + nums[k] - target) < abs(result - target):
                    result = nums[i] + nums[j] + nums[k]
                if result == target:
                    return result
                if nums[i] + nums[j] + nums[k] > target:
                    k -= 1
                else:
                    j += 1
        return result

解题思路：本题是力扣15题《三数之和》的变化版，第15题是三个数之和为0，本题是三个数之和最接近目标值target，所以解题思路相似。

先将数组排序，首先分析特殊情况，如果数组只有三个数，那最接近目标值的三数之和必然就是三个数相加。因为将数组做了排序，如果目标值小于前三个数之和，那最接近目标值的三数之和就是前三个数之和，同理如果目标值大于最大的三个数之和，那最接近目标值的三数之和就是最后三个数之和。

对于一般的情况，首先先遍历获取第一个数，然后再用双指针的方式取第二个数和第三个数，将三数之和初始化为前三个数之和。使用双指针时，第二个数从第一个数的后一个开始取，第三个数从数组的最后一个数开始取，如果三数之和大于目标值，则第三个数的指针前移，如果三数之和小于目标值，则第二个数的指针后移，如果三数之和等于目标值直接返回。在遍历过程中不断更新三数之和，当找到与目标值相等或遍历完数组之后，程序结束。

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1:
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

代码实现：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == '':
            return []
        conversion = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        def backtrack(index):
            if index == len(digits):
                result.append("".join(temp))
            else:
                digit = digits[index]
                for x in conversion[digit]:
                    temp.append(x)
                    backtrack(index + 1)
                    temp.pop()
        result = []
        temp = []
        backtrack(0)
        return result    

解题思路：本题需要将字符串中每个数字对应的字母组合在一起，所以要遍历每一个数字对应的多个字母，然而数字的个数是0到4，不知道是几层遍历，不好求解。这里可以用回溯法，回溯法刚好可以穷举解空间的所有可能。参考：循序渐进，搞懂什么是回溯算法

按照回溯法的求解步骤，先定义回溯的解空间，本题是求数字对应的所有字母组合，所以结果是一个数组。回溯时，搜索树是一个高度最高为4的搜索树，深度优先遍历时在每一层取一个字母。在每次遍历到搜索树的叶结点时，会得到一种组合，将组合保存到求解的数组中，直到遍历完整个搜索树。

结合代码，首先定义好数字和字母的映射关系，初始化求解的结果数组result，回溯时的字母组合数组temp。然后定义回溯函数backtrack()，在回溯函数中，如果遍历到叶结点，就找到一种组合，所以当遍历的高度等于搜索树的高度时，要把当前的字母组合temp保存到result中，如果没有到叶结点，就在当前的结点取一个字母添加到temp中，往回回溯时，将上一个添加的字母从temp中移除，也就是将temp中的最后一个字母移除。最后调用回溯函数backtrack()，从高度0开始，从根结点开始遍历搜索树。

特殊情况，digits如果长度为0，此时不存在字母组合，直接返回空数组。

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 你可以按 任意顺序 返回答案 。

示例 1:
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109

代码实现：

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        if len(nums) < 4:
            return []
        nums.sort()
        result = []
        for i in range(len(nums) - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, len(nums) - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                x = j + 1
                y = len(nums) - 1
                while x < y:
                    if x < y and nums[i] + nums[j] + nums[x] + nums[y] < target:
                        x += 1
                        while nums[x] == nums[x-1] and x < y:
                            x += 1
                    if x < y and nums[i] + nums[j] + nums[x] + nums[y] > target:
                        y -= 1
                        while nums[y] == nums[y+1] and x < y:
                            y -= 1
                    if x < y and nums[i] + nums[j] + nums[x] + nums[y] == target:
                        result.append([nums[i], nums[j], nums[x], nums[y]])
                        x += 1
                        while nums[x] == nums[x-1] and x < y:
                            x += 1
        return result

解题思路：四数之和是三数之和的升级版，数字多了一个，但是整体解题思路不变，只是时间复杂度更大，情况也更复杂了。解题方法是嵌套遍历前两个数，后两个数用双指针。

先将数组排序，首先遍历取第一个数和第二个数，第一个数可以从数组第一个数遍历到数组的倒数第四个数，第二个数可以从第一个数的后一个数遍历到数组的倒数第三个数。然后用双指针取第三个数和第四个数，第三个数从第二个数的后一个数开始取，第四个数从数组最后一个数开始取。遍历第一个数和第二个数时，如果当前数值与前一个数值相等，则跳过（剪枝）。

取到四个数后，将四数之和与目标值比较，如果四数之和小于目标值，则第三个数的指针右移，如果四数之和大于目标值，则第四个数的指针左移，如果四数之和等于目标值，则找到一种组合，将当前组合保存到结果中。这里有两个注意点，一是找到一种组合后，不能跳过当前遍历，因为如果当前的四数之和等于0，第三个数变大，同时第四个数变小，可能还有其他组合的和也等于0，所以找到一种组合后，将第三个数的指针右移继续找。二是在移动第三个数或第四个数的指针时，如果当前的值等于上一个数的值，应继续移动指针，否则会将重复的组合添加到结果中，并且可能还有连续几个值相等的情况，所以代码是在while循环中移动指针。这里虽然多了一层循环，只有当数组中连续多个值相等才会跑到while循环的代码，对时间复杂度基本没有影响。

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1:
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1
输出：[]
示例 3：
输入：head = [1,2], n = 1
输出：[1]
提示：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

代码实现：

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        prev = ListNode(0, head)
        fast, slow = prev, prev
        for i in range(n):  
            fast = fast.next
        while fast.next:
            fast = fast.next  
            slow = slow.next
        slow.next = slow.next.next
        return prev.next

解题思路：要删除链表中的倒数第N个结点，首先要找到目标结点的前一个结点，也就是倒数第 n+1 个结点，修改前一个结点的 next 指针，让它指向目标结点的下一个结点，即倒数第 n-1 个结点。参考：Python实现单向链表

要找到链表的倒数第 n+1 个结点，可以先求出链表的长度 L ，第 L-n 个结点就是倒数 n+1 个结点。这样需要遍历两次链表，第一次求长度，第二次找倒数 n+1 个结点。还有一种更好的方法是使用双指针，这里的双指针和前面求三数之和时的用法有点差异，也叫快慢指针，两个指针的移动方向一样，一个在前一个在后。

在开始使用指针前，因为要找倒数第 n+1 个结点，假如 n 等于链表长度，也就是要删除链表的头结点，此时不存在倒数第 n+1 个结点，所以需要先对链表做一个特殊处理，在链表前加一个前置节点，使得双指针具有一般性。

在初始状态，让两个指针都指向链表的前置节点，然后让快的一个指针先向前移动 n 个结点，然后两个指针以相同的速度向后移动，直到快指针移动到链表的末尾，此时慢指针指向的节点就是倒数第 n+1 个结点。此时，将倒数第 n+1个结点的 next 指向倒数第 n-1 个结点，即可从链表中删除倒数第 n 个结点。

题目要求返回链表的头，因为在链表的前面加了一个前置节点，所以链表的头是前置节点的下一个节点，即 prev.next 。

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

示例 1:
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

代码实现：

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'(': ')', '{': '}', '[': ']'}
        stack = []
        for c in s:
            if c in dic:
                stack.append(c)
            elif stack and dic[stack[-1]] == c:
                stack.pop()
            else:
                return False
        return not stack

解题思路：本题中，有效的字符串中括号是成对的，并且是按规则闭合的（可以嵌套），三种类型的括号都是先有左括号再有右括号，这种成对的判断刚好可以对应栈的入栈和出栈，所以可以用栈来实现本题。参考：Python实现栈

先初始化一个字典，维护左括号与右括号的关系，并初始化一个空栈（代码中这个栈用列表、字符串等都行）。遍历字符串s，如果当前的符号是关系字典中的key，则入栈，如果栈非空，并且当前的符号与栈顶的符号对应，能组成一组闭合的括号，则将栈顶的符号出栈。如果是其他情况（栈为空时遇到右括号、右括号与当前栈顶的左括号类型不一样不能闭合），则直接返回False。

遍历完字符串s，如果栈是空的，则表示字符串s有效，所有括号都能按规则闭合，如果栈非空，则表示字符串s无效，还剩余未闭合的括号。