LeetCode DAY 7 (11-12)

我果然还是一条懒狗，拖更了两天，今天补上。

11. 盛最多水的容器（中等）

题目描述

给定n个非负整数a1，a2，…，an，每个数代表坐标中的一个点(i, ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i, ai)和(i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且n的值至少为2。

图中垂直线代表输入数组[1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。

示例：

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

代码

解法1：暴力穷举法

本懒狗第一个想到的办法就是写两个for循环穷举所有情况…

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        maxarea = 0
        for i in range(0, len(height)-1):
            for j in range(i+1, len(height)):
                area = (j-i)*min(height[i], height[j])
                if maxarea < area:
                    maxarea = area
        return maxarea

解法2：（双指针法）利用题意中的特点

我们知道，盛水的多少取决于容器最短的那根木板，还有两块木板之间的距离。
我们将初始位置放在列表的开始和末尾，为了增大两块木板之间的面积，我们不得不将较短的木板向内侧移动以寻求更长的木板，这样虽然会导致木板之间的距离变短，但还是有可能找到比初始位置面积要大的情况存在。

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right = 0, len(height)-1
        # 记录面积
        maxarea = 0
        while left < right:
        	# 两块木板之间的距离
            b = right - left
            if height[left] < height[right]:
                h = height[left]
                left += 1
            else:
                h = height[right]
                right -= 1
            area = b*h
            if maxarea < area:
                maxarea = area
        return maxarea

12. 整数转罗马数字（中等）

题目描述

罗马数字包含以下七种字符： I， V， X， L，C，D和M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如，罗马数字2写做II，即为两个并列的I。12写做XII，即为X+II。27写做XXVII,即为XX+V+II。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如4不写做IIII，而是IV。数字1在数字5的左边，所表示的数等于大数5减小数1得到的数值4 。同样地，数字9表示为IX。这个特殊的规则只适用于以下六种情况：

• I可以放在V(5)和X(10)的左边，来表示4和9。
• X可以放在L(50)和C(100)的左边，来表示40和90。 
• C可以放在D(500)和M(1000)的左边，来表示400和900。

给定一个整数，将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例1:

输入: 3
输出: "III"

示例2:

输入: 4
输出: "IV"

示例3:

输入: 9
输出: "IX"

示例4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

代码

解法1：分情况讨论

这是我最开始的想法：既然这道题有这么多种情况，那我就直接分情况讨论吧。
总共大致分成了三种情况，一种是题目中给出的，也就是单个字符的数值，和特例（数字小的数字在大的数字的左边的情况）；第二种是数字大于5(50,500等)的，最后一种当然就是数字小于5(50,500等)的。将属于第一种情况的键值对写入字典中。

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        dict_str = {1:'I', 5:'V', 10:'X', 50:'L', 100:'C', 500:'D', 1000:'M', 4: 'IV', 9:'IX', 40:'XL', 90:'XC', 400:'CD', 900:'CM'}
        # 用来存储转换成的罗马数字符号的列表，是倒着存储的，因此最后需要重排序
        ans_list = []
        # 用来存储数字位的倍数
        count = 1
        while num != 0:
            a = num % 10
            num_str = a * count
            # 在字典中，取出value即是该位的罗马数字值
            if num_str in dict_str:
                ans_list.append(dict_str[num_str])
            # 大于5，需要变成'5的倍数的罗马值'+'某个1倍数的罗马值'*b
            elif a>5:
                b = a-5
                ans_list.append(dict_str[5*count]+dict_str[count]*b)
            # 小于5，即 '某个1倍数的罗马值'*a
            elif a<5:
                ans_list.append(dict_str[count]*a)
            count *= 10
            num //= 10
        return ''.join(ans_list[::-1])

解法2：贪心算法

我们每次用最大面值的来替换，可以保证用的罗马字符最少且最终的组合唯一。
其实我们仔细看这些面值，除了特殊的4,9,40,90之类的数，其余都是要么小于5，然后就是几个I连在一起，要么就是大与5，在几个I的左边再加上5(50,500等)对应的罗马数字。
只要除去特例，我们每次判断，取面值最大的，然后把该符号加在后面即可，对于特例，直接在字典或列表中加入即可。

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        ans = ''
        for index in range(0,13):
            while num >= nums[index]:
                ans += romans[index]
                num -= nums[index]
        return ans