媒体网站开发,访问wap网站,大连企业网站建设,wordpress前端后端CONTENTS LeetCode 11. 盛最多水的容器#xff08;中等#xff09;LeetCode 12. 整数转罗马数字#xff08;中等#xff09;LeetCode 13. 罗马数字转整数#xff08;简单#xff09; LeetCode 11. 盛最多水的容器#xff08;中等#xff09;
【题目描述】
给定一个长… CONTENTS LeetCode 11. 盛最多水的容器中等LeetCode 12. 整数转罗马数字中等LeetCode 13. 罗马数字转整数简单 LeetCode 11. 盛最多水的容器中等
【题目描述】
给定一个长度为 n 的整数数组 height。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。 找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明你不能倾斜容器。
【示例1】 输入[1,8,6,2,5,4,8,3,7]
输出49
解释图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下容器能够容纳水表示为蓝色部分的最大值为 49。【示例2】
输入height [1,1]
输出1【提示】 n h e i g h t . l e n g t h n height.length nheight.length 2 ≤ n ≤ 1 0 5 2\le n\le 10^5 2≤n≤105 0 ≤ h e i g h t [ i ] ≤ 1 0 4 0\le height[i]\le 10^4 0≤height[i]≤104
【分析】 很巧妙的一道贪心思维题我们先在最左边和最右边设置两个指针每次将指针指向的数较小的那个指针往中间靠拢一格且每次都维护一遍最大值即可。因为当一个指针往中间移动时矩形的宽度缩小了想要面积变大那肯定需要指针指向的数值即矩形高度变大而矩形的高度的瓶颈在于较短的那一条边因此移动较小的指针。 【代码】
class Solution {
public:int maxArea(vectorint height) {int res 0;for (int l 0, r height.size() - 1; l r; ){res max(res, (r - l) * min(height[l], height[r]));if (height[l] height[r]) l;else r--;}return res;}
};LeetCode 12. 整数转罗马数字中等
【题目描述】
罗马数字包含以下七种字符IVXLCD 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如罗马数字 2 写做 II即为两个并列的 1。12 写做 XII即为 X II。27 写做 XXVII即为 XX V II。
通常情况下罗马数字中小的数字在大的数字的右边。但也存在特例例如 4 不写做 IIII而是 IV。数字 1 在数字 5 的左边所表示的数等于大数 5 减小数 1 得到的数值 4。同样地数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况
I 可以放在 V5和 X10的左边来表示 4 和 9。X 可以放在 L50和 C100的左边来表示 40 和 90。C 可以放在 D500和 M1000的左边来表示 400 和 900。
给你一个整数将其转为罗马数字。
【示例1】
输入: num 3
输出: III【示例2】
输入: num 58
输出: LVIII
解释: L 50, V 5, III 3.【示例3】
输入: num 1994
输出: MCMXCIV
解释: M 1000, CM 900, XC 90, IV 4.【提示】 1 ≤ n u m ≤ 3999 1\le num\le 3999 1≤num≤3999
【分析】 我们先打个表找规律把几个特殊的数字打表记下来然后从高到低枚举以 2964 为例先循环判断是否大于1000若满足则减去1000并在答案中添加 M整个模拟流程如下
2964
1964 M
964 MM
64 MMCM
14 MMCML
4 MMCMLX
0 MMCMLXIV【Python代码】
class Solution:def intToRoman(self, num: int) - str:dic collections.OrderedDict(M1000, CM900, D500, CD400, C100, XC90,L50, XL40, X10, IX9, V5, IV4, I1)res for k, v in dic.items():while num v:res k; num - vreturn resLeetCode 13. 罗马数字转整数简单
【题目描述】
罗马数字包含以下七种字符IVXLCD 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000例如罗马数字 2 写做 II即为两个并列的 1。12 写做 XII即为 X II。27 写做 XXVII即为 XX V II。
通常情况下罗马数字中小的数字在大的数字的右边。但也存在特例例如 4 不写做 IIII而是 IV。数字 1 在数字 5 的左边所表示的数等于大数 5 减小数 1 得到的数值 4。同样地数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况
I 可以放在 V5和 X10的左边来表示 4 和 9。X 可以放在 L50和 C100的左边来表示 40 和 90。C 可以放在 D500和 M1000的左边来表示 400 和 900。
给定一个罗马数字将其转换成整数。
【示例1】
输入: s III
输出: 3【示例2】
输入: s LVIII
输出: 58
解释: L 50, V 5, III 3.【示例3】
输入: s MCMXCIV
输出: 1994
解释: M 1000, CM 900, XC 90, IV 4.【提示】 1 ≤ s . l e n g t h ≤ 15 1\le s.length\le 15 1≤s.length≤15 s 仅含字符 (I, V, X, L, C, D, M) 题目数据保证 s 是一个有效的罗马数字且表示整数在范围 [1, 3999] 内 题目所给测试用例皆符合罗马数字书写规则不会出现跨位等情况 IL 和 IM 这样的例子并不符合题目要求49 应该写作 XLIX999 应该写作 CMXCIX
【分析】 和上一题相似先对罗马数字进行观察发现除了4、40、400和9、90、900以外的其他罗马数字直接将每个字母转换成对应的整数相加即可。上面提到的这6个罗马数字他们的前一位数字比后一位数字更小对其进行特判即可。 【Python代码】
class Solution:def romanToInt(self, s: str) - int:dic dict(M1000, D500, C100, L50, X10, V5, I1)res 0for i in range(len(s)):if i 1 len(s) and dic[s[i]] dic[s[i 1]]:res - dic[s[i]]else:res dic[s[i]]return res
