leetcode 11-20

11.盛水最多的容器

给定n个非负整数a[n]，每个数代表一个点(i,a[i])，画n条垂线，每条垂线的端点分别为(i,a[i])和(i,0)，选两条线，使它们与x轴构成的容器可以容纳最多的水。

class Solution:
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        ans = 0
        i, j = 0, len(height)-1
        while i < j:
            ans = max(ans, (j-i)*min(height[i], height[j]))
            if height[i] <= height[j]:
                i += 1
            else:
                j -= 1
        return ans

12.整数转罗马数字

在罗马数字表示法中，字母"IVXLCDM"分别代表1, 5, 10, 50, 100, 500, 1000。给定一个1〜3999的整数，将其转成罗马数字。

class Solution:
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        a = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000]
        b = ['I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M']
        ans = ''
        x = len(a) - 1
        while num > 0:
            if num >= a[x]:
                ans += b[x]
                num -= a[x]
            else:
                x -= 1
        return ans

13.罗马数字转整数

给定一个范围在1〜3999的罗马数字，将其转换成整数。

class Solution:
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        a = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
        ans = 0
        for i in range(len(s)):
            if i+1 < len(s) and a[s[i]] < a[s[i+1]]:
                ans -= a[s[i]]
            else:
                ans += a[s[i]]
        return ans

14.最长公共前缀

输入一个字符串数组，求所有字符串的最长公共前缀。

class Solution:
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """

        def prefix(a, b):
            ret = ''
            for i, j in zip(a, b):
                if i != j:
                    break
                ret += i
            return ret

        ans = ''
        for i in range(len(strs)):
            if i == 0:
                ans = strs[i]
            else:
                ans = prefix(ans, strs[i])
        return ans

15.三数之和

给定一个包含n个整数的数组nums[n]，判断nums中是否存在三个元素a,b,c使得a+b+c=0？找出所有满足条件且不重复的三元组。

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        ans = set()
        for i, a in enumerate(nums):
            if i and nums[i] == nums[i-1]:
                continue
            L = i+1
            R = len(nums)-1
            while L < R:
                t = a + nums[L] + nums[R]
                if t < 0:
                    L += 1
                elif t > 0:
                    R -= 1
                else:
                    ans.add((a, nums[L], nums[R]))
                    L += 1
                    R -= 1
        return list(ans)

16.最接近的三数之和

给定一个包括n个整数的数组nums和一个目标值target，找出nums中的三个整数，使得它们的和与target最接近，返回这三个数的和。

class Solution:
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        ans = sum(nums[:3])
        dif = abs(target - ans)
        for i, a in enumerate(nums):
            if i and nums[i-1] == a:
                continue
            L = i+1
            R = len(nums)-1
            while L < R:
                t = a + nums[L] + nums[R]
                if abs(t-target) < dif:
                    dif = abs(t-target)
                    ans = t
                if t < target:
                    L += 1
                elif t > target:
                    R -= 1
                else:
                    break
        return ans

17.电话号码的字母组合

在手机上数字2-9的键对应着字母a-z，给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        ans = ['']
        a = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
        for d in digits:
            ans = [j+i for j in ans for i in a[int(d)]]
        return ans

18.四数之和

给定一个包含n个整数的数组nums和一个目标值target，判断nums中是否存在四个元素a,b,c,d使得a+b+c+d=target，找出所有满足条件且不重复的四元组。

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        ans = set()
        for a, A in enumerate(nums):
            if a and nums[a-1] == A:
                continue
            for b in range(a+1, len(nums)):
                B = nums[b]
                if b-1 > a and nums[b-1] == B:
                    continue
                L = b+1
                R = len(nums)-1
                while L < R:
                    t = A+B+nums[L]+nums[R]
                    if t < target:
                        L += 1
                    elif t > target:
                        R -= 1
                    else:
                        ans.add((A,B,nums[L],nums[R]))
                        L += 1
                        R -= 1
        return list(ans)

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

给定一个链表，删除倒数第n个节点，并返回链表的头结点，给定的n保证有效。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        a, b, c = None, head, head
        for i in range(n):
            c = c.next
        while c:
            a, b, c = b, b.next, c.next
        if a:
            a.next = b.next
            return head
        return b.next

20.有效的括号

给定一个只包含大中小括号的字符串，判断字符串是否有效。注意空字符串有效。

class Solution:
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        a = []
        tag = {')':'(', ']':'[', '}':'{'}
        for i in s:
            if i in '([{':
                a.append(i)
            else:
                if a and a[-1] == tag[i]:
                    a.pop()
                else:
                    return False
        return len(a) == 0