LeetCode日常打卡11~15

11. 盛最多水的容器

分析：比较简单的一道题，面积问题，宽高都很容易理解。暴力法会超时。使用双指针即可。

扩展思考，这道题感觉没什么好挖掘的。变化顶多是坐标尺变换一下。判断时注意一下就好。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        #双指针
        max_area = left = 0
        right = len(height) - 1
        while left < right:
            max_area = max(max_area,(right - left)*min(height[left],height[right]))
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return max_area

12. 整数转罗马数字

分析：实现不难。不过，看到优秀解答。忍不住拷贝下来。发散思路真的很重要。

参考luohaha

方法1：第一种方法，依次取出个十百千位，然后转为字符串

class Solution:
    def intToRoman(self, num: int) -> str:
        from collections import deque

        roman = {1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X', 40: 'XL', 50: 'L', 90: 'XC',
                 100: 'C', 400: 'CD', 500: 'D', 900: 'CM', 1000: 'M'}
        q = deque()

        i = 0
        while num:
            num, digit = divmod(num, 10)
            times = pow(10, i)
            digit *= times
            i += 1
            if digit in roman:
                q.appendleft(roman[digit])
            elif digit >= 5 * times:
                q.appendleft(roman[times] * ((digit - 5 * times) // times))
                q.appendleft(roman[5 * times])
            else:
                q.appendleft(roman[times] * (digit // times))

        return ''.join(q)

第二种方法，题目范围位1-3999，用字典保存个十百千位上可能出现的所有罗马数字，依次取出千百个十位，在字典中找到数字对应的罗马数字即可

class Solution:
    def intToRoman(self, num: int) -> str:
        roman = [
            ['', "M", "MM", "MMM"],
            ['', "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],
            ['', "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],
            ['', "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],
        ]
        num_l = [1000, 100, 10, 1]
        roman_num = ''

        for k, v in enumerate(num_l):
            roman_num += roman[k][num//v]
            num %= v
        return roman_num

第三种解法，将数字依次递减，直到减为0，将减去的数字替换为罗马数字即可

class Solution:
    def intToRoman(self, num: int) -> str:
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        reps = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        roman_num = ''

        for i in range(13):
            while num >= values[i]:
                num -= values[i]
                roman_num += reps[i]
        return roman_num

13. 罗马数字转整数

分析：相比上一道题差不多。巧妙一处在于如何处理，满减情况。

class Solution:
    def romanToInt(self, s: str) -> int:
        dic = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
        last = 0
        now = 0
        result = 0
        for i in s:
            now = dic[i]
            if now > last and last != 0:
                result = (result - last)+(now-last)
            else:
                result += now
                last = now
        return result

14. 最长公共前缀

分析：本以为只是一道简单的题，发掘出不错方法。学到了。

方法一：利用python的max()和min()，在Python里字符串是可以比较的，按照ascII值排，举例abb， aba，abac，最大为abb，最小为aba。所以只需要比较最大最小的公共前缀就是整个数组的公共前缀。

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        s1 = min(strs)
        s2 = max(strs)
        for i,x in enumerate(s1):
            if x != s2[i]:
                return s2[:i]
        return s1

2、利用python的zip函数，把str看成list然后把输入看成二维数组，左对齐纵向压缩，然后把每项利用集合去重，之后遍历list中找到元素长度大于1之前的就是公共前缀

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ""
        ss = list(map(set, zip(*strs)))
        res = ""
        for i, x in enumerate(ss):
            x = list(x)
            if len(x) > 1:
                break
            res = res + x[0]
        return res

15. 三数之和

分析：先排序，建立列表。建立三数之和，然后判断。注意如果相等，需要往中间逼近。逼近同时注意去掉数字相同情况，减少运算复杂度。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res =[]
        i = 0
        for i in range(len(nums)):
            if i == 0 or nums[i]>nums[i-1]:
                l = i+1
                r = len(nums)-1
                while l < r:
                    s = nums[i] + nums[l] +nums[r]
                    if s ==0:
                        res.append([nums[i],nums[l],nums[r]])
                        l +=1
                        r -=1
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                        while r > l and nums[r] == nums[r+1]:
                            r -= 1
                    elif s>0:
                        r -=1
                    else :
                        l +=1
        return res