LeetCode 第11题~第13题
LeetCode 第11题-盛最多水的容器
题目描述：
给定一个长度为n的整数数组height。有n条垂线，第i条线的两个端点是（i,0）和（i,height[i]）。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳更多的水。返回容器可以储存的最大水量，不可以倾斜容器。
难度：中等
题目链接：11. 盛最多水的容器 - 力扣（LeetCode）
示例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==height.length
- 2<=n<=10^5
- 0<=height[i]<=10^4
##双指针
##面积等于长度（两条线段的间距）乘以高度（两条线段中的短边）
##area=min(height[left],height[right])*(right-left)
##初始化left=0，right=n-1
public class Solution{
public int MaxArea(int[] height)
{
int maxArea=0,left=0,right=height.Length-1,maxHeight=0;
while(left<right)
{
//如果有一条线段小于当前最大线段长，则直接跳过
if(height[left]<=maxHeight) left++;
if(height[right]<=maxHeight) right++;
//计算当前面积
int width = right-left,high=Math.min(height[left],height[right]),area=width*high;
maxArea=Math.Max(maxArea,area);
maxHight = Math.Max(maxHeight,high);
//移动较短的垂线指针
if(height[left]<height[right]) left++;
else right++;
}
return maxArea;
}
}LeetCode 第12题-整数转罗马数字
题目描述：
罗马数字是通过添加从最高到最低的小数位值的转换而形成的，将小数位值转换为罗马数字有以下规则：
- 如果该值不是以4或9开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
- 如果该值以4或9开头，使用减法形式，表示从以下符号中减去一个符号，例如4是5（Ⅴ）减1（Ⅰ）：Ⅳ，9是10（Ⅹ）减1（Ⅰ）：Ⅸ。仅使用以下减法形式：4 (
IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。- 只要10的次方（I，X，C，M）最多可以连续附加三次以代表10的倍数。你不能附加5（Ⅴ），50（L）或500（D）。如果需要将符号附加4次，请使用减法形式。
给定一个整数，将其转换为罗马数字。
示例1：
输入：num = 3749 输出："MMMDCCXLIX" 解释： 3000 = MMM (1000 + 1000 + 1000) 700 = DCC (500 + 100 + 100) 40 = XL (50 - 10) 9 = IX (10 - 1)示例2：
输入：num = 58 输出："LVIII" 解释： 50 = L 8 = VIII示例3:
输入：num = 1994 输出："MCMXCIV" 解释： 1000 = M 900 = CM 90 = XC 4 = IV提示：1<=num<=3999
解题思路
方法一：贪心算法
使用贪心的思路，每次尽可能使用最大的符号。
public class Solution{ private static readonly(int value,string symbol)[] ValueSymbols={ (1000,"M"),(900,"CM"),(500,"D"),(400,"CD"),(100,"C"),(90,"XC"),(50,"L"),(40,"XL"),(10,"X"),(9,"IX"),(5,"V"),(4,"IV"),(1,"I") }; public string IntToRoman(int num){ StringBuilder result = new StringBuilder(); foreach(var (value,symbol) in ValueSymbols) { while(num>=value) result.Append(symbol),num=num-value; } return result.ToString(); } }方法二：硬编码数位
针对每个数位（个位、十位、百位、千位）分别处理。
public class Solution{ private static readonly string[] Thousands={"","M","MM","MMMM"}; private static readonly string[] Hundreds = {"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"}; private static readonly string[] Tens = {"","X","XX","XXX","XL","L","LX","LXX","LXXXX","XC"}; private static readonly string[] Ones = {"","I","II","III","IV","V","VI","VII","VIII","IX"}; public string IntToRoman(int num) { StringBuilder result = new StringBuilder(); result.Append(Thousands[num/1000]); result.Append(Hundreds[(num%1000)/100]); result.Append(Tens[(num%100)/10]); result.Append(Ones[num%10]); } return result.ToString(); }
LeetCode 第13题-罗马数字转整数
题目描述：
罗马数字和整数的转换如第12题所示，通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如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：
输入: s = "III" 输出: 3示例2：
输入: s = "IV" 输出: 4示例3：
输入: s = "IX" 输出: 9示例4:
输入: s = "IX" 输出: 9示例5：
输入: s = "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4提示：
- 1<=s.length<=15
- s仅包含字符（‘I’,'V','X','L','C','D','M'）
- 题目数据保证s是一个有效的罗马数字，且表示整数在范围[1,3999]内
- 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况
#从左到右扫描
public class Solution
{
private Dictionary<char,int> symbolValues = new Dictionary<char,int>
{
{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}
};
public int RomanToInt(string s)
{
int result = 0,n=s.Length;
for(int i=0;i<n;i++)
{
int value = symbolValues[s[i]];
//如果不是最后一个字符且当前值小于下一个值
if(i<n-1 && value<symbolValues[s[i+1]]) result = result - value;
else result = result+value;
}
return result;
}
}