11. Container With Most Water

思路:使用双指针法，表示左右两个边界，将两个边界较小的值进行移动，记录移动过程中的最大值。

# @lc app=leetcode id=11 lang=python3
#
# [11] Container With Most Water
#

# @lc code=start
class Solution:
    # 双指针法
    def maxArea(self, height: List[int]) -> int:
        left, right, width, res = 0, len(height) - 1, len(height) - 1, 0
        for w in range(width, 0, -1):
            # 如果左边的数值小，就向左移动一个位置，反之向右移动一个位置
            if height[left] < height[right]:
                res, left = max(res, height[left] * w), left + 1
            else:
                res, right = max(res, height[right] * w), right - 1
        return res

12. Integer to Roman

思路：这道题的解题思路比较粗暴，直接将所有可能的数字列出。之后进行取余和整除操作即可。

#
# @lc app=leetcode id=12 lang=python3
#
# [12] Integer to Roman
#

# @lc code=start
class Solution:
    def intToRoman(self, num: int) -> str:
        M = ["", "M", "MM", "MMM"]
        C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
        return M[num//1000] + C[(num % 1000)//100] + X[(num % 100)//10] + I[num % 10]

13. Roman to Integer

思路:和12题思路类似建立一个hash表，将所有的进制存到hash表中。还有一个点是将roman数字中的减法操作用加法操作替换掉即可。

# @lc app=leetcode id=13 lang=python3
#
# [13] Roman to Integer
#

# @lc code=start
class Solution:
    def romanToInt(self, s: str) -> int:
        translations = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        number = 0
        # 将所有的减操作变换成加法操作
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
        s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
        s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
        for char in s:
            number += translations[char]
        return number

14. Longest Common Prefix

思路：将列表中的首个元素取出来和后面的元素进行对比，通过后面元素的长度和字符的对比来判断是否停止循环，还有一个坑就是，如果列表中只有一个元素，直接将元素返回即可。

#
# @lc app=leetcode id=14 lang=python3
#
# [14] Longest Common Prefix
#
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""
        for i in range(len(strs[0])):
            for string in strs[1:]:
                if i >= len(string) or string[i] != strs[0][i]:
                    return strs[0][:i]
        return strs[0]

15.3Sum

思路：为了方便后面去重，先将数组做一个排序，排序之后就是一个两层的遍历，第三个数用前两个数之后表示。有一个trick，就是当x不在字典中时，将d[-v-x]存到字典中，如果后面遇到x在字典中，说明之前已经遇到过第二个数了，这时候直接添加到set中就可以了。

#
# @lc app=leetcode id=15 lang=python3
#
# [15] 3Sum
#

# @lc code=start
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1
                else:
                    res.add((v, -v-x, x))
        return map(list, res)

16. 3Sum Closest

思路：和3数之和类似，只不过是添加了一个距离最小值的计算，先排序，之后通过使用两个指针，根据和target的大小关系，判断指针的移动方向。

#
# @lc app=leetcode id=16 lang=python3
#
# [16] 3Sum Closest
#

# @lc code=start


class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = sum(nums[:3])
        for i in range(len(nums)):
            # 双指针 
            left, right = i+1, len(nums) - 1
            while left < right:
                s = sum((nums[i], nums[left], nums[right]))
                # 保存新的最小值
                if abs(s-target) < abs(res-target):
                    res = s
                if s < target:
                    left += 1
                elif s > target:
                    right -= 1
                # 如果是0，直接返回
                else:
                    return res
        return res

17 Letter Combinations of a Phone Number

思路:一道经典的回溯问题，因为这道题目只有两层，所以用循环也可以做。第一层循环添加第一个字符，第二层循环添加第二个字符。如图：

image.png

#
# @lc app=leetcode id=17 lang=python3
#
# [17] Letter Combinations of a Phone Number
#
class Solution:
    def letterCombinations(self, digits):
        lookup = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }
        if not digits:
            return []
        res = [""]
        for num in digits:
            next_res = []
            for alp in lookup[num]:
                for tmp in res:
                    next_res.append(tmp+alp)
            res = next_res 
        return res

18

思路：和3sum没有本质区别，只不过是添加了一位数字

#
# @lc app=leetcode id=18 lang=python3
#
# [18] 4Sum
#

# @lc code=start
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        N = len(nums)
        nums.sort()
        res = []
        i = 0
        while i < N - 3:
            j = i + 1
            while j < N - 2:
                k = j + 1
                l = N - 1
                remain = target - nums[i] - nums[j]
                while k < l:
                    if nums[k] + nums[l] > remain:
                        l -= 1
                    elif nums[k] + nums[l] < remain:
                        k += 1
                    else:
                        res.append([nums[i], nums[j], nums[k], nums[l]])
                        while k < l and nums[k] == nums[k + 1]:
                            k += 1
                        while k < l and nums[l] == nums[l - 1]:
                            l -= 1
                        k += 1
                        l -= 1
                while j < N - 2 and nums[j] == nums[j + 1]:
                    j += 1
                j += 1
            while i < N - 3 and nums[i] == nums[i + 1]:
                i += 1
            i += 1
        return res

19. Remove Nth Node From End of List

思路:使用双指针，快指针先走n个位置，慢指针后面再走。当快指针走到尾部，慢指针跳过下一个指针就是删除了倒数第 $n$ 个节点。

#
# @lc app=leetcode id=19 lang=python3
#
# [19] Remove Nth Node From End of List
#

# @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:
        if not head:
            return head 
        dummy = ListNode(-1)
        dummy.next = head 
        prev = dummy 
        cur = dummy 
        while prev and n>=0:
            prev = prev.next 
            n -= 1
        while prev:
            prev = prev.next 
            cur = cur.next 
        cur.next = cur.next.next 
        return dummy.next

20. Valid Parentheses

#
# @lc app=leetcode id=20 lang=python3
#
# [20] Valid Parentheses
#
class Solution:
    def isValid(self, s: str) -> bool:
        res = []
        for t in s:
            if t in ["(","[","{"]:
                res.append(t)
            elif  res == [] :
                return False
            elif t ==")" and res!= [] and res.pop() != "(":
                return False 
            elif t == "]" and res != [] and res.pop() != "[":
                return False
            elif t == "}" and res != [] and res.pop() != "{":
                return False
        if res!=[]:
            return False 
        else:
            return True

Leetcode系列11-20